Fitness landscape analysis and memetic algorithms for the quadratic assignment problem

In this paper, a fitness landscape analysis for several instances of the quadratic assignment problem (QAP) is performed, and the results are used to classify problem instances according to their hardness for local search heuristics and meta-heuristics based on local search. The local properties of the fitness landscape are studied by performing an autocorrelation analysis, while the global structure is investigated by employing a fitness distance correlation analysis. It is shown that epistasis, as expressed by the dominance of the flow and distance matrices of a QAP instance, the landscape ruggedness in terms of the correlation length of a landscape, and the correlation between fitness and distance of local optima in the landscape together are useful for predicting the performance of memetic algorithms-evolutionary algorithms incorporating local search (to a certain extent). Thus, based on these properties, a favorable choice of recombination and/or mutation operators can be found. Experiments comparing three different evolutionary operators for a memetic algorithm are presented.     

Fitness landscapes and evolvability

In this paper, we develop techniques based on evolvability statistics of the fitness landscape surrounding sampled solutions. Averaging the measures over a sample of equal fitness solutions allows us to build up fitness evolvability portraits of the fitness landscape, which we show can be used to compare both the ruggedness and neutrality in a set of tunably rugged and tunably neutral landscapes. We further show that the techniques can be used with solution samples collected through both random sampling of the landscapes and online sampling during optimization. Finally, we apply the techniques to two real evolutionary electronics search spaces and highlight differences between the two search spaces, comparing with the time taken to find good solutions through search.     

A tutorial for competent memetic algorithms: model, taxonomy, and design issues

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.     

Locally-adaptive and memetic evolutionary pattern search algorithms

Recent convergence analyses of evolutionary pattern search algorithms (EPSAs) have shown that these methods have a weak stationary point convergence theory for a broad class of unconstrained and linearly constrained problems. This paper describes how the convergence theory for EPSAs can be adapted to allow each individual in a population to have its own mutation step length (similar to the design of evolutionary programing and evolution strategies algorithms). These are called locally-adaptive EPSAs (LA-EPSAs) since each individual's mutation step length is independently adapted in different local neighborhoods. The paper also describes a variety of standard formulations of evolutionary algorithms that can be used for LA-EPSAs. Further, it is shown how this convergence theory can be applied to memetic EPSAs, which use local search to refine points within each iteration.     

Multiobjective memetic algorithms for time and space assembly line balancing

This paper presents three proposals of multiobjective memetic algorithms to solve a more realistic extension of a classical industrial problem: time and space assembly line balancing. These three proposals are, respectively, based on evolutionary computation, ant colony optimisation, and greedy randomised search procedure. Different variants of these memetic algorithms have been developed and compared in order to determine the most suitable intensification–diversification trade-off for the memetic search process. Once a preliminary study on nine well-known problem instances is accomplished with a very good performance, the proposed memetic algorithms are applied considering real-world data from a Nissan plant in Barcelona (Spain). Outstanding approximations to the pseudo-optimal non-dominated solution set were achieved for this industrial case study.     

Two memetic algorithms for heterogeneous fleet vehicle routing problems

The vehicle routing problem (VRP) plays an important role in the distribution step of supply chains. From a depot with identical vehicles of limited capacity, it consists in determining a set of vehicle trips of minimum total length, to satisfy the demands of a set of customers. In general, the number of vehicles used is a decision variable. The heterogeneous fleet VRP (HFVRP or HVRP) is a natural generalization with several vehicle types, each type being defined by a capacity, a fixed cost, a cost per distance unit and a number of vehicles available. The vehicle fleet mix problem (VFMP) is a variant with an unlimited number of vehicles per type. This paper presents two memetic algorithms (genetic algorithms hybridized with a local search) able to solve both the VFMP and the HVRP. They are based on chromosomes encoded as giant tours, without trip delimiters, and on an optimal evaluation procedure which splits these tours into feasible trips and assigns vehicles to them. The second algorithm uses a distance measure in solution space to diversify the search. Numerical tests on standard VFMP and HFVRP instances show that the two methods, especially the one with distance measure, compete with published metaheuristics and improve several best-known solutions.     

A case study of memetic algorithms for constraint optimization

There is a variety of knapsack problems in the literature. Multidimensional 0–1 knapsack problem (MKP) is an NP-hard combinatorial optimization problem having many application areas. Many approaches have been proposed for solving this problem. In this paper, an empirical investigation of memetic algorithms (MAs) that hybridize genetic algorithms (GAs) with hill climbing for solving MKPs is provided. Two distinct sets of experiments are performed. During the initial experiments, MA parameters are tuned. GA and four MAs each using a different hill climbing method based on the same configuration are evaluated. In the second set of experiments, a self-adaptive (co-evolving) multimeme memetic algorithm (MMA) is compared to the best MA from the parameter tuning experiments. MMA utilizes the evolutionary process as a learning mechanism for choosing the appropriate hill climbing method to improve a candidate solution at a given time. Two well-known MKP benchmarks are used during the experiments.     

Orderly algorithms for graph generation

