[PYTHON] Solving the traveling salesman problem with the genetic algorithm (GA) and its library (vcopt)

: anchor: Purpose of this article

In this article, we will solve a simple example of the traveling salesman problem that often appears in mathematical optimization problems by using the Python library "vcopt", which is a solver that applies the Genetic Algorithm (GA). I will explore it. Also, let's see how to solve and use vcopt "Global optimization of the order represented by the traveling salesman problem".

: anchor: What is vcopt?

A combinatorial optimization solver using the Genetic Algorithm (GA) developed by Vignette & Clarity LLC (https://vigne-cla.com/). Written in the Python language. Various functions are implemented in the solver, but this time I will try to find a solution with the function [vcopt (). TspGA () function] that finds the global optimization of the order (sorting).

: anchor: Example

Let's take a look at an example of the traveling salesman problem.

: speech_balloon: Problem

`ruby:5.1.problem`


If you visit 5 cities, the distance traveled between the cities is shown in Table 5..Consider the traveling salesman problem given in 1.
For example, A-B-C-D-E-When you visit with A, the total distance traveled is 30+ 30 + 25 + 30 + 10 =It becomes 125.
Consider a patrol route that requires the shortest travel distance.

** Table 5.1 **

	B	C	D	E
A	30	30	25	10
B		30	45	20
C			25	20
D				30

: speech_balloon: ** Thinking **

The problem setting defines the distance between cities, so you can calculate this distance for each route to get a solution. In vcopt, a function [** tspGA () **] that calculates "global optimization of order" is provided as standard, so use this. (For details on tspGA (), refer to the vcopt tutorial etc.)

: desktop: Easy optimization package "vcopt" tutorial 　https://vigne-cla.com/vcopt-tutorial/

However, when using the above function [tspGA ()], it is necessary to set the evaluation function as one of the parameters. This evaluation function needs to be implemented independently as a function to calculate the total distance for each route.

Also, although not specified in the problem statement, this problem assumes that you are leaving City A and returning to City A again. If you show the route that goes around and returns in a diagram, you can imagine that it will be a figure close to a circle (a distorted circle) with connected lines. The lines do not break in the middle or overlap on the same path. This is called a cycle. When finding this cycle, vcopt has an explanation of the solution, so apply this.

: desktop: 8-6. Solving the traveling salesman problem with vcopt (How do you close the cycle?) 　https://vigne-cla.com/8-6/

: a: ** Answer **

Consider the program. First, load the required libraries.

`tspga.py`


from vcopt import vcopt
import numpy as np

The evaluation function is defined below. As mentioned above, it is one of the arguments (parameters) required when executing the function [tspGA ()].

`tspga.py`


#A function that calculates the distance between cities
def tsp_score(para):

    para_full = np.hstack((0, para, 0))　　... (1)

The above is for vcopt to calculate the value of this merit function when solving the combination optimization problem, and to maximize or minimize it or to approach the target value. Since the purpose of this time is to reduce the total distance as much as possible in the traveling salesman problem, we will define a function to calculate the total distance when traveling to each city. The function name is tsp_score. As an argument, it is an array (para) of index numbers representing each city. One thing to keep in mind here is that it does not include only City A. The contents of this index number array will be described later.

Regarding (1) above, there is a detailed explanation in "Solving the Traveling Salesman Problem with vcopt (How to close the cycle?)", But after leaving City A and traveling to other cities, City A again. It is a sentence to set the condition to return to. The number 0 is the index number for city A. The index number representing the city is defined below.

Please do not write "... (1)" in the program.

Next, define the distance between cities as a constant.

`tspga.py`


    dis = [[0 for i in range(5)] for j in range(5)]
    dis[0][0] = 50
    dis[0][1] = 30
    dis[0][2] = 30
　　...

For the above, we made a two-dimensional array with the constant name dis. For example, if you move from city A (index number: 0) to city B (index number: 1), set the value with dis [0] [1]. The setting value is 30. Only a part of the above source is posted. In the actual source, set between all cities. Please refer to the entire source at the end of this article.

Since it is not possible to patrol the same city in succession, if the same index number continues, the distance value is set to 50. By setting a large value so as not to go around the same city, the value of the evaluation function is increased so that it is not selected as the solution for optimization.

The rest of the definition of the merit function is shown below.

`tspga.py`


    distance = 0
    for step in range(5):
        distance += dis[para_full[step]][para_full[step + 1]]

    return distance

The above is the process of calculating the total distance (variable name: distance) when moving between cities and returning it to the caller of the function. step is a number that indicates the number of visits when traveling around the city. Loop the step with 0 to 4 in the for statement, and add up the distance traveled between the stepth city and the step + 1st city.

This concludes the definition of the evaluation function. Enter the main processing of the program.

`tspga.py`


para = [1,2,3,4]

The above are the parameters given to the function [tspGA ()], which are the elements to consider the combination. In this problem, the city to be visited is rearranged (combined) to find a solution, so the element is the city number. However, as mentioned above, the cities at the start and end points of the patrol are A, so city A has already been decided and is not subject to sorting (combination). The target is cities B to E, and the index numbers are 1 to 4.

The evaluation function [tsp_score ()] defined earlier also has the argument para, which points to the same variable. The tsp_score function is called internally when vcopt executes tsp_score (), and the parameter para is also set automatically.

Next, execute the function [tspGA ()] that calculates the optimization solution.

`tspga.py`


para, score = vcopt().tspGA(para,       #Elements to be sorted
                            tsp_score,  #Evaluation function
                            0.0)        #Target value

Set three arguments (parameters) when calling tspGA () above. The first argument is the "element to be sorted". This time it is the index number of all cities except city A. The second argument is the "evaluation function". The contents of the evaluation function are explained in the definition part of this function. The third argument is the "target value". The target value is 0. The travel distance does not actually become 0, but since the patrol route with the smallest travel distance is the solution to the problem, it is set to 0 to determine the direction in which it becomes smaller. For details on the arguments (parameters), refer to the vcopt tutorial.

There are two return values for the function, para is the array after sorting, and score is the total distance (minimum distance) calculated as the solution after optimization.

Below, para and score are displayed on the screen at the end of the program.

`tspga.py`


print('para=',para)
print('score=',score)

This is the end of programming. The actual execution result is as follows.

___________________ info ___________________ para_range : n=4 score_func : <class 'function'> aim : 0.0 show_pool_func : 'bar' seed : None pool_num : 40 max_gen : None core_num : 1 (*vcopt, vc-grendel) ___________________ start __________________ Scoring first gen 40/40
Mini 2-opting first gen 40/40
| +<| gen=80, best_score=110.0 __________________ results _________________ para : [3 2 1 4] score : 110.0 ____________________ end ___________________ para= [3 2 1 4] score= 110.0

As a result of the optimization, the solution is as follows. para = [3 2 1 4] This means that the city's circuit route represents cities D, C, B, E. This time, city A is the starting point and ending point, so I finally found out that the patrol route should be as follows.

** Patrol route A → D → C → B → E → A **

The total distance is ** 110 **.

The entire program is shown below.

`tspga.py`


from vcopt import vcopt
import numpy as np

#Traveling salesman problem

#A function that calculates the distance between cities
def tsp_score(para):

    para_full = np.hstack((0, para, 0))

    dis = [[0 for i in range(5)] for j in range(5)]
    dis[0][0] = 50
    dis[0][1] = 30
    dis[0][2] = 30
    dis[0][3] = 25
    dis[0][4] = 10
    dis[1][0] = 30
    dis[1][1] = 50
    dis[1][2] = 30
    dis[1][3] = 45
    dis[1][4] = 20
    dis[2][0] = 30
    dis[2][1] = 30
    dis[2][2] = 50
    dis[2][3] = 25
    dis[2][4] = 20
    dis[3][0] = 25
    dis[3][1] = 45
    dis[3][2] = 25
    dis[3][3] = 50
    dis[3][4] = 30
    dis[4][0] = 10
    dis[4][1] = 20
    dis[4][2] = 20
    dis[4][3] = 30
    dis[4][4] = 50

    distance = 0
    for step in range(5):
        distance += dis[para_full[step]][para_full[step + 1]]

    return distance


para = [1,2,3,4]

para, score = vcopt().tspGA(para,       #Elements to be sorted
                            tsp_score,  #Evaluation function
                            0.0)        #Target value

print('para=',para)
print('score=',score)

: anchor: Exhibit

This article is based on the exercises described in the following reference texts on mathematical optimization.

■ Reference text "IT Text Mathematical Optimization" Shizuka Kuno, et al. [Author] Information Processing Society of Japan [edit]

: anchor: Opinions etc.

If you have any opinions or corrections, please let us know.