Functional Programming and Intelligent Algorithms

# Exercises

## 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

• population size (number of chromosomes)
• maximum number of iterations
• selection rate
• mutation rate

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

• ability to find the correct target string
• cost of the GA-generated string (zero for finding the correct string)
• number of iterations needed
• total runtime

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

• abc123.,;
• descartes: cogito ergo sum
• 2+2 is: 4, 2*2 is: 4; why is _/not/_ 2.2*2.2 equal to 4.4?!

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 / robin.t.bye@ntnu.no