The existence of orderly analogues of graph generators proposed by Heap and Farrell is established. The modifications to these algorithms supply practical methods enabling one to generate exhaustive lists of graphs and locally restricted graphs; moreover, the difficulty involved in ensuring that no duplications occur in the list is greatly reduced.     

Estimating meme fitness in adaptive memetic algorithms for combinatorial problems

Among the most promising and active research areas in heuristic optimisation is the field of adaptive memetic algorithms (AMAs). These gain much of their reported robustness by adapting the probability with which each of a set of local improvement operators is applied, according to an estimate of their current value to the search process. This paper addresses the issue of how the current value should be estimated. Assuming the estimate occurs over several applications of a meme, we consider whether the extreme or mean improvements should be used, and whether this aggregation should be global, or local to some part of the solution space. To investigate these issues, we use the well-established COMA framework that coevolves the specification of a population of memes (representing different local search algorithms) alongside a population of candidate solutions to the problem at hand. Two very different memetic algorithms are considered: the first using adaptive operator pursuit to adjust the probabilities of applying a fixed set of memes, and a second which applies genetic operators to dynamically adapt and create memes and their functional definitions. For the latter, especially on combinatorial problems, credit assignment mechanisms based on historical records, or on notions of landscape locality, will have limited application, and it is necessary to estimate the value of a meme via some form of sampling. The results on a set of binary encoded combinatorial problems show that both methods are very effective, and that for some problems it is necessary to use thousands of variables in order to tease apart the differences between different reward schemes. However, for both memetic algorithms, a significant pattern emerges that reward based on mean improvement is better than that based on extreme improvement. This contradicts recent findings from adapting the parameters of operators involved in global evolutionary search. The results also show that local reward schemes outperform global reward schemes in combinatorial spaces, unlike in continuous spaces. An analysis of evolving meme behaviour is used to explain these findings.     

Energy-aware topology control for wireless sensor networks using memetic algorithms

Cost-effective topology control is critical in wireless sensor networks. While much research has been carried out in this aspect using various methods, no attention has been made on utilizing modern heuristics for this purpose. This paper proposes a memetic algorithm-based solution for energy-aware topology control for wireless sensor networks. This algorithm (called ToCMA), using a combination of problem-specific light-weighted local search and genetic algorithms, is able to solve the minimum energy network connectivity (MENC) this NP-hard problem in an approximated manner that performs better than the classical minimum spanning tree (MST) solution. The outcomes of ToCMA can also be utilized for various network optimization and fault-tolerant purposes.     

Worst case analysis of a greedy algorithm for graph thickness

In this paper, we consider a greedy algorithm for thickness of graphs. The greedy algorithm we consider here takes a maximum planar subgraph away from the current graph in each iteration and repeats this process until the current graph has no edge. The greedy algorithm outputs the number of iterations which is an upper bound of thickness for an input graph G=(V,E). We show that the performance ratio of the greedy algorithm is .     

Genetic operators for hierarchical graph clustering

In this paper we propose an encoding scheme and ad hoc operators for a genetic approach to hierarchical graph clustering. Given a connected graph whose vertices correspond to points within a Euclidean space and a fitness function, a hierarchy of graphs in which each vertex corresponds to a connected subgraph of the graph below is generated. Both the number of clustering levels and the number of clusters on each level are not fixed a priori and are subject to optimization.     

Priority algorithms for graph optimization problems

We continue the study of priority or “greedy-like” algorithms as initiated in Borodin et al. (2003) [10] and as extended to graph theoretic problems in Davis and Impagliazzo (2009) [12]. Graph theoretic problems pose some modeling problems that did not exist in the original applications of Borodin et al. and Angelopoulos and Borodin (2002) [3]. Following the work of Davis and Impagliazzo, we further clarify these concepts. In the graph theoretic setting, there are several natural input formulations for a given problem and we show that priority algorithm bounds in general depend on the input formulation. We study a variety of graph problems in the context of arbitrary and restricted priority models corresponding to known “greedy algorithms”.     

Efficient parallel algorithms for graph problems

We present an efficient technique for parallel manipulation of data structures that avoids memory access conflicts. That is, this technique works on the Exclusive Read/Exclusive Write (EREW) model of computation, which is the weakest shared memory, MIMD machine model. It is used in a new parallel radix sort algorithm that is optimal for keys whose values are over a small range. Using the radix sort and known results for parallel prefix on linked lists, we develop parallel algorithms that efficiently solve various computations on trees and unicycular graphs. Finally, we develop parallel algorithms for connected components, spanning trees, minimum spanning trees, and other graph problems. All of the graph algorithms achieve linear speedup for all but the sparsest graphs.Part of this work was done while the first author was at the University of Illinois, Urbana-Champaign, the second author was at Carnegie-Mellon University, and the third author was at the Hebrew University and the Courant Institute of Mathematical Sciences, New York University. A preliminary version of this work was presented at the 1986 International Conference on Parallel Processing.     

Efficient parallel algorithms for graph problems

