The theory of “Universal Darwinism” was coined by Richard Dawkins in 1983 to provide a unifying framework governing the evolution of any complex systems. 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 systems 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 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” was also introduced and defined by Dawkins 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 (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 is now used under various names including Hybrid Evolutionary Algorithm, Baldwinian Evolutionary Algorithm, Lamarckian Evolutionary Algorithms, Cultural Algorithm 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.
Aspects of memetics when dealt within a computational framework is termed as "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. Henceforth, the framework of MC extends the notion of memes to cover conceptual entities of knowledge-enhanced procedures or representations.
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.
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.
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.
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.
Memetic algorithms are the subject of intense scientific research (a scientific journal 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 problems. To cite some of them: graph partitioning, multidimensional knapsack, travelling salesman problem, quadratic assignment problem, set cover problem, minimal graph colouring, max independent set problem, bin packing problem and generalized assignment problem.
More recent applications include (but are not limited to): training of artificial neural networks, pattern recognition, robotic motion planning, beam orientation, circuit design, electric service restoration, medical expert systems, single machine scheduling, automatic timetabling (notably, the timetable for the NHL ), manpower scheduling , nurse rostering and function optimisation, processor allocation, maintenance scheduling (for example, of an electric distribution network), VLSI design and clustering of gene expression profiles.
Research from C.H. Hsu et al broadens understanding of innovative computing information and control.(Report)
Nov 03, 2008; According to a study from Changhua, Taiwan, "This study proposes an innovative method based on the memetic algorithm to determine...