Memetic algorithms represent one of the recent growing areas of research in evolutionary computation

Evolutionary computation

In computer science, evolutionary computation is a subfield of artificial intelligence that involves combinatorial optimization problems....

. The term MA is now widely used as a synergy of evolutionary or any population-based approach with separate individual learning or local improvement procedures for problem search. Quite often, MA are also referred to in the literature as Baldwinian Evolutionary algorithms (EA)

Evolutionary algorithm

In artificial intelligence, an evolutionary algorithm is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses some mechanisms inspired by biological evolution: reproduction, mutation, recombination, and selection...

, Lamarckian EAs, cultural algorithms or genetic local search.

Introduction

The theory of “Universal Darwinism

Universal darwinism

Universal Darwinism refers to a variety of approaches that extend the theory of Darwinism beyond its original domain of biological evolution on Earth...

” was coined by Richard Dawkins

Richard Dawkins

Clinton Richard Dawkins, FRS, FRSL , known as Richard Dawkins, is a British ethologist, evolutionary biologist and author...

 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 gene

Gene

A gene is a molecular unit of heredity of a living organism. It is a name given to some stretches of DNA and RNA that code for a type of protein or for an RNA chain that has a function in the organism. Living beings depend on genes, as they specify all proteins and functional RNA chains...

s, but applicable to any complex system that exhibit the principles of inheritance

Inheritance

Inheritance is the practice of passing on property, titles, debts, rights and obligations upon the death of an individual. It has long played an important role in human societies...

, variation

Variation

- Physics :* Magnetic variation, difference between magnetic north and true north, measured as an angle* Variation , any perturbation of the mean motion or orbit of a planet or satellite, particularly of the moon- Mathematics :* Bounded variation...

 and selection

Selection

In the context of evolution, certain traits or alleles of genes segregating within a population may be subject to selection. Under selection, individuals with advantageous or "adaptive" traits tend to be more successful than their peers reproductively—meaning they contribute more offspring to the...

, thus fulfilling the traits of an evolving
system. For example, the new science of memetics represents the mind-universe analogue 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

Meme

A meme is "an idea, behaviour or style that spreads from person to person within a culture."A meme acts as a unit for carrying cultural ideas, symbols or practices, which can be transmitted from one mind to another through writing, speech, gestures, rituals or other imitable phenomena...

” was also introduced and defined by Dawkins

Richard Dawkins

Clinton Richard Dawkins, FRS, FRSL , known as Richard Dawkins, is a British ethologist, evolutionary biologist and author...

 in 1976 as “the basic unit of cultural transmission, or imitation”, and in the English Oxford 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

Genetic algorithm