We present an efficient technique for parallel manipulation of data structures that avoids memory access conflicts. That is, this technique works on the Exclusive Read/Exclusive Write (EREW) model of computation, which is the weakest shared memory, MIMD machine model. It is used in a new parallel radix sort algorithm that is optimal for keys whose values are over a small range. Using the radix sort and known results for parallel prefix on linked lists, we develop parallel algorithms that efficiently solve various computations on trees and “unicycular graphs.” Finally, we develop parallel algorithms for connected components, spanning trees, minimum spanning trees, and other graph problems. All of the graph algorithms achieve linear speedup for all but the sparsest graphs.     

Combinatorial algorithms for distributed graph coloring

Numerous problems in Theoretical Computer Science can be solved very efficiently using powerful algebraic constructions. Computing shortest paths, constructing expanders, and proving the PCP Theorem, are just few examples of this phenomenon. The quest for combinatorial algorithms that do not use heavy algebraic machinery, but are roughly as efficient, has become a central field of study in this area. Combinatorial algorithms are often simpler than their algebraic counterparts. Moreover, in many cases, combinatorial algorithms and proofs provide additional understanding of studied problems. In this paper we initiate the study of combinatorial algorithms for Distributed Graph Coloring problems. In a distributed setting a communication network is modeled by a graph $G=(V,E)$ of maximum degree $\varDelta $ . The vertices of $G$ host the processors, and communication is performed over the edges of $G$ . The goal of distributed vertex coloring is to color $V$ with $(\varDelta + 1)$ colors such that any two neighbors are colored with distinct colors. Currently, efficient algorithms for vertex coloring that require $O(\varDelta + \log ^* n)$ time are based on the algebraic algorithm of Linial (SIAM J Comput 21(1):193–201, 1992) that employs set-systems. The best currently-known combinatorial set-system free algorithm, due to Goldberg et al. (SIAM J Discret Math 1(4):434–446, 1988), requires $O(\varDelta ^2+\log ^*n)$ time. We significantly improve over this by devising a combinatorial $(\varDelta + 1)$ -coloring algorithm that runs in $O(\varDelta + \log ^* n)$ time. This exactly matches the running time of the best-known algebraic algorithm. In addition, we devise a tradeoff for computing $O(\varDelta \cdot t)$ -coloring in $O(\varDelta /t + \log ^* n)$ time, for almost the entire range $1 < t < \varDelta $ . We also compute a Maximal Independent Set in $O(\varDelta + \log ^* n)$ time on general graphs, and in $O(\log n/ \log \log n)$ time on graphs of bounded arboricity. Prior to our work, these results could be only achieved using algebraic techniques. We believe that our algorithms are more suitable for real-life networks with limited resources, such as sensor networks.     

Advanced fitness landscape analysis and the performance of memetic algorithms

Memetic algorithms (MAs) have demonstrated very effective in combinatorial optimization. This paper offers explanations as to why this is so by investigating the performance of MAs in terms of efficiency and effectiveness. A special class of MAs is used to discuss efficiency and effectiveness for local search and evolutionary meta-search. It is shown that the efficiency of MAs can be increased drastically with the use of domain knowledge. However, effectiveness highly depends on the structure of the problem. As is well-known, identifying this structure is made easier with the notion of fitness landscapes: the local properties of the fitness landscape strongly influence the effectiveness of the local search while the global properties strongly influence the effectiveness of the evolutionary meta-search. This paper also introduces new techniques for analyzing the fitness landscapes of combinatorial problems; these techniques focus on the investigation of random walks in the fitness landscape starting at locally optimal solutions as well as on the escape from the basins of attractions of current local optima. It is shown for NK-landscapes and landscapes of the unconstrained binary quadratic programming problem (BQP) that a random walk to another local optimum can be used to explain the efficiency of recombination in comparison to mutation. Moreover, the paper shows that other aspects like the size of the basins of attractions of local optima are important for the efficiency of MAs and a local search escape analysis is proposed. These simple analysis techniques have several advantages over previously proposed statistical measures and provide valuable insight into the behaviour of MAs on different kinds of landscapes.     

BubbleSearch: A simple heuristic for improving priority-based greedy algorithms

We introduce BubbleSearch, a general approach for extending priority-based greedy heuristics. Following the framework recently developed by Borodin et al., we consider priority algorithms, which sequentially assign values to elements in some fixed or adaptively determined order. BubbleSearch extends priority algorithms by selectively considering additional orders near an initial good ordering. While many notions of nearness are possible, we explore algorithms based on the Kendall-tau distance (also known as the BubbleSort distance) between permutations. Our contribution is to elucidate the BubbleSearch paradigm and experimentally demonstrate its effectiveness.     

Constraint programming and graph algorithms

Aconstraint system includes a set of variables and a set of relations among these variables, calledconstraints. The solution of a constraint system is an assignment of values to variables so that all, or many, of the relations are made true. A simple and efficient method for constraint resolution has been proposed in the work of B.N. Freeman-Benson, J. Maloney, and A. Borning. We show how their method is related to the classical problem of graph matching, and from this connection we derive new resolution algorithms.