# 蚁群算法

Italy scholar Dorigo M. et al. proposed Ant colony algorithm at European Conference on Artificial Life, ECAL) in 1991.

1) Basic Ideas

Ant Colony Algorithm(ACA) simulates how ants find the food. Why ants can find the shortest way from their nest to the food? Pheromone is the key. Pheromone can be detected and its concentration can be measured by ants. A lot of ant behaviors are regulated by pheromone. Ants are prone to move toward places where pheromone concentration is high. If the way is shorter, the concentration of pheromone is higher, thus this way will attract more ants, and the concentration gets higher. So this kind of information positive feedback helps ants find the shortest way.

Suppose there are two ways from $B$ to $C$, say $BFC$ and $BEC$, and $BF=CF=1$, $BE=CE=0.5$. There are 30 ants come from $B$ to $C$ per second, and 30 ants come from $C$ to $B$ per second, and velocity of ants is 1 per second, every ant releases a unit concentration pheromone per second. The pheromone will volatilize after 1 second. At $t=0$, there is no pheromone on the ways, so there will be 15 ants go $BF$ $BE$, $CF$, and $CE$. While at $t=1$, there are 30 ants come to $B$, and they find that the concentration of pheromone on $BF$ is 15, while the concentration on $BE$ is 30(released by 15 ants come from $B$ to $E$ and 15 ants come from $E$ to $B$). So 20 ants will go $BE$, 10 ants will go $BF$. The same for $C$. So some seconds later, all the ants will go $BEC$, the shortest way in this example.

2) Applications

Traveling salesman problem(TSP) is a typical combinatory optimization problem, it’s a NP problem.

TSP: $C=\{c_1,\cdots,c_n\}$ is a set of $n$ cities. Distance between $c_i$ and $c_j$ is $d_{ij}$ for $i\ne{j}$. The target is to find a shortest way. One can traverse each city only once and return to the start city by going this way.

To solve TSP by ACA, we assume

i) ant releases pheromone on the way between $c_i$ and $c_j$;

ii) ant selects the next city with probability related to the distance from current city and the concentration of pheromone on the way between the two cities;

iii) ant can not go to the city which has been traveled to if the ant does not finish its journey and get back to the start city. This can be realized by tabu list;

Assume there are $m$ ants. Set $\tau_{ij}(t)$ the concentration of pheromone. At time $t=0$, $\tau_{ij}(0)=const$ where $const$ is a predefined constant.

Ant $k$($k=1,\cdots,m$) selects city $j$ at time $t$ from city $i$ with probability $p_{ij}^k(t)$. Ants will select the way which is short to go and has higher concentration of pheromone. Use

$p_{ij}^k(t)=\begin{cases}\frac{[\tau_{ij}(t)]^\alpha\cdot[\eta_{ij}(t)]^\beta}{\sum\limits_{s\in{allowed_k}}{[\tau_{is}(t)]^\alpha\cdot[\eta_{is}(t)]^\beta }},j\in{allowed_k}\\0,else\end{cases}$

where $allowed_k=\{C-tabu_k\}$, cities that ant $k$ has not traveled to at time $t$, $tabu_k$($k=1,\cdots,m$) records the cities ant $k$ has traveled to. $\alpha$ is the factor of pheromone, determining the importance of pheromone. $\beta$ is the factor of expectation of prior knowledge. $\eta_{ij}$ is the prior knowledge about the way from city $i$ to $j$. In TSP, $\eta_{ij}=\frac{1}{d_{ij}}$.

The pheromone is volatile. We update all the $\tau_{ij}(t)$’s after all the ants finished traveling. Set

$\tau_{ij}(t+n)=(1-\rho)\tau_{ij}(t)+\Delta\tau_{ij}(t),$

$\Delta\tau_{ij}(t)=\sum\limits_{k=1}^m\Delta\tau_{ij}^k(t),$

where $\rho$ is the volatilization factor of pheromone taking value from $[0,1)$, $\delta\tau_{ij}(t)$ is the increment of pheromone on the way from $i$ to $j$, and it has initial value 0. $\Delta\tau_{ij}^k(t)$ is the pheromone released on the way from $i$ to $j$ by ant $k$. Set

$\Delta\tau_{ij}^k(t)=\begin{cases}\frac{Q}{L_k},\ if\ ant\ k\ has\ traveled\ from\ i\ to\ j,\\0,\ else\end{cases}$

where $Q$ is a constant, standing for the total pheromone in a comlete travel. $L_k$ is the total length of the complete travel way. This update method is called Ant-Cycle Model.

There are other update strategies for $\tau_{ij}(t)$, such as Ant-Quantity Model, Ant-Density Model and so on.

3) Implementation procedure

Using Ant-Cycle Model, ACA can be implemented by steps:

1. Initiate parameters, set time $t=0$, loop count $N_c=0$, max loop count $N_{cmax}$, initial pheromone concentration $\tau_{ij}(t)=const$, $\delta\tau_{ij}(t)=0$.

2. Randomly select $m$ cities for all ants to start from.

3. Loop count $N_c=N_c+1$.

4. Tabu list index $k=0$.

5. $k=k+1$.

6. Calculate the probability of $p_{ij}^k(t)$, where $j\in{\{C-tabu_k\}}$. Select the next city with largest $p_{ij}^k(t)$, and add the city to the tabu list.

7. If $k < m$, i.e. ants have not finished traveling, then go to step 5, else go to step 8.

8. Update pheromone on the ways between each two cities.

9. If $N_c < N_{cmax}$, go to step 3, else, jump out of the loop and output the result.

The time complexity of TSP is $T(n)=O(N_C\cdot{n^2\cdot{m}})$.