Traveleling Salesman - Evolutionär

Das Traveling-Salesman Problem gilt als eines der schwierigsten Probleme der kombinatorischen Optimierung. Effiziente Lösungsverfahren sind für dieses Problem nicht bekannt. Wir stellen hier eine Heuristik aus dem Bereich der Evolutionären Algorithmen zur Lösung dieses Problems dar.
 Bitte schalten Sie Java ein, um eine Cinderella-Konstruktion zu sehen.

Bitte schalten Sie Java ein, um eine Cinderella-Konstruktion zu sehen. Knoten verschieben Bitte schalten Sie Java ein, um eine Cinderella-Konstruktion zu sehen. Knoten hinzufügen Bitte schalten Sie Java ein, um eine Cinderella-Konstruktion zu sehen. Knoten löschen

Bei einem Evolutionären Algorithmus hat man eine Population von Individuen, die sich über den Lauf mehrerer Generationen durch Selektion, Kreuzung (Cross-Over) und Mutation verändert. Dabei erhofft man sich, dass - entsprechend dem Darwinismus - sich besonders gute Eigenschaften durchsetzen.
Beim Beispiel des TSP sind die Individuen konkrete Touren durch die Städte, d.h. bestimmte Permutationen der Knoten. Eine Tour gilt dabei als besonders überlebensfähig, wenn die eine möglichst kurze Gesamtlänge besitzt. Die Population besteht also aus einer festen Zahl zunächst zufällig gewählter Permutationen. Ein Generationswechsel erfolgt in den drei Schritten Selektion - Cross-Over - Mutation.

initEvolution():={
   population=[];
   forall(1..readni(),
      population=append(population,randomPermutation(length(staedte)));
   );
   generation=0;
   population;
};
 
 
nextGeneration(population,staedte):={
     generation=generation+1;
 
     population=selektion(population,staedte,readsk());  
     population=crossover(population,staedte,readcw());
     population=mutation(population,readmw());
 
     population;
};

Selektion
Aus der vorhandenen Population werden Individuen ausgewählt, die überleben und sich vermehren. Andere Individuen sterben aus.
Zunächst wird das stärkste Individuum - also die kürzeste Tour - ausgewählt. Diese Tour überlebt auf alle Fälle.
Anschließend werden wiederholt zwei zufällige Individuen ausgewählt und in einen Zweikampf geschickt. Dabei wird ihre Länge verglichen und mit einer Wahrscheinlichkeit in Abhängigkeit des Verhältnisses der beiden Tourlängen überlebt die kürzere oder die längere Tour. Eine Kopie der siegreichen Tour wandert in die neue Population. So kann es vorkommen, dass ein Individuum mehrfach in einer Population vorhanden ist.
Die Wahrscheinlichkeit wird noch durch den Selektionskoeffizienten beeinflusst. Je größer der Selektionskoeffizient ist, umso größer ist die Wahrscheinlichkeit, dass die kürzere Tour gewählt wird. Bei einem Selektionskoeffizient von Null haben beide Touren die gleiche Wahrscheinlichkeit, bei einem Koeffizienten von 100 wird die kürzere Tour fast sicher genommen.

selektion(pop, staedte,sk):={
   neuePop=[besteLoesung(pop,staedte)];
   forall(1..(readni()-1),
      r1=randomint(length(pop))+1;
      r2=randomint(length(pop))+1;
      // Nimm Tour mit Wahrscheinlichkeit in Abhängigkeit des Quotienten der beiden Tourlängen
      neuePop = append(neuePop,
         if(random()<1-1/(1+(tourlaenge(pop_r2,staedte)/tourlaenge(pop_r1,staedte))^sk), pop_r1,pop_r2));
   );
   neuePop;
};

Cross-Over
Zwei benachbarte Individuen werden mit der Cross-Over-Wahrscheinlichkeit gekreuzt. Dazu wird eine Teilsequenz der Touren ausgewählt, die in beiden Touren ausgetauscht wird. Der Rest der Touren wird entsprechend angepasst.

crossover(pop,staedte,cw):={
   neuePop=[];
   j=1;
   while{j<length(pop),
      elt1=pop_j;
      elt2=pop_(j+1);
      if(random()<cw,
        schnitt=sort([randomint(length(elt1))+1,randomint(length(elt1))+1]);
        seg1=sublist(elt1,schnitt_1,schnitt_2);
        seg2=sublist(elt2,schnitt_1,schnitt_2);
        elt1=elt1--seg2;
        elt2=elt2--seg1;
        neuePop = neuePop
                  ++[
                     if(schnitt_1>1,sublist(elt1,1,schnitt_1-1),[])
                     ++seg2
                     ++if(schnitt_1<=length(elt1),sublist(elt1,schnitt_1,length(elt1)),[]),
                     if(schnitt_1>1,sublist(elt2,1,schnitt_1-1),[])
                     ++seg1
                     ++if(schnitt_1<=length(elt2),sublist(elt2,schnitt_1,length(elt2)),[]);
                  ];
 
      //else
      ,
         //Eltern unverändert übernehmen
         neuePop = neuePop++[elt1,elt2];
      );
      j=j+2;
   };
   neuePop;
};

Mutation
Jede Tour wird mit der Mutationswahrscheinlichkeit mutiert. Dazu werden zwei beliebig gewählte Knoten der Tour mit einander vertauscht.

mutation(pop,mw):={
  neuePop=[];
  forall(pop,
    if(random()<mw,
      r1=randomint(length(#))+1;
      r2=randomint(length(#))+1;
      help=#_r1;
      #_r1=#_r2;
      #_r2=help;
    );
    neuePop=neuePop++[#];
  );
  
  neuePop;  
};


Das Applet zeigt in jeder Generation das beste Individuum an. Darüber hinaus wird die beste Tour angezeigt, die im Laufe der Evolution gefunden wurde sowie die bisher beste gefundene Lösung über alle Evolutionen (seit dem Start des Applets). Durch Klicken auf den roten, blauen oder grünen Punkt kann die Anzeige dieser Touren jeweils unterdrückt werden. Die Zahl in den Klammern hinter der Länge der besten Tour der aktuellen Generation zeigt an, wie oft das beste Individuum in der aktuellen Population enthalten ist.

< zurück | weiter >