Evolutionary systems c++ assignment

/* Evolutionary Systems Assignment 1 (30% of unit) (Guided Practical Exercise 3) 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 [login to view URL] 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 ## Deliverables */ #include <cstdlib> #include <ctime> #include <iostream> #include <cmath> using namespace std; 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 } void steadyStateGaMainStep() { /* 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); } 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++) { steadyStateGaMainStep(); if (reproduction%20000==0) outputStatistics(reproduction); } return 0; } ## Platform Unix or Linux on a Gnu shell