Ich habe versucht, viele Treffer zu erzielen, indem ich mit "Circular Salesman Problem Genetic Algorithm" gegoogelt habe.
Das ** Patrol Salesman Problem ** ist das Problem, den kürzesten Weg zurück zum ursprünglichen Punkt zu finden und alle $ N $ Punkte einmal zu durchlaufen. Die Gesamtzahl der Routen, die alle $ N $ -Punkte durchlaufen und zurückkehren, beträgt $ (N-1)! / 2 $. Wenn es 3 Punkte gibt, gibt es einen Weg. Wenn es 4 Punkte gibt, gibt es 3 Möglichkeiten. Wenn es 5 Punkte gibt, gibt es 12 Möglichkeiten. Mit zunehmender Anzahl von Punkten steigt die Gesamtzahl der Routen explosionsartig an. Es dauert enorm lange, den kürzesten Weg zwischen ihnen zu finden.
Wenn dies jedoch bedingt ist, können Sie die Route in praktischer Zeit finden.
Wenn Sie beispielsweise wissen, dass sich ein Punkt an der Spitze eines konvexen Polygons befindet, ist der kürzeste Pfad dieses konvexe Polygon. Darüber hinaus gibt es verschiedene Suchmethoden wie genetische Algorithmen, Annealing-Methoden und selbstorganisierende Karten, sofern diese ** fast ** kürzer sind.
** Genetischer Algorithmus ** ist einer der Suchalgorithmen für Kombinationsoptimierungsprobleme und basiert auf der Evolution lebender Organismen. Da das Problem des Handlungsreisenden auch eines der kombinierten Optimierungsprobleme ist, kann ein genetischer Algorithmus verwendet werden. Das Verfahren zum Suchen nach einem genetischen Algorithmus ist wie folgt.
Der genetische Algorithmus wird mit einem Organismus verglichen und mit den folgenden Worten erklärt.
Kommentar des Suganuma-Labors der Shizuoka-Universität für Wissenschaft und Technologie Beginnen Sie mit dem genetischen Algorithmus! --SlideShare
Ordnen Sie den genetischen Algorithmus für das Problem des Handlungsreisenden an.
Sei $ p_0, p_1, \ dots, p_N $ die $ N + 1 $ Punkte, die der Verkäufer durchläuft. Die Route, die von $ p_0 $ ausgeht, alle Punkte in numerischer Reihenfolge der Punkte durchläuft und zu $ p_0 $ zurückkehrt, kann als $ p_0, p_1, \ dots, p_N, p_0 $ ausgedrückt werden. $ p_1, p_2, \ dots, p_N, p_0, p_1 $ sind Routen, die denselben Kreis von $ p_1 $ aus beginnen. Die Länge des Schleifenpfads ist gleich, unabhängig davon, welchen Punkt Sie als Startpunkt auswählen. Legen Sie den Startpunkt also auf $ p_0 $ fest und stellen Sie die Route als $ p_ {i_1}, \ dots, p_ {i_N} $ dar. Da die Pfadlänge auch dann gleich ist, wenn das Ganze parallel verschoben wird, setzen Sie $ p_0 = O $ und verschieben Sie die anderen Punkte parallel. Der auf diese Weise geschaffene Weg ist ein Individuum.
Verwenden Sie zur Anpassung die Länge des von der Person dargestellten Pfades.
Wenn der Abstand zwischen zwei Punkten $ p, p '$ $ d (p, p') $ ist, beträgt die Länge der Route $ p_ {i_1}, \ dots p_ {i_N} $ $ d (p_0, p_ {i_1}) + d (p_0, p_ {i_N} + \ sum_ {k = 1} ^ {N-1} d (p_ {i_k}, p_ {i_ {k + 1}}) $. Je kleiner die Länge, desto besser die Route. Je höher die Zahl, desto besser die Anpassungsfähigkeit. Verwenden Sie daher die Umkehrung der Länge oder die Vorzeichenumkehrung. Diesmal habe ich die Code-Inversion verwendet.
Wenn der Wert umso kleiner ist, je besser die Anpassungsfähigkeit ist, verwenden Sie die Länge so wie sie ist.
Zum Zeitpunkt der Kreuzung wird anstelle der Erzeugung von Kindergenerationen aus allen Individuen der Elterngeneration ** eine Auswahl ** getroffen, so dass es umso einfacher ist, Nachkommen zu hinterlassen, je anpassungsfähiger die Individuen sind.
Außerdem ist es bei der Auswahl von Individuen umso einfacher, bei den Nachkommen zu bleiben, je höher die Anpassungsfähigkeit ist.
Es gibt drei Hauptoptionen. Alle haben Vor- und Nachteile, verwenden Sie sie also in Kombination.
Wählen Sie in absteigender Reihenfolge der Anpassungsfähigkeit. Da ausgezeichnete Individuen bleiben, konvergiert es schnell. Andererseits ist der Einfluss exzellenter Individuen in den frühen Stadien stark, und wenn die Generationen zunehmen, kann die Vielfalt abnehmen und in eine Sackgasse (= lokale Lösung) der Evolution geraten.
Wählen Sie basierend auf der aus der Anpassungsfähigkeit berechneten Wahrscheinlichkeit. Gene mit geringer Anpassungsfähigkeit bleiben erhalten (obwohl weniger wahrscheinlich), sodass die Diversität nicht abnimmt. Andererseits können Gene mit hoher Anpassungsfähigkeit verworfen werden und es kann keine Lösung erreicht werden.
Es gibt verschiedene Möglichkeiten, die Wahrscheinlichkeit zu berechnen.
--Roulette-Wahrscheinlichkeit ... $ (individuelle Anpassungsfähigkeit) \ div (Summe der Anpassungsfähigkeit der Generation) $. Dies ist effektiv, wenn der Grad der Anpassungsfähigkeit positiv und die Varianz groß ist.
Extrahieren Sie nach dem Zufallsprinzip $ n $ Individuen aus der Bevölkerung und belassen Sie die Person mit der höchsten Anpassungsfähigkeit. Wiederholen Sie diesen Vorgang, bis die erforderliche Anzahl von Personen erfasst ist. Gene mit geringer Anpassungsfähigkeit bleiben probabilistisch, so dass die Diversität nicht stark abnimmt. Andererseits können Gene mit hoher Anpassungsfähigkeit verworfen werden und es kann keine Lösung erreicht werden.
Ich werde zwei Möglichkeiten vorstellen, die Route auszudrücken (Codierung).
Dies ist eine Ausdrucksmethode, bei der die Punktnummern so angeordnet sind, wie sie sind. Die Gene sind Punktzahlen $ 1, \ Punkte, N $. Die Chromosomen sind eine Reihe von Genen, die nicht dupliziert sind, $ g_1, \ dots, g_N $. Wenn $ g_i = k $ ist, bedeutet dies, dass $ p_k $ im $ i $ th durchlaufen wird. Unten finden Sie ein Beispiel für eine Route durch 5 Punkte und deren sequentielle Codierung.
\{ p_4, p_1, p_3, p_5, p_2 \} \rightarrow 4, 1, 3, 5, 2
Diese Darstellung behält immer $ g_i \ neq g_j (i \ neq j) $.
Vorläufercodierung ist ein beliebiger Name. Ich kannte den offiziellen Namen nicht.
Dies ist eine Ausdrucksmethode, die die Reihenfolge der Punktsequenz ohne die übergebenen Punkte verwendet. Das $ i $ -te Gen $ g_i $ nimmt bis zu $ N-i + 1 $ auf, die Anzahl der verbleibenden Punkte. Wenn Sie eine Folge von Punkten $ P_1 = p_1, p_2, \ dots, p_N $ haben, gehen Sie wie folgt vor, um $ g_i $ zu bestimmen:
Unten finden Sie ein Beispiel für eine Route durch 5 Punkte und ihre Ordnungscodierung.
\{ p_4, p_1, p_3, p_5, p_2 \} \rightarrow 4, 1, 2, 2, 1 \\
\begin{array}{lll}
p_1, p_2, p_3, p_4, p_5 & -, -, -, -, - &Entfernen Sie Punkte, während Sie die Position in der Sequenz aufzeichnen\\
p_1, p_2, p_3, p_5 & 4, -, -, -, - & p_4 ist der 4 ..\\
p_2, p_3, p_5 & 4, 1, -, -, - & p_1 ist der erste\\
p_2, p_5 & 4, 1, 2, -, - & p_3 ist der zweite\\
p_2 & 4, 1, 2, 2, - & p_5 ist die zweite\\
& 4, 1, 2, 2, 1 & p_2 ist der erste
\end{array}
Bei dieser Darstellung bleibt $ g_i \ le N-i + 1 $ immer erhalten. Stattdessen kann dieselbe Zahl im Chromosom erscheinen ($ g_i = g_j (i \ neq j) $). Die Entsprechung zwischen dem Gen $ g_i $ und den Punkten ist nicht intuitiv und kann nur durch Untersuchen von $ g_1, \ dots, g_ {i-1} $ gefunden werden.
Bei sich kreuzenden Organismen ist es üblich, gepaarte Chromosomen auszutauschen oder entsprechende Abschnitte zwischen Chromosomen auszutauschen. Darüber hinaus gibt es verschiedene Mutationen, da die Position der Gene nicht eingeschränkt ist und die Länge der Chromosomen flexibel ist.
Da das Chromosom des Verkäufers codierungsabhängige Einschränkungen aufweist, definieren wir Überkreuzungen und Mutationen innerhalb dieses Bereichs.
――Da die Einschränkung der Sequenzcodierung darin besteht, dass jedes Gen einmal vorhanden ist, muss so gearbeitet werden, dass die Chromosomen nicht doppelt gekreuzt werden (glücklicherweise haben kluge Köpfe die Kreuzung für geordnete Gene entwickelt. ). Andererseits ist der Austausch von Genen in einem Chromosom leicht zu beschreiben, da er die Einschränkungen nicht durchbricht.
Suchen Sie aus den beiden Chromosomen die Gruppe mit demselben Punkt- und Positionspaar und tauschen Sie die Gruppen aus.
\begin{array}{cc}
Elternteil 1& 1\acute{2}345678 \\
Elternteil 2& 6\grave{7}852341
\end{array}
\rightarrow
\begin{array}{c}
1\acute{2}3456\acute{7}8 \\
6\grave{7}8523\grave{4}1
\end{array}
\rightarrow \dots \rightarrow
\begin{array}{c}
1\acute{2}3\acute{4}\acute{5}6\acute{7}8 \\
6\grave{7}8\grave{5}\grave{2}3\grave{4}1
\end{array}
\rightarrow
\begin{array}{cc}
Kind 1& 1\hat{7}3\hat{5}\hat{2}6\hat{4}8 \\
Kind 2& 6\hat{2}8\hat{4}\hat{5}3\hat{7}1
\end{array}
Wählen Sie eine zufällige Position $ r $ und sehen Sie sich die Gene $ {g_1} _r, {g_2} _r $ an dieser Position in Elternteil 1 und Elternteil 2 an. Die Gene $ {g_1} _r und {g_2} _r $ werden zwischen Elternteil 1 bzw. Elternteil 2 ausgetauscht. Wiederholen Sie dies mehrmals, um Chromosomen von Kind 1 und Kind 2 zu erzeugen.
\begin{array}{cc}
Elternteil 1& 12\acute{3}4567\grave{8} \\
Elternteil 2& 67\grave{8}52\acute{3}41
\end{array}
\rightarrow
\begin{array}{cc}
Kind 1& 12\acute{8}4567\acute{3} \\
Kind 2& 67\grave{3}52\grave{8}41
\end{array}
Elternteil 1 erbt den zufälligen Abschnitt des Chromosoms wie es für das Kind ist. Elternteil 2 füllt die Lücken, indem es die fehlenden Gene im Kind übernimmt, damit sie nicht außer Betrieb sind.
\begin{array}{cc}
Elternteil 1& \acute{1}\acute{2}\acute{3}|456|\acute{7}\acute{8} \\
Elternteil 2& 6\grave{7}\grave{8}5\grave{2}\grave{3}4\grave{1}
\end{array}
\rightarrow
\begin{array}{cc}
Kind& \grave{7}\grave{8}\grave{2}|456|\grave{3}\grave{1}
\end{array}
Bestimmen Sie einige zufällige Positionen $ r_1, \ dots, r_k $ und sehen Sie sich die Gene $ g_ {r_1}, \ dots, g_ {r_k} $ an diesen Positionen in Elternteil 1 an. Sortieren Sie diese Gene $ g_ {r_1}, \ dots, g_ {r_k} $ in Elternteil 2 in der Reihenfolge in Elternteil 1, um die Chromosomen in Kind 1 zu erzeugen. Tauschen Sie Elternteil 1 und Elternteil 2 aus und machen Sie dasselbe, um Kind 2 zu generieren.
\begin{array}{cc}
Elternteil 1& 1\acute{2}3\acute{4}\acute{5}67\acute{8} \\
Elternteil 2& 67\grave{8}\grave{5}\grave{2}3\grave{4}1
\end{array}
\rightarrow
\begin{array}{cc}
Kind 1& 67\acute{2}\acute{4}\acute{5}3\acute{8}1
\end{array}
Bestimmen Sie einige zufällige Positionen $ r_1, \ dots, r_k $. Kind 1 erbt die Gene $ g_ {r_1}, \ dots, g_ {r_k} $ an diesen Positionen von Elternteil 1. Die fehlenden Gene werden ungeordnet von Elternteil 2 vererbt. Tauschen Sie Elternteil 1 und Elternteil 2 aus und machen Sie dasselbe, um Kind 2 zu generieren.
\begin{array}{cc}
Elternteil 1& 1\acute{2}3\acute{4}\acute{5}67\acute{8} \\
Elternteil 2& \grave{6}\grave{7}852\grave{3}4\grave{1}
\end{array}
\rightarrow
\begin{array}{cc}
Kind& \grave{6}\acute{2}\grave{7}\acute{4}\acute{5}\grave{3}\grave{1}\acute{8}
\end{array}
Wenn es nur ein Kind gibt, sind einheitliche Ordnungskreuzung und einheitliche Positionskreuzung gleichwertig.
Es durchsucht zwei Chromosomen nach einem Abschnitt, in dem derselbe Satz von Genen aufgereiht ist, und tauscht die Abschnitte aus, um die Kinder 1 und 2 zu erzeugen.
\begin{array}{cc}
Elternteil 1& 1\acute{2}\acute{3}\acute{4}\acute{5}678 \\
Elternteil 2& 678\grave{5}\grave{3}\grave{2}\grave{4}1
\end{array}
\rightarrow
\begin{array}{cc}
Kind 1& 1\grave{5}\grave{3}\grave{2}\grave{4}678 \\
Kind 2& 678\acute{2}\acute{3}\acute{4}\acute{5}1
\end{array}
Die Gene werden für jeden Abschnitt von zwei zufällig ausgewählten Abschnitten ausgetauscht.
\begin{array}{cc}
Elternteil& 1|\acute{2}\acute{3}\acute{4}|56|\grave{7}\grave{8}|
\end{array}
\rightarrow
\begin{array}{cc}
Kind& 1|\grave{7}\grave{8}|56|\acute{2}\acute{3}\acute{4}|
\end{array}
Verschiebt einen zufällig ausgewählten Abschnitt an eine andere Position.
\begin{array}{cc}
Elternteil& 1|\acute{2}\acute{3}\acute{4}\acute{5}|678
\end{array}
\rightarrow
\begin{array}{cc}
Kind& 167|\acute{2}\acute{3}\acute{4}\acute{5}|8
\end{array}
Wählen Sie zufällig zwei Gene aus, $ g_1, g_2 $, und verschieben Sie $ g_1 $ vor $ g_2 $. Es ist eine besondere Form der Translokation.
\begin{array}{cc}
Elternteil& 1\acute{2}3456\grave{7}8
\end{array}
\rightarrow
\begin{array}{cc}
Kind& 1\grave{7}\acute{2}34568
\end{array}
Invertiert die Reihenfolge der Gene für zufällig ausgewählte Abschnitte.
\begin{array}{cc}
Elternteil& 1|\acute{2}\acute{3}\acute{4}|5678
\end{array}
\rightarrow
\begin{array}{cc}
Kind& 1|\acute{4}\acute{3}\acute{2}|5678
\end{array}
Ordnen Sie die Reihenfolge der Gene für zufällig ausgewählte Abschnitte zufällig neu an.
\begin{array}{cc}
Elternteil& 1|\acute{2}\acute{3}\acute{4}\acute{5}|678
\end{array}
\rightarrow
\begin{array}{cc}
Kind& 1|\acute{4}\acute{2}\acute{5}\acute{3}|678
\end{array}
Zwei Chromosomen werden an einer zufälligen Stelle geschnitten und ausgetauscht.
\begin{array}{cc}
Elternteil 1& g_1 g_2 g_3 | g_4 g_5 g_6 \\
Elternteil 2& h_1 h_2 h_3 | h_4 h_5 h_6
\end{array}
\rightarrow
\begin{array}{cc}
Kind 1& g_1 g_2 g_3 | h_4 h_5 h_6 \\
Kind 2& h_1 h_2 h_3 | g_4 g_5 g_6
\end{array}
Tauschen Sie die Abschnitte aus, in denen zwei Chromosomen an zwei zufälligen Punkten geschnitten werden.
\begin{array}{cc}
Elternteil 1& g_1 g_2 | g_3 g_4 g_5 | g_6 \\
Elternteil 2& h_1 h_2 | h_3 h_4 h_5 | h_6
\end{array}
\rightarrow
\begin{array}{cc}
Kind 1& g_1 g_2 | h_3 h_4 h_5 | g_6 \\
Kind 2& h_1 h_2 | g_3 g_4 g_5 | h_6
\end{array}
Tauschen Sie die Abschnitte aus, in denen zwei Chromosomen an mehreren zufälligen Punkten geschnitten werden.
\begin{array}{cc}
Elternteil 1& g_1 | g_2 g_3 | g_4 g_5 | g_6 \\
Elternteil 2& h_1 | h_2 h_3 | h_4 h_5 | h_6
\end{array}
\rightarrow
\begin{array}{cc}
Kind 1& g_1 | h_2 h_3 | g_4 g_5 | h_6 \\
Kind 2& h_1 | g_2 g_3 | h_4 h_5 | g_6
\end{array}
Die Gene jedes der beiden Chromosomen werden mit einer angemessenen Wahrscheinlichkeit ausgetauscht.
\begin{array}{cc}
Elternteil 1& g_1 g_2 g_3 g_4 g_5 g_6 \\
Elternteil 2& h_1 h_2 h_3 h_4 h_5 h_6
\end{array}
\rightarrow
\begin{array}{cc}
Kind 1& g_1 h_2 g_3 h_4 h_5 g_6 \\
Kind 2& h_1 g_2 h_3 g_4 g_5 h_6
\end{array}
Ersetzen Sie ein Gen an einer zufälligen Position durch ein anderes Gen.
\begin{array}{cc}
Elternteil& g_1 g_2 g_3 g_4 g_5 g_6
\end{array}
\rightarrow
\begin{array}{cc}
Kind& g_1 h_2 g_3 h_4 g_5 g_6
\end{array}
Es produziert ein ganz neues Individuum, kein Kreuz oder eine Mutation.
Ich hatte vor, das Programm zu veröffentlichen, indem ich kurz das Problem des genetischen Algorithmus / des reisenden Verkäufers einführte, aber da die Einführung des genetischen Algorithmus zu einem langen Satz geworden ist, werde ich das Programm in einem separaten Artikel schreiben.