Diversity Allocation for Dynamic Optimization using the Extended Compact Genetic Algorithm

Abstract

This paper investigates the issues of maintaining diversity in the Extended Compact Genetic Algorithm (ECGA) for handling Dynamic Optimization Problems (DOPs). Specifically, we focused on how a diversity maintenance mechanism places samples in the search space, and derive an approach that is more appropriate for DOPs that change progressively. The discussion proceeds in two parts. First, we reaffirm the perspective that the problem structure should be considered when maintaining diversity for addressing DOPs. This point is demonstrated by an additively decomposable DOP in which each subfunction has two complementary optima. Following that, we further discuss how we can better allocate the samples for DOPs that change progressively by thinking about the current promising region, which should contain the current optima, and its neighborhood. Based on this notion, we devise a mechanism that utilizes the information provided by the probabilistic models from ECGA and uses a trade-off between exploration and exploitation to achieve the desired diversity allocation. The empirical results show that our approach follows the changing optima better compared to techniques that use Restricted Tournament Replacement (RTR). Furthermore, it requires only half of the function evaluations needed by approaches that use RTR.