Dynamic evolutionary optimisation: an analysis of frequency and magnitude of change

In this paper, we rigorously analyse how the magnitude and frequency of change may affect the performance of the algorithm (1+1) EA_dyn on a set of artificially designed pseudo-Boolean functions, given a simple but well-defined dynamic framework. We demonstrate some counter-intuitive scenarios that allow us to gain a better understanding of how the dynamics of a function may affect the runtime of an algorithm. In particular, we present the function Magnitude, where the time it takes for the (1+1) EA_dyn to relocate the global optimum is less than n²log n (i.e., efficient) with overwhelming probability if the magnitude of change is large. For small changes of magnitude, on the other hand, the expected time to relocate the global optimum is e^Ω(n) (i.e., highly inefficient). Similarly, the expected runtime of the (1+1) EA_dyn on the function Balance is O(n²) (efficient) for a high frequencies of change and n^Ω(√n) (highly inefficient) for low frequencies of change. These results contribute towards a better understanding of dynamic optimisation problems in general and show how traditional analytical methods may be applied in the dynamic case.