Memetic algorithm

Pablo Moscato characterized an MA as follows: "Memetic algorithms are a marriage between a population-based global search and the heuristic local search made by each of the individuals. ... The mechanisms to do local search can be to reach a local optimum or to improve (regarding the objective cost function) up to a predetermined level." And he emphasizes "I am not constraining an MA to a genetic representation.".[9] This original definition 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, 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.[2] The following pseudo code would correspond to this general definition of an MA:

Pseudo code

   Procedure Memetic Algorithm
   Initialize: Generate an initial population, evaluate the individuals and assign a quality value to them;
   while Stopping conditions are not satisfied do
       Evolve a new population using stochastic search operators.
       Evaluate all individuals in the population and assign a quality value to them.
       Select the subset of individuals, ${\displaystyle \Omega _{il}}$, that should undergo the individual improvement procedure.
       for each individual in ${\displaystyle \Omega _{il}}$ do
           Perform individual learning using meme(s) with frequency or probability of ${\displaystyle f_{il}}$, with an intensity of ${\displaystyle t_{il}}$.
           Proceed with Lamarckian or Baldwinian learning.
       end for
   end while

Lamarckian learning in this context means to update the chromosome according to the improved solution found by the individual learning step, while Baldwinian learning leaves the chromosome unchanged and uses only the improved fitness. This pseudo code leaves open which steps are based on the fitness of the individuals and which are not. In question are the evolving of the new population and the selection of ${\displaystyle \Omega _{il}}$.

Since most MA implementations are based on EAs, the pseudo code of a corresponding representative of the first generation is also given here, following Krasnogor:[10]

Pseudo code

   Procedure Memetic Algorithm Based on an EA
   Initialization: ${\displaystyle t=0}$;  // Initialization of the generation counter
                   Randomly generate an initial population ${\displaystyle P(t)}$;
                   Compute the fitness ${\displaystyle f(p)\ \ \forall p\in P(t)}$;
   while Stopping conditions are not satisfied do
       Selection:  Accordingly to ${\displaystyle f(p)}$ choose a subset of ${\displaystyle P(t)}$ and store it in ${\displaystyle M(t)}$;
       Offspring: Recombine and mutate individuals ${\displaystyle p\in M(t)}$ and store them in ${\displaystyle M'(t)}$;
       Learning: Improve ${\displaystyle p'}$ by local search or heuristic ${\displaystyle \forall p'\in M'(t)}$;
       Evaluation: Compute the fitness ${\displaystyle f(p')\ \ \forall p'\in M'(t)}$;
       if Lamarckian learning then
          Update chromosome of ${\displaystyle p'}$ according to improvement ${\displaystyle \forall p'\in M'(t)}$;
       fi
       New generation: Generate ${\displaystyle P(t+1)}$ by selecting some individuals from ${\displaystyle P(t)}$ and ${\displaystyle M'(t)}$;
       ${\displaystyle t=t+1}$;  // Increment the generation counter
   end while
   Return best individual ${\displaystyle p\in P(t-1)}$ as result;

There are some alternatives for this MA scheme. For example:

• All or some of the initial individuals may be improved by the meme(s).
• The parents may be locally improved instead of the offspring.
• Instead of all offspring, only a randomly selected or fitness-dependent fraction may undergo local improvement. The latter requires the evaluation of the offspring in ${\displaystyle M'(t)}$ prior to the Learning step.

Multi-meme,[11] hyper-heuristic[12][13] and meta-Lamarckian MA[14][15] 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. Subsequently, the decoded meme of each respective individual/chromosome 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 continuing to be used. For a review on second generation MA; i.e., MA considering multiple individual learning methods within an evolutionary system, the reader is referred to.[16]

Co-evolution[17] and self-generating MAs[18] 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.

In the context of continuous optimization, individual learning exists in the form of local heuristics or conventional exact enumerative methods.[21] 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 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.

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,[19] 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[22] that it may be worthwhile to apply individual learning on every individual if the computational complexity of the individual learning is relatively low.

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[23] 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.[24]

Individual learning intensity, ${\displaystyle t_{il}}$, 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.

It is to be decided whether a found improvement is to work only by the better fitness (Baldwinian learning) or whether also the individual is adapted accordingly (lamarckian learning). In the case of an EA, this would mean an adjustment of the genotype. This question has been controversially discussed for EAs in the literature already in the 1990s, stating that the specific use case plays a major role.[25][26][27] The background of the debate is that genome adaptation may promote premature convergence. This risk can be effectively mitigated by other measures to better balance breadth and depth searches, such as the use of structured populations.[28]