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