Recent Advances in Memetic Algorithms

Memetic Evolutionary Algorithms (MAs) are a class of stochastic heuristics for global optimization which combine the parallel global search nature of Evolutionary Algorithms with Local Search to improve individual solutions. These techniques are being applied to an increasing range of application domains with successful results, and the aim of this book is both to highlight some of these applications, and to shed light on some of the design issues and considerations necessary to a successful implementation. In this chapter we provide a background for the rest of the volume by introducing Evolutionary Algorithms (EAs) and Local Search. We then move on to describe the synergy that arises when these two are combined in Memetic Algorithms, and to discuss some of the most salient design issues for a successful implementation. We conclude by describing various other ways in which EAs and MAs can be hybridized with domain-specific knowledge and other search techniques.

The objective of the maximum diversity problem (MDP) is to select a set of m-elements from larger set of n-elements such that the selected elements maximize a given diversity measure. The paper presents an evolutionary algorithm incorporating local search — memetic algorithm (MA) — for the MDP which consists of a greedy method, simple evolutionary operators, a repair method, and a k-flip local search based on variable depth search. In the MA, the k-flip local search starts with a feasible solution and obtains a local optimum in the feasible search space. Since infeasible solutions may be created by the simple crossover and mutation operators even if they start with feasible ones found by the local search, the repair method is applied to such infeasible solutions after the crossover and the mutation in order to guarantee feasibility of solutions to the problem. To show the effectiveness of the MA with the k-flip local search, we compare with a MA with 2-flip local search for large-scale problem instances (of up to n=2500) which are larger than those investigated by other researchers. The results show that the k-flip local search based MA is effective particularly for larger instances. We report the best solution found by the MA as this is the first time such large instances are tackled.

The VRP (Vehicle Routing Problem) and the CARP (Capacitated Arc Routing Problem) involve the routing of vehicles in an undirected network to service respectively a set of nodes or a set of arcs. Motivated by applications in waste collection, we define a more general model called NEARP (Node, Edge and Arc Routing Problem) for tackling mixed graphs with required nodes, edges and arcs. A memetic algorithm (MA) is developed for the NEARP. An evaluation on standard VRP and CARP benchmarks shows that the MA is competitive with most metaheuristics for these particular cases of the NEARP. We finally propose a set of NEARP instances, together with the solutions costs achieved by the MA, as a challenge for other researchers in vehicle routing.

Many combinatorial optimization problems occur in the calibration of modern automotive combustion engines. In this contribution, simple hill-climbing algorithms (HCs) for three special problems are incorporated in Memetic Algorithms (MAs) using specific crossover and mutation operators. First, the k-exchange algorithm as a well known technique of D-optimal design of experiments (DOE) is improved. Second, a (near-)optimum test bed measurement scheduling (TBS) as a variant of the traveling salesman problem (TSP) is calculated, and third, the final design of look-up tables (LTD) for electronic control units is optimized. It is shown that in all cases MAs that work on locally optimal solutions calculated by the corresponding HCs significantly improve former results using Genetic Algorithms (GAs). The algorithms have been successfully applied at BMW Group Munich.

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.

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 “meta-learning” of problem features provides a means of creating highly scalable algorithms.

Terminal assignment is an NP-hard problem in communications networks. It involves assigning a set of terminals to a set of concentrators with a cost for each assignment. The objective is to minimize the total cost of the assignment and the number of concentrators used. A number of heuristic algorithms, including genetic algorithms, have been proposed for solving this problem. This chapter studies several evolutionary and hybrid approaches to terminal assignment. Firstly, a novel chromosome representation scheme based on concentrators is proposed. This representation compares favourably against the existing terminal-based representation, which scales poorly for large problems. Extensive experiments have been carried out. The results show that our evolutionary algorithms using the concentrator-based representation outperform significantly existing genetic algorithms using the terminal-based representation. Secondly, a number of new search operators used in our algorithms are also investigated empirically in order to evaluate their effectiveness for the terminal assignment problem. Finally, different combinations of evolutionary algorithms and local search are studied in this chapter. Both Lamarckian evolution and Baldwin effect have been examined in combining an evolutionary algorithm and local search. Our results show that hybrid algorithms perform better than either evolutionary algorithms or local search. However, there is no significant difference between Lamarckian-evolution-style combination and Baldwin-effect-style combination.

Memetic Algorithms (MAs) are Evolutionary Algorithms (EAs) that apply some sort of local search to further improve the fitness of individuals in the population. This paper provides a forum for identifying and exploring the key issues that affect the design and application of Memetic Algorithms. Several approaches of integrating Evolutionary Computation models with local search techniques (i.e Memetic Algorithms) for efficiently solving underlying VLSI circuit partitioning problem were presented. A Constructive heuristic technique in the form of GRASP was utilized to inject the initial population with good initial solutions to diversify the search and exploit the solution space. Furthermore, the local search technique was able to enhance the convergence rate of the Evolutionary Algorithm by finely tuning the search on the immediate area of the landscape being considered. Future work involves adaptive techniques to fine-tune parameter of the Genetic Algorithm and Local Search when combined to form a Memetic Algorithm. Balancing exploration and exploitation is yet another issue that needs to be addressed more carefully.

This chapter reports the results of Multimeme algorithms that employ adaptive helpers. A Multimeme Algorithm resorts to a variety of local search neighborhoods for its local search stage allowing for a more robust global search. Each neighborhood is explored by an adaptive helper that allows non-improving moves that render the Memetic algorithm even more robust to deceptive local optima. We will report results on the use of a single adaptive helper Memetic algorithm for the Traveling Salesman Problem (TSP) and on adaptive helpers within a Multimeme algorithm for the TSP and Protein Structure Prediction Problem (PSP).

