The Ant Heuristic 'Reloaded'

As a swarm-based optimization heuristic, the Ant System (AS) was proposed to deal with the Traveling Salesman Problem (TSP). Classifified as a constructive approach, AS was inspired by the ants’ social behavior.In Practice, its implementation reveals three basic variants that exploit two operating models: a fifirst “natural” model, where ants move and update pheromones, with consideration of distances between towns, to defifine the Ant-Quantity variant, and without considering distances for the Ant-Density variant. Or an “abnormal” second model, where ants move and delay updates until all ants have completed a full cycle, then consider the tour length which defifines the Ant-Cycle that was claimed to be the best variant. We reload the AS and reconsider these three basic ant algorithms and their respective two models. We propose to explore an “overlooked” third model, which consists of further expanding the “abnormal” ants’ attitude, forcing them to move and update pheromones, simultaneously, after every single move, thus conceiving the Ant-Step model. Keeping the option whether or not to consider distances, we propose two new AS basic algorithms: the Ant-Step-Quantity and the Ant-Step-Density. The aim of this paper is to present and assess these two new basic AS variants in respect to the three existing ones, specially the one considered the best, through an experimental study on various symmetric TSP benchmarks.