Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Jul 30th, 2012  |  syntax: D  |  size: 2.78 KB  |  views: 22  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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.        
  101.         //we need to start from home and return to home
  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. }