Memetic algorithms (MAs) with greedy initialization and recombination operators have been successfully applied to several combinatorial optimization problems, including the traveling salesman problem and the graph bipartitioning problem. In this contribution, a k-opt local search heuristic and a greedy heuristic for NK-landscapes are proposed for use in memetic algorithms. The latter is used for the initialization of the population and in a greedy recombination operator. Memetic algorithms with k-opt local search and three different variation operators, including the newly proposed greedy recombination operator, are compared on three types of NK-landscapes. In accordance with the landscape analysis, the MAs with recombination perform better than the MAs with mutation for landscapes with low epistasis. Moreover, the MAs are shown to be superior to previously proposed MAs using 1-opt local search.

In this chapter we concentrate on one particular class of Global-Local Search Hybrids, Memetic Algorithms (MAs), and we describe the implementation of “self-assembling” mechanisms to produce the local searches the MA uses. To understand the context in which self-assembling is applied we discuss some important aspects of Memetic theory and how these concepts could be harnessed to implement more competitive MAs. Our implementation is tested in two problems, Maximum Contact Map Overlap Problem (MAX-CMO) and the NK-Landscape Problems.

Three lessons can be drawn from this paper:

Genetic and evolutionary algorithms (GEAs) are being employed to solve a wide range of problems in search and optimization. Most real-world applications use GEAs in combination with domain specific methods to achieve superior performance. Such combinations, often referred to as hybrids, stand to gain much from a system-level framework for efficiently combining global searchers such as GEAs with domain-specific and local searchers. This chapter presents the foundations for such a framework. The theory herein attempts to attain the optimal division of labor between global and local search so that the desired solution quality can be obtained in the minimum time, or given a fixed time budget, the best solution quality can be obtained. It relies on a two-fold decomposition: the hybrid is composed of a global searcher and a local searcher, and the search space is divided into basins of attraction from where the local search can lead to the desired solution quality. The framework allows us to choose between different schedules so as to maximize chances of success. The framework utilizes knowledge of run duration theory and uses the quality of solution at each generation to compute the parameters needed by the theory. The study also looks at characteristics of a class of functions (known as traps) that determine the speedups that can be obtained from using local search.

The concept of optimization—finding the extrema of a function that maps candidate’ solutions’ to scalar values of ‘quality’—is an extremely general and useful idea that can be, and is, applied to innumerable problems in science, industry, and commerce. However, the vast majority of ‘real’ optimization problems, whatever their origins, comprise more than one objective; that is to say, ‘quality’ is actually a vector, which may be composed of such distinct attributes as cost, performance, profit, environmental impact, and so forth, which are often in mutual conflict. Until relatively recently this uncomfortable truth has been (wilfully?) overlooked in the sciences dealing with optimization, but now, increasingly, the idea of multiobjective optimization is taking over the centre ground. Multiobjective optimization takes seriously the fact that in most problems the different components that describe the quality of a candidate solution cannot be lumped together into one representative, overall measure, at least not easily, and not before some understanding of the possible ‘tradeoffs’ available has been established. Hence a multiobjective optimization algorithm is one which deals directly with a vector objective function and seeks to find multiple solutions offering different, optimal tradeoffs of the multiple objectives. This approach raises several unique issues in optimization algorithm design, which we consider in this article, with a particular focus on memetic algorithms (MAs). We summarize much of the relevant literature, attempting to be inclusive of relatively unexplored ideas, highlight the most important considerations for the design of multiobjective MAs, and finally outline our visions for future research in this exciting area.

Learning Classifier Systems have previously been shown to have some application in deducing the characteristics of complex multi-modal test environments to a suitable level of accuracy. In this study, an accuracy-based Learning Classifier System, XCS, is used. The system has the capability of inducing a set of general rules from a sample of data points using a combination of Reinforcement Learning and a Genetic Algorithm. The investigation presented here builds on earlier work in this area by considering the application of a memetic approach during learning. The motivation for this investigation is identify if any increases in learning speed and classification performance can be made. The type of memetic learning used is based on Lamarckian Evolution but has several subtle differences from the standard approach. In particular, the Learning Classifier System is based on a Reinforcement Learning paradigm that has a dynamic effect on the fitness landscape. And, the form of lifetime learning used is based on a Widrow-Hoff delta rule update procedure in which changes to an individual’s genotypic description are based upon some distance measure between the individual and a “focal rule”’ (analogous to a local optima in a standard MA). In addition, no distinction is made between genotype and phenotype. Initial investigations focus on the effects on performance for three different learning rates and three different “focal rule” identification options for two different test environments - a two-dimensional and a decomposable six-dimensional test environment. Results show that improvements can be made over a non-memetic approach. The study also considers the use of a self-adaptive learning mechanism. Self-adaptation has been suggested as beneficial for Genetic Algorithms where the technique is usually used for adapting the mutation rate in a time-dependant and decentralised way. However, the investigation of a self-adaptive learning mechanism presented here focuses on the benefits of adjusting the Widrow-Hoff learning rate used within the memetic-learning component of the system. The mechanism was applied to both test environments. Results show that the mechanism can provide a more robust learning system both in terms of reduction in the number of system parameters and increased generalisation and solution convergence. Further detailed analysis of experimental results for the decomposable six-dimensional test function is also performed. This would otherwise be non-trivial for a non-decomposable six-dimensional function. The classification accuracy of several different versions of the system including those systems with and without memetic or self-adaptive memetic learning are analysed region by region showing the effects of the new learning approach at a much greater level of detail. Analysis shows that the self-adaptive memetic version of the classifier system outperforms the non-adaptive and non-memetic versions in some of the regions.