## 2 Principle of MAX-MIN Ant System Algorithm  
The ant colony algorithm is an optimization algorithm that was inspired by the behavior of real ants. It is one of the important methods of solving TSP. The basic ant colony algorithm needs a long search time and is prone to premature stagnation. In order to overcome these disadvantages, researchers continue to optimize the basic ant colony algorithm. In 1997, [PERSON] _et al_. proposed MAX-MIN ant algorithm (MMAS) [12]. There are two main differences between MMAS and the basic ant colony algorithm. The first one is that MMAS only updates pheromone for the shortest path in the current loop, which ensures that the algorithm searches in the vicinity of the shortest path then finds out the global optimal solution gradually. The second one is that the pheromone on each side is controlled in a fixed range (\(\tau_{min}\), \(\tau_{max}\)) to avoid the algorithm converging to the local optimal solution too fast. \(\tau_{min}\) and \(\tau_{max}\) are the minimum value and the maximum value of pheromone, respectively.  
The main process of using MMAS to solve TSP is as follows:  
(1) Initializing ants, cities and tabu list. At first, place \(m\) ants randomly in \(n\) cities. Pheromone values of every path between cities are initialized to the maximum value \(\tau_{max}\). For each ant, there is a tabu list to record the cities which the ant has gone by. The initialization of the tabu list is the city where the ant is situated. The values of pheromone released by ants in each path are initialized to 0.  
(2) Constructing the ant paths. An ant moves from city \(i\) to \(j\) with probability  
\[P_{ij}=\begin{cases}\dfrac{\left[\tau_{ij}(t)\right]^{\alpha}\times\left[\tau_ {ij}(t)\right]^{\beta}}{\sum_{j\subset callowed_{k}}\left[\tau_{ij}(t) \right]^{\alpha}\times\left[\tau_{ij}(t)\right]^{\beta}}\end{cases}j\subset allowed _{k}\\ 0\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\where \(\tau_{ij}(t)\) is the amount of pheromone deposited for transition from city \(i\) to \(j\) in time \(t,\,\alpha\) is a parameter to control the influence of \(\tau_{ij}(t)\), \(\eta_{ij}(t)\) is the desirability of city transition _ij_ (_a prior_ knowledge, typically \(1/d_{ij}\), where \(d\) is the distance) in time \(t\) and \(\beta\) is a parameter to control the influence of \(\eta_{ij}\). \(\tau_{ij}\) and \(\eta_{ij}\) represent the attractiveness and trail level for the other possible city transitions. _Allowedk_ is the set of cities which are not in the tabu list. Equation (1) shows that ants will not choose cities in the tabu list to ensure the legitimacy of solutions.  
(3) Operating the pheromone. In iteration, one ant is to complete a traversal of all cities. When all ants tabu lists have been filled, path constructions are finished. Compute the length of the path that each ant has passed by. Compare all paths to find the shortest one, and then save it, which is denoted as \(C^{best}\). The pheromone is updated by  
\[\left\{\tau_{tj}=(1-\rho)\tau_{ij}+\Delta\tau_{ij}\text{ {if {ij} is in }}C^{best}\right. \tag{2}\] \[\left.0\text{ {otherwise}}\right.\]  
where \(\rho\) is the pheromone evaporation coefficient and \(\Delta\tau_{ij}=1/\,C^{best}\). The minimum value and the maximum value of pheromone are respectively \(\tau_{min},\,\tau_{max}\). Go to step 2 after the pheromone operation until meeting the termination condition of the algorithm: result converging or reaching the maximum number of iterations.