完了

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

スキル: C プログラミング, C#プログラミング, エンジニアリング, MySQL, PHP, ソフトウェアアーキテクチャ, ソフトウェアテスト

さらに表示: 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

採用者について:
( 6件のレビュー ) United Kingdom

プロジェクトID: #3013322

アワード:

kartanvw

See private message.

$17 USD 11日以内
(5レビュー)
1.8

7人のフリーランサーが、このジョブに平均$101で入札しています

lmxvw

See private message.

$51 USD 11日以内
(126件のレビュー)
4.7
lalesculiviu

See private message.

$170 USD 11日以内
(18件のレビュー)
4.2
homeworktutor

See private message.

$170 USD 11日以内
(12件のレビュー)
2.4
eyenetsolut

See private message.

$127.5 USD 11日以内
(14件のレビュー)
2.5
thanasisk

See private message.

$110.5 USD 11日以内
(5件のレビュー)
0.9
sandelvw

See private message.

$63.75 USD 11日以内
(0件のレビュー)
0.0