Introduction

I tried to make a lot of hits by googled with "Traveling salesman problem genetic algorithm".

Execution result

[Python code] This is the result of searching for some point clouds on Google Colaboratory with the code created in ().

--time ... execution time --epoch ... Number of generations --fitness ... fitness of approximate solution --length ... Path length of approximate solution --path ... Approximate solution path --Graph ... $ p_1, p_2, \ dots, p_N $, and the optimal solution path in the middle generation

Since the genetic algorithm has a strong random number element, the calculation time and approximate solution change each time it is executed. If you can't reproduce similar results, try again a few times.

25 grid points

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)

Random 30 points

This is a randomly generated point cloud path. The initial state is messy, but you can see how it is organized with each generation. The bottom row shows the transition of fitness, the number of generations, the number of offspring produced, and the distribution of fitness in the final 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)

Random 30 points: 1pondo

We searched for a one-way route with one of $ p_1, \ dots, and p_N $ as the start and end points, instead of the route with the origin as the start and end points. In the graph, only the blue line is the searched path. You can see how it converges on a path different from the path with the origin as the start and end point.

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)

Random 30 points: 1pondo: with penalty

It is a one-way route as above, but if you proceed away from the origin, the difference in distance from the origin is added to the route length as a penalty. You can see how it converges on a different path than without penalty. Comparing the 47th and 95th generations, the fitness has decreased, but the route length has increased. The penalty seems to be working.

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)

in conclusion

Although it is a simple implementation, it can search for the optimal solution in a surprisingly short time. However, as the number of points increases, the search time increases exponentially. Next, we aim to reduce the search time by adjusting hyperparameters and devising the implementation.

[PYTHON] Try to solve the traveling salesman problem with a genetic algorithm (execution result)