• API
• FAQ
• Tools
• Trends
• Archive
SHARE
TWEET

# Untitled

a guest Jul 30th, 2012 25 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import std.stdio;
2. import std.algorithm;
3. import std.random;
4. import std.array;
5. import std.math;
6.
7. struct city{
8.         int x;
9.         int y;
10. }
11.
12. struct chromosome{
13.         city[] dna;
14. }
15.
16. chromosome[2] crossOver(chromosome mother, chromosome father){
17.         assert(mother.dna.length==father.dna.length);
18.
19.         foreach(a;mother.dna)
20.                 assert(mother.dna.count(a)==father.dna.count(a));
21.
22.         //we map 1 dna unit from the mother to a corresponding unit of the father (and vice versa)
23.         // 4 1 2 3 5
24.         // 5 3 1 2 4
25.         //
26.         // if we map 1 => 3
27.         // 4 3 2 1 5
28.         // 5 1 3 2 4
29.
30.         int mapIndex=uniform(0,mother.dna.length);
31.
32.         auto point1=mother.dna.dup[mapIndex];
33.         auto point2=father.dna.dup[mapIndex];
34.
35.         //we're mapping point1 to point1
36.         swap(mother.dna[mother.dna.countUntil(point1)],mother.dna[mother.dna.countUntil(point2)]);
37.         swap(father.dna[father.dna.countUntil(point1)],father.dna[father.dna.countUntil(point2)]);
38.
39.         return [mother,father];
40. }
41.
42. chromosome mutate(chromosome victim){
43.         int from=uniform(0,victim.dna.length);
44.         int to=uniform(0,victim.dna.length);
45.         swap(victim.dna[from],victim.dna[to]);
46.         return victim;
47. }
48.
49. chromosome[] reproduce(chromosome mother,chromosome father){
50.         //we reproduce
51.         //mother's and father's dna are preserved because they contain a good solution
52.         //we also add a mutation of mother/father
53.         //a crossing over of mother/father
54.         //and a crossing over + mutation
55.         chromosome[] returnvalue;
56.         returnvalue~=mother;
57.         returnvalue~=father;
58.
59.         returnvalue~=mutate(mother);
60.         returnvalue~=mutate(father);
61.
62.         chromosome[] crossedOver=crossOver(mother,father);
63.         chromosome[] crossedOverAndMutated=array(map!(x => mutate(x))(crossedOver));
64.
65.         returnvalue~=crossedOver;
66.         returnvalue~=crossedOverAndMutated;
67.
68.         return returnvalue;
69. }
70. void main(){
71.         city[] cities=[city(20,0),city(50,50),city(75,30),city(0,10),city(25,25),city(10,65)];
72.         chromosome[] workers;
73.         while(workers.length<60){
74.                 randomShuffle(cities);
75.                 if(!canFind(workers,chromosome(cities)))
76.                         workers~=chromosome(cities.dup);
77.         }
78.
79.         bool fitnessCompare(chromosome first,chromosome second){
80.                 return fitness(first)>fitness(second);
81.         }
82.
83.         while(true){
84.                 workers=array(sort!(fitnessCompare)(workers));
85.
86.                 writeln(workers[0]);
87.                 stdout.flush();
88.
89.                 chromosome[] newWorkers;
90.                 for(int x=0;x<10;x+=2)
91.                         newWorkers~=reproduce(workers[x],workers[x+1]);
92.
93.                 workers=newWorkers;
94.         }
95.
96. }
97.
98. float fitness(chromosome victim){
99.         city[] cities=victim.dna;
100.
102.         cities=city(0,0) ~ cities;
103.         cities~=city(0,0);
104.
105.         float travelled=0f;
106.         for(int x=0;x<cities.length-1;x++)
107.                 travelled+=distance(cities[x],cities[x+1]);
108.         writeln(100/travelled);
109.         return 100/travelled;
110. }
111.
112. float distance(city from,city to){
113.         return sqrt(cast(float)(pow(to.x-from.x,2) + pow(to.y-from.y,2)));
114. }
RAW Paste Data
Top