Please use this identifier to cite or link to this item:
Title: A memetic ant colony optimization algorithm for the dynamic travelling salesman problem
Authors: Mavrovouniotis, M
Yang, S
Keywords: Memetic algorithm;Ant colony optimization;Dynamic optimization problem;Travelling salesman problem;Inver-over operator;Local search;Simple inversion;Adaptive inversion
Issue Date: 2011
Publisher: Springer Verlag
Citation: Soft Computing, 15(7): 1405 - 1425, Jul 2011
Abstract: Ant colony optimization (ACO) has been successfully applied for combinatorial optimization problems, e.g., the travelling salesman problem (TSP), under stationary environments. In this paper, we consider the dynamic TSP (DTSP), where cities are replaced by new ones during the execution of the algorithm. Under such environments, traditional ACO algorithms face a serious challenge: once they converge, they cannot adapt efficiently to environmental changes. To improve the performance of ACO on the DTSP, we investigate a hybridized ACO with local search (LS), called Memetic ACO (M-ACO) algorithm, which is based on the population-based ACO (P-ACO) framework and an adaptive inver-over operator, to solve the DTSP. Moreover, to address premature convergence, we introduce random immigrants to the population of M-ACO when identical ants are stored. The simulation experiments on a series of dynamic environments generated from a set of benchmark TSP instances show that LS is beneficial for ACO algorithms when applied on the DTSP, since it achieves better performance than other traditional ACO and P-ACO algorithms.
Description: Copyright @ Springer-Verlag 2010.
ISSN: 1433-7479
Appears in Collections:Publications
Computer Science
Dept of Computer Science Research Papers

Files in This Item:
File Description SizeFormat 
Fulltext.pdf466.53 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.