Extended Virtual Loser Genetic Algorithm for the Dynamic Traveling Salesman Problem

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 replace 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 Salesman Problem and compared with different types of EAs. The statistical results based on the experiments show the efficiency, robustness and adaptability of the different versions of eVLGA.