Improving memory-based evolutionary algorithms for dynamic environments

Abstract

Evolutionary Algorithms (EAs) are powerful tools for optimization problems. The success of applying EAs to solve hard problems involving static environments is clear and well recognized. Nevertheless, many real-world problems have characteristics and conditions that can change over time. The EAs dealing with this type of problem can face di±culties due to the convergence of the population toward a speci¯c region of the search space. When the environment changes it is hard for this converged population to quickly readapt to the new conditions. Di®erent improvements have been made to the standard EA to make it more robust in dynamic problems: the increase of diversity, the incorporation of memory, the use of multi-populations or the inclusion of anticipation methods. The use of memory is advantageous when the underlying dynamics of the environment follows a certain pattern. Typically, memory-based approaches react to the change after it has happened and use the memory to help the EA readapt to the new conditions. Also, the memory size is established o®-line and kept constant, and is usually a small fraction of the global number of individuals. When the capacity of the memory is attained, a replacing strategy must be used to choose which individual should be deleted to insert a new one. In this thesis we introduce important and novel contributions, to address some of the drawbacks of current approaches, thus enhancing memory-based EAs for coping with dynamic environments. First, we propose di®erent approaches to make memory more useful and e®ective: di®erent replacing strategies are proposed, which maximize the capacity and the diversity of the memorized solutions. We also study the infuence of the choice of the memory size and propose an innovative algorithm that allows the memory size to evolve to a suitable capacity, according to the moment and characteristics of the dynamic problem. Second, we propose two different biologically inspired genetic operators, which promote different degrees of diversity of the population. We study the effect that different levels of diversity have in the performance of the algorithms. We are interested in analyzing if in memory-based EAs the promotion of high diversity is always necessary and advantageous. Third, we introduce different prediction techniques that allow the EA to forecast both the time of the next change and the direction of this change. Using this information we can anticipate the change and effectively prepare the EA before that change occurs, highly increasing the EA's performance and adaptability. All the mentioned approaches are tested using different benchmark problems, working under different types of dynamics. The results obtained from an exhaustive experimentation are statistically analyzed, and they prove the effectiveness of the proposed contributions.