On the elusivity of dynamic optimisation problems

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.