Fast Re-Optimization of LeadingOnes with Frequent Changes

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)


In real-world optimization scenarios, the problem instance that we are asked to solve may change during the optimization process, e.g., when new information becomes available or when the environmental conditions change. In such situations, one could hope to achieve reasonable performance by continuing the search from the best solution found for the original problem. Likewise, one may hope that when solving several problem instances that are similar to each other, it can be beneficial to 'warm-start' the optimization process of the second instance by the best solution found for the first. However, it was shown in [Doerr et al., GECCO 2019] that even when initialized with structurally good solutions, evolutionary algorithms can have a tendency to replace these good solutions by structurally worse ones, resulting in optimization times that have no advantage over the same algorithms started from scratch. Doerr et al. also proposed a diversity mechanism to overcome this problem. Their approach balances greedy search around a best-so-far solution for the current problem with search in the neighborhood around the best-found solution for the previous instance. In this work, we first show that the re-optimization approach suggested by Doerr et al. reaches a limit when the problem instances are prone to more frequent changes. More precisely, we show that they get stuck on the dynamic LeadingOnes problem in which the target string changes periodically. We then propose a modification of their algorithm which interpolates between greedy search around the previous-best and the current-best solution. We empirically evaluate our smoothed re-optimization algorithm on LeadingOnes instances with various frequencies of change and with different perturbation factors and show that it outperforms both a fully restarted (1+1) Evolutionary Algorithm and the re-optimization approach by Doerr et al.

Original languageEnglish
Title of host publication2022 IEEE Congress on Evolutionary Computation, CEC 2022 - Conference Proceedings
PublisherIEEE Press
Number of pages8
ISBN (Electronic)9781665467087
Publication statusPublished - 06 Sept 2022
Externally publishedYes
Event2022 IEEE Congress on Evolutionary Computation, CEC 2022 - Padua, Italy
Duration: 18 Jul 202223 Jul 2022

Publication series

Name2022 IEEE Congress on Evolutionary Computation, CEC 2022 - Conference Proceedings


Conference2022 IEEE Congress on Evolutionary Computation, CEC 2022
Period18 Jul 202223 Jul 2022


Dive into the research topics of 'Fast Re-Optimization of LeadingOnes with Frequent Changes'. Together they form a unique fingerprint.

Cite this