Population Control meets Doob's Martingale Theorems: the Noise-free Multimodal Case
This work addresses optimization challenges in multimodal domains for researchers and practitioners, offering an incremental improvement over existing methods by enhancing escape from local minima.
The paper tackles the problem of optimizing multimodal functions in noise-free settings by combining a test-based population size adaptation method with a naive recommendation strategy, demonstrating experimentally and proving theoretically that it can escape plateaus with probability one while avoiding random restarts.
We study a test-based population size adaptation (TBPSA) method, inspired from population control, in the noise-free multimodal case. In the noisy setting, TBPSA usually recommends, at the end of the run, the center of the Gaussian as an approximation of the optimum. We show that combined with a more naive recommendation, namely recommending the visited point which had the best fitness value so far, TBPSA is also powerful in the noise-free multimodal context. We demonstrate this experimentally and explore this mechanism theoretically: we prove that TBPSA is able to escape plateaus with probability one in spite of the fact that it can converge to local minima. This leads to an algorithm effective in the multimodal setting without resorting to a random restart from scratch.