Memetic algorithms outperform evolutionary algorithms in multimodal optimisation

摘要

Memetic algorithms integrate local search into an evolutionary algorithm to combine the advantages of rapid exploitation and global optimisation. We provide a rigorous runtime analysis of memetic algorithms on the Hurdle problem, a landscape class of tunable difficulty with a “big valley structure”, a characteristic feature of many hard combinatorial optimisation problems. A parameter called hurdle width describes the length of fitness valleys that need to be overcome. We show that the expected runtime of plain evolutionary algorithms like the (1+1) EA increases steeply with the hurdle width, yielding superpolynomial times to find the optimum, whereas a simple memetic algorithm, (1+1) MA, only needs polynomial expected time. Surprisingly, while increasing the hurdle width makes the problem harder for evolutionary algorithms, it becomes easier for memetic algorithms.