Advertisement
Published in:
2012 | OriginalPaper | Chapter
Ant Colony System with Selective Pheromone Memory for TSP
Author : Rafał Skinderowicz
Published in: Computational Collective Intelligence. Technologies and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Ant Colony System (ACS) is a well known metaheuristic algorithm for solving difficult optimization problems inspired by the foraging behaviour of social insects (ants). Artificial ants in the ACS cooperate indirectly through deposition of pheromone trails on the edges of the problem representation graph. All trails are stored in a pheromone memory, which in the case of the Travelling Salesman Problem (TSP) requires
O
(
n
2
) memory storage, where
n
is the size of the problem instance. In this work we propose a novel
selective pheromone memory model
for the ACS in which pheromone values are stored only for the selected
subset
of trails. Results of the experiments conducted on several TSP instances show that it is possible to significantly reduce ACS memory requirements (by a constant factor) without impairing the quality of the solutions obtained.