Effective ACO-Based Memetic Algorithms for Symmetric and Asymmetric Dynamic Changes

Abstract

Ant colony optimization (ACO) algorithms have proved to be suitable for solving dynamic optimization problems (DOPs). The integration of local search operators with ACO has also proved to significantly improve the output of ACO algorithms. However, almost all previous works of ACO in DOPs do not utilize local search operators. In this work, the {mathcal M}{mathcal A}{mathcal X}-{mathcal M}{mathcal I}{mathcal N} Ant System ({mathcal M}{mathcal M}AS), one of the best ACO variations, is integrated with advanced and effective local search operators, i.e., the Lin-Kernighan and the Unstringing and Stringing heuristics, resulting in powerful memetic algorithms. The best solution constructed by ACO is passed to the operator for local search improvements. The proposed memetic algorithms aim to combine the adaptation capabilities of ACO for DOPs and the superior performance of the local search operators. The travelling salesperson problem is used as the base problem to generate both symmetric and asymmetric dynamic test cases. Experimental results show that the {mathcal M}{mathcal M}AS is able to provide good initial solutions to the local search operators especially in the asymmetric dynamic test cases.