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

作     者：Mavrovouniotis, Michalis Yang, Shengxiang 

作者机构：Univ Leicester Dept Comp Sci Leicester LE1 7RH Leics England Brunel Univ Dept Informat Syst & Comp Uxbridge UB8 3PH Middx England 

出 版 物：《SOFT COMPUTING》 (Soft Comput.)

年 卷 期：2011年第15卷第7期

页      面：1405-1425页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Engineering and Physical Sciences Research Council (EPSRC) of UK [EP/E060722/01, EP/E060722/02] EPSRC [EP/E060722/1] Funding Source: UKRI 

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

摘      要：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.