We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
The Ant Heuristic "Reloaded".
- Authors
Zeghida, Djamel; Bounour, Nora; Khelifi, Sarra
- Abstract
As a swarm-based optimization heuristic, the Ant System (AS) was proposed to deal with the Traveling Salesman Problem (TSP). Classified 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 first "natural" model, where ants move and update pheromones, with consideration of distances between towns, to define 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 defines 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.
- Subjects
ANT algorithms; TRAVELING salesman problem; ANTS; HEURISTIC
- Publication
Statistics, Optimization & Information Computing, 2022, Vol 10, Issue 1, p282
- ISSN
2311-004X
- Publication type
Article
- DOI
10.19139/soic-2310-5070-1218