Large Population Sizes and Crossover Help in Dynamic Environments
This work addresses performance issues in evolutionary algorithms for dynamic optimization problems, providing incremental insights into algorithm design for specific theoretical scenarios.
The paper tackled the problem of optimizing dynamic linear functions, specifically Dynamic BinVal, by investigating the effects of larger population sizes and crossover in evolutionary algorithms. It found that moderately increased population sizes extend efficient configurations and crossover substantially boosts this effect, with the hardest optimization region differing between algorithms.
Dynamic linear functions on the hypercube are functions which assign to each bit a positive weight, but the weights change over time. Throughout optimization, these functions maintain the same global optimum, and never have defecting local optima. Nevertheless, it was recently shown [Lengler, Schaller, FOCI 2019] that the $(1+1)$-Evolutionary Algorithm needs exponential time to find or approximate the optimum for some algorithm configurations. In this paper, we study the effect of larger population sizes for Dynamic BinVal, the extremal form of dynamic linear functions. We find that moderately increased population sizes extend the range of efficient algorithm configurations, and that crossover boosts this positive effect substantially. Remarkably, similar to the static setting of monotone functions in [Lengler, Zou, FOGA 2019], the hardest region of optimization for $(μ+1)$-EA is not close the optimum, but far away from it. In contrast, for the $(μ+1)$-GA, the region around the optimum is the hardest region in all studied cases.