Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

A memetic ant colony optimization algorithm for the dynamic travelling salesman problem

A memetic ant colony optimization algorithm for the dynamic travelling salesman problem 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Soft Computing Springer Journals

A memetic ant colony optimization algorithm for the dynamic travelling salesman problem

Soft Computing , Volume 15 (7) – Dec 29, 2010

Loading next page...
 
/lp/springer-journals/a-memetic-ant-colony-optimization-algorithm-for-the-dynamic-travelling-8vH8tS5M7e

References (71)

Publisher
Springer Journals
Copyright
Copyright © 2010 by Springer-Verlag
Subject
Engineering; Mathematical Logic and Foundations; Control, Robotics, Mechatronics; Artificial Intelligence (incl. Robotics); Computational Intelligence
ISSN
1432-7643
eISSN
1433-7479
DOI
10.1007/s00500-010-0680-1
Publisher site
See Article on Publisher Site

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.

Journal

Soft ComputingSpringer Journals

Published: Dec 29, 2010

There are no references for this article.