[optimization][ACO]Ant colony optimization in the travel salesman problem (TSP)

Step by step. (image source: Author, Somewhere in East Taiwan.)

Purpose:

1. introduce ant colony optimization (ACO) in the classical travel salesman problem (TSP) application using Python. (ACO_TSP problem)
2. understand the ACO_TSP principle by illustrations on the Python
3. a connective knowledge to the Max-Min Ant System (MMAS) optimization session[1].

Introduction:

1. TSP problem is a classical problem since 1832 [from wiki]. It aims to find out the shortest path during a salesman visiting cities below illustration. Nowadays, cities can be referred to as the Printed Circuit Board (PCB) drilling holes in the modem industry application for the shortest manufacture time.
2. ACO method is proposed by Dr. Marco Dorigo in his dissertation 1992. The reference is shown in [2].

ACO_TSP problem illustration. Each red point represents a city(left); the total travel path length(right)

Python code implementation:

The example code is below with the SKO package[3] which consists of other optimization algorithms and example codes.

In this code, there are 3 ants(line20-size_pop) to find out the shortest travel path among 12 cities(line8–num_points). Function cal_total_distance refers to path length computation. In other words, this is the “target function” in your application. Line19~21 are the major ACO process route to find out the best travel path sequence in the data format of a Python’s list. For explanation, line23~31 are the user-interface expression.

ACO_TSP example Python code. Source: heavily refer to the SKO package’s example file.

The insight of the SKO package:

We will divide into SKO’s ACA_TSP function to fuse the algorithms with Python steps by steps. There are two significant factors, pheromone τ, and visibility η in the ACO algorithm. The pheromone τ refers to the remained information on each path while ants pass through. The visibility η denotes the reciprocal distance between nodes. Possibility P consists of the pheromone τ and visibility η product and its summation. Given the shortest travel path, the high remained pheromone τ and the also high visibility η makes Possibility P stronger. Hence, Line38~39 computes the Possibility P. Later, the Line40 chooses the shortest travel path sequence by means of Possibility P . Finally, the line51~58 update the pheromone τ with disappear factor ρ. The parameter Q is the total pheromone in the constant value. Return to Line37, the new travel path sequence is defined for the next computation.

ACO_TSP algorithm. (source: Author, and SKO’s ACA_TSP function code)

Result:

The below illustration indicates the travel path sequence iteration result. In the left part, the series number of red points are connected; in the right part, the total(overall) travel path length is dropped down from 3.84 to 3.35. However, the new sequence (iteration #6) conducts the high mileage in the 4.29. While the iteration process completed, the iteration #5 sequence is reported as the best one.

ACO_TSP algorithm result. (source: Author)

Conclusion:

In this article, we introduce the Ant Colony Optimization method in solving the Salesman Travel Problem using Python and SKO package. Algorithms and software codes explain in parallel to understanding its theory intact. The result is shown with the iteration process for proving its ideas.

Reference:

[1]: [optimization][MMAS] Max-Min Ant System in finding the minimum value of a polynomial equation

[optimization][MMAS] Max-Min Ant System in finding the minimum value of a polynomial equation

[2] M. Dorigo, V. Maniezzo, and A. Colorni, “Ant system: optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 26, no. 1. doi: 10.1109/3477.484436. pp. 29–41, 1996.

[3] Genetic Algorithm, Particle Swarm Optimization, Simulated Annealing, Ant Colony Optimization Algorithm, Immune Algorithm, Artificial Fish Swarm Algorithm, Differential Evolution and TSP(Traveling salesman) 遗传、粒子群、模拟退火、蚁群算法等

guofei9987/scikit-opt