Coevolving Memetic Algorithms: A Review and Progress Report
---
paper_title: The co-evolution of memetic algorithms for protein structure prediction

paper_content:

This paper describes a co-evolutionary learning-optimisation approach to Protein Structure Prediction which uses a Memetic Algorithm as its underlying search method. Instance-specific knowledge can be learned, stored and applied by the system in the form of a population of rules. These rules determine the neighbourhoods used by the local search process, which is applied to each member of the co-evolving population of candidate solutions.
---
paper_title: A tutorial for competent memetic algorithms: model, taxonomy, and design issues

paper_content:

The combination of evolutionary algorithms with local search was named "memetic algorithms" (MAs) (Moscato, 1989). These methods are inspired by models of natural systems that combine the evolutionary adaptation of a population with individual learning within the lifetimes of its members. Additionally, MAs are inspired by Richard Dawkin's concept of a meme, which represents a unit of cultural evolution that can exhibit local refinement (Dawkins, 1976). In the case of MA's, "memes" refer to the strategies (e.g., local refinement, perturbation, or constructive methods, etc.) that are employed to improve individuals. In this paper, we review some works on the application of MAs to well-known combinatorial optimization problems, and place them in a framework defined by a general syntactic model. This model provides us with a classification scheme based on a computable index D, which facilitates algorithmic comparisons and suggests areas for future research. Also, by having an abstract model for this class of metaheuristics, it is possible to explore their design space and better understand their behavior from a theoretical standpoint. We illustrate the theoretical and practical relevance of this model and taxonomy for MAs in the context of a discussion of important design issues that must be addressed to produce effective and efficient MAs.
---
paper_title: Co-evolving memetic algorithms: a learning approach to robust scalable optimisation

paper_content:

This paper presents and examines the behaviour of a system whereby the rules governing local search within a memetic algorithm are co-evolved alongside the problem representation. We describe the rationale for such a system, and then describe the implementation of a simple version in which the evolving rules are encoded as (condition:action) patterns applied to problem representation. We investigate the behaviour of the algorithm on a suite of test problems, and show considerable performance improvements over a simple genetic algorithm, a memetic algorithm using a fixed neighbourhood function, and a similar memetic algorithm which uses random rules, i.e. with the learning mechanisms disabled. Analysis of these results enables us to draw some conclusions about the way that even the simplified system is able to discover and exploit certain forms of structure and regularities if these exist within the problem space. We show that this "meta-learning" of problem features provides a means of creating highly scalable algorithms for some types of problems. We further demonstrate that in the absence of this kind of exploitable patterns, the use of continually evolving neighbourhood functions for the local search operators adds robustness to the memetic algorithm in a manner similar to variable neighbourhood search. Finally we draw some initial conclusions about the way in which this meta-learning takes place, via examination of the use of different pivot rules and pairing strategies between the population of solution and the population of rules.
---
paper_title: Self Generating Metaheuristics in Bioinformatics: The Proteins Structure Comparison Case

paper_content:

In this paper we describe the application of a so called "Self-Generating" Memetic Algorithm to the Maximum Contact Map Overlap problem (MAX-CMO). The maximum overlap of contact maps is emerging as a leading modeling technique to obtain structural alignment among pairs of protein structures. Identifying structural alignments (and hence similarity among proteins) is essential to the correct assessment of the relation between proteins structure and function. A robust methodology for structural comparison could have impact on the process of rational drug design. ::: ::: The Self-Generating Memetic Algorithm we present in this work evolves concurrently both the solutions (i.e. proteins alignments) and the local search move operators that it needs to solve the problem instance at hand. The concurrent generation of local search strategies and solutions allows the Memetic Algorithm to produce better results than those given by a Genetic Algorithm and a Memetic Algorithm with human-designed local searchers. The approach has been tried in four different data sets (1 data set composed of randomly generated proteins and the other 3 data sets with real world proteins) with encouraging results.
---
paper_title: A Hyperheuristic Approach to Scheduling a Sales Summit

paper_content:

