A memetic algorithm (MA) in
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
and
operations research
Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve deci ...
, is an extension of the traditional
genetic algorithm
In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to gene ...
. It may provide a sufficiently good solution to an
optimization problem
In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions.
Optimization problems can be divided into two categories, depending on whether the variables ...
. It uses a
local search technique to reduce the likelihood of
premature convergence.
Memetic algorithms represent one of the recent growing areas of research in
evolutionary computation
In computer science, evolutionary computation is a family of algorithms for global optimization inspired by biological evolution, and the subfield of artificial intelligence and soft computing studying these algorithms. In technical terms, they ...
. 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, MAs are also referred to in the literature as Baldwinian
evolutionary algorithm
In computational intelligence (CI), an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses mechanisms inspired by biological evolution, such as reproduc ...
s (EAs), Lamarckian EAs, cultural algorithms, or genetic local search.
Introduction
Inspired by both Darwinian principles of natural evolution and
Dawkins' notion of a
meme
A meme ( ) is an idea, behavior, or style that spreads by means of imitation from person to person within a culture and often carries symbolic meaning representing a particular phenomenon or theme. A meme acts as a unit for carrying cultural i ...
, the term ''memetic algorithm'' (MA) was introduced by
Pablo Moscato in his technical report
in 1989 where he viewed MA as being close to a form of population-based hybrid
genetic algorithm
In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to gene ...
(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)
heuristic
A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate, ...
s are captured within memetic algorithms thus rendering a methodology that balances well between generality and problem specificity. This two-stage nature makes them a special case of
dual-phase evolution.
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'' or ''memetic computation'' (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.
The development of MAs
1st generation
The first generation of MA refers to hybrid
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
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, also known as generalized Darwinism, universal selection theory, or Darwinian metaphysics, is a variety of approaches that extend the theory of Darwinism beyond its original domain of biological evolution on Earth. Universal ...
, 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.
, that should undergo the individual improvement procedure.
''Perform'' individual learning using meme(s) ,
''Proceed'' with Lamarckian or Baldwinian learning.
end for
end while
]
2nd generation
Multi-meme, hyper-heuristic 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
The genotype of an organism is its complete set of genetic material. Genotype can also be used to refer to the alleles or variants an individual carries in a particular gene or genetic location. The number of alleles an individual can have in a ...
. Subsequently, the decoded meme of each respective individual/chromosome
A chromosome is a long DNA molecule with part or all of the genetic material of an organism. In most chromosomes the very long thin DNA fibers are coated with packaging proteins; in eukaryotic cells the most important of these proteins are ...
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 of 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
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...
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 exists in the form of local heuristics or conventional exact enumerative methods. Examples of individual learning strategies include the hill climbing
numerical analysis, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution ...
, Simplex method, Newton/Quasi-Newton method, interior point method
Interior-point methods (also referred to as barrier methods or IPMs) are a certain class of algorithms that solve linear and nonlinear convex optimization problems.
An interior point method was discovered by Soviet mathematician I. I. Dikin in 1 ...
s, conjugate gradient method
In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is positive-definite. The conjugate gradient method is often implemented as an iterativ ...
, line search, and other local heuristics. Note that most of the common individual learning methods are deterministic.
In combinatorial optimization, on the other hand, individual learning methods commonly exist in the form of heuristics (which can be deterministic or stochastic) that are tailored to a specific problem of interest. Typical heuristic procedures and schemes include the k-gene exchange, edge exchange, first-improvement, and many others.
Applications
Memetic algorithms 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''.
Researchers have used memetic algorithms to tackle many classical NP problems. To cite some of them: graph partition
In mathematics, a graph partition is the reduction of a graph to a smaller graph by partitioning its set of nodes into mutually exclusive groups. Edges of the original graph that cross between the groups will produce edges in the partitioned graph ...
ing, multidimensional knapsack, travelling salesman problem
The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...
, quadratic assignment problem
The quadratic assignment problem (QAP) is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems first introduced by Ko ...
, set cover problem
The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972.
Given a set of elements (called the univ ...
, minimal graph coloring, max independent set problem, bin packing problem
The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has ma ...
, and generalized assignment problem.
More recent applications include (but are not limited to) business analytics
Business analytics (BA) refers to the skills, technologies, and practices for continuous iterative exploration and investigation of past business performance to gain insight and drive business planning. Business analytics focuses on developing ne ...
and data science
Data science is an interdisciplinary field that uses scientific methods, processes, algorithms and systems to extract or extrapolate knowledge and insights from noisy, structured and unstructured data, and apply knowledge from data across a br ...
,[ ] training of artificial neural network
Artificial neural networks (ANNs), usually simply called neural networks (NNs) or neural nets, are computing systems inspired by the biological neural networks that constitute animal brains.
An ANN is based on a collection of connected unit ...
s, pattern recognition
Pattern recognition is the automated recognition of patterns and regularities in data. It has applications in statistical data analysis, signal processing, image analysis, information retrieval, bioinformatics, data compression, computer graphi ...
, robotic motion planning
Motion planning, also path planning (also known as the navigation problem or the piano mover's problem) is a computational problem to find a sequence of valid configurations that moves the object from the source to destination. The term is used ...
, beam
Beam may refer to:
Streams of particles or energy
*Light beam, or beam of light, a directional projection of light energy
**Laser beam
*Particle beam, a stream of charged or neutral particles
**Charged particle beam, a spatially localized grou ...
orientation, circuit design
The process of circuit design can cover systems ranging from complex electronic systems down to the individual transistors within an integrated circuit. One person can often do the design process without needing a planned or structured design ...
, electric service restoration, medical expert system
In artificial intelligence, an expert system is a computer system emulating the decision-making ability of a human expert.
Expert systems are designed to solve complex problems by reasoning through bodies of knowledge, represented mainly as if†...
s, single machine scheduling, automatic timetabling (notably, the timetable for the NHL
The National Hockey League (NHL; french: Ligue nationale de hockey—LNH, ) is a professional ice hockey league in North America comprising 32 teams—25 in the United States and 7 in Canada. It is considered to be the top ranked professional ...
), manpower scheduling, nurse rostering optimisation, processor allocation, maintenance scheduling (for example, of an electric distribution network), multidimensional knapsack problem, VLSI
Very large-scale integration (VLSI) is the process of creating an integrated circuit (IC) by combining millions or billions of MOS transistors onto a single chip. VLSI began in the 1970s when MOS integrated circuit (Metal Oxide Semiconductor) c ...
design, clustering of gene expression profiles, feature/gene selection, parameter determination for hardware fault injection, and multi-class, multi-objective feature selection
In machine learning and statistics, feature selection, also known as variable selection, attribute selection or variable subset selection, is the process of selecting a subset of relevant features (variables, predictors) for use in model construc ...
.
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
Soft Computing Journal, Completed & In Press, 2008.
* ttps://web.archive.org/web/20100306001555/http://cec2007.nus.edu.sg/ IEEE Congress on Evolutionary Computation (CEC 2007) Singapore
Special Session on Memetic Algorithms
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: Cybernetics, Vol. 37, No. 1, February 2007.
Series: Studies in Fuzziness and Soft Computing, Vol. 166, , 2005.
Special Issue on Memetic Algorithms
Evolutionary Computation Fall 2004, Vol. 12, No. 3: v-vi.
References
{{reflist, 30em
Evolutionary algorithms