# Rank-Based Ant System with Originality Reinforcement and Pheromone Smoothing
## 3 Extension of Rank-Based Ant System
### Algorithm  
Once the originality utility function and the pheromone smoothing strategy have been introduced, below is described the proposed extension of Rank-based Ant System, which incorporates both strategies. Algorithm 2 shows the pseudocode of the algorithm and Figure 4 its general overflow. The algorithm requires similar parameters to AS\({}_{Rank}\): pheromone evaporation rate \(\rho\), the number of ants per iteration \(m\), the number of ants that deposit pheromones \(w\), and the pheromone and heuristic influence parameters \(\alpha\) and \(\beta\). The steps of the algorithm are the following. First, the algorithm starts with the initialization of the pheromone table to a constant value \(\tau_{0}\), and of the matrix \(\
u\) to zero (as \(\
u_{i,j}\) accounts for the number of ants that have traversed each edge \(arc(i,j)\) in the graph \(G\)). Within the main iteration loop, the tours of \(m\) ants are constructed component by component according to the ACO probabilistic transition rule given by Equation (1). Additionally, in line 7, the counter of ants \(\
u_{i,j}\) that have traversed \(arc(i,j)\) is updated. Once the \(m\) tours (\(s_{1:m}\)) have been constructed, they are ranked and selected according to their fitness and originality following the steps sketched in Figure 5 and explained as follows. First, all the tours are evaluated and the \((w-1)\) best are selected (line 11). Then, the \((w-1)\) best tours of the iteration are evaluated and ranked according to the originality utility function given by Equation (9), obtaining in this way a rank of the dissimilarity of the \((w-1)\) best tours with respect all the explored tours (line 13). Moreover, in the case that the best solution of the iteration is better than the global best solution, \(s_{gb}\) is updated (line 12). In line 14, the pheromone update process takes place according to Equation (11); all pheromone values are evaporated, and the \((w-1)\) best tours of the current iteration and the global best tour are reinforced. \[\tau_{i,j}=(1-\rho)\tau_{i,j}+\sum_{r_{o}=1}^{w-1}(w-r_{o})\bigtriangleup\tau _{i,j}^{r}+w\bigtriangleup\tau_{i,j}^{gb} \tag{11}\]  
The best-so-far tour gives the strongest feedback, as its contribution is multiplied by the weight equal to \(w\), the \((w-1)\) best ants of the iteration deposit a pheromone quantity multiplied by a weight \((w-r_{o})\), which is higher for the more original solutions (lower \(r_{o}\)). The update of the pheromones is similar to the original AS\({}_{Rank}\), with the exception that the ranking considered for the reinforcement is a ranking of originality, instead of fitness. In this way, the proposed algorithm rewards the originality of the tours with good fitness values. Figure 3: Pheromone trails before (on the **left**) and after (on the **right**) of pheromone smoothing. Figure 4: Algorithm flowchart of the proposed AS\({}_{ORank}^{\text{\tiny{IS}}}\) method. Figure 5: Steps of the process of selection and ranking of solutions for the pheromone reinforcement (where \(s_{k}^{i}\) represents a solution component of the tour of length \(l\) of the \(k\)-th ant).