Open AccessAn Early Exploratory Method to Avoid Local Minima in Ant Colony System
Author(s) -
Thanet Satukitchai,
Kietikul Jearanaitanakij
Publication year - 1970
Publication title -
ecti transactions on computer and information technology
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.132
H-Index - 2
ISSN - 2286-9131
DOI - 10.37936/ecti-cit.2016101.56397
Subject(s) - local optimum , ant colony optimization algorithms , travelling salesman problem , mathematical optimization , maxima and minima , computer science , ant colony , extremal optimization , local search (optimization) , path (computing) , scheduling (production processes) , metaheuristic , combinatorial optimization , mathematics , meta optimization , mathematical analysis , programming language
Ant Colony Optimization (ACO) is a famous technique for solving the Travelling Salesman Problem (TSP.) The first implementation of ACO is Ant System. Itcan be used to solve different combinatorial optimization problems, e.g., TSP, job-shop scheduling, quadratic assignment. However, one of its disadvantages is that it can be easily trapped into local optima. Although there is an attempt by Ant Colony System (ACS) to improve the local optima by introducing local pheromone updating rule, the chance of being trapped into local optima still persists. This paper presents an extension of ACS algorithm by modifying the construction solution phase of the algorithm, the phase that ants move and build their tours, to reduce the duplication of tours produced by ants. This modification forces ants to select unique path which has never been visited by other ants in the current iteration. As a result, the modified ACS can explore more search space than the conventional ACS. The experimental results on five standard benchmarks from TSPLIB show improvements on both the quality and the number of optimal solutions founded.