Einführung

Ich habe versucht, viele Treffer zu erzielen, indem ich mit "Circular Salesman Problem Genetic Algorithm" gegoogelt habe.

Ausführungsergebnis

[Python-Code] Dies ist das Ergebnis der Suche nach einigen Punkten in Google Colaboratory mit dem in () erstellten Code.

--time ... Ausführungszeit --epoch ... Anzahl der Generationen --fitness ... Anpassungsfähigkeit der Näherungslösung --length ... Pfadlänge der ungefähren Lösung --path ... Pfad der ungefähren Lösung --Graph ... $ p_1, p_2, \ dots, p_N $ und der Pfad der optimalen Lösung in der mittleren Generation

Da der genetische Algorithmus ein starkes zufälliges Element aufweist, ändern sich die Berechnungszeit und die ungefähre Lösung bei jeder Ausführung. Wenn Sie ähnliche Ergebnisse nicht reproduzieren können, versuchen Sie es einige Male erneut.

25 Gitterpunkte

import numpy as np
from GaTsp import *

loggers = (Logger_trace(level=2), Logger_leaders())
pts_m = np.array([(x+random.random()/5-2.09, y+random.random()/5-2.09) for x in range(5) for y in range(5)])
spc_m = Species(points=pts_m)  # matrix points
mdl = Model(species=spc_m)
mdl.fit(loggers=loggers)
Logger.plot_all(loggers=loggers)

Zufällige 30 Punkte

Dies ist ein zufällig generierter Punktgruppenpfad. Der Ausgangszustand ist chaotisch, aber Sie können sehen, wie er mit jeder Generation organisiert ist. Die untere Reihe zeigt den Übergang der Anpassungsfähigkeit, die Anzahl der Individuen in der Generation, die Anzahl der produzierten Nachkommen und die Verteilung der Anpassungsfähigkeit in der letzten Generation.

import numpy as np
from GaTsp import *

loggers = (
    Logger_trace(level=2),
    Logger_leaders(),
    Logger_fitness(),
    Logger_population(),
    Logger_population(show_breeded=True),
    Logger_last_fitness_histgram(),
)
loggers = (Logger_trace(level=2), Logger_leaders())
spc_r = Species(N=30, seed=30)
mdl = Model(species=spc_r)
mdl.fit(loggers=loggers)
Logger.plot_all(loggers=loggers)

Zufällige 30 Punkte: gerade Straße

Wir suchten nach einer Einwegroute mit einem von $ p_1, \ dots und p_N $ als Start- und Endpunkt anstelle der Route mit dem Ursprung als Start- und Endpunkt. In der Grafik ist nur die blaue Linie die gesuchte Route. Sie können sehen, wie es zu einem Pfad konvergiert, der sich von dem Pfad unterscheidet, dessen Start- und Endpunkt der Ursprung sind.

import numpy as np
from GaTsp import *

class SpeciesPolyline(Species):
    def measure(self, path:np.ndarray, *args, **kwargs):
        length = self._distance_map[path[:-1], path[1:]].sum()
        return length

loggers = (Logger_trace(level=2), Logger_leaders())
spc_p = SpeciesPolyline(N=30, seed=30)
mdl = Model(species=spc_p)
mdl.fit(loggers=loggers)
Logger.plot_all(loggers=loggers)

Zufällige 30 Punkte: Gerade Straße: Strafe

Es ist eine Einbahnstraße wie oben, aber wenn Sie vom Ursprung weggehen, wird der Unterschied in der Entfernung vom Ursprung als Länge zur Routenlänge addiert. Sie können sehen, wie es auf einem anderen Weg konvergiert als ohne Strafe. Im Vergleich zur 47. und 95. Generation hat die Anpassungsfähigkeit abgenommen, aber die Streckenlänge hat zugenommen. Die Strafe scheint zu funktionieren.

class SpeciesSpiral(SpeciesPolyline):
    def penalty(self, path:np.ndarray, *args, **kwargs):
        penalties = self._to_origin[path[1:]] - self._to_origin[path[:-1]]
        penalty = penalties[penalties > 0].sum()
        return penalty

loggers = (Logger_trace(level=2), Logger_leaders())
spc_s = SpeciesSpiral(N=30, seed=30)
mdl = Model(species=spc_s)
mdl.fit(loggers=loggers)
Logger.plot_all(loggers=loggers)

abschließend

Obwohl es sich um eine einfache Implementierung handelt, können Sie in überraschend kurzer Zeit die optimale Lösung finden. Mit zunehmender Punktzahl steigt die Suchzeit jedoch exponentiell an. Als nächstes wollen wir die Suchzeit reduzieren, indem wir die Hyperparameter anpassen und die Implementierung entwickeln.

[PYTHON] Versuchen Sie, das Problem des Handlungsreisenden mit einem genetischen Algorithmus zu lösen (Ausführungsergebnis)