Memetic Algorithm - Introduction

Introduction

The theory of “Universal Darwinism” was coined by Richard Dawkins in 1983 to provide a unifying framework governing the evolution of any complex system. In particular, “Universal Darwinism” suggests that evolution is not exclusive to biological systems; i.e., it is not confined to the narrow context of the genes, but applicable to any complex system that exhibit the principles of inheritance, variation and selection, thus fulfilling the traits of an evolving system. For example, the new science of memetics represents the mind-universe analog to genetics in culture evolution that stretches across the fields of biology, cognition, and psychology, which has attracted significant attention in the last decades. The term “meme” was also introduced and defined by Dawkins in 1976 as “the basic unit of cultural transmission, or imitation”, and in the Oxford English Dictionary as “an element of culture that may be considered to be passed on by non-genetic means”.

Inspired by both Darwinian principles of natural evolution and Dawkins’ notion of a meme, the term “Memetic Algorithm” (MA) was first introduced by Moscato in his technical report in 1989 where he viewed MA as being close to a form of population-based hybrid genetic algorithm (GA) coupled with an individual learning procedure capable of performing local refinements. The metaphorical parallels, on the one hand, to Darwinian evolution and, on the other hand, between memes and domain specific (local search) heuristics are captured within memetic algorithms thus rendering a methodology that balances well between generality and problem specificity. In a more diverse context, memetic algorithms are now used under various names including Hybrid Evolutionary Algorithms, Baldwinian Evolutionary Algorithms, Lamarckian Evolutionary Algorithms, Cultural Algorithms, or Genetic Local Search. In the context of complex optimization, many different instantiations of memetic algorithms have been reported across a wide range of application domains, in general, converging to high-quality solutions more efficiently than their conventional evolutionary counterparts.

In general, using the ideas of memetics within a computational framework is called "Memetic Computing" (MC). With MC, the traits of Universal Darwinism are more appropriately captured. Viewed in this perspective, MA is a more constrained notion of MC. More specifically, MA covers one area of MC, in particular dealing with areas of evolutionary algorithms that marry other deterministic refinement techniques for solving optimization problems. MC extends the notion of memes to cover conceptual entities of knowledge-enhanced procedures or representations.