# Travelling Salesman Problem

Genetic algorithm for The Travelling Salesman problem

Guide:

A. In this exercise you will write a Steady-State GA (see lecture 4) to solve

the "Travelling Salesman problem" for a specific set of towns: Find a short

round-trip route that passes through the 30 towns at these coordinates:

1:82, 7 ; 2:91,38 ; 3:62,32 ; 4:71,44 ; 5:83,69 ; 6:68,58

7:54,67 ; 8:87,76 ; 9:13,40 ; 10:71,71 ; 11:44,35 ; 12:18,54

13:64,60 ; 14:37,84 ; 15:41,94 ; 16: 2,99 ; 17: 7,64 ; 18:22,60

19:25,62 ; 20:54,62 ; 21: 4,50 ; 22:74,78 ; 23:18,40 ; 24:24,42

25:25,38 ; 26:41,26 ; 27:45,21 ; 28:58,69 ; 29:58,35 ; 30:83,46

Use a population size of 1000 and a run length of 1 million reproductions.

B. Read through the code in this question and make sure you understand what

each part should do

C. Fill in the CCCC to complete the code that calculates the genotype fitnesses

D. Fill in the DDDDs to complete the code that selects parents for reproduction

E. Fill in the EEEEs to produce the child genotype using mutation and crossover

Your mutation function should swap two towns around in a route.

Your crossover function should copy the towns before a cut point from

parent 1 and take the remaining towns in the order they appear in parent 2.

F. Test that your program compiles and runs

To compile: g++ -O3 -o EvSysEx3 [url removed, login to view]

Then to run: ./EvSysEx3

G. The optimal route has length 423.741. It is quite possible to evolve this.

At worst you should be able to find routes of length < 500.

Test that your program produces the correct output

H. Submit your source code using the submit command (details on the course web page).

#include <cstdlib>

#include <ctime>

#include <iostream>

#include <cmath>

using namespace std;

## Deliverables

const int numTowns = 30;

const int numGenotypes = 1000;

const int genotypeLength = numTowns;

const int numReproductions = 1000000;

const int numMutationsPerReproduction = 1;

const int towns[numTowns][2]=

{ {82, 7} , {91,38} , {62,32} , {71,44} , {83,69} , {68,58} ,

{54,67} , {87,76} , {13,40} , {71,71} , {44,35} , {18,54} ,

{64,60} , {37,84} , {41,94} , { 2,99} , { 7,64} , {22,60} ,

{25,62} , {54,62} , { 4,50} , {74,78} , {18,40} , {24,42} ,

{25,38} , {41,26} , {45,21} , {58,69} , {58,35} , {83,46} };

double distances[numTowns][numTowns];

int genotypes[numGenotypes][genotypeLength];

double fitness[numGenotypes]; // fitness = -1 * route length

int fittestIndividual = 0;

void randomise() // seed the random number generator from the system clock

{

srand(time(0));

}

int random(int n) // return a random integer between 0 and n-1

{

return (int) (((double) n)*rand()/(RAND_MAX+1.0));

}

void calculateFitness(int individual) // fitness = -1 * route length

{

CCCC

}

void initialise()

{

randomise();

/* calculate distances between towns */

for (int i=0;i<numTowns;i++) for (int j=0;j<=i;j++)

{ int dx=towns[j][0]-towns[i][0], dy=towns[j][1]-towns[i][1];

distances[i][j] = distances[j][i] = sqrt((double)(dx*dx+dy*dy));

}

/* generate initial (random) population */

for (int individual=0;individual<numGenotypes;individual++)

{ int remainingTowns[numTowns];

for (int i=0;i<numTowns;i++) remainingTowns[i] = i;

for (int g=0;g<genotypeLength;g++)

{

int index = random(numTowns-g);

genotypes[individual][g] = remainingTowns[index];

remainingTowns[index] = remainingTowns[numTowns-g-1];

}

}

/* calculate fitness array for initial population */

for (int individual=0;individual<numGenotypes;individual++)

calculateFitness(individual);

}

void mutate(int individual) // swap two towns in individual's route

{

EEEE

}

void crossover(int parentA, int parentB, int child)

{

EEEE

}

{

/* pick three individuals a,b,c at random */

DDDD

/* reorder such that c is the least fit */

DDDD

/* but don't loose fittestIndividual */

if (c==fittestIndividual) {int temp=b;b=c;c=temp;}

/* crossover a,b (in random order) to create child that replaces c */

if (random(2)) {int temp=a;a=b;b=temp;}

crossover(a,b,c);

/* mutate child */

for (int m=0;m<numMutationsPerReproduction;m++) mutate(c);

/* calculate fitness of child */

calculateFitness(c);

}

## Platform

void outputStatistics(int numRreproductionsSoFar)

{

if (!numRreproductionsSoFar) cout << "#repros\tbest\t: route" << endl;

cout << numRreproductionsSoFar << "\t" << -fitness[fittestIndividual] << "\t:";

for (int g=0;g<genotypeLength;g++)

cout << " " << genotypes[fittestIndividual][g]+1;

cout << endl;

}

int main()

{

initialise();

outputStatistics(0);

for (int reproduction=1;reproduction<=numReproductions;reproduction++)

{

if (reproduction%20000==0) outputStatistics(reproduction);

}

return 0;

}

Windows XP , Unix