The concept of a hyperheuristic is introduced as an approach that operates at a higher lever of abstraction than current metaheuristic approaches. The hyperheuristic manages the choice of which lower-level heuristic method should be applied at any given time, depending upon the characteristics of the region of the solution space currently under exploration. We analyse the behaviour of several different hyperheuristic approaches for a real-world personnel scheduling problem. Results obtained show the effectiveness of our approach for this problem and suggest wider applicability of hyperheuristic approaches to other problems of scheduling and combinatorial optimisation.
---
paper_title: Operator and parameter adaptation in genetic algorithms

paper_content:

Genetic Algorithms are a class of powerful, robust search techniques based on genetic inheritance and the Darwinian metaphor of “Natural Selection”. These algorithms maintain a finite memory of individual points on the search landscape known as the “population”. Members of the population are usually represented as strings written over some fixed alphabet, each of which has a scalar value attached to it reflecting its quality or “fitness”. The search may be seen as the iterative application of a number of operators, such as selection, recombination and mutation, to the population with the aim of producing progressively fitter individuals.
---
paper_title: Classification of adaptive memetic algorithms: a comparative study

paper_content:

Adaptation of parameters and operators represents one of the recent most important and promising areas of research in evolutionary computations; it is a form of designing self-configuring algorithms that acclimatize to suit the problem in hand. Here, our interests are on a recent breed of hybrid evolutionary algorithms typically known as adaptive memetic algorithms (MAs). One unique feature of adaptive MAs is the choice of local search methods or memes and recent studies have shown that this choice significantly affects the performances of problem searches. In this paper, we present a classification of memes adaptation in adaptive MAs on the basis of the mechanism used and the level of historical knowledge on the memes employed. Then the asymptotic convergence properties of the adaptive MAs considered are analyzed according to the classification. Subsequently, empirical studies on representatives of adaptive MAs for different type-level meme adaptations using continuous benchmark problems indicate that global-level adaptive MAs exhibit better search performances. Finally we conclude with some promising research directions in the area.
---
paper_title: An Introduction to Variable Neighborhood Search

paper_content:

In this paper we examine a relatively unexplored approach to the design of heuristics, the guided change of neighborhood in the search process. Using systematically this idea and very little more, i.e., only a local search routine, leads to a new metaheuristic, which is widely applicable. We call this approach Variable Neighborhood Search (VNS).
---
paper_title: A Study on the use of ``self-generation'' in memetic algorithms

paper_content:

A vast number of very successful applications of Global-Local Search Hybrids have been reported in the literature in the last years for a wide range of problem domains. The majority of these papers report the combination of highly specialized pre-existing local searchers and usually purpose-specific global operators (e.g. genetic operators in an Evolutionary Algorithm). In this paper we concentrate on one particular class of Global-Local Search Hybrids, Memetic Algorithms (MAs), and we describe the implementation of ``self-generating'' mechanisms to produce the local searches the MA uses. This implementation is tested in two problems, NK-Landscape Problems and the Maximum Contact Map Overlap Problem (MAX-CMO).
---
paper_title: Parameter control in evolutionary algorithms

paper_content:

The issue of controlling values of various parameters of an evolutionary algorithm is one of the most important and promising areas of research in evolutionary computation: it has a potential of adjusting the algorithm to the problem while solving the problem. In the paper we: 1) revise the terminology, which is unclear and confusing, thereby providing a classification of such control mechanisms, and 2) survey various forms of control which have been studied by the evolutionary computation community in recent years. Our classification covers the major forms of parameter control in evolutionary computation and suggests some directions for further research.
---
paper_title: A Tabu-search Hyperheuristic for Timetabling and Rostering

paper_content:

