A critique of the memetic algorithm

A pseudo-code representation of the algorithm (or one of its variants) is as follows:

1. Start with an initial population
2. Evaluate fitness
3. For each individual do local search for improvement, update fitness
4. Selection of individuals for crossover.
5. Generate new population by genetic operations.
6. repeat step 2

Comparing this with the original genetic algorithm, we see that the only difference is step 3, where a local search is conducted. If we imagine the search landscape as hilly with many local maxima, the local search would most likely find the local optima, and the normal genetic crossover would find new solutions. It is sometimes said that memetic algorithms are hybrid genetic algorithms, combining a population based global search with individual local search.

Computational results indicate a vast improvement relative to genetic algorithms.

Critique of the memetic algorithm.

It is when we look at a memetic algorithm as a kind of model of how memes work, that we find that it doesn’t reflect the idea of memes very well.

Some of the reasons are:

1. MA still works with genes as the sole replicator, memes do not appear in the algorithm at all

2. There is no mechanism how memes are copied from individual to individual, nor how memes are modified and combined to meme plexes

3. There is no global meme pool existing across generations of populations.

4. It is not clear how memes affect the fitness of individuals.

The global meme pool is almost like the pheromones in the ant colony algorithm, except that they can undergo memetic operations and survive generations.

Granted that these points are valid, it remains to be seen whether a “true” memetic algorithm can be devised, which mimics memes better and yet is an improvement of MA in terms of performance. A cursory consideration tells us that such an algorithm will be much more complex than MA, since it would have 2 kinds of replicators, and 2 sets of genetic and memetic operations. Whereas the genes are practically linear in nature, memes have nonlinear structure.

It is probable that the memes in such an algorithm will be domain specific, memes for problem A can be quite different from memes for problem B.

Reference:

P. Moscato, On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms, Caltech Concurrent Computation Program, C3P Report 826, (1989).


Memetic Algorithms' Home Page