## Description

## Using a genetic algorithm to

approximate a solution to the traveling salesman problem

## Introduction

Assignment 2 is ready at last! For this take-home coding project, you will produce an object oriented

implementation of the traveling salesman problem using a genetic algorithm. Fun for all shall be had!

We will examine the traveling salesman problem. Suppose we have an unordered container of cities to

visit. We want to sort and visit the cities in a sequence that minimizes the distance traveled. With a

small number of cities this is trivial, but with a large number of cities this can take a very, very long

time (what is the big O of this type of problem)? A genetic algorithm is one approach that makes this

easier.

A genetic algorithm is an algorithm that draws inspiration from theories of natural selection. That is,

we start with a ‘population’ of sample candidates, evaluate their fitness, perform some sort of

cross-over and mutation, and continue until we have a solution that most closely meets our needs or

meets our termination criteria.

1 Setup

Please complete the following:

1. No late submissions will be accepted for any reason.

2. Clone your repo using github classroom: https://classroom.github.com/a/g5mY2R0T

3. Fill out your name and student number at the top of main.cpp

4. Ensure you commit and push your work frequently. You will not earn full marks if you don’t

5. Include a plaintext readme file which must include your full name on the first line and your student number on the second

line. Leave line three blank.

6. On line four of your readme.txt file, write either “100% complete” or describe any outstanding issues.

7. Your program must execute when pressing the play button in CLion. Any tweaks the markers must make to run your code

will result in lost marks.

8. You may work in pairs and submit your work together

2 Requirements

Your second take-home programming assignment is about the Traveling Salesman problem. Given a

list of cities and their coordinates, what is the shortest possible route that visits each city and returns to

the original city

The Traveling Salesman Problem is one of the most intensely studied problems in the field of

optimization. While there are exact algorithms for finding the shortest route (including brute-force

search, of course), calculating the solution can take years! We will explore a heuristic that finds a good

solution, possibly a very good solution, in a reasonable amount of time: a genetic algorithm.

A genetic algorithm is an algorithm that draws inspiration from theories of natural selection. That is,

we start with a ‘population’ of sample candidates, evaluate their fitness, perform some sort of

crossover and mutation, and continue until we have a solution that most closely meets our needs or

meets our termination criteria.

Start by reading the accompanying paper entitled Genetic Algorithms, A Survey. It’s not a heavy

read, and it’s very interesting.

Your program must implement an object oriented solution to the following scenario:

1. A city has a name and a set of coordinates which we will call x and y because x and y are easier

to type than longitude and latitude.

2. We will limit coordinates for this simulation to the range [0, 1000]. That is, x and y for all cities

will be between 0 and 1000 inclusive.

3. A tour is what we will call a list of cities. A tour contains a list of all the cities in the simulation

and a fitness rating. The fitness rating evaluates the distance the traveling salesman would need

to travel to visit the cities in the order they appear in the tour.

4. The program will start by creating a group of cities. Ensure each city is assigned a unique name

or sequence number and a random set of coordinates.

5. Create a population of tours. Each tour must contain the entire list of cities sorted randomly.

That is, we will have a data structure that manages a collection of tours, and each tour will

manage a sequence of the cities on the map that begins in a randomly shuffled state.

6. Determine and record the fitness of each tour. The fitness must be a double that represents the

quality of the tour. Shorter tours are better quality, and will have better fitness. A good idea is to

use the inverse of the total distance traveled, possibly multiplied by some scalar.

7. Make a note of the shortest, i.e., fittest, tour. This is our starting distance or base_distance. This is

where our genetic algorithm starts.

8. Implement the genetic algorithm iteratively until we observe a predetermined improvement, i.e.,

until we see that base_distance / best_distance > IMPROVEMENT_FACTOR:

(a) Selection: keep the best tour by moving the fittest to the front of the population. We won’t

change it in this iteration, and we will call it an ’elite’ individual