Hyperheuristics can be defined to be heuristics which choose between heuristics in order to solve a given optimisation problem. The main motivation behind the development of such approaches is the goal of developing automated scheduling methods which are not restricted to one problem. In this paper we report the investigation of a hyperheuristic approach and evaluate it on various instances of two distinct timetabling and rostering problems. In the framework of our hyperheuristic approach, heuristics compete using rules based on the principles of reinforcement learning. A tabu list of heuristics is also maintained which prevents certain heuristics from being chosen at certain times during the search. We demonstrate that this tabu-search hyperheuristic is an easily re-usable method which can produce solutions of at least acceptable quality across a variety of problems and instances. In effect the proposed method is capable of producing solutions that are competitive with those obtained using state-of-the-art problem-specific techniques for the problems studied here, but is fundamentally more general than those techniques.
---
paper_title: Meta-Lamarckian learning in memetic algorithms

paper_content:

Over the last decade, memetic algorithms (MAs) have relied on the use of a variety of different methods as the local improvement procedure. Some recent studies on the choice of local search method employed have shown that this choice significantly affects the efficiency of problem searches. Given the restricted theoretical knowledge available in this area and the limited progress made on mitigating the effects of incorrect local search method choice, we present strategies for MA control that decide, at runtime, which local method is chosen to locally improve the next chromosome. The use of multiple local methods during a MA search in the spirit of Lamarckian learning is here termed Meta-Lamarckian learning. Two adaptive strategies for Meta-Lamarckian learning are proposed in this paper. Experimental studies with Meta-Lamarckian learning strategies on continuous parametric benchmark problems are also presented. Further, the best strategy proposed is applied to a real-world aerodynamic wing design problem and encouraging results are obtained. It is shown that the proposed approaches aid designers working on complex engineering problems by reducing the probability of employing inappropriate local search methods in a MA, while at the same time, yielding robust and improved design search performance.
---
paper_title: Genetic Programming using Genotype-Phenotype Mapping from Linear Genomes into Linear Phenotypes

paper_content:

In common genetic programming approaches, the space of genotypes, that is the search space, is identical to the space of phenotypes, that is the solution space. Facts and theories from molecular biology suggest the introduction of non-identical genospaces and phenospaces, and a generic genotype-phenotype mapping which maps unconstrained genotypes into syntactically correct phenotypes. Neutral variants come into effect due to this mapping. They enhance genetic diversity and allow for escaping local optima in phenospace via high-dimensional saddle surfaces in genospace. We propose a concrete mapping that maps linear binary genotypes into linear phenotypes of an arbitrary context-free programming language. Empirical results are presented which show that the mapping improves the performance of GP under mutation and reproduction.
---
paper_title: Adaptively Parameterised Evolutionary Systems: Self Adaptive Recombination and Mutation in a Genetic Algorithm

paper_content:

It has long been recognised that the choice of recombination and mutation operators and the rates at which they are applied to a Genetic Algorithm will have a significant effect on the outcome of the evolutionary search, with sub-optimal values often leading to poor performance. In this paper an evolutionary algorithm (APES) is presented within which both the units of heredity and the probability that those units will subject to mutation are learnt via self adaptation of the genetic material. Using Kaufmann's NK model, this algorithm is compared to a number of combinations of frequently used crossover operators with “standard” mutation rates. The results demonstrate competitive times to find maxima on simple problems, and (on the most complex problems) results which are significantly better than the majority of other algorithms tested. This algorithm represents a robust adaptive search method which is not dependant on expert knowledge of genetic algorithm theory or practice in order to perform effectively.
---
paper_title: ORIGINS OF ORDER IN EVOLUTION: SELF-ORGANIZATION AND SELECTION

paper_content:

This article is written as a prolegomena, both to a research program, and a forthcoming book discussing the same issues in greater detail (Kauffman, 1991). The suspicion that evolutionary theory needs broadening is widespread. To accomplish this, however, will not be easy. The new framework I shall discuss here grows out of the realization that complex systems of many kinds exhibit high spontaneous order. This implies that such order is available to evolution and selective forces for further molding. But it also implies, quite profoundly, that the spontaneous order in such systems may enable, guide and limit selection. Therefore, the spontaneous order in complex systems implies that selection may not be the sole source of order in organisms, and that we must invent a new theory of evolution which encompasses the marriage of selection and self-organization.
---
paper_title: Evolving Teamwork and Coordination with Genetic Programming

