# Rank-Based Ant System with Originality Reinforcement and Pheromone Smoothing
## 3 Extension of Rank-Based Ant System
### Pheromone Smoothing Mechanism  
This section presents a pheromone smoothing strategy to escape from the stagnation situation. For a better understanding of the stagnation situation, visual representations of the pheromone trails obtained with AS\({}_{Rank}\) when solving a TSP instance with 14 cities after 0, 5, 10 and 200 iterations are shown in Figure 2. Note that the pheromone matrix is a square matrix of dimension \(n\times n\), where \(n\) is the number of nodes (cities) and in this TSP example, \(n=14\). Each element of the pheromone matrix \(\tau_{i,j}\) contains the pheromone quantity associated with the edge that goes from node \(i\) to node \(j\). For the representations, the pheromone levels are translated into gray scale, where black and white represent the highest and the lowest pheromone trail values, respectively. At the beginning of the algorithm, all the pheromone values are initialized with the same pheromone value \(\tau_{0}\), with the exception of the values of the diagonal representing no movement (i.e., \(i=j\)), which are not allowed in TSP (and thus are represented in white in Figure 2). After each AS\({}_{Rank}\) iteration, all the pheromone trails are evaporated and some pheromone trails are reinforced (the ones included in the best tours of the iteration and the best-found tour). The effect of this pheromone update can be observed in the pheromone representations of Figure 2. Additionally, the symmetry along the main diagonal of the pheromone matrix is due to the fact that the example is a symmetric TSP instance. As the difference among the pheromone values increases, ants are more likely to choose those arcs that were chosen by the best ants from previous iterations. This pheromone reinforcement enables AS\({}_{Rank}\) to explore promising regions of the search space obtaining high-quality solutions in a reasonable time. Yet, this usually leads AS\({}_{Rank}\) into early stagnation situations, in which all ants follow the same path. Stagnation can be clearly observed in the pheromone trails after 100 iterations shown in Figure 2 (right-bottom). In this case, the pheromone encodes a unique path (only fourteen of all the possible elements of half of the pheromone matrix have a non-negligible pheromone quantity). For this simple TSP instance with only fourteen cities, the encoded path in the pheromone table happens to be the optimal one. However, this is not usually the case and often AS\({}_{Rank}\) is trapped into a local minimum. The proposed pheromone smoothing mechanism, given by Equation (10), rescales the pheromone trails to the range \([\gamma\tau_{0},\tau_{0}]\), \(0<\gamma<1\). Note that if \(\gamma\) equals 1, all the pheromomes will be reinitialized to the constant value \(\tau_{0}\), and previously learned information would be lost. \[\tau=\gamma\tau_{0}+\frac{\tau-min(\tau)}{max(\tau)-min(\tau)}(1-\gamma)\tau_{0} \tag{10}\]  
Figure 3 shows an example of the resulting pheromone trails of \(AS_{rank}\) before and after applying the pheromone smoothing strategy. The image on the left of Figure 3 shows the pheromone trails when the algorithm is near a stagnation situation. The noticeable difference among the pheromone values can be observed, leading to the construction of very similar ant tours and thus a limited exploration of the search space. The image on the right of Figure 3 shows the pheromone trails after applying the pheromone smoothing strategy, where the pheromomes are rescaled \([0.1\tau_{0},\tau_{0}]\) with \(\tau_{0}=m/f(s_{sb})\)[14]. It can be observed that after applying the pheromone smoothing mechanism, the learned information is still preserved, but the differences among the pheromone trails \(\tau_{i,j}\) have decreased. In this way, the diversity of the ant tours produced by the algorithm after the pheromone smoothing  
mechanism is increased, allowing the algorithm to escape from stagnation without losing previously learned information.