(b) Crossover: mix the rest of the routes and create new routes. Replace every other tour in the

population with a new tour generated by crossing some parents. Choose each parents by selecting a subset of tours from the population to represent potential parents, and selecting

the fittest from the subset. That is, Each parent is the fittest of a subset of size

PARENT_POOL_SIZE of the population, randomly selected. We cross the

NUMBER_OF_PARENTS parents to create a child tour, and keep doing this to replace all of

the non-elite tours in the population.

To cross two parents, select a random index and use the cities from one parent to populate

the mixed tour up to and including that index, and then the cities from the second parent to

top up the tour, making sure we don’t add cities that are already in the mixed tour.

If a city in a following parent has already been added to the tour, simply move to the next

city in the tour.

(c) Mutation: Randomly select 20 to 30 percent of your tours to mutate (excluding the elite

tour!). Feel free to change the number of tours to mutate. Calculate a random mutation

value for each city in a specified specified tour. If this value < MUTATION_RATE, then the

city is swapped with the adjacent city from the same tour.

(d) Evaluation: assign each new tour a fitness level.

(e) Report: provide the user with information about the algorithm’s progress.

9. Implement the Singleton and Facade design patterns by creating a SingletonFacade class to hide the

complexity of running the genetic algorithm above. The main function in main.cpp should get an

instance of the singleton and call a run() function to start the steps listed above.

10.Some constants and behaviors you may wish to consider include (but are not limited to):

(a) CITIES_IN_TOUR the number of cities we are using in each simulation, start with 32 but it

would be nice if the user can choose

(b) POPULATION_SIZE the number of candidate tours in our population maybe 32 but it

would be nice if the user can choose

(c) SHUFFLES the number of times a swap must be effected for a shuffle to finish if writing your own

custom swap function. Maybe 64 is a good number. If using the standard library shuffle function,

then 1 shuffle per tour is fine.

(d) ITERATIONS the maximum number of times the algorithm should iterate maybe 1000

(e) MAP_BOUNDARY the largest legal coordinate should be 1000

(f) PARENT_POOL_SIZE the number of members randomly selected from the population

when choosing a parent, from which the fittest is made a ’parent’ maybe 5 is a good number

(g) MUTATION_RATE is probably low like 15 percent but it would be nice if the user can choose

(h) NUMBER_OF_PARENTS the actual number of ’parent’ tours crossed to generate each

’offspring’ tour

(i) NUMBER_OF_ELITES should start at 1, but I am curious how changing this would modify

the algorithm’s effectiveness

(j) IMPROVEMENT_FACTOR is a percentage that indicates what percent the new elite fitness

needs to improve over the base distance before exiting the algorithm loop

(k) shuffle_cities to shuffle the cities in a tour

(l) get_distance_between_cities to calculate the distance between two cities

(m) get_tour_distance reports the distance between the cities as they are listed in a tour

(n) determine_fitness determines the fitness of a tour

(o) select_parents will select the parents for a new tour from a population

(p) crossover creates a new tour from a given set of parent tours

(q) mutate may mutate a tour

(r) contains_city checks if a tour contains a specific city.

3 Expected Output

Your output should clearly indicate how the algorithm is improving every iteration. This includes but isn’t

limited to:

1. Iteration number

2. If new elite found

– Display “NEW ELITE FOUND: ” and only the Elite’s distance

If no new Elite found

– Display the Elite’s distance

– Display the Best Non Elite distance

3. Improvement over base so far

At the end, there should be a final report of the results that include:

1. Number of iterations

2. Report of the base and best distance

3. Whether your improvement factor was achieved

4. Output of the base route.

5. Output of the route taken to achieve the best distance.

4 Grading

This assignment will be marked out of 20. For full marks, you must:

1. (2 points) Commit and push to GitHub after each non-trivial change to your code

2. (8 points) Successfully write and test a program that implements the requirements using an

object oriented solution

