Implement simple GA

lecture 16 Nov 2010

use galib247
genetic operators
application of GA

population of candidates
candidate is represented by a fix length binary string

char idv[100]; // individual candidate
idv = "001010101011010"

population is array of individual

candidate[i]

to get each binary digit assume we use two-d index
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
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
nextcandidate[ population size ]
for i = 1 to population size, step 2
    a = pickparent()
    b = pickparent()
    nextcandidate[i] = singleCross1(a,b)
    nextcandidate[i+1] = singleCross2(a,b)
for i = 1 to population size
    candidate[i] = nextcandidate[i]

pickparent
fitness proportional 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

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 25 Nov 2010