Intelligent Optimization Strategies in Uncertain and Dynamic Environments

In this paper, we rigorously analyse how the magnitude and frequency of change may affect the performance of the algorithm (1+1) EAdyn 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) EAdyn to relocate the global optimum is less than n2 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) EAdyn on the function BALANCE is O(n2) (efficient) for 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.