Memetic Algorithms: The Polynomial Local Search Complexity Theory Perspective

In previous work (Krasnogor, . In: Studies on the Theory and Design Space of Memetic Algorithms. Ph.D. thesis, University of the West of England, Bristol, UK, 2002; Krasnogor and Smith, IEEE Trans Evol Algorithms 9(6):474–488, 2005) we develop a syntax-only classification of evolutionary algorithms, in particular so-called memetic algorithms (MAs). When “syntactic sugar” is added to our model, we are able to investigate the polynomial local search (PLS) complexity of memetic algorithms. In this paper we show the PLS-completeness of whole classes of problems that occur when memetic algorithms are applied to the travelling salesman problem using a range of mutation, crossover and local search operators. Our PLS-completeness results shed light on the worst case behaviour that can be expected of a memetic algorithm under these circumstances. Moreover, we point out in this paper that memetic algorithms for graph partitioning and maximum network flow (both with important practical applications) also give rise to PLS-complete problems.

---

Electronic Supplementary Material The online version of this article (doi:) contains supplementary material, which is available to authorized users.      

Hybrid immune algorithm with Lamarckian local search for multi-objective optimization

Lamarckian learning has been introduced into evolutionary computation as local search mechanism. The relevant research topic, memetic computation, has received significant amount of interests. In this study, a novel Lamarckian learning strategy is designed for improving the Nondominated Neighbor Immune Algorithm, a novel hybrid multi-objective optimization algorithm, Multi-objective Lamarckian Immune Algorithm (MLIA), is proposed. The Lamarckian learning performs a greedy search which proceeds towards the goal along the direction obtained by Tchebycheff approach and generates the improved progenies or improved decision vectors, so single individual will be optimized locally and the newcomers yield an enhanced exploitation around the nondominated individuals in less-crowded regions of the current trade-off front. Simulation results based on twelve benchmark problems show that MLIA outperforms the original immune algorithm and NSGA-II in approximating Pareto-optimal front in most of the test problems. When compared with the state of the art algorithm MOEA/D, MLIA shows better performance in terms of the coverage of two sets metric, although it is laggard in the hypervolume metric.     

The linear ordering problem: Instances,search space analysis and algorithms

The linear ordering problem is an NP-hard problem that arises in a variety of applications. Due to its interest in practice, it has received considerable attention and a variety of algorithmic approaches to its solution have been proposed. In this paper we give a detailed search space analysis of available benchmark instance classes that have been used in various researches. The large fitness-distance correlations observed for many of these instances suggest that adaptive restart algorithms like iterated local search or memetic algorithms, which iteratively generate new starting solutions for a local search based on previous search experience, are promising candidates for obtaining high performing algorithms. We therefore experimentally compared two such algorithms and the final experimental results suggest that, in particular, the memetic algorithm is a new state-of-the-art approach to the linear ordering problem.     

Local Search Methods for the Optimal Winner Determination Problem in Combinatorial Auctions

In this paper, both stochastic local search (SLS) and tabu search (TS) are studied for the optimal winner determination problem (WDP) in combinatorial auctions. The proposed methods are evaluated on various benchmark problems, and compared with the hybrid simulated annealing (SAGII), the memetic algorithms (MA) and Casanova. The computational experiments show that the SLS provides competitive results and finds solutions of a higher quality than TS and Casanova methods.     

A preference-based multi-objective evolutionary algorithm R-NSGA-II with stochastic local search

Incorporation of a decision maker’s preferences into multi-objective evolutionary algorithms has become a relevant trend during the last decade, and several preference-based evolutionary algorithms have been proposed in the literature. Our research is focused on improvement of a well-known preference-based evolutionary algorithm R-NSGA-II by incorporating a local search strategy based on a single agent stochastic approach. The proposed memetic algorithm has been experimentally evaluated by solving a set of well-known multi-objective optimization benchmark problems. It has been experimentally shown that incorporation of the local search strategy has a positive impact to the quality of the algorithm in the sense of the precision and distribution evenness of approximation.     

Memetic techniques for examination timetabling