paper_content:

Some problems can be solved only by multiagent teams. In using genetic programming to produce such teams, one faces several design decisions. First, there are questions of team diversity and of breeding strategy. In one commonly used scheme, teams consist of clones of single individuals; these individuals breed in the normal way and are cloned to form teams during fitness evaluation. In contrast, teams could also consist of distinct individuals. In this case one can either allow free interbreeding between members of different teams, or one can restrict interbreeding in various ways. A second design decision concerns the types of coordination-facilitating mechanisms provided to individual team members; these range from sensors of various sorts to complex communication systems. This paper examines three breeding strategies (clones, free, and restricted) and three coordination mechanisms (none, deictic sensing, and name-based sensing) for evolving teams of agents in the Serengeti world, a simple predator/prey environment. Among the conclusions are the fact that a simple form of restricted interbreeding outperforms free interbreeding in all teams with distinct individuals, and the fact that name-based sensing consistently outperforms deictic sensing.
---
paper_title: Toward Machine Learning Through Genetic Code-like Transformations

paper_content:

The gene expression process in nature involves several representation transformations of the genome. Translation is one among them; it constructs the amino acid sequence in proteins from the nucleic acid-based mRNA sequence. Translation is defined by a code book, known as the universal genetic code. This paper explores the role of genetic code and similar representation transformations for enhancing the performance of inductive machine learning algorithms. It considers an abstract model of genetic code-like transformations (GCTs) introduced elsewhere [21] and develops the notion of randomized GCTs. It shows that randomized GCTs can construct a representation of the learning problem where the mean-square-error surface is almost convex quadratic and therefore easier to minimize. It considers the functionally complete Fourier representation of Boolean functions to analyze this effect of such representation transformations. It offers experimental results to substantiate this claim. It shows that a linear classifier like the Perceptron [38] can learn non-linear XOR and DNF functions using a gradient-descent algorithm in a representation constructed by randomized GCTs. The paper also discusses the immediate challenges that must be solved before the proposed technique can be used as a viable approach for representation construction in machine learning.
---
paper_title: Self adaptation of mutation rates in a steady state genetic algorithm

paper_content:

This paper investigates the use of genetically encoded mutation rates within a "steady state" genetic algorithm in order to provide a self-adapting mutation mechanism for incremental evolution. One of the outcomes of this work will be a reduction in the number of parameters required to be set by the operator, thus facilitating the transfer of evolutionary computing techniques into an industrial setting. The NK family of landscapes is used to provide a variety of different problems with known statistical features in order to examine the effects of changing various parameters on the performance of the search. A number of policies are considered for the replacement of members of the population with newly created individuals and recombination of material between parents, and a number of methods of encoding for mutation rate are investigated. Empirical comparisons (using the "best-of current-population" metric) over a range of test problems show that a genetic algorithm incorporating the best "flavour" of the adaptive mutation operator outperformed the same algorithm when using any one of a variety of "standard" fixed mutation rates suggested by other authors.
---
paper_title: Evolving artificial intelligence

paper_content:

The majority of research in artificial intelligence has been devoted to modeling the symptoms of intelligent behavior as we observe them in ourselves. Investigation into the causative factors of intelligence have been passed over in order to more rapidly obtain the immediate consequences of intelligence. The results of these efforts have been computer programs that achieve outstanding performance, but only in very limited domains of application. ::: It is suggested that attention be given to the mechanisms that generate intelligence. Intelligence may be defined as that property which enables a system to adapt its behavior to meet desired goals in a range of environments. Three organizational forms of intelligence are characterized within the present discussion: (1) phylogenetic (arising within the phyletic line of descent), (2) ontogenetic (arising within the individual), and (3) sociogenetic (arising within the group). It is argued that all three forms of intelligence are equivalent in process and that all intelligent systems are inherently evolutionary in nature. ::: Simulating natural evolution provides a method for machine generated intelligent behavior. A series of experiments is conducted to quantify the efficiency and effectiveness of evolutionary problem solving. The results indicate that this "evolutionary programming" can rapidly discover nearly optimum solutions to a broad range of problems. Mathematical analysis of the algorithm and its variations indicates that the process will converge to the global best available solution. Automatic control and gaming experiments are conducted in which an evolutionary program must discover suitable strategies for solving the task at hand. No credit assignment or other heuristic evaluations are offered to the evolutionary programs. The results indicate the utility of using simulated evolution for general problem solving.
---
paper_title: Varying sample sizes for the co-evolution of heterogeneous agents

