文档介绍：ic Algorithms (GA)
A class of probabilistic search algorithms.
Inspired by natural ics and biological evolution.
Uses concept of “survival of fittest”.
GA originally developed by John Holland (1975)
GA –general concepts
Iterative procedure(iterative improvement)
Produces a series of “generations of populations” one per iteration
Each member of a population represents a feasible solution,called a chromosome.
bag
chromosomes
Combine and die(mating)
p1
1
2
3
K
m
evolution
Chromosome-a feasible solution
Selection crossover mutation
Pk
P3
The population during iteration of GA is denoted by the “bag”
Pi={X1i,X2i,……..,Xni}.
Xmi denotes the m th member of the population in i th iteration and n is the size of the population.
Pi;is a bag ,not a set,hence can contain repeated solutions, . all entries need not be unique.
Initial population P1,may be created randomly or by a deterministic (constructive) heuristic.
Cost(x) is the cost of solution function is user supplied.
Assume cost(x)>=0 V X.
Let fitness of (x) =1/1+cost(x), thus V x,
0<=fitness(x)<=1.
Average-fitness(Pi)=Σ fitness(xji)
Best-fitness(Pi) =max{fitness(xji)}
Going from P1 to P2 to P3…..
is called “evolution”.
Goal:ensure that it is highly likely that
average-fitness(Pi)>average-fitness(Pj) for i>j.
We go from Pi to Pi+1 via an evolution function that usually consists of ponents called operators.
Operators
Selection: select some members of current population to move to the next to select “highly fit “ solutions.
Use an (imaginary) roulette wheel technique.
Fitness of .37 => 37%
2
1
n
3
4
Area is
Proportional to fitness value
Example
Chromosome fitness
A .21
B .14
C .10
D .02
E .33
F .20
-----------
A
21%
D 2%
10%
F
20%
E
33%
B
14%
C
1) When wheel is turned and eventually stops,probability of stopping at A is 2) The function select-roulette(f) spins roulette wheel by a random degree(uniform between 0 and 2) and retu