In this paper, we investigate the effectiveness of combining the main components of the memetic algorithms (MAs) on the quality of solutions produced for Uncapacitated Examination Timetabling Problem (UETP). These components are recombination, randomness, and neighbourhood structures. The Harmony Search Algorithm (HSA), which is a variation of MA, is used to perform different combinations of these components. It has three main components: Memory Consideration using the recombination, Random Consideration using the randomness and Pitch Adjustment using the neighbourhood structures (or local search). The combinations among MA components are evaluated using 17 different scenarios each of which reflects a combination of one, two or three components. The results show that the system that combines the three components (recombination, randomness, and neighbourhood structures) provides the best results. Furthermore, the best results obtained from the convergence scenarios were compared with 22 other methods that used a de facto dataset defined by Carter et al. (in Journal of the Operational Research Society 74:373–383, 1996) for UETP. The results exceed those produced by the previous methods in 2 out of 12 datasets.     

Memetic cooperative models for the tool switching problem

This work deals with memetic-computing agent-models based on the cooperative integration of search agents endowed with (possibly different) optimization strategies, in particular memetic algorithms. As a proof-of-concept of the model, we deploy it on the tool switching problem (ToSP), a hard combinatorial optimization problem that arises in the area of flexible manufacturing. The ToSP has been tackled by different algorithmic methods ranging from exact to heuristic methods (including local search meta-heuristics, population-based techniques and hybrids thereof, i.e., memetic algorithms). Here we consider an ample number of instances of this cooperative memetic model, whose agents are adapted to cope with this problem. A detailed experimental analysis shows that the meta-models promoting the cooperation among memetic algorithms provide the best overall results compared with their constituent parts (i.e., memetic algorithms and local search approaches). In addition, a parameter sensitivity analysis of the meta-models is developed in order to understand the interplay among the elements of the proposed topologies.     

A unified framework for population-based metaheuristics

Based on the analysis of the basic schemes of a variety of population-based metaheuristics (PBMH), the main components of PBMH are described with functional relationships in this paper and a unified framework (UF) is proposed for PBMH to provide a comprehensive way of viewing PBMH and to help understand the essential philosophy of PBMH from a systematic standpoint. The relevance of the proposed UF and some typical PBMH methods is illustrated, including particle swarm optimization, differential evolution, scatter search, ant colony optimization, genetic algorithm, evolutionary programming, and evolution strategies, which can be viewed as the instances of the UF. In addition, as a platform to develop the new population-based metaheuristics, the UF is further explained to provide some designing issues for effective/efficient PBMH algorithms. Subsequently, the UF is extended, namely UFmeme to describe the Memetic Algorithms (MAs) by adding local search (memetic component) to the framework as an extra-feature. Finally, we theoretically analyze the asymptotic convergence properties of PBMH described by the UF and MAs by the UFmeme.     

Variations on memetic algorithms for graph coloring problems

Graph vertex coloring with a given number of colors is a well-known and much-studied NP-complete problem. The most effective methods to solve this problem are proved to be hybrid algorithms such as memetic algorithms or quantum annealing. Those hybrid algorithms use a powerful local search inside a population-based algorithm. This paper presents a new memetic algorithm based on one of the most effective algorithms: the hybrid evolutionary algorithm (HEA) from Galinier and Hao (J Comb Optim 3(4): 379–397, 1999). The proposed algorithm, denoted HEAD—for HEA in Duet—works with a population of only two individuals. Moreover, a new way of managing diversity is brought by HEAD. These two main differences greatly improve the results, both in terms of solution quality and computational time. HEAD has produced several good results for the popular DIMACS benchmark graphs, such as 222-colorings for \({<}{} \texttt {dsjc1000.9}{>}\), 81-colorings for \({<}{} \texttt {flat1000\_76\_0}{>}\) and even 47-colorings for \({<}{} \texttt {dsjc500.5}{>}\) and 82-colorings for \({<}{} \texttt {dsjc1000.5}{>}\).     

Multi-wave algorithms for metaheuristic optimization

We propose new iterated improvement neighborhood search algorithms for metaheuristic optimization by exploiting notions of conditional influence within a strategic oscillation framework. These approaches, which are unified within a class of methods called multi-wave algorithms, offer further refinements by memory based strategies that draw on the concept of persistent attractiveness. Our algorithms provide new forms of both neighborhood search methods and multi-start methods, and are readily embodied within evolutionary algorithms and memetic algorithms by solution combination mechanisms derived from path relinking. These methods can also be used to enhance branching strategies for mixed integer programming.     