paper_content:

The evolution of a heterogeneous team is a complex problem. Evolving teams if a single population can retard the GA's ability to specialize emergent behavior, but co-evolution requires a system for evaluation at trial time. If two few combinations of partners are tested, the GA is unable to recognize fit agents; if too many agents are tested, the resultant computation time becomes excessive. We created a system based on punctuated anytime learning that only periodically tests samples of partner combinations to reduce computation time and tested a variety of sample sizes. In this paper, we present a successful method of varying the sample sizes, dependent on the level of fitness, using a box pushing task for comparison.
---
paper_title: Adaptive Global Optimization with Local Search

paper_content:

This dissertation examines the performance of genetic algorithm (GA) hybrids that use local search to solve global optimization problems. GAs are a class of adaptive global sampling methods that take many cues from mechanisms observed in natural evolution. GAs maintain a population of solutions that are used to generate new solutions in the search space. GA hybrids using local search (GA-LS hybrids) are motivated by the apparent need to employ both a global and local search strategy to provide an effective global optimization method. Previous experimental results have found that GA-LS hybrids not only find better solutions than the GA, but also optimize more efficiently. ::: To improve the efficiency of GA-LS hybrids, I propose and experimentally validate methods that selectively apply local search to solutions in the GA's population. First, local search is randomly applied with a fixed frequency. Experiments with this method illustrate a trade-off between the refinement performed by local search and the reliability of the competitive search performed by the GA. Next, I describe two classes of adaptive methods. Distribution-based adaptive methods use redundancy in the population to avoid performing unnecessary local searches. Fitness-based adaptive methods use the fitness information in the population to bias the local search towards individuals that have better fitness. An experimental analysis indicates that these adaptive methods can significantly improve the efficiency of GA-LS hybrids. ::: This dissertation explores implications of these results for parallel GAs. In particular, a MIMD design for geographically structured genetic algorithms (GSGAs) is described. GSGAs were initially developed for SIMD architectures, where it is difficult to selectively apply local search. An analytic and experimental analysis of MIMD GSGAs demonstrates that they scale well for large problems. ::: GA-LS hybrids are used to solve global optimization problems in several application domains. First, GA-LS hybrids are used to find the weights of a neural network to solve the six-bit symmetry problem. Next, they are used to solve a simple 19 atom molecular conformation problem. Finally, they are applied to a drug docking problem. When compared to simulated annealing, GA-LS hybrids not only find better solutions and optimize more efficiently.
---
paper_title: Evolutionary Algorithms, Fitness Landscapes and Search

paper_content:

A new model of fitness landscapes suitable for the consideration of evolutionary and other search algorithms is developed and its consequences are investigated. Answers to the questions "What is a landscape?" "Are landscapes useful?" and "What makes a landscape difficult to search?" are provided. The model makes it possible to construct landscapes for algorithms that employ multiple operators, including operators that act on or produce multiple individuals. It also incorporates operator transition probabilities. The consequences of adopting the model include a "one operator, one landscape" view of algorithms that search with multiple operators. An investigation into crossover landscapes and hillclimbing algorithms on them illustrates the dual role played by crossover in genetic algorithms. This leads to the "headless chicken" test for the usefulness of crossover to a given genetic algorithm and to serious questions about the usefulness of maintaining a population. A "reverse hillclimbing" algorithms is presented that allows the determination of details of the basin of attraction points on a landscape. These details can be used to directly compare members of a class of hillclimbing algorithms and to accurately predict how long a particular hillclimber will take to discover a given point. A connection between evolutionary algorithms and the heuristic search algorithms of Artificial Intelligence and Operations Research is established. One aspect of this correspondence is investigated in detail: the relationship between fitness functions and heuristic functions. By considering how closely fitness functions approximate the ideal heuristic functions, a measure of search difficult is obtained. The measure, fitness distance correlation, is a remarkably reliableble indicator of problem difficulty for a genetic algorithm on many problems taken from the genetic algorithms literature, even though the measure incorporates no knowledge of the operation of a genetic algorithm. This leads to one answer to the question "What makes a problem hard (or easy) for a genetic algorithm?" The answer is perfectly in keeping with what has been well known in Artificial Intelligence for over thirty years.
---
paper_title: A tutorial for competent memetic algorithms: model, taxonomy, and design issues

