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

Date

2011

Advisors

Journal Title

Journal ISSN

ISSN

1432-7643

Volume Title

Publisher

Springer-Verlag

Type

Article

Peer reviewed

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

Keywords

Memetic algorithm, Ant colony optimization, Dynamic optimization problem, Travelling salesman problem, Inver-over operator, Local search, Simple inversion, Adaptive inversion

Citation

Mavrovouniotis, M. and Yang, S. (2011) A memetic ant colony optimization algorithm for the dynamic travelling salesman problem. Soft Computing, 15 (7), July 2011, pp. 1405-1425.

Rights

Research Institute

Institute of Artificial Intelligence (IAI)