Memetic algorithms for solving job-shop scheduling problems

The job-shop scheduling problem is well known for its complexity as an NP-hard problem. We have considered JSSPs with an objective of minimizing makespan while satisfying a number of hard constraints. In this paper, we developed a memetic algorithm (MA) for solving JSSPs. Three priority rules were designed, namely partial re-ordering, gap reduction and restricted swapping, and used as local search techniques in our MA. We have solved 40 benchmark problems and compared the results obtained with a number of established algorithms in the literature. The experimental results show that MA, as compared to GA, not only improves the quality of solutions but also reduces the overall computational time.     

Hybridizations within a graph-based hyper-heuristic framework for university timetabling problems

A significant body of recent literature has explored various research directions in hyper-heuristics (which can be thought as heuristics to choose heuristics). In this paper, we extend our previous work to construct a unified graph-based hyper-heuristic (GHH) framework, under which a number of local search-based algorithms (as the high level heuristics) are studied to search upon sequences of low-level graph colouring heuristics. To gain an in-depth understanding on this new framework, we address some fundamental issues concerning neighbourhood structures and characteristics of the two search spaces (namely, the search spaces of the heuristics and the actual solutions). Furthermore, we investigate efficient hybridizations in GHH with local search methods and address issues concerning the exploration of the high-level search and the exploitation ability of the local search. These, to our knowledge, represent entirely novel directions in hyper-heuristics. The efficient hybrid GHH obtained competitive results compared with the best published results for both benchmark course and exam timetabling problems, demonstrating its efficiency and generality across different problem domains. Possible extensions upon this simple, yet general, GHH framework are also discussed.     

PSOHS: an efficient two-stage approach for data clustering

Cluster analysis is an important task in data mining and refers to group a set of objects such that the similarities among objects within the same group are maximal while similarities among objects from different groups are minimal. The particle swarm optimization algorithm (PSO) is one of the famous metaheuristic optimization algorithms, which has been successfully applied to solve the clustering problem. However, it has two major shortcomings. The PSO algorithm converges rapidly during the initial stages of the search process, but near global optimum, the convergence speed will become very slow. Moreover, it may get trapped in local optimum if the global best and local best values are equal to the particle’s position over a certain number of iterations. In this paper we hybridized the PSO with a heuristic search algorithm to overcome the shortcomings of the PSO algorithm. In the proposed algorithm, called PSOHS, the particle swarm optimization is used to produce an initial solution to the clustering problem and then a heuristic search algorithm is applied to improve the quality of this solution by searching around it. The superiority of the proposed PSOHS clustering method, as compared to other popular methods for clustering problem is established for seven benchmark and real datasets including Iris, Wine, Crude Oil, Cancer, CMC, Glass and Vowel.     

Memetic algorithm based on marriage in honey bees optimization for flexible job shop scheduling problem

This paper proposes a new memetic algorithm based on marriage in honey bees optimization (MBO) algorithm for solving the flexible job shop scheduling problem. The proposed algorithm introduces four new features to the standard MBO algorithm, mainly to get the search to move away from the local optimum: (1) the use of a harmony memory to improve the quality of initial population; (2) the introduction of a new crossover operator called triparental crossover to help increase the genetic diversity in the offspring; (3) the addition of adaptive crossover probability (\(\hbox {P}_{\mathrm{c}})\) and mutation probability (\(\hbox {P}_{\mathrm{m}})\) to remove the need for users to specify these probabilities; and (4) the incorporation of simulated annealing algorithm embedded with a set of heuristics to enhance the local search capability. The proposed algorithm was evaluated and compared to several state-of-the-art algorithms in the literature. The experimental results on five sets of standard benchmarks show that the proposed algorithm is very effective in solving the flexible job shop scheduling problems.     

Pareto memetic algorithm for multiple objective optimization with an industrial application

Multiple objective combinatorial optimization problems are difficult to solve and often, exact algorithms are unable to produce optimal solutions. The development of multiple objective heuristics was inspired by the need to quickly produce acceptable solutions. In this paper, we present a new multiple objective Pareto memetic algorithm called PMS^MO. The PMS^MO algorithm incorporates an enhanced fine-grained fitness assignment, a double level archiving process and a local search procedure to improve performance. The performance of PMS^MO is benchmarked against state-of-the-art algorithms using 0–1 multi-dimensional multiple objective knapsack problem from the literature and an industrial scheduling problem from the aluminum industry.     