paper_content:

The combination of evolutionary algorithms with local search was named "memetic algorithms" (MAs) (Moscato, 1989). These methods are inspired by models of natural systems that combine the evolutionary adaptation of a population with individual learning within the lifetimes of its members. Additionally, MAs are inspired by Richard Dawkin's concept of a meme, which represents a unit of cultural evolution that can exhibit local refinement (Dawkins, 1976). In the case of MA's, "memes" refer to the strategies (e.g., local refinement, perturbation, or constructive methods, etc.) that are employed to improve individuals. In this paper, we review some works on the application of MAs to well-known combinatorial optimization problems, and place them in a framework defined by a general syntactic model. This model provides us with a classification scheme based on a computable index D, which facilitates algorithmic comparisons and suggests areas for future research. Also, by having an abstract model for this class of metaheuristics, it is possible to explore their design space and better understand their behavior from a theoretical standpoint. We illustrate the theoretical and practical relevance of this model and taxonomy for MAs in the context of a discussion of important design issues that must be addressed to produce effective and efficient MAs.
---
paper_title: Theory for the folding and stability of globular proteins

paper_content:

Using lattice statistical mechanics, we develop theory to account for the folding of a heteropolymer molecule such as a protein to the globular and soluble state. Folding is assumed to be driven by the association of solvophobic monomers to avoid solvent and opposed by the chain configurational entropy. Theory predicts a phase transition as a function of temperature or solvent character. Molecules that are too short or too long or that have too few solvophobic residues are predicted not to fold. Globular molecules should have a largely solvophobic core, but there is an entropic tendency for some residues to be "out of place", particularly in small molecules. For long chains, molecules comprised of globular domains are predicted to be ther- modynamically more stable than spherical molecules. The number of accessible conformations in the globular state is calculated to be an exceedingly small fraction of the number available to the random coil. Previous estimates of this number, which have motivated kinetic theories of folding, err by many tens of orders of magnitude.
---
paper_title: The co-evolution of memetic algorithms for protein structure prediction

paper_content:

This paper describes a co-evolutionary learning-optimisation approach to Protein Structure Prediction which uses a Memetic Algorithm as its underlying search method. Instance-specific knowledge can be learned, stored and applied by the system in the form of a population of rules. These rules determine the neighbourhoods used by the local search process, which is applied to each member of the co-evolving population of candidate solutions.
---
paper_title: Genetic Algorithms for Protein Folding Simulations

paper_content:

Genetic algorithms methods utilize the same optimization procedures as natural genetic evolution, in which a population is gradually improved by selection. We have developed a genetic algorithm search procedure suitable for use in protein folding simulations. A population of conformations of the polypeptide chain is maintained, and conformations are changed by mutation, in the form of conventional Monte Carlo steps, and crossovers in which parts of the polypeptide chain are interchanged between conformations. For folding on a simple two-dimensional lattice it is found that the genetic algorithm is dramatically superior to conventional Monte Carlo methods.
---
paper_title: Protein structure prediction with co-evolving memetic algorithms

paper_content:

