# Rank-Based Ant System with Originality Reinforcement and Pheromone Smoothing
###### Abstract  
Ant Colony Optimization (ACO) encompasses a family of metaheuristics inspired by the foraging behaviour of ants. Since the introduction of the first ACO algorithm, called Ant System (AS), several ACO variants have been proposed in the literature. Owing to their superior performance over other alternatives, the most popular ACO algorithms are Rank-based Ant System (AS\({}_{Rank}\)), Max-Min Ant System (MMAS) and Ant Colony System (ACS). While AS\({}_{Rank}\) shows a fast convergence to high-quality solutions, its performance is improved by other more widely used ACO variants such as MMAS and ACS, which are currently considered the state-of-the-art ACO algorithms for static combinatorial optimization problems. With the purpose of diversifying the search process and avoiding early convergence to a local optimal, the proposed approach extends AS\({}_{Rank}\) with an originality reinforcement strategy of the top-ranked solutions and a pheromone smoothing mechanism that is triggered before the algorithm reaches stagnation. The approach is tested on several symmetric and asymmetric Traveling Salesman Problem and Sequential Ordering Problem instances from TSPLIB benchmark. Our experimental results show that the proposed method achieves fast convergence to high-quality solutions and outperforms the current state-of-the-art ACO algorithms AS\({}_{Rank}\), MMAS and ACS, for most instances of the benchmark. ant colony optimization; metaheuristics; pheromone smoothing; originality reinforcement; combinatorial optimization +
Footnote †: journal:  
mention just a few. The interested reader is referred to the handbooks of metaheuristics in [5; 6; 7] and references within for a general overview of the field and its applications to hard optimization problems. One of the most popular metaheuristics is _Ant Colony Optimization_ (ACO). Rather than a single method, ACO consists of a family of metaheuristics inspired by the foraging activity of natural ants, capable of finding the shortest path between a food source and their nest through a pheromone deposit mechanism. ACO metaheuristics guide their search through the solution space of combinatorial optimization problems using a problem-specific heuristic and the information saved in the pheromone table, which is learned by means of the reinforcement of the pheromone values corresponding to the best decisions in previous iterations of the algorithm. The first ant colony-based algorithm, called Ant System (AS) [8; 9], was originally applied to solve the Traveling Salesman Problem (TSP): finding the shortest closed loop that traverses once a group of cities. Since the introduction of AS, several ACO algorithms have been proposed. Among them, three algorithms stand out owing to their superior performance and, as a result, for being the most often used ACO algorithms: the Rank-based Ant System (AS\({}_{Rank}\)) [10], Max-Min Ant System (MMAS) [11] and Ant Colony System (ACS) [12]. All ACO algorithms guide their search through the solution space by means of a probabilistic decision method that combines the information given by the heuristic and the pheromones. However, ACO algorithms may differ in the rules defined to update the pheromone trails or the different transition rules that combine the heuristic and pheromone information. Additionally, more recent metaheuristics combine ACO with other techniques, for instance, Best-Worst Ant System (BWAS) [13], integrates several components from Evolutionary Computation. Nevertheless, the ACO algorithms (MMAS and ACS) are by far more popular than hybrid methods and are used in a variety of combinatorial optimization problems [14; 15; 16]. The reinforcement of previous best decisions by means of pheromone deposit mechanism enables ACO algorithms to focus the search on promising regions of the search space, making it possible to find high-quality solutions for high-complexity problems in a reasonable computational time.