Solving the routing and wavelength assignment problem with a multilevel distributed memetic algorithm

The Routing and Wavelength Assignment problem is a graph optimization problem which deals with optical networks, where communication requests in a network have to be fulfilled. In this paper, we present a multilevel distributed memetic algorithm (ML-DMA) for the static RWA which finds provable optimal solutions for most benchmark instances with known lower bounds and is capable of handling large instances. Components of our ML-DMA include iterated local search, recombination, multilevel scaling, and a gossip-based distribution algorithm. Results demonstrated that our ML-DMA is among the most sophisticated heuristic RWA algorithms published so far.     

Competitive Memetic Algorithms for Arc Routing Problems

The Capacitated Arc Routing Problem or CARP arises in applications like waste collection or winter gritting. Metaheuristics are tools of choice for solving large instances of this NP-hard problem. The paper presents basic components that can be combined into powerful memetic algorithms (MAs) for solving an extended version of the CARP (ECARP). The best resulting MA outperforms all known heuristics on three sets of benchmark files containing in total 81 instances with up to 140 nodes and 190 edges. In particular, one open instance is broken by reaching a tight lower bound designed by Belenguer and Benavent, 26 best-known solutions are improved, and all other best-known solutions are retrieved.     

Boosting local search with Lagrangian relaxation

Local search algorithms play an essential role in solving large-scale combinatorial optimization problems. Traditionally, the local search procedure is guided mainly by the objective function of the problem. Hence, the greedy improvement paradigm poses the potential threat of prematurely getting trapped in low quality attraction basins. In this study, we intend to utilize the information extracted from the relaxed problem, to enhance the performance of the local search process. Considering the Lin-Kernighan-based local search (LK-search) for the p-median problem as a case study, we propose the Lagrangian relaxation Assisted Neighborhood Search (LANS). In the proposed algorithm, two new mechanisms, namely the neighborhood reduction and the redundancy detection, are developed. The two mechanisms exploit the information gathered from the relaxed problem, to avoid the search from prematurely targeting low quality directions, and to cut off the non-promising searching procedure, respectively. Extensive numerical results over the benchmark instances demonstrate that LANS performs favorably to LK-search, which is among the state-of-the-art local search algorithms for the p-median problem. Furthermore, by embedding LANS into other heuristics, the best known upper bounds over several benchmark instances could be updated. Besides, run-time distribution analysis is also employed to investigate the reason why LANS works. The findings of this study confirm that the idea of improving local search by leveraging the information induced from relaxed problem is feasible and practical, and might be generalized to a broad class of combinatorial optimization problems.     

Handling equality constraints in evolutionary optimization

Over the last few decades several methods have been proposed for handling functional constraints while solving optimization problems using evolutionary algorithms (EAs). However, the presence of equality constraints makes the feasible space very small compared to the entire search space. As a consequence, the handling of equality constraints has long been a difficult issue for evolutionary optimization methods. This paper presents a Hybrid Evolutionary Algorithm (HEA) for solving optimization problems with both equality and inequality constraints. In HEA, we propose a new local search technique with special emphasis on equality constraints. The basic concept of the new technique is to reach a point on the equality constraint from the current position of an individual solution, and then explore on the constraint landscape. We believe this new concept will influence the future research direction for constrained optimization using population based algorithms. The proposed algorithm is tested on a set of standard benchmark problems. The results show that the proposed technique works very well on those benchmark problems.     

Global optimization based on novel heuristics,low-discrepancy sequences and genetic algorithms

In this paper a new heuristic hybrid technique for bound-constrained global optimization is proposed. We developed iterative algorithm called GLP_τS that uses genetic algorithms, LP_τ low-discrepancy sequences of points and heuristic rules to find regions of attraction when searching a global minimum of an objective function. Subsequently Nelder–Mead Simplex local search technique is used to refine the solution. The combination of the three techniques (Genetic algorithms, LP_τO Low-discrepancy search and Simplex search) provides a powerful hybrid heuristic optimization method which is tested on a number of benchmark multimodal functions with 10–150 dimensions, and the method properties – applicability, convergence, consistency and stability are discussed in detail.