Functional Programming and Intelligent Algorithms

# Exercises

## Week 14: The travelling salesperson problem (TSP)

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

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