On the elusivity of dynamic optimisation problems.

Alza, Joan; Bartlett, Mark; Ceberio, Josu; McCall, John

Abstract

The field of dynamic optimisation continuously designs and compares algorithms with adaptation abilities that deal with changing problems during their search process. However, restarting the search algorithm after a detected change is sometimes a better option than adaptation, although it is generally ignored in empirical studies. In this paper, we suggest the elusivity formulation to (i) quantify the preference for restart over adaptation for algorithms running on dynamic problems, and (ii) evaluate the advantage and behaviour of adaptation. Informally, we state that a dynamic problem is elusive to an algorithm if restart is more effective than adapting to changes. After reviewing existing formalisms for dynamic optimisation, the elusivity concept is mathematically defined and applied to two published empirical studies to evaluate its utility. Conducted experiments show that replicated works include elusive problems, where restart is better than (or equal to) adaptation, and demonstrate that some empirical research effort is being devoted to evaluating adaptive algorithms in circumstances where there is no advantage. Hence, we recommend how and when elusivity analysis can be gainfully included in empirical studies in the field of dynamic optimisation.

Citation

ALZA, J., BARTLETT, M., CEBERIO, J. and MCCALL, J. 2023. On the elusivity of dynamic optimisation problems. Swarm and evolutionary computation [online], In Press, article 101289. Available from: https://doi.org/10.1016/j.swevo.2023.101289

• Journal Article Type: Article
• Acceptance Date: Mar 2, 2023
• Online Publication Date: Mar 17, 2023
• Deposit Date: Mar 17, 2023
• Publicly Available Date: Mar 18, 2024
• Journal: Swarm and Evolutionary Computation
• Print ISSN: 2210-6502
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Article Number: 101289
• DOI: https://doi.org/10.1016/j.swevo.2023.101289
• Keywords: Dynamic optimization problem; Elusivity; Adaptative advantage; Online solving; Restart
• Public URL: https://rgu-repository.worktribe.com/output/1913445