Ich habe versucht, ein Programm in Java zu erstellen, das das Problem des Handlungsreisenden mit einem genetischen Algorithmus löst
Ich habe zufällig geforscht, um mit einem genetischen Algorithmus zu lösen. Ich habe es in dem Sinne gemacht, die Anzahl der Schritte für die Zukunft zu erhöhen.
Was ist das Problem des Handlungsreisenden?
Es ist ein Problem, über die Reihenfolge nachzudenken, in der Sie am kürzesten passieren können, wenn Sie einen Strich an einem bestimmten Punkt in $ n $ schreiben. Wenn die Anzahl der Städte, die in einem Strich geschrieben werden sollen, $ n $ beträgt, beträgt die Anzahl der möglichen Kombinationen $ \ frac {(n-1)!} {2} $.
Was ist ein genetischer Algorithmus?
Es ist eine der Evolutionsberechnungen, die die Evolution von Lebewesen modellieren. Die Kombination von Lösungen wird als Chromosom angesehen, und die Lösung wird durch Wiederholung genetischer Manipulationen wie Kreuzung und Mutation entwickelt, und schließlich wird die beste Lösung gesucht.
Klassenfluss
Da wir in Java programmieren, werden wir jede Klasse der Reihe nach betrachten. Das Klassendiagramm ist wie folgt. Klicken Sie hier für die Literatur, auf die im Entwurf verwiesen wird [^ 1]
Die Klasse dieses Programms ist wie folgt.
- Punktklasse: $ x $, $ y $ Speichert jede Koordinate.
- Kartenklasse: Eine Klasse, die die Daten der Punktklasse aggregiert und als Karte zusammenfügt.
- Tour-Klasse: Eine Klasse, die Routen basierend auf der Map-Klasse speichert.
- TourWithGA-Klasse: Eine von der Tour-Klasse abgeleitete Klasse, die genetische Algorithmen lösen kann.
- tspSample-Klasse: Dies ist die Hauptklasse.
- tspIO-Klasse: Eine Klasse, die Koordinaten aus einer Datei liest.
- Sortierklasse: Eine Klasse für die Rangfolge von Personen. (Nicht im obigen Klassendiagramm enthalten.)
- Chromosomenklasse: Eine Klasse von Chromosomen. Die Gene sind in einer Sequenz enthalten.
- Einzelklasse: Eine Klasse von Populationen. Eine Reihe von Chromosomenklassen und ein Elite-Chromosom vom Chromosomentyp werden gespeichert.
Unter diesen werden drei genetische Algorithmen verwendet: ** TourWithGA **, ** Chromosom ** und ** Individuen **.
In Bezug auf die Genmanipulation implementiert die Chromosomenklasse Methoden zur Berechnung der Mutation und der Genkompatibilität, und die Einzelklasse implementiert Crossover, Genregeneration / -selektion und Elitekonservierung als Methoden.
Als Strategie wird es unter Bezugnahme auf die von Maekawa et al. [^ 2] vorgeschlagene EXX-Methode (Branch Exchange Crossing) erstellt.
Verhalten genetischer Algorithmen
Da es viel Quellcode gibt, lesen Sie bitte den Quellcode für Details. Ich werde die Spezifikationen erläutern, indem ich mich auf die Operation im genetischen Algorithmus konzentriere.
Kartendaten
Geben Sie den Standort der Stadt im Problem des Handlungsreisenden in eine CSV-Datei ein. Der Inhalt der CSV-Datei ist
berlin52.csv
52,
565,575
25,185
345,750
945,685
845,655
880,660
25,230
・
・
・
Geben Sie in der ersten Zeile die Anzahl der Städte ein, die gelesen werden können. Geben Sie ab der zweiten Zeile die Koordinaten $ x $ und $ y $ der Stadt ein.
Die Hauptklasse des Programms ist ** tspSample **. Beim Laufen in Java
$ java tspSample <CSV-Datei zum Lesen>
Bitte so ausführen.
Wenn das Lesen erfolgreich ist,
city_num= 52
565.000 575.000
25.0000 185.000
345.000 750.000
945.000 685.000
845.000 655.000
・
・
・
Auf diese Weise wird die Anzahl der gelesenen Städte und Stadtdaten an die Konsole ausgegeben.
Erste individuelle Generation
Generieren Sie eine anfängliche Population, die Kinder vom Typ Individuum genetisch manipuliert. Insbesondere in der Chromosomenklasse wird es als eine Sequenz von Städten als Gensequenz exprimiert. Die Tour-Klasse verfügt über eine Methode namens makeTour (), die zufällig eine Schaltung generiert. Nach dem Erzeugen der Schaltung wird die Schaltung in die Gensequenz kopiert.
Konformitätsberechnung
Der Konformitätsgrad wird basierend auf der Potenzgesetzskalierung berechnet. Die Anzahl der Städte $ n $ kann aus der Map-Klasse und die Schaltungslänge $ l $ aus der getDistance () -Methode der Tour-Klasse ermittelt werden.
\mathrm{Fitness} = \left(\frac{n}{l} \right)^3
Spielen / auswählen
Im Programm verwenden wir zwei Individuals-Klassen. Führen Sie eine genetische Manipulation mit ** Eltern ** durch. In der nächsten Generation überleben ** Kinder ** die Chromosomen ihrer Eltern basierend auf dem Grad der Chromosomenkompatibilität. $ N_ {\ mathrm {p}} $ wird in Eltern gespeichert, und $ N_ {\ mathrm {c}} $ wird in Kindern gespeichert. ($ N_ {\ mathrm {p}} \ geq N_ {\ mathrm {c}} $)
Was das Überleben betrifft, so werden die oberen $ N_ {\ mathrm {c}} $ Chromosomen in der Reihenfolge der Anpassungsfähigkeit der Chromosomen bei den Eltern zum Überleben gebracht. Da jedoch Elite-Individuen immer in die Bevölkerung einbezogen werden müssen, ist das Elite-Individuum in der Bevölkerung am kompatibelsten, wenn die Kompatibilität des am besten kompatiblen Chromosoms in der Bevölkerung größer ist als die Kompatibilität des Elite-Chromosoms. Update auf ein höheres Chromosom. Wenn nicht, ersetzen Sie das $ N_ {\ mathrm {c}} $ -te Chromosom durch ein Elite-Chromosom.
Die Methode zur Auswahl des Elternchromosoms, das genetisch aus den überlebenden Populationskindern manipuliert werden soll, besteht darin, den erwarteten Überlebenswert des Elternindividuums aus der folgenden Formel zu berechnen, wenn der Kompatibilitätsgrad des Chromosoms $ C_i $ bei den Kindern $ f_i $ beträgt.
\mathrm{Experience} = \frac{N_{\mathrm{p}} \times f_i}{N_{\mathrm{c}} \times \overline{f}}
$ \ Overline {f} $ ist die durchschnittliche Anpassung der Chromosomen bei Kindern. Wählen Sie das übergeordnete Chromosom so viele wie den erwarteten Wert (nach dem Dezimalpunkt abgerundet) aus und kopieren Sie es auf das übergeordnete Element. Der Teil nach dem Dezimalpunkt wird für die Roulette-Auswahl verwendet.
Wenn Sie für alle Chromosomen so viele Eltern auswählen, wie Sie erwarten, haben die Eltern einige leere Chromosomen. Die übrigen Eltern wählen ihre Eltern durch Roulette-Auswahl aus.
Um zu verhindern, dass dasselbe Chromosom aus den ausgewählten Eltern ausgewählt wird, werden zwei zufällig aus dem Elternchromosom ausgewählt, damit sie sich nicht überlappen, und sie werden gekreuzt.
Kreuzung / Mutation
Crossover basiert auf der Crossover-Wahrscheinlichkeit und Mutation basiert auf der Mutationswahrscheinlichkeit. Siehe Referenz [2] für Details.
Genetische Korrektur
Der genetische Algorithmus hat eine starke Fähigkeit, eine globale optimale Lösung zu finden, hat jedoch eine Schwäche in der lokalen Suchfähigkeit. Daher wird das Gen vor der Berechnung der Eignung durch die 2-Opt-Methode korrigiert, die eine der sequentiellen Verbesserungsmethoden für das Problem des Handlungsreisenden ist.
Ich habe es tatsächlich versucht
$ N_ {\ mathrm {c}} = $ 100, $ N_ {\ mathrm {p}} = $ 150, maximale Anzahl von Generationen: 300, Crossover-Wahrscheinlichkeit: 0,8, Mutationswahrscheinlichkeit: 0,1, 52 Stadt-Benchmark-Problem Berlin52 (optimaler Wert) : 7544,366)). .. Für die abgeschlossene Route werden die Daten in die Datei result.csv im selben Verzeichnis ausgegeben.
city_num= 52
565.000 575.000
25.0000 185.000
345.000 750.000
(Weggelassen)
595.000 360.000
1340.00 725.000
1740.00 245.000
start...
0 7742.647
1 7742.647
2 7742.647
3 7742.647
4 7544.366
5 7544.366
6 7544.366
(Weggelassen)
294 7544.366
295 7544.366
296 7544.366
297 7544.366
298 7544.366
299 7544.366
300 7544.366
7544.366
stop.
Bearbeitungszeit: 3157/ms
schließlich
Diese Verzweigungsaustauschkreuzung wird als die zweitbeste Methode nach der Verzweigungsassemblierungskreuzungsmethode zur Lösung des zyklischen Planungsproblems mit einem genetischen Algorithmus bezeichnet. Es wird gesagt, dass die Methode unter Verwendung der Zweigstellenkreuzung derzeit die beste Methode zur Lösung des genetischen Algorithmus für das Problem des Handlungsreisenden ist. Ich würde es gerne eines Tages versuchen. Da ich Planungsprobleme studiere, möchte ich ein Programm erstellen, das Planungsprobleme löst.
Quellcode
Der Quellcode ist öffentlich zugänglich. Der Code ist möglicherweise schmutzig, weil ich in einem Labor war, in dem Java nicht sehr häufig verwendet wird ... (Bitte zögern Sie nicht, mir Ratschläge zu geben.) https://github.com/SHIMADONBEY/GAwithTSP.git
Verweise
[^ 2]: [Maekawa, Tamaki, Kita, Nishikawa: Eine Lösung für das Problem des Handlungsreisenden durch einen genetischen Algorithmus, Proceedings of the Society of Automatic Measurements, Band 31, Nr. 5, S. 598-605, 1995.] https://www.jstage.jst.go.jp/article/sicetr1965/31/5/31_5_598/_pdf)