# Rank-Based Ant System with Originality Reinforcement and Pheromone Smoothing
## 2 Ant Colony Optimization
### Ant Colony Optimization Algorithms
In MMAS only one ant is used to update the pheromone trails at each iteration. Consequently, the modified pheromone update rule is given by  
\[\tau_{i,j}=(1-\rho)\tau_{i,j}+\bigtriangleup\tau_{i,j}^{best} \tag{5}\]  
where only the arcs traversed by the best ant are reinforced with a pheromone quantity inversely proportional to the fitness of the best ant tour \(\bigtriangleup\tau_{i,j}^{best}=1/f(s_{best})\). Depending on the MMAS implementation, it can be considered the iteration-best (\(s_{ibi}\)) ant or the global-best ant (\(s_{gb}\)). Furthermore, MMAS imposes lower and upper limits \(\tau_{min}\) and \(\tau_{max}\) on all the pheromone values in order to avoid stagnation. Hence, at each iteration after the pheromone update process given by Equation (5) takes place, it is ensured that the pheromone values respects the limits, i.e., \(\tau_{min}<\tau_{i,j}<\tau_{max}\), \(\forall\tau_{i,j}\). Recommended values for the pheromone trail limits indicated by [11; 14] are \(\tau_{max}=1/(\rho f(s_{gb}))\) and \(\tau_{min}=\tau_{max}(1-\sqrt[w]{0.05})/(0.5n-1)\), where \(n\) is the number of cities (nodes) in the graph. These pheromone limits \([\tau_{min},\tau_{max}]\) avoid the situation of strict stagnation (all tours of an iteration being the same). Instead, this may lead to a situation (convergence of MMAS) where the pheromone values of the arcs corresponding to the best-found tour have associated a pheromone value equal to \(\tau_{max}\), and the remaining arcs to \(\tau_{min}\). In this convergence situation, all the ants do not follow the same tours (stagnation), but still, the exploration of the search space and the possibility of finding better solutions during the following iterations is quite limited. As a further means of increasing the exploration, some MMAS implementations consider occasional reinitializations of the pheromone trails when the algorithm approaches stagnation or when no improved tour has been generated for a large number of iterations [11]. **Ant Colony System (ACS)**, proposed by [PERSON] and [PERSON] [12], is considered, along with MMAS, the best performing variant of AS [14; 15; 16]. ACS implements several modifications with respect to AS. First, it exploits the experience accumulated by the ants more strongly than AS does through the use of a more aggressive action choice rule given by Equation (6):  
\[j= \begin{cases}argmax_{I\in\mathbb{N}_{i}^{k}}\tau_{ii}[v_{il}]^{\beta}&q\leq q _{0}\\ J&\text{otherwise}\end{cases}  \tag{6}\]  
where \(q\) is a random variable uniformly distributed in [0, 1], \(q_{0}\) is an algorithm parameter (\(0<q_{0}<1\)), and \(J\) is a random variable selected according to the probability distribution given by Equation (1) (with \(\alpha=1\)). In this way, the ants select with a probability \(q_{0}\) the next node \(j\) based on the best decision according to the pheromone trails and heuristic information (the node \(j\) with maximum associated probability \(p_{i,j}^{k}\) given by Equation (1)), while with probability \((1-q_{0})\), the ants choose the next node according to the probability distribution \(p_{i,j}^{k}\) given by Equation (1). Regarding the pheromone update process, at the end of each algorithm iteration, ACS only applies the pheromone evaporation and reinforcement to those arcs belonging to best-so-far ant, according to Equation (7):  
\[\tau_{i,j}=(1-\rho)\tau_{i,j}+\bigtriangleup\tau_{i,j}^{gb}\quad\forall arc(i, j)\in s_{gb} \tag{7}\]where \(\rho\) is the pheromone evaporation parameter and \(\triangle\tau_{i,j}^{gb}=1/f(s_{gb})\). In addition to the global pheromone trail update rule given by Equation (7), that is applied after the \(m\) ant tours are constructed, ACS also considers a local pheromone update rule that is applied immediately after an ant has crossed an \(arc(i,j)\) during the tour construction, according to Equation (8):  
\[\tau_{i,j}=(1-\xi)\tau_{i,j}+\xi\tau_{0} \tag{8}\]  
where \(\xi\) (\(0<\xi<1\)) and \(\tau_{0}\) are two algorithm parameters.