When and What Kind of Memetic Algorithms Perform Well

Abstract

The synergy between exploration and exploitation has been a prominent issue in optimization. The rise of memetic algorithms, a category of optimization techniques which feature the explicit exploration-exploitation coordination, much accentuates this issue. While memetic algorithms have achieved remarkable success in a wide range of real-world applications, the key to a successful exploration-exploitation synergy still remains obscure. Manifold empirical results and theoretical derivations have been proposed and provided various perspectives from different algorithm-problem complexes to this issue. In our previous work, the concept of local search zones was proposed to provide an alternative perspective depicting the general behavior of memetic algorithms on a broad range of problems. In this work, based on the local search zone concept, we further investigate how the problem landscape and the way the algorithm explores and exploits the search space affect the performance of a memetic algorithm. The collaborative behavior of several representative archetypes of memetic algorithms, which exhibit different degrees of explorability and exploitability, are illustrated empirically and analytically on problems with different landscapes. As the empirical results consist with the local search zone concept and describe the behavior of various memetic algorithms on different problems, this work may reveal some essential design principals for memetic algorithms.