2 Exercises
2.1 Testing
You should test that the TSP GA works properly on a set of TSP data such as wi29.txt and
dj38.txt. Create a test module called TestTSPGA.hs to hold your code:
1module TestTSPGA where
The module should import the TSPGA module:
1import TSPGA
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 -- read in TSP test data and obtain a list cities with positions
2 -- obtain a PRNG g
3 -- initialise a random population
4 -- print the decoded population (list of candidate tours)
5 -- evolve the population for itMax iterations
6 -- print the decoded evolved population (list of evolved tours)
7 -- print the decoded best chromosome found and its cost,
8 -- that is, the tour and its distance
9 -- compare the distance of the tour with the optimal distance
10 -- check that the solution is valid
To help you out, here is an example module implementing the steps listed above:
1main :: IO ()
2main = do
3 contents <- readFile ~wi29.txt~
4 let s = map words (lines contents)
5 let cities = map stringsToCity s
6 g <- newStdGen
7 let (initPop, g’) = randPop g
8 putStr ~Initial population decoded to cities:\n~
9 print $ decodePopulation initPop
10 let newPopEvolved = fst $ evolvePop g’ itMax cities initPop
11 putStr ~newPopEvolved:\n~
12 print newPopEvolved
13 putStr ~Valid tours using encoded chromosomes:\n~
14 print $ map validTour newPopEvolved
15 putStr ~Final population decoded to cities:\n~
16 print $ decodePopulation newPopEvolved
17 putStr ~Valid tours using decoded chromosomes:\n~
18 print $ map validTour (decodePopulation newPopEvolved)
19 let bestSolution = (decodePopulation newPopEvolved) !! 0
20 putStr ~Best solution:\n~
21 print bestSolution
22 putStr ~Cost of solution:\n~
23 print $ chromCost cities (newPopEvolved !! 0)
24 let bestTour = chromToTour cities (newPopEvolved !! 0)
25 putStr ~Best solution as a list of cities with positions:\n~
26 print bestTour
27 putStr ~Length of tour:\n~
28 print $ distanceTour bestTour
29 putStr ~Length of optimal tour: \n~
30 putStrLn ~27603 (wi29) and 6656 (dj38)~
31 putStrLn ~ Deviation from optimal:~
32 let deviation = ((distanceTour bestTour) - 27603) / 27603
33 print deviation -- for wi29
34 putStr ~Valid solution:\n~
35 print $ validTour’ bestSolution (length cities)
36
37stringsToCity :: [String] -> City
38stringsToCity [c, x, y] = (read c, (read x, read y))
39
40validTour :: [CityID] -> Bool
41validTour tour = [1..length tour] == sort tour
42
43validTour’ :: [CityID] -> Int -> Bool
44validTour’ tour n = [1..n] == sort tour
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 a optimal TSP tour
- cost (distance) of the GA-generated tour (deviation from optimal)
- number of iterations needed
- total runtime
for the two TSP problems wi29.txt and dj38.txt.