Too strong fitness selection bias can lead to sub-optimal solution
Too little fitness bias selection results in unfocused and meandering search
Parent selection
Chance to be selected as parent proportional to fitness
Roulette wheel
To avoid problems with fitness function
Tournament
Not a very important parameter
Uniform randomly selection
Probability selection : proportional to their fitness
Tournament selection (Multiple Objectives)
Build a small comparison set Randomly select a pair with the higher rank one beats the lower one Non-dominated one beat the dominated one Niche count: the number of points in the population within certain distance, higher the niche count, lower the rank.
Etc.
Others
Global Optimal
Parameter Tuning
Parallelism
Random number generators
7. Example Of Coding For TSP:
Binary
Cities are binary coded; chromosome is string of bits
Most chromosomes code for illegal tour
Several chromosomes code for the same tour
Path
Cities are numbered; chromosome is string of integers
Most chromosomes code for illegal tour
Several chromosomes code for the same tour
Ordinal
Cities are numbered, but code is complex
All possible chromosomes are legal and only one chromosome for each tour
Several others
8. Roulette wheel:
Sum the fitness of all chromosomes, call it T
Generate a random number N between 1 and T
Return chromosome whose fitness added to the running total is equal to or larger than N
Chance to be selected is exactly proportional to fitness
Chromosome :1 2 3 4 5 6
Fitness : 8 2 17 7 4 11
Running total :8 10 27 3438 49
N (1 £ N £ 49): 23
Selected :3
9. Tournament:
Binary tournament
Two individuals are randomly chosen; the fitter of the two is selected as a parent
Probabilistic binary tournament
Two individuals are randomly chosen; with a chance p, 0.5<p<1, the fitter of the two is selected as a parent
Larger tournaments
n individuals are randomly chosen; the fittest one is selected as a parent
By changing n and/or p, the GA can be adjusted dynamically
10. Problems With Fitness Range:
Premature Convergence
DFitness too large
Relatively superfit individuals dominate population
Population converges to a local maximum
Too much exploitation; too few exploration
Slow Finishing
DFitness too small
No selection pressure
After many generations, average fitness has converged, but no global maximum is found; not sufficient difference between best and average fitness
Too few exploitation; too much exploration
11. Solutions For These Problems:
Use tournament selection
Implicit fitness remapping
Adjust fitness function for roulette wheel
Explicit fitness remapping
Fitness scaling
Fitness windowing
Fitness ranking
12. Fitness Function:
Purpose
Parent selection
Measure for convergence
For Steady state: Selection of individuals to die
Should reflect the value of the chromosome in some "real” way
Next to coding the most critical part of a GA
Fitness scaling
Fitness values are scaled by subtraction and division so that worst value is close to 0 and the best value is close to a certain value, typically 2
Chance for the most fit individual is 2 times the average
Chance for the least fit individual is close to 0
Problems when the original maximum is very extreme (super-fit) or when the original minimum is very extreme (super-unfit)
Can be solved by defining a minimum and/or a maximum value for the fitness
Example of Fitness Scaling
Fitness windowing
Same as window scaling, except the amount subtracted is the minimum observed in the n previous generations, with n e.g. 10
Same problems as with scaling
Fitness Ranking
Individuals are numbered in order of increasing fitness
The rank in this order is the adjusted fitness
Starting number and increment can be chosen in several ways and influence the results
No problems with super-fit or super-unfit
Often superior to scaling and windowing
Fitness Evaluation
A key component in GA
Time/quality trade off
Multi-criterion fitness
Multi-Criterion Fitness
Dominance and Indifference
For an optimization problem with more than one objective function (fi, i=1,2,…n)
given any two solution X1and X2, then
X1dominates X2( X1X2), if
fi(X1) >= fi(X2), for all i = 1,…,n
X1is indifferent with X2( X1~X2), if X1does not dominate X2, and X2does not dominate X1
Pareto Optimal Set
If there exists no solution in the search space which dominates any member in the set P, then the solutions belonging the the set P constitute a global Pareto-optimal set.
Pareto optimal front
Dominance Check
Weighted sum
F(x) = w1f1(x1) + w2f2(x2) +…+wnfn(xn)
Problems?
Convex and convex Pareto optimal frontSensitive to the shape of the Pareto-optimal front
Selection of weights?
Need some pre-knowledge
Not reliable for problem involving uncertainties
Optimizing single objective
Maximize: fk(X) Subject to: fj(X) <= Ki ,i <> k , X in F where F is the solution space.
Preference based weighted sum
(ISMAUT Imprecisely Specific Multiple Attribute Utility Theory)
F(x) = w1f1(x1) + w2f2(x2) +…+wnfn(xn)
Preference
Given two know individuals X and Y, if we prefer X than Y, then F(X) > F(Y), that is w1(f1(x1)-f1(y1)) +…+wn(fn(xn)-fn(yn)) > 0
All the preferences constitute a linear space Wn={w1,w2,…,wn}
w1(f1(x1)-f1(y1)) +…+wn(fn(xn)-fn(yn)) > 0
w1(f1(z1)-f1(p1)) +…+wn(fn(zn)-fn(pn)) > 0, etc
For any two new individuals Y’ and Y’’, how to determine which one is more preferable?
Construct the dominant relationship among some indifferent ones according to the preferences.
