CS4601: Introduction to Intelligent Computing
Genetic Algorithms (GAs)
Motivation behind Genetic Algorithms (GAs):
- Look at what evolution brings us?
-
Vision
- Hearing
- Smelling
- Taste
- Touch
- Learning and reasoning
- Can we emulate the evolutionary process with today's
fast computers?
Basic Terms of GAs:
GA Flowchart:
- Step 1:
- Initialize a population with randomly generated
individuals and evaluate the fitness value of each
individual.
- Step 2:
-
- (a)
Select two members from the population with
probabilities proportional to their fitness values.
- (b)
Apply crossover with a probability equal
to the crossover rate.
- (c)
Apply mutation with a probability equal
to the mutation rate.
- (d)
Repeat (a) to (d) until enough members
are generated to form the next generation.
- Step 3:
- Repeat steps 2 and 3 until a stopping criterion is met.
|
Producing the next generation in GAs.
|
GA for Continuous Optimization: An Example:
Find the max. of the peaks function:
z = peaks(x, y)
= 3*(1-x)^2*exp(-(x^2) - (y+1)^2)
- 10*(x/5 - x^3 - y^5)*exp(-x^2-y^2) - 1/3*exp(-(x+1)^2 - y^2).
|
|
Surface plot of z = peaks(x, y)
|
Contour plot of z = peaks(x, y)
|
GA process:
(You can watch the animation of GA optimization process for the "peaks"
function by executing the MATLAB file
go_ga.m located at
ftp://ftp.cs.nthu.edu.tw/pub/CS/papers/jang/book/soft. Other
auxiliary files are:
evalpopu.m,
evaleach.m,
nextpopu.m,
bit2num.m,
peaksfcn.m, and
wavefcn.m.)
|
|
|
Initial Population
|
Population after the 5th generation
|
Population after the 10th generation
|
Performance across generations:
Advantages of GAs:
- Derivative freeness
(derivatives of the peaks function).
- Parallel algorithms in nature; potential massive speedup on
parallel-processing machine
- For both continuous and discrete (combinatorial) optimization
- stochastic and less likely to get trapped in local minima
- Flexibility
Weakness of GAs:
- Slowness
- Good encoding schemes (together with crossover and mutation
operators) are somewhat non-intuitive for a given task
- Resolution requirement
- Overhead of encoding and decoding
Reported GA Applications:
- Neural networks modeling
- Fuzzy modeling
- Chemical process: PH control
- Helicopter control
- Combinatorial problems
- And many, many others
Reference:
Neuro-Fuzzy and Soft Computing
This page is maintained by
Jyh-Shing Roger Jang.
Comments and suggestions are welcome:
jang@cs.nthu.edu.tw.