Extended Virtual Loser Genetic Algorithm for the Dynamic Traveling Salesman Problem

Authors

Abstract

The use of memory-based Evolutionary Algorithms (EAs) for dynamic optimization problems (DOPs) has proved to be efficient, namely when past environments reappear later. Memory EAs using associative approaches store the best solution and additional information about the environment. In this paper we propose a new algorithm called Extended Virtual Loser Genetic Algorithm (eVLGA) to deal with the Dynamic Traveling Salesman Problem (DTSP). In this algorithm, a matrix called extended Virtual Loser (eVL) is created and updated during the evolutionary process. This matrix contains information that reflects how much the worst individuals differ from the best, working as environmental information, which can be used to avoid past errors when new individuals are created. The matrix is stored into memory along with the current best individual of the population and, when a change is detected, this information is retrieved from memory and used to create new individuals that re- place the worst of the population. eVL is also used to create immigrants that are tested in eVLGA and in other standard algorithms. The performance of the investigated eVLGAs is tested in different instances of the Dynamic Traveling Sales- man Problem and compared with different types of EAs. The statistical results based on the experiments show the efficiency, robustness and adaptability of the different ver- sions of eVLGA.

Keywords

Evolutionary Algorithms, Dynamic Environments, Memory, Associative Memory, Virtual Loser, Dynamic Traveling Salesman problem, Permutations

Conference

Proceedings of the 2013 Genetic and Evolutionary Computation Conference (GECCO 2013), Christian Blum (Ed.), pp. 869-876, Amsterdam, The Netherlands, 06-10, ACM, New York, NY, USA, 2013. 2013