Memetic algorithm

Memetic algorithm

The memetic algorithm is inspired by the interaction of genetic evolution and cultural evolution. Universal Darwinism is the generalization of genes beyond biological systems to any system where discrete units of information can be inherited and subjected to evolutionary forces of selection and variation. The term "meme" of the algorithm memetic is used to refer to discrete cultural information, suggesting the interplay between genetic and cultural evolution.

The genotype evolves according to the interaction of the phenotype with the environment. This interaction is measured by cultural phenomena which influence the selection mechanisms, and even the pairing and recombination mechanisms. Cultural information is shared among individuals, spreading across the population in the form of memes relating to their fitness or the fitness that memes confer on individuals. Collectively, the interaction of genotype and memotype enhances the fitness of the population in the environment.

The goal of the information processing strategy is to exploit a population-based global search technique to broadly locate good areas of the search space, combined with the repeated use of a heuristic of local search by individual solutions to locate the local optimum. Ideally, the memetic algorithm embraces the duality of genetic and cultural evolution, allowing transmission, selection, inheritance, and variation of memes as well as genes.

memetic algorithm

The above procedure describes a simple or first-order memetic algorithm that shows the improvement of individual solutions distinct from a global search, but does not show the independent evolution of memes.

Global search provides the broad exploration mechanism, while improving the individual solution through local search provides an exploitation mechanism. A balance is needed between local and global mechanisms to ensure that the system does not prematurely converge to a local optimum and does not consume unnecessary computing resources. Local search should be specific to the problem and representation, while global search can be generic and non-specific (black box). Memetic algorithms have been applied to a range of constraint optimization, combinatorial and continuous problem areas.