Fast Re-Optimization of LeadingOnes with Frequent Changes

Allbwn ymchwil: Pennod mewn Llyfr/Adroddiad/Trafodion CynhadleddTrafodion Cynhadledd (Nid-Cyfnodolyn fathau)


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.

Iaith wreiddiolSaesneg
Teitl2022 IEEE Congress on Evolutionary Computation, CEC 2022 - Conference Proceedings
CyhoeddwrIEEE Press
Nifer y tudalennau8
ISBN (Electronig)9781665467087
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsCyhoeddwyd - 06 Medi 2022
Cyhoeddwyd yn allanolIe
Digwyddiad2022 IEEE Congress on Evolutionary Computation, CEC 2022 - Padua, Yr Eidal
Hyd: 18 Gorff 202223 Gorff 2022

Cyfres gyhoeddiadau

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


Cynhadledd2022 IEEE Congress on Evolutionary Computation, CEC 2022
Gwlad/TiriogaethYr Eidal
Cyfnod18 Gorff 202223 Gorff 2022

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'Fast Re-Optimization of LeadingOnes with Frequent Changes'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn