On the analysis of the (1+1) memetic algorithm
Loading...
Date
2007-06-04T16:11:37Z
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Memetic algorithms are evolutionary algorithms incorporating local search to increase exploitation. This hybridization has been fruitful
in countless applications. However, theory on memetic algorithms is
still in its infancy.
Here, we introduce a simple memetic algorithm, the (1+1) Memetic
Algorithm ((1+1) MA), working with a population size of 1 and no
crossover. We compare it with the well-known (1+1) EA and randomized local search and show that these three algorithms can outperform
each other drastically.
On problems like, e. g., long path problems it is essential to limit
the duration of local search. We investigate the (1+1) MA with a fixed
maximal local search duration and define a class of fitness functions
where a small variation of the local search duration has a large impact
on the performance of the (1+1) MA.
All results are proved rigorously without assumptions.