Functional Programming and Intelligent Algorithms

Description of a basic GA

Week 12: The binary GA

1 Description of a basic GA

1.1 Introduction

A chromosome c is an encoded candidate solution to the optimisation problem of optimising f(c). The design parameters that we want to optimise must be translated (encoded) from their original domain to a format suitable for the GA, usually arrays of bits or real-valued numbers, often normalised to the interval [0, 1]. The bits or numbers are usually called genes. A chromosome is a list of genes, whilst a population is a list of chromosomes.

The objective function quantifies that quality of candidate solutions, that is, how well they fulfill the desired design criteria. The selection criterion determines how many chromosomes in a population survives from one iteration to the next. For examle, using the roulette wheel method, the cost (fitness) associated with each chromosome is evaluated and the chromosomes are given a weighted selection probability according to their cost, where a smaller cost (greater fitness) results in a greater probability.

A pre-determined fraction, of chromosomes (typically half the population) is then randomly picked, with low cost (high fitness) chromosomes having a greater chance of being picked and kept for survival and reproduction.

For mating, several crossover methods exists, where genes from two parent chromosomes are combined into one or several offspring, which are then put back into the population, replacing those chromosomes that were not selected for mating.

After mating, a fraction of the chromosomes will have one or several of their genes mutated. This means flipping (inverting) bits for binary chromosomes, or changing the values of these genes to random numbers within some allowable range.

Next, each of the chromosomes in the updated population is evaluated by the objective function and the population is sorted in descending order of performance (ability to minimise cost or maximise fitness).

The process repeats until the maximum number of iterations has been reached, or the solution (the best chromosome) has reached a satisfactory performance. Then the algorithm ends and returns the best chromosome, which is decoded back to its original domain.

1.2 Iterative (imperative) pseudocode for a GA

The basic steps that almost any GA consists of are outlined in high-level pseudocode in the pseudocode below, where we adopt a cost function as our objective function (loosely adapted from ?, and other sources). Note that the pseudocode given is imperative and procedural, whereas you need to reformulate it to being functional and declarative in Haskell (see the next section).

INITIALISATION 
    define encoding scheme for chromosomes $ c $; 
    define objective function $ f(c) $; 
    set criteria for selection, crossover, mutation, elitism; 
    generate initial $ population $ of chromosomes; 
    sort $ population $ in increasing order of cost; 
    $ bestChrom \leftarrow population[0] $; 
    set $ minCost,\ maxIterations $; 
    $ i \leftarrow 1 $; 
LOOP 
    While{i < maxIterations OR bestCost > minCost}{ 
        evaluate cost for each chromosome; 
        select chromosomes for mating; 
        perform mating, crossover, mutation, elitism; 
        update $ population $; 
        sort $ population $ in increasing order of cost; 
        $ bestChrom \leftarrow population[0] $; 
        $ bestCost \leftarrow f(bestChrom)$; 
        $ i \leftarrow i+1 $; 
    } 
    return $ i, bestChrom, bestCost $; 
    decode $ bestChrom $ to original domain;

1.3 Functional Haskell code outline for the binary GA

The following Haskell code outlines how you should be able to run your binary GA from a test module:

1module TestBinaryGA where 
2 
3import BinaryGA 
4import System.Random (newStdGen) 
5 
6main :: IO () 
7main = do 
8        g <- newStdGen 
9        let (initPop, g’) = randPop g 
10        putStr ~Initial population decoded to strings:\n~ 
11        print $ decodePopulation initPop 
12        let newPopEvolved = fst $ evolvePop g itMax initPop 
13        putStr ~Final population decoded to strings:\n~ 
14        print $ decodePopulation newPopEvolved 
15        putStr ~Target:\n~ 
16        print target 
17        putStr ~Best solution:\n~ 
18        print $ (decodePopulation newPopEvolved) !! 0 
19        putStr ~Cost of solution:\n~ 
20        print $ chromCost (encodeString target) (newPopEvolved !! 0)
You may choose to implement the evolutionary function evolvePop as follows 1-- Evolve the population n times 
2evolvePop :: StdGen -> Int -> Population -> (Population, StdGen) 
3evolvePop g 0 pop = (newpop, g) 
4    where newpop = toPopulation $ sortPop $ evalPop (encodeString target) pop 
5evolvePop g n pop = evolvePop g (n-1) newPop 
6    where (newPop, g’) = evolvePopOnce g pop
where 1-- Single evolution of the population 
2evolvePopOnce :: StdGen -> Population -> (Population, StdGen) 
3evolvePopOnce g pop = (newPopMutated, g4) 
4    where (g’, g’’) = split g 
5          targetC = encodeString target 
6          parents = toPopulation $ getParents $ sortPop $ evalPop targetC pop 
7          (offspring, g3) = matePairwise g parents 
8          newPop = parents ++ offspring 
9          mutIdx = mutIndices newPop g3 
10          (newPopMutated, g4) = mutatePop g’’ mutIdx newPop
If you do so, obviously you need to implement the other functions that evolvePop and evolvePopOnce rely on.

The tutorial in Section 2 walks you through the development of a complete working binary GA.


Last updated: 7th April 2017
Robin T. Bye / robin.t.bye@ntnu.no