introduction

J'ai essayé de faire beaucoup de hits en googlé avec "Circular Salesman Problem Genetic Algorithm".

Résultat d'exécution

[Code Python] Ceci est le résultat de la recherche de certains points sur Google Colaboratory avec le code créé dans ().

--time ... temps d'exécution --epoch ... nombre de générations --fitness ... adaptabilité de la solution approximative --length ... Longueur du chemin de la solution approximative --path ... Chemin de la solution approximative --Graphe ... $ p_1, p_2, \ dots, p_N $, et le chemin de la solution optimale dans la génération intermédiaire

Puisque l'algorithme génétique a un fort élément aléatoire, le temps de calcul et la solution approximative changent à chaque fois qu'il est exécuté. Si vous ne parvenez pas à reproduire des résultats similaires, réessayez plusieurs fois.

25 points de grille

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)

30 points au hasard

Il s'agit d'un chemin de groupe de points généré aléatoirement. L'état initial est désordonné, mais vous pouvez voir comment il est organisé à chaque génération. La rangée inférieure montre la transition de l'adaptabilité, le nombre d'individus dans la génération, le nombre de descendants produits et la répartition de l'adaptabilité dans la génération finale.

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)

30 points au hasard: route droite

Nous avons recherché une route à sens unique avec l'un des $ p_1, \ points et p_N $ comme points de départ et d'arrivée, au lieu de la route avec l'origine comme points de départ et d'arrivée. Dans le graphique, seule la ligne bleue correspond à l'itinéraire recherché. Vous pouvez voir comment il converge vers un chemin différent du chemin dont les points de départ et d'arrivée sont l'origine.

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)

Aléatoire 30 points: Route droite: pénalité

Il s'agit d'un itinéraire à sens unique comme ci-dessus, mais si vous vous éloignez de l'origine, la différence de distance par rapport à l'origine est ajoutée à la longueur de l'itinéraire comme pénalité. Vous pouvez voir comment il converge sur un chemin différent de celui sans pénalité. En comparant les 47e et 95e générations, l'adaptabilité a diminué, mais la longueur de l'itinéraire a augmenté. La sanction semble fonctionner.

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)

en conclusion

Bien qu'il s'agisse d'une implémentation simple, vous pouvez trouver la solution optimale en un temps étonnamment court. Cependant, à mesure que le nombre de points augmente, le temps de recherche augmentera de façon exponentielle. Ensuite, nous visons à réduire le temps de recherche en ajustant les hyper paramètres et en concevant l'implémentation.

[PYTHON] Essayez de résoudre le problème du voyageur de commerce avec un algorithme génétique (résultat de l'exécution)