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

Introduction

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

-Theory -Python code -Execution result

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)

image.png

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)

image.png

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)

image.png

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)

image.png

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.

Recommended Posts

Try to solve the traveling salesman problem with a genetic algorithm (execution result)
Try to solve the traveling salesman problem with a genetic algorithm (Theory)
Try to solve the traveling salesman problem with a genetic algorithm (Python code)
I tried "Implementing a genetic algorithm (GA) in python to solve the traveling salesman problem (TSP)"
Finding a solution to the N-Queen problem with a genetic algorithm (2)
Finding a solution to the N-Queen problem with a genetic algorithm (1)
Solve the traveling salesman problem with OR-Tools
Try to solve the fizzbuzz problem with Keras
The story of the algorithm drawing a ridiculous conclusion when trying to solve the traveling salesman problem properly
Try to solve the internship assignment problem with Python
Solving the traveling salesman problem with the genetic algorithm (GA) and its library (vcopt)
Solve the Python asymmetric traveling salesman problem with a branch and bound method
Solving the nurse scheduling problem (shift optimization) with a genetic algorithm
Try to solve the N Queens problem with SA of PyQUBO
I wanted to solve the ABC164 A ~ D problem with Python
Solve a simple traveling salesman problem using a Boltzmann machine with simulated annealing
How to fix the initial population with a genetic algorithm using DEAP
Try to solve a set problem of high school math with Python
Try to solve the Python class inheritance problem
Try to solve the man-machine chart with Python
How to try the friends-of-friends algorithm with pyfof
I tried to implement the traveling salesman problem
The first algorithm to learn with Python: FizzBuzz problem
I tried to solve the problem with Python Vol.1
About the traveling salesman problem
[Python] Try optimizing FX systole parameters with a genetic algorithm
I tried to solve a combination optimization problem with Qiskit
A story about how to deal with the CORS problem
Try to model a multimodal distribution using the EM algorithm
About the Ordered Traveling Salesman Problem
Let's write a program to solve the 4x4x4 Rubik's Cube! 2. Algorithm
Find the optimal value of a function with a genetic algorithm (Part 2)
Solve the Python knapsack problem with a branch and bound method
Try to solve the shortest path with Python + NetworkX + social data
Solve the subset sum problem with a full search in Python
Try to solve the function minimization problem using particle swarm optimization
Want to solve a simple classification problem?
Stack problem: Try to solve "20. Valid Parentheses"
How to solve the bin packing problem
Try the Variational-Quantum-Eigensolver (VQE) algorithm with Blueqat
The 16th offline real-time how to write reference problem to solve with Python
Search the maze with the python A * algorithm
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Python: I tried the traveling salesman problem
The 19th offline real-time how to write reference problem to solve with Python
I want to solve the problem of memory leak when outputting a large number of images with Matplotlib
How to pass the execution result of a shell command in a list in Python
A simple workaround for bots to try to post tweets with the same content
[AtCoder] Solve A problem of ABC101 ~ 169 with Python
Try to calculate a statistical problem in Python
Try to draw a life curve with python
Try to make a "cryptanalysis" cipher with Python
Save the object to a file with pickle
Try to make a dihedral group with Python
Try creating a FizzBuzz problem with a shell program
Solving the Python knapsack problem with the greedy algorithm
Set the output destination of the execution result to Vim started as a modeless window
Try to create a battle record table with matplotlib from the data of "Schedule-kun"
I tried to solve the virtual machine placement optimization problem (simple version) with blueqat
A memo on how to overcome the difficult problem of capturing FX with AI
Try to create a waveform (audio spectrum) that moves according to the sound with python