A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...

 (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.

1st generation

The first generation of MA refers to hybrid algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

s, a marriage between a population-based global search (often in the form of an evolutionary algorithm) coupled with a cultural evolutionary stage. This first generation of MA although encompasses characteristics of cultural evolution (in the form of local refinement) in the search cycle, it may not qualify as a true evolving system according to Universal Darwinism

Universal darwinism

Universal Darwinism refers to a variety of approaches that extend the theory of Darwinism beyond its original domain of biological evolution on Earth...

, since all the core principles of inheritance/memetic transmission, variation and selection are missing. This suggests why the term MA stirred up criticisms and controversies among researchers when first introduced.

Pseudo code:

Procedure Memetic Algorithm
Initialize: Generate an initial population;
while Stopping conditions are not satisfied do
Evaluate all individuals in the population.
Evolve a new population using stochastic search operators.
Select the subset of individuals, , that should undergo the individual improvement procedure.
for each individual in do
Perform individual learning using meme(s) with frequency or probability of , for a period of .
Proceed with Lamarckian or Baldwinian learning.
end for
end while
----

2nd generation

Multi-meme, Hyper-heuristic

Hyper-heuristic

A hyper-heuristic is a heuristic search method that seeks to automate, often by the incorporation of machine learning techniques, the process of selecting, combining, generating or adapting several simpler heuristics to efficiently solve computational search problems...

and Meta-Lamarckian MA are referred to as second generation MA exhibiting the principles of memetic transmission and selection in their design. In Multi-meme MA, the memetic material is encoded as part of the genotype

Genotype

The genotype is the genetic makeup of a cell, an organism, or an individual usually with reference to a specific character under consideration...

. Subsequently, the decoded meme of each respective individual / chromosome

Chromosome

A chromosome is an organized structure of DNA and protein found in cells. It is a single piece of coiled DNA containing many genes, regulatory elements and other nucleotide sequences. Chromosomes also contain DNA-bound proteins, which serve to package the DNA and control its functions.Chromosomes...

 is then used to perform a local refinement. The memetic material is then transmitted through a simple inheritance mechanism from parent to offspring(s). On the other hand, in hyper-heuristic and meta-Lamarckian MA, the pool
of candidate memes considered will compete, based on their past merits in generating local improvements through a reward mechanism, deciding on which meme to be selected to proceed for future local refinements. Memes with a higher reward have a greater chance of being replicated or copied. For a review on second generation MA, i.e., MA considering multiple individual learning methods within
an evolutionary system, the reader is referred to.

3rd generation

Co-evolution and self-generating MAs may be regarded as 3rd generation MA where all three principles satisfying the definitions of a basic evolving system have been considered. In contrast to 2nd generation MA which assumes that the memes to be used are known a priori, 3rd generation MA utilizes a rule-based local search to supplement candidate solutions within the evolutionary system, thus capturing regularly repeated features or patterns in the problem space.

Some design notes

The frequency and intensity of individual learning directly define the degree of evolution (exploration) against
individual learning (exploitation) in the MA search, for a given fixed limited computational budget. Clearly, a more intense
individual learning provides greater chance of convergence to the local optima but limits the amount of evolution that
may be expended without incurring excessive computational resources. Therefore, care should be taken when setting
these two parameters to balance the computational budget available in achieving maximum search performance. When only a portion of the population individuals undergo learning, the issue on which subset of individuals to improve need to be considered to maximize the utility of MA search. Last but not least, the individual learning procedure/meme used also favors a different neighborhood structure, hence the need to decide which meme or memes to use for a given optimization problem at hand would be required.

How often should individual learning be applied?

One of the first issues pertinent to memetic algorithm design is to consider how often the individual learning should be applied, i.e., individual learning frequency. In one case, the effect of individual learning frequency on MA search performance was considered where various configurations of the individual learning frequency at different stages of the MA search were investigated. Conversely, it was shown elsewhere that it may be worthwhile to apply individual learning on every individual if the computational complexity of the individual learning is relatively low.

On which solutions should individual learning be used?

On the issue of selecting appropriate individuals among the EA population that should undergo individual learning, fitness-based and distribution-based strategies were studied for adapting the probability of applying individual learning on the population of chromosomes in continuous parametric search problems with Land extending the work to combinatorial optimization problems. Bambha et al. introduced a simulated heating technique for systematically integrating parameterized individual learning into evolutionary algorithms to achieve maximum solution quality.

How long should individual learning be run?

Individual learning intensity, , is the amount of computational budget allocated to an iteration of individual learning, i.e., the maximum computational budget allowable for individual learning to expend on improving a single solution.

What individual learning method or meme should be used for a particular problem or individual?

In the context of continuous optimization, individual learning/individual learning exists in the form of local heuristics or conventional exact enumerative methods. Examples of individual learning strategies include the hill climbing, Simplex method, Newton/Quasi-Newton method, interior point methods, conjugate gradient method, line search and other local heuristics. Note that most of common individual learninger are deterministic.

In combinatorial optimization, on the other hand, individual learning methods commonly exists in the form of heuristics (which can be deterministic or stochastic), that are tailored to serve a problem of interest well. Typical heuristic procedures and schemes include the k-gene exchange, edge exchange, first-improvement, and many others.

Applications

Memetic algorithms are the subject of intense scientific research (a scientific journal

Scientific journal

In academic publishing, a scientific journal is a periodical publication intended to further the progress of science, usually by reporting new research. There are thousands of scientific journals in publication, and many more have been published at various points in the past...

 devoted to their research is going to be launched) and have been successfully applied to a multitude of real-world problems. Although many people employ techniques closely related to memetic algorithms, alternative names such as hybrid genetic algorithms are also employed. Furthermore, many people term their memetic techniques as genetic algorithms. The widespread use of this misnomer hampers the assessment of the total amount of applications.

Researchers have used memetic algorithms to tackle many classical NP

NP (complexity)

In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...

 problems. To cite some of them: graph partition

Graph partition

In mathematics, the graph partition problem is defined on data represented in the form of a graph G= , with V vertices and E edges, such that it is possible to partition G into smaller components with specific properties. For instance, a k-way partition divides the vertex set into k smaller...

ing, multidimensional knapsack

Knapsack problem

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the count of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as...

, travelling salesman problem

Travelling salesman problem

The travelling salesman problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once...

, quadratic assignment problem

Quadratic assignment problem

The quadratic assignment problem is one of fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems....

, set cover problem

Set cover problem

The set covering problem is a classical question in computer science and complexity theory.It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms...

, minimal graph colouring, max independent set problem, bin packing problem

Bin packing problem

In computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. In it, objects of different volumes must be packed into a finite number of bins of capacity V in a way that minimizes the number of bins used....

 and generalized assignment problem

Generalized assignment problem

In applied mathematics, the maximum generalized assignment problem is a problem in combinatorial optimization. This problem is a generalization of the assignment problem in which both tasks and agents have a size...

.

More recent applications include (but are not limited to): training of artificial neural network

Artificial neural network

An artificial neural network , usually called neural network , is a mathematical model or computational model that is inspired by the structure and/or functional aspects of biological neural networks. A neural network consists of an interconnected group of artificial neurons, and it processes...

s, pattern recognition

Pattern recognition

In machine learning, pattern recognition is the assignment of some sort of output value to a given input value , according to some specific algorithm. An example of pattern recognition is classification, which attempts to assign each input value to one of a given set of classes...

, robotic motion planning

Motion planning

Motion planning is a term used in robotics for the process of detailing a task into discrete motions....

, beam

Charged particle beam

A charged particle beam is a spatially localized group of electrically charged particles that have approximately the same velocity . The kinetic energies of the particles are typically measured in keV or MeV, much larger than the energies of particles at ambient temperature...

 orientation, circuit design

Circuit design

The process of circuit design can cover systems ranging from complex electronic systems all the way down to the individual transistors within an integrated circuit...

, electric service restoration, medical expert system

Expert system

In artificial intelligence, an expert system is a computer system that emulates the decision-making ability of a human expert. Expert systems are designed to solve complex problems by reasoning about knowledge, like an expert, and not by following the procedure of a developer as is the case in...

s, single machine scheduling

Single machine scheduling

Single-machine scheduling or single-resource scheduling is the process of assigning a group of tasks to a single machine or resource. The tasks are arranged so that one or many performance measures may be optimized.-Performance measures:...

, automatic timetabling (notably, the timetable for the NHL), manpower scheduling

Schedule (workplace)

A schedule, often called a rota, is a list of employees who are working on any given day, week, or month in a workplace. A schedule is necessary for the day-to-day operation of any retail store or manufacturing facility. The process of creating a schedule is called scheduling...

, nurse rostering and function optimisation, processor allocation, maintenance scheduling (for example, of an electric distribution network), multidimensional knapsack problem, VLSI design, clustering of gene expression profiles

Expression profiling

In the field of molecular biology, gene expression profiling is the measurement of the activity of thousands of genes at once, to create a global picture of cellular function. These profiles can, for example, distinguish between cells that are actively dividing, or show how the cells react to a...

, feature/gene selection, and multi-class, multi-objective feature selection

Feature selection

In machine learning and statistics, feature selection, also known as variable selection, feature reduction, attribute selection or variable subset selection, is the technique of selecting a subset of relevant features for building robust learning models...

.

Recent Activities in Memetic Algorithms

• IEEE Workshop on Memetic Algorithms (WOMA 2009). Program Chairs: Jim Smith, University of the West of England, U.K.; Yew-Soon Ong, Nanyang Technological University, Singapore; Gustafson Steven, University of Nottingham; U.K.; Meng Hiot Lim, Nanyang Technological University, Singapore; Natalio Krasnogor, University of Nottingham, U.K.
• Memetic Computing Journal, first issue appeared in January 2009.
• 2008 IEEE World Congress on Computational Intelligence (WCCI 2008), Hong Kong, Special Session on Memetic Algorithms.
• Special Issue on 'Emerging Trends in Soft Computing - Memetic Algorithm', Soft Computing Journal, Completed & In Press, 2008.
• IEEE Computational Intelligence Society Emergent Technologies Task Force on Memetic Computing
• IEEE Congress on Evolutionary Computation (CEC 2007), Singapore, Special Session on Memetic Algorithms.
• 'Memetic Computing' by Thomson Scientific's Essential Science Indicators as an Emerging Front Research Area.
• Special Issue on Memetic Algorithms, IEEE Transactions on Systems, Man and Cybernetics - Part B, Vol. 37, No. 1, February 2007.
• Recent Advances in Memetic Algorithms, Series: Studies in Fuzziness and Soft Computing , Vol. 166, ISBN 978-3-540-22904-9, 2005.
• Special Issue on Memetic Algorithms, Evolutionary Computation Fall 2004, Vol. 12, No. 3: v-vi.