1 Description of a basic GA
1.1 Introduction
A chromosome is an encoded candidate solution to the optimisation problem of optimising . 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 . 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.