Functional Programming and Intelligent Algorithms


Week 12: The binary GA

3 Exercises

3.1 Testing

You should test that the binary GA for string learning works properly on a set of test strings. Create a test module called TestBinaryGA.hs to hold your code:

1module TestBinaryGA where The module should import the GA module: 1import BinaryGA You should then implement a main function with the necessary steps to verify proper functionality of the GA: 1main :: IO () 
2main = do
For example, you could do something like the following: 1        -- select a target string 
2        -- obtain a PRNG g 
3        -- initialise a random population 
4        -- print the decoded population (list of candidate strings) 
5        -- evolve the population for itMax iterations 
6        -- print the decoded evolved population (list of evolved strings) 
7        -- print the decoded best chromosome found and its cost

Example: To help you out, here is an example main function implementing the steps listed above:

1main :: IO () 
2main = do 
3        g <- newStdGen 
4        let (initPop, g’) = randPop g 
5        putStr ~Initial population decoded to strings:\n~ 
6        print $ decodePopulation initPop 
7        let newPopEvolved = fst $ evolvePop g itMax initPop 
8        putStr ~Final population decoded to strings:\n~ 
9        print $ decodePopulation newPopEvolved 
10        putStr ~Target:\n~ 
11        print target 
12        putStr ~Best solution:\n~ 
13        print $ (decodePopulation newPopEvolved) !! 0 
14        putStr ~Cost of solution:\n~ 
15        print $ chromCost (encodeString target) (newPopEvolved !! 0)

Experiment with algorithm settings such as

and discuss how your choice of GA settings affect the following:

for a number of different test strings, e.g.

If you modify your cost functions or implement other cost functions, examine the performance of the GA for each of these.

3.2 Solve your own problem

This exercise is about adapting the binary GA to some other problem. Find a problem that a binary GA can solve. A suitable problem can be a combinatorial problem, a sequencing problem, or something else where a binary encoding scheme could be useful. You will need to think about how to encode the chromosomes, e.g., the sequence of genes could correspond to a sequence with which a problem is solved. You must also define new cost functions to evaluate the chromosomes. Much of the existing code can be reused.

Last updated: 7th April 2017
Robin T. Bye /