We present a coevolutionary learning-optimisation approach to protein structure prediction which uses a memetic algorithm as its underlying search method. Instance-specific knowledge can be learned, stored and applied by the system in the form of a population of rules. These rules determine the neighbourhoods used by the local search process, which is applied to each member of the coevolving population of candidate solutions. A generic coevolutionary framework is proposed for this approach, and then the implementation of a simple self-adaptive instantiation is described. A rule defining the local search's move operator is encoded as a {condition : action} pair and added to the genotype of each individual. It is demonstrated that the action of mutation and crossover on the patterns encoded in these rules, coupled with the action of selection on the resultant phenotypes is sufficient to permit the discovery and propagation of knowledge about the instance being optimised. The algorithm is benchmarked against a simple genetic algorithm, a memetic algorithm using a fixed neighbourhood function, and a similar memetic algorithm which uses random (rather than evolved) rules and shows significant improvements in terms of the ability to locate optimum configurations using Dill's HP model. It is shown that this "metalearning" of problem features provides a means of creating highly scaleable algorithms.
---
paper_title: Protein Structure Prediction With Evolutionary Algorithms

paper_content:

Evolutionary algorithms have been successfully applied to a variety of molecular structure prediction problems. In this paper we reconsider the design of genetic algorithms that have been applied to a simple protein structure prediction problem. Our analysis considers the impact of several algorithmic factors for this problem: the conformational representation, the energy formulation and the way in which infeasible conformations are penalized. Further we empirically evaluate the impact of these factors on a small set of polymer sequences. Our analysis leads to specific recommendations for both GAs as well as other heuristic methods for solving PSP on the HP model.
---
paper_title: A tutorial for competent memetic algorithms: model, taxonomy, and design issues

paper_content:

The combination of evolutionary algorithms with local search was named "memetic algorithms" (MAs) (Moscato, 1989). These methods are inspired by models of natural systems that combine the evolutionary adaptation of a population with individual learning within the lifetimes of its members. Additionally, MAs are inspired by Richard Dawkin's concept of a meme, which represents a unit of cultural evolution that can exhibit local refinement (Dawkins, 1976). In the case of MA's, "memes" refer to the strategies (e.g., local refinement, perturbation, or constructive methods, etc.) that are employed to improve individuals. In this paper, we review some works on the application of MAs to well-known combinatorial optimization problems, and place them in a framework defined by a general syntactic model. This model provides us with a classification scheme based on a computable index D, which facilitates algorithmic comparisons and suggests areas for future research. Also, by having an abstract model for this class of metaheuristics, it is possible to explore their design space and better understand their behavior from a theoretical standpoint. We illustrate the theoretical and practical relevance of this model and taxonomy for MAs in the context of a discussion of important design issues that must be addressed to produce effective and efficient MAs.
---

Title: Coevolving Memetic Algorithms: A Review and Progress Report

Section 1: INTRODUCTION
Description 1: Introduce the concepts of Memetic Algorithms (MAs) and the Coevolving Memetic Algorithm (COMA), and provide a background on the importance of local search (LS) operators in hybrid algorithms.

Section 2: RELATED WORK
Description 2: Discuss related research and algorithms that use multiple LS operators, self-adaptation and coevolution, and draw parallels to other fields.

Section 3: APPROACH
Description 3: Describe the proposed approach for representing and adapting LS components within an MA framework using COMA, including the specifics of the algorithms.

Section 4: EXPERIMENTS WITH SIMPLE SELF-ADAPTIVE MODELS
Description 4: Present results and analyze preliminary experiments using a simple self-adaptive model to investigate the benefits of adaptive variable-length rules in optimization.

Section 5: COEVOLUTIONARY EXPERIMENTS
Description 5: Review experiments that test more complex coevolutionary forms of the COMA model, examining pivot and pairing strategies and noise tolerance.

Section 6: BENCHMARK TESTING ON MAX-3SAT
Description 6: Provide detailed results and analysis from benchmark testing on the MAX-3SAT problem, assessing the effects of more adaptable LS definitions.

Section 7: DISCUSSION AND FUTURE WORK
Description 7: Discuss the implications of the results, draw conclusions from the experiments, and suggest directions for future research.

Section 8: ACKNOWLEDGMENT
Description 8: Acknowledge the contributions of individuals and funding sources that supported the research.