Prabhas Chongstitvatana
prabhas@chula.ac.th
Department of computer engineering
Chulalongkorn University
Intelligent Systems Laboratory
http://isl.cp.eng.chula.ac.th/
lecture to master students at the department of computer science, Rangsit university 18 August 2002
outline
3 sections of 45 min. each
- motivation, background theory of EA
- basics of EA, examples from Genetic Algorithms
- applications, mostly from my research
for hard problems: (usually means can be solved in exponential-time)
mostly they can not be solved exactly, so there are other techniques
to solve them
- approximate algorithm
- heuristics
- probabilistic
approximate algorithms give "known" (proven) bound relative to "best" answer.
heuristic codes "human intuition" into algorithms. It can be regarded as "problem solving as search".
probabilistic algorithms relies on randomization. The answer is not always correct but the bound on error probability is known.
randomization + problem solving as search = Evolutionary Algorithms
searching is done in space-state
the search process is based on backtracking, pruning such as branch
and bound algorithms
Most Artificial intelligence work can be summarised as emphasize on
knowledge
and search, A* search
local search
deterministic
- same input -- same output
- time bound is non-statistical
- exact answer
fitness landscape
population based
solution improvement
** not problem dependent, weak search
example: time tabling problems
Schema theorem
Schema with above average fitness grows exponentially.
implicit parallelism
explicit parallelism
another example: GA for data clustering
examples from my research
- robot programming
- evolvable hardware
- bin-packing
- computer graphics