# Rank-Based Ant System with Originality Reinforcement and Pheromone Smoothing
## 2 Ant Colony Optimization
### Ant Colony Optimization Algorithms  
ACO metaheuristics formulate the combinatorial optimization problems as finding the best ant tour (best solution) in a graph \(G=(C,L)\) defined by a set of nodes \(C\) and arcs \(L\). For instance, in the TSP problem, each node represents a city and each edge has assigned the distance between each pair of cities. Hence, the problem is formulated as finding the closed tour of minimal length that visit once all the nodes in the graph. ACO metaheuristics are population-based algorithms that at each iteration construct \(m\) ant tours (solutions) combining the information learned in previous iterations with a problem-specific heuristic. In order to save the information of previous good ant tours, ACO algorithms use a table that assigns a pheromone value \(\tau_{i,j}\) to each edge in the graph. These pheromone values are typically initialized with a constant value for all edges, and later reinforced as the ants with better fitness traverse them. The ant tours are constructed component by component according to the probabilities determined by the transition rule, given by Equation (1). This transition rule states the probability \(p_{i,j}^{k}\) that the \(k\)-th ant moves from node \(i\) to node \(j\), assigning higher probabilities to the edges with higher pheromone \(\tau_{i,j}\) and heuristic values \(\eta_{i,j}\) according to:  
\[p_{i,j}^{k}=\frac{\tau_{i,j}^{\alpha}\,\eta_{i,j}^{\beta}}{\sum_{l\in N_{i}^{ k}}\tau_{i,j}^{\alpha}\,\eta_{i,j}^{\beta}},\quad j\in N_{i}^{k} \tag{1}\]  
where \(\alpha\) and \(\beta\) are the parameters that control the pheromone and heuristic influence, respectively, and \(N_{i}^{k}\) is the feasible neighbourhood of ant \(k\). For instance, in the case of TSP where the cities (nodes) can only be visited once, \(N_{i}^{k}\) corresponds to the set of unvisited cities. The basic operation mode of an ACO algorithm, summarized in Algorithm 1, is as follows: at every algorithm iteration, the \(m\) artificial ants start their tours from initial nodes (randomly chosen in TSP) and construct their tours by combining the information of the heuristic \(\eta\) and the pheromones \(\tau\). In this way, at every iteration, \(m\) candidate solutions (ant tours) are constructed, each one having a corresponding fitness value such as the length of the tour in TSP. Optionally, after the tours of the \(m\) ants are completed, a local search procedure may be considered (for example \(k\)-exchange neighbourhood for TSP). Next, a positive feedback strategy that rewards the best ant tours is implemented by means of the update of the pheromone table. Finally, when the considered stop criterion is met, the algorithm returns the best-found tour. Once every ant has finished its tour (which corresponds to a candidate solution to the optimization problem), the pheromone update (evaporation and deposit processes) takes place. In AS, the pheromone update process is given by the following rule:  
\[\tau_{i,j}=(1-\rho)\tau_{i,j}+\sum_{k=1}^{m}\triangle\tau_{i,j}^{k}\quad, \quad\forall arc(i,j)\in L \tag{2}\]  
where the parameter \(\rho\) (with \(0<\rho<1\)) is the pheromone evaporation parameter, which controls the rate at which the pheromone is evaporated. The evaporation mechanism affects all the edges in the graph and helps to avoid the unlimited accumulation of the pheromone trails. The second term of Equation (2) corresponds to the pheromone deposit of theartificial ants. In AS, all the ants deposit a pheromone quantity \(\bigtriangleup\tau^{k}_{i,j}\) proportional to their quality in all the arcs belonging to their tour:  
\[\bigtriangleup\tau^{k}_{i,j}=\left\{ \begin{array}{ll}1/f(s_{k}),&\text{if }\text{arc}(i,j)\in s_{k}\\ 0&\text{otherwise}\end{array} \right. \tag{3}\]  
where \(f(s_{k})\) is the fitness of the \(k\)-th ant tour \(s_{k}\), which in TSP corresponds to the length of the tour.