3. (6 points) Clear output indicating how the algorithms is improving as well as a final report of the

results

4. (4 points) Write code that is commented and formatted correctly using good variable names,

efficient design choices, atomic functions, thorough tests

You may work in pairs and submit your work together. Good luck, and have fun.

Sample output:

Original elite: Distance: 9017.88

(sausu->tsuyani->nawohu->hireyo->okin->sasona->kanre->wonose->eyuko->mukiwo->kot

suyu->mauhe->ikisa->muhaa->noyuko->ronori->tauri->erayu->shimeki->kowoki->sausu)

— STARTING ALGORITHM —

Iteration: 0

NEW ELITE FOUND:

Distance: 8598.85

Improvement over base: 1.04873

Iteration: 1

NEW ELITE FOUND:

Distance: 8323.25

Improvement over base: 1.08346

Iteration: 2

NEW ELITE FOUND:

Distance: 7372.14

Improvement over base: 1.22324

Iteration: 3

Elite distance: 7372.14

Best non-elite distance: 9088.85

Improvement over base: 1.22324

Iteration: 4

Elite distance: 7372.14

Best non-elite distance: 8406.17

Improvement over base: 1.22324

Iteration: 5

NEW ELITE FOUND:

Distance: 7029.23

Improvement over base: 1.28291

Iteration: 6

NEW ELITE FOUND:

Distance: 6512.82

Improvement over base: 1.38463

Iteration: 7

NEW ELITE FOUND:

Distance: 5815.84

Improvement over base: 1.55057

Iteration: 8

Elite distance: 5815.84

Best non-elite distance: 6864.05

Improvement over base: 1.55057

Iteration: 9

Elite distance: 5815.84

Best non-elite distance: 6436.06

Improvement over base: 1.55057

Iteration: 10

NEW ELITE FOUND:

Distance: 5815.07

Improvement over base: 1.55078

…

Iteration: 320

Elite distance: 4190.01

Best non-elite distance: 6150.27

Improvement over base: 2.15223

Iteration: 321

Elite distance: 4190.01

Best non-elite distance: 5772.07

Improvement over base: 2.15223

Iteration: 322

Elite distance: 4190.01

Best non-elite distance: 5339.8

Improvement over base: 2.15223

Iteration: 323

Elite distance: 4190.01

Best non-elite distance: 4772.55

Improvement over base: 2.15223

Iteration: 324

Elite distance: 4190.01

Best non-elite distance: 4524.76

Improvement over base: 2.15223

Iteration: 325

Elite distance: 4190.01

Best non-elite distance: 7039.32

Improvement over base: 2.15223

Iteration: 326

Elite distance: 4190.01

Best non-elite distance: 6084.58

Improvement over base: 2.15223

Iteration: 327

Elite distance: 4190.01

Best non-elite distance: 4999.41

Improvement over base: 2.15223

Iteration: 328

Elite distance: 4190.01

Best non-elite distance: 6839.36

Improvement over base: 2.15223

Iteration: 329

NEW ELITE FOUND:

Distance: 4118.16

Improvement over base: 2.18978

Iteration: 330

NEW ELITE FOUND:

Distance: 3743.19

Improvement over base: 2.40914

— FINISHED ALGORITHM —

Total iterations: 331

Original elite:

Distance: 9017.88

(sausu->tsuyani->nawohu->hireyo->okin->sasona->kanre->wonose->eyuko->mukiwo->kotsuyu->mauhe->iki

sa->muhaa->noyuko->ronori->tauri->erayu->shimeki->kowoki->sausu)

Best elite:

Distance: 3743.19

(ikisa->erayu->shimeki->noyuko->sausu->kotsuyu->ronori->hireyo->mauhe->okin->nawohu->eyuko->wono

se->mukiwo->muhaa->sasona->kanre->kowoki->tauri->tsuyani->ikisa)

Improvement factor reached!

Improvement factor: 2.40914