Implement simple GA
This lecture discusses how to implement a simple Genetic
Algorithm. The "program" will be written in a pseudo code.
First, we define population of candidates. A candidate is
represented by a fix length binary string.
char
idv[100]; // individual candidate
idv = "001010101011010"
Then, the population is an array of individuals
candidate[i]
to simplify notation, we use the second dimension to get each binary
digit.
candidate[i][d]
simple GA is
1 generate random string to be first generation population
2 evaluate each candidate
3 select good parents
4 generate next generation population
use single point crossover
5 repeat step 2 to 4 until satisfy
generate random pop
for i = 1 to population
size
candidate[i] =
generate random string {0,1}
evaluate candidates, the objective function is defined by the problem
fitness is kept in fit[.]
correspond to candidate[.]
for i =1 to population size
apply
objective function to candidate[i] -> fit[i]
generate next generation
// this is a second population, used to hold the next generation
nextcandidate[ population
size
]
for i = 1 to population
size, step 2
a =
pickparent()
b =
pickparent()
nextcandidate[i] = singleCross1(a,b)
//
assume singleCross1 returns one of the child
nextcandidate[i+1] = singleCross2(a,b)
//
and singleCross2 returns another child
for i = 1 to population
size
candidate[i] =
nextcandidate[i]
// copy
the next generation back to the old population
pickparent by fitness proportional selection
the probability of an individual being picked is proportioned to its
fitness
assume fit[.] 0...1 then sum of all fitness is 0..n
we use "accumulative sum of fitness" to determine which individual is
being picked
// another name is "roulette wheel" selection
assume fit[i] 0..1
x = random 0..population
size
sum = 0
for i = 1 to population
size
sum += fit[i]
if x >
sum return i
singleCross(a,b)
x = random 1 to (length of
candidate - 1)
firstchild = copy
candidate[a] 1..x concat to
copy
candidate[b] x+1..end
secondchild = copy
candidate[b] 1..x concat to
copy
candidate[a] x+1..end
An individual is encoded into a binary string. The encoding
method affects all genetic operations.
lecture 16 Nov 2010
encoding of individual
This is problem dependent. The easiest way is to use
{0,1}* binary
string. However other coding can be used, such as Grey
code. Integer encoding is a more useful representation. For
example, a
Traveling Saleman Problem (TSP) can represent a tour of n cities by a
string of number 0..n of length n. The solution can be found by
permuting all possibilities of this string and check for the minimum
cost tour.
last update 26 Nov 2010