Inhaltsverzeichnis |
Übungen
Springerproblem
Überprüfen Sie die Aussage, dass für 1 < n < 5 keine Springertour existiert, durch Probieren.
Lokale Suche
Schauen Sie sich noch mal das Hill Climbing, Threshold Accepting, simulated annealing, Tabu-Suche und den Sintflut-Algorithmus an.
Evolutionäre Algorithmen
Erzeugen Sie aus einer Startpopulation mit A=(1, 2, 3, 4, 5), B=(2, 4, 3, 1, 5), C=( 1, 3, 5, 2, 4)und D=(4, 2, 5, 3, 1) 4 weitere Lösungskandidaten durch Evolution. Führen Sie dazu für die ersten beiden Individuen jeweils eine Rekombination von A,B und C,D durch und wählen Sie für die beiden verbleibenden einfach A und C. Mutieren Sie anschließend alle neuen Individuen durch invertierende Mutation. Bewerten Sie alle 8 Individuen nach Gesamtweg mit der Entfernungsmatrix und wählen Sie die 4 besten aus.
Entfernungsmatrix:
Hinweis: benutzen Sie zur Bestimmung der Mutationsbereiche diesen Zufallszahlengenerator (bei 2 gleichen Werten ist die Mutation neutral):
Lösungsvorschlag:
Details
Rekombination von A,B
1. Adjazenzinformationen vereinigen und für jeden Knoten aufschreiben:
Adj(1)={2,5} \cup {3,5}={2,3,5}
Adj(2)={1,3} \cup {4,5}={1,3,4,5}
Adj(3)={2,4} \cup {1,4}={1,2,4}
Adj(4)={3,5} \cup {2,3}={2,3,5}
Adj(5)={1,4} \cup {1,2}={1,2,4}
2. Einen Startknoten aus denen der "Eltern" wählen.
Hier wird S = 2 gewählt.
3. Den gerade verwendeten Knoten aus den Adjazenzmengen entfernen.
Neue Adjazenzmengen:
Adj(1)={3,5}
Adj(2)={1,3,4,5}
Adj(3)={1,4}
Adj(4)={3,5}
Adj(2)={1,4}
4. Aus der Menge an möglichen Nachfolgeknoten den bzw einen mit der niedrigsten Anzahl Nachfolgemöglichkeiten auswählen:
Alle kommen mit nun noch 2 möglichen Folgeknoten infrage. Hier wird Knoten 1 gewählt.
(Sollte kein Folgeknoten mehr zur Auswahl stehen, so muss ein zufälliger noch nicht verwendeter Knoten ausgewählt werden.)
5. Schritte 3 und 4 wiederholen, bis alle Knoten verwendet sind.
Endergebnis (Vorschlag): E=(2, 3, 1, 5, 4)
Mit der Rekombination von C,D kann analog verfahren werden. Ein mögliches Ergebnis lautet F=(3, 4, 5, 2, 1)
Mutation findet durch zufällige Auswahl von Start- und Endknoten eines Teilstückes und Inversion der Elementreihenfolge in diesem Teilstück statt.
z.B. für A mit Startknoten 1 und Endknoten 5 (Das Teilstück ist hier also gleich des gesamten Kandidaten): A'=(5, 4, 3, 2, 1)
oder für E mit Startknoten 3 und Endknoten 4: E'=(2, 4, 5, 1, 3)
Zur Bewertung einfach die Längen aus der Entfernungsmatrix addieren.
Länge(A)= 5 + 6 + 1 + 7 + 4 = 23
Aus den insgesamt 8 Lösungskandidaten die 4 optimalsten (geringster Weg) wählen.
Diese ausgewählten Kandidaten würden in einem Algorithmus erneut durch den Zylkus geschickt, sodass an die Optimallösung angenähert wird.