On the role of modularity in evolutionary dynamic optimisation

The field of evolutionary dynamic optimisation is concerned with the application of evolutionary algorithms to dynamic optimisation problems. In recent years, numerous new algorithms have been proposed to track the problem's potentially moving global optimum as closely as possible. A large proportion of these techniques attempts to exploit possible similarities between successive problem instances, primarily using previously found solutions as starting points for future instances: If the previous global optimum is in close proximity to the new global optimum (in the genotype space), such transfer of knowledge should allow the algorithm to locate the new global optimum in less time than a random restart may require. However, it is clear that distance alone may be insufficient to guarantee such computational savings. In this paper, we propose a simple framework that may be used to create bi-modular problems with a variable degree of epistasis. We subsequently study how the dependencies between the two modules may affect the difficulty (number of function evaluation required) of relocating the new global optimum. We find that, given a simple (1+1) EA, even a modest degree of linkage between the problem's otherwise independent modules may have a significant impact on these attributes. © 2010 IEEE.