Workshop Theory of Randomized Search Heuristics

(colocated with ICALP 2007)


On the Parametrization of Memetic Evolutionary Algorithms

by Dirk Sudholt

Memetic evolutionary algorithms are powerful randomized search heuristics integrating local search into the random search process of evolutionary algorithms. This hybridization has proven its usefulness in countless applications covering a wide area of practical problems. However, the design of memetic algorithms suffers from the burden of parametrization as computational resources have to be spread adequately among local and evolutionary search. In order to design powerful memetic algorithms, one has to care about when to apply local search, to which individuals in the population, and how much computational effort to devote to local search.

We address the first and the third question and investigate a generic memetic algorithm defined for the optimization of pseudo-Boolean functions. Following common design guidelines, local search is called with a fixed frequency and local search is allowed to run for a fixed number of iterations, the so-called local search depth. We argue that the choice of both the local search frequency and the local search depth can be crucial for the success of the algorithm and present example functions where the algorithm is very sensitive to even small changes of the parametrization.
More precisely, changing the local search depth by a small additive term can decide between polynomial versus exponential optimization times with high probability. On another class of functions altering the local search frequency by a factor of 2 can have the same effect. Both results are two-sided: increasing a parameter can either be beneficial or desastrous in the above-mentioned way.

Back to mainpage