Em Andamento

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 [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

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

Habilidades: Programação C, Programação C#, Engenharia, MySQL, PHP, Arquitetura de software, Teste de Software

Ver mais: what is a programming algorithm, what is algorithm in programming, what is a algorithm in programming, unix systems programming, unit test order, unit test generator, time in ga, the assignment problem, test code generator, systems programming, std find algorithm, std algorithm, solve the assignment problem, solve assignment problem, rand c programming, programming question in c, programming guide, problem assignment, practical programming in c, practical programming, practical php programming, practical c programming, php programming problem set, optimal assignment, o 1 algorithm

Acerca do Empregador:
( 6 comentários ) United Kingdom

ID do Projeto: #3013322

Premiar a:

kartanvw

See private message.

$17 USD em 11 dias
(5 Avaliações)
1.8

7 freelancers estão ofertando em média $101 para este trabalho

lmxvw

See private message.

$51 USD in 11 dias
(126 Comentários)
4.7
lalesculiviu

See private message.

$170 USD in 11 dias
(18 Comentários)
4.2
homeworktutor

See private message.

$170 USD in 11 dias
(12 Comentários)
2.4
eyenetsolut

See private message.

$127.5 USD in 11 dias
(14 Comentários)
2.5
thanasisk

See private message.

$110.5 USD in 11 dias
(5 Comentários)
0.9
sandelvw

See private message.

$63.75 USD in 11 dias
(0 Comentários)
0.0