Aufgabe 6.9 Lösung

[locutus]

Die Rekombination von p1 und p2 mittels Cycle-Crossover ergibt ...

ix 1 2 3 4 5 6 7 8 9
p1 7 6 9 8 5 2 1 4 3
p2 9 8 2 6 4 5 3 7 1
ch 7 8 9 6 5 2 3 4 1

Am Anfang wird 7 von p1 in ch übernommen. Dann kann 9 nicht mehr von p2 übernommen werden und muss somit ebenfalls von p1 übernommen werden. Das Gleiche gilt für die darauf folgenden Stellen und ergibt insgesamt den Zyklus (7,9,2,5,4). Um durch Rekombination eine neue Permutation zu erzeugen werden nun die verbleibenden Stellen in ch von p2 übernommen. Das ergibt dann die Zyklen (8,6) und (3,1).

[Sensei]

hab ich auch so... ziemlich fades bsp ;)

[wolti]

Ja. Ich habe auch dieses Ergebniss. Was mich allerdings ein bisschen wundert. Das ganze ist ja hier nur zur Rekombination von zwei Lösungen gedacht. -> Nicht ein sehr sinnvolles Beispiel oder ?

1) Ich starte mit 2 Anfangslösungen. Dann Selektiere ich mal aus meinen gegebenen Lösungen ein Paar raus nach irgendeinem Verfahren (Ich nehme k raus, und suche unter diesen k dann die zwei besten <-> Meiner Meinung nach die Tournament Selektion).
2) Dann kombiniere ich diese beiden Lösungen (Mit dem verwendeten Alg).
3) Dann mutiere ich diese Lösung noch ein bisschen und bewerte sie.
4) Ich schaue mir an wie gut die Lösungen sind, und ob eine so gut ist, dass ich bereit bin aufzuhören.

5) Bei Abbruchkriterium ?? Das ist etwas komisch. Denn das Optium zu ermitteln ist ja auch nicht ganz so einfach bei diesem Problem, denn dann hätte ich schon eine Lösung. Bzw. Wer sagt mir, bei diesem Quadratic Assignment Problem, was eine mögliche untere Schranke sein könnte. Denn wenn ich sie Rate kann es sein, daß ich sie nie erreiche.

Grüße,
Wolti

[Sensei]

das ganze is ja auh nur ein verbesserungsverfahren --> das optimum wird man nur selten erreichen
außerdem muss man das ja wenn dann über viele generationen machen.
aber ich stimme dir zu... irgendwie is es schon komisch.... aber ich denke wir betrachten nur einen kleinen teil vom prob.