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()
    c,d = singleCross(a,b)          // singleCross returns two children
    nextcandidate[i] = c
    nextcandidate[i+1] = d
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
//we use "accumulative sum of fitness" to determine which individual is being picked
// another name is "roulette wheel" selection

x = random 0..sum of all fitness
sum = 0
for i = 1 to population size
    sum += fit[i]
    if x > sum return i

singleCross(a,b) // single point crossover
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.

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 13 Jan 2026