# Rank-Based Ant System with Originality Reinforcement and Pheromone Smoothing
## 2 Ant Colony Optimization
### Ant Colony Optimization Algorithms
In general, arcs that are used by many ants and which are contained in shorter tours will receive higher pheromone deposits and therefore, will more likely be chosen in the next iterations of ACO. ```
ACO parameters \(\tau\leftarrow\) initialise pheromone trails while termination condition not met do for\(k=1\) to \(m\)do\(\triangleright\) for every ant for every step until the \(k\)-th ant has completed the tour do  select node \(j\) to visit next according to transition rule \(\triangleright\) Equation (1) endfor endfor Apply local search (optional)  Update pheromone trails \(\tau\) endwhile
```  
**Algorithm 1** ACO metaheuristic  
Since the introduction of AS in [8], several ACO algorithms have been proposed, with Rank-based Ant System (AS\({}_{Rank}\)) [10], Max-Min Ant System (MMAS) [11] and Ant Colony System (ACS) [12] standing out. These ACO algorithms differ from AS in the pheromone update process in Equation (3), with the exception of ACS, which also considers a modified transition rule given by Equation (6) from the one given by Equation (1). The pheromone reinforcement enables ACO algorithms to focus the search on promising regions of the search space allowing them to find high-quality solutions in reasonable computational time. However, the pheromone reinforcement is also responsible for stagnation, an undesirable situation where no better tour is likely to be found anymore. The stagnation situation happens when at each choice point, the pheromone trail is significantly higher for one choice than for all the others. In such a situation, the ants construct the same tours over and over again and the exploration of the search space stops, limiting the possibility of finding a tour with better fitness. One particularity of AS extensions is that they direct the ant's search in a more aggressive way and that their search is focused on a specific region of the search space [14]. This higher exploitation may, however, induce early stagnation situations. Thus, AS extensions need to be endowed with features intended to counteract stagnation (e.g., the pheromone limits in MMAS and local update rule in ACS). The pheromone update process of the AS extensions, Rank-based AS, MMAS and ACS, are detailed below. **Rank-based Ant System (AS\({}_{Rank}\))** is an extension of AS proposed by [PERSON] et al. [10], which incorporates the idea of ranking to the pheromone update process. Rank-based AS follows a similar procedure to Algorithm 1, but its pheromone update incorporates the idea of ranking of solutions and elitist strategy. While in AS, all ants deposit pheromones according to Equation (2), in Rank-based AS, only \(w\) ants deposit pheromones: the best tour found so far, \(s_{gb}\), deposits a pheromone quantity proportional to the algorithm parameter \(w\) and the \((w-1)\) best ants of the iteration deposit a pheromone quantity proportional to their ranking \(r\), as expressed by Equation (4):  
\[\tau_{i,j}=(1-\rho)\tau_{i,j}+\sum_{r=1}^{w-1}(w-r)\bigtriangleup\tau^{r}_{i,j }+w\bigtriangleup\tau^{gb}_{i,j} \tag{4}\]where \(w\) is a parameter of the algorithm chosen by the user that determines the number of ants that deposit pheromones, and \(r\) corresponds to the ranking of the classification of the ants according to their fitness (where better fitness is associated with lower ranking). In Equation (4), \((1-\rho)\tau_{i,j}\) accounts for the pheromone evaporation, which is applied to all pheromone trails. Additionally, the pheromone trails corresponding to the tours of the \((w-1)\) best ants of the iteration are reinforced as by a quantity equal to \((w-r)\bigtriangleup\tau_{i,j}^{r}\), where \(\bigtriangleup\tau_{i,j}^{r}=1/f(s_{r})\). Finally, the pheromone trails corresponding to the global-best found solution \(s_{gb}\) are reinforced with a quantity equal to \(w\bigtriangleup\tau_{i,j}^{gb}\), where \(\bigtriangleup\tau_{i,j}^{gb}=1/f(s_{gb})\). **Max-Min Ant System (MMAS)**, proposed by [PERSON] and [PERSON] [11], is one of the best performing variants of AS [14; 15; 16].