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.     

Coevolving memetic algorithms: a review and progress report.

Coevolving memetic algorithms are a family of metaheuristic search algorithms in which a rule-based representation of local search (LS) is coadapted alongside candidate solutions within a hybrid evolutionary system. Simple versions of these systems have been shown to outperform other nonadaptive memetic and evolutionary algorithms on a range of problems. This paper presents a rationale for such systems and places them in the context of other recent work on adaptive memetic algorithms. It then proposes a general structure within which a population of LS algorithms can be evolved in tandem with the solutions to which they are applied. Previous research started with a simple self-adaptive system before moving on to more complex models. Results showed that the algorithm was able to discover and exploit certain forms of structure and regularities within the problems. This "metalearning" of problem features provided a means of creating highly scalable algorithms. This work is briefly reviewed to highlight some of the important findings and behaviors exhibited. Based on this analysis, new results are then presented from systems with more flexible representations, which, again, show significant improvements. Finally, the current state of, and future directions for, research in this area is discussed.     

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.     

On the hybridization of memetic algorithms with branch-and-bound techniques.

Branch-and-bound (BnB) and memetic algorithms represent two very different approaches for tackling combinatorial optimization problems. However, these approaches are compatible. In this correspondence, a hybrid model that combines these two techniques is considered. To be precise, it is based on the interleaved execution of both approaches. Since the requirements of time and memory in BnB techniques are generally conflicting, a truncated exact search, namely, beam search, has opted to be carried out. Therefore, the resulting hybrid algorithm has a heuristic nature. The multidimensional 0-1 knapsack problem and the shortest common supersequence problem have been chosen as benchmarks. As will be shown, the hybrid algorithm can produce better results in both problems at the same computational cost, especially for large problem instances.     

A comparative analysis of evolutionary and memetic algorithms for community detection from signed social networks

To detect communities in signed networks consisting of both positive and negative links, two new evolutionary algorithms (EAs) and two new memetic algorithms (MAs) are proposed and compared. Furthermore, two measures, namely the improved modularity Q and the improved modularity density D-value, are used as the objective functions. The improved measures not only preserve all properties of the original ones, but also have the ability of dealing with negative links. Moreover, D-value can also control the partition to different resolutions. To fully investigate the performance of these four algorithms and the two objective functions, benchmark social networks and various large-scale randomly generated signed networks are used in the experiments. The experimental results not only show the capability and high efficiency of the four algorithms in successfully detecting communities from signed networks, but also indicate that the two MAs outperform the two EAs in terms of the solution quality and the computational cost. Moreover, by tuning the parameter in D-value, the four algorithms have the multi-resolution ability.     

The impact of parametrization in memetic evolutionary algorithms

Memetic (evolutionary) algorithms integrate local search into the search process of evolutionary algorithms. As computational resources have to be spread adequately among local and evolutionary search, one has to care about when to apply local search and how much computational effort to devote to local search. Often local search is called with a fixed frequency and run for a fixed number of iterations, the local search depth. There is empirical evidence that these parameters have a significant impact on performance, but a theoretical understanding as well as concrete design guidelines are missing.     

Low bit depth representation motion estimation algorithms: a comparative study

A comparative study of low complexity motion estimation algorithms is presented. The algorithms included in the study are the 1-bit transform, the 2-bit transform, the constrained 1-bit transform and the multiplication free 1-bit transform which are using different motion estimation strategies compared to standard exhaustive search algorithm-mean absolute difference or similar combinations. These techniques provide better performance in terms of computational load compared to traditional algorithms. Although the accuracy of motion compensation is only slightly lower comparing to the other techniques, results in terms of objective quality (peak signal-to-noise ratio) and entropy are comparable. This fact, nominates them as suitable candidates for inclusion in embedded devices applications where lower complexity translates to lower power consumption and consequently improved device autonomy.     

A comparative study of staff removal algorithms

This paper presents a quantitative comparison of different algorithms for the removal of stafflines from music images. It contains a survey of previously proposed algorithms and suggests a new skeletonization based approach. We define three different error metrics, compare the algorithms with respect to these metrics and measure their robustness with respect to certain image defects. Our test images are computer-generated scores on which we apply various image deformations typically found in real-world data. In addition to modern western music notation our test set also includes historic music notation such as mensural notation and lute tablature. Our general approach and evaluation methodology is not specific to staff removal, but applicable to other segmentation problems as well.     

A comparative study of image processing algorithms

We compared the performances of the well-known image processing algorithms run on a set of reference images. For this, the algorithm-distorted images are compared against “ground truth” images.     

How landscape ruggedness influences the performance of real-coded algorithms: a comparative study

Ruggedness has a strong influence on the performance of algorithms, but it has been barely studied in real-coded optimization, mainly because of the difficulty of isolating it from a number of involved topological properties. In this paper, we propose a framework consisting of increasing ruggedness function sets built by a mechanism which generates multiple funnels. This mechanism introduces different levels of sinusoidal distortion which can be controlled to isolate the singular influence of some related features. Some commonly used measures of ruggedness have been applied to analyze these sets of functions, and a numerical study to compare the performance of some representative algorithms has been carried out. The results confirm that ruggedness has an influence on the performance of the algorithm, proving that it depends on the multi-funnel structure and peak features, such as height and relative size of the global peak, and not on the number of peaks.     

Use of biased neighborhood structures in multiobjective memetic algorithms

In this paper, we examine the use of biased neighborhood structures for local search in multiobjective memetic algorithms. Under a biased neighborhood structure, each neighbor of the current solution has a different probability to be sampled in local search. In standard local search, all neighbors of the current solution usually have the same probability because they are randomly sampled. On the other hand, we assign larger probabilities to more promising neighbors in order to improve the search ability of multiobjective memetic algorithms. In this paper, we first explain our multiobjective memetic algorithm, which is a simple hybrid algorithm of NSGA-II and local search. Then we explain its variants with biased neighborhood structures for multiobjective 0/1 knapsack and flowshop scheduling problems. Finally we examine the performance of each variant through computational experiments. Experimental results show that the use of biased neighborhood structures clearly improves the performance of our multiobjective memetic algorithm.     

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.     

Practical fusion algorithms for rotation matrices: A comparative study

Many computer vision, sensor fusion, and robotic applications require the estimation of a 3 × 3 rotation matrix from a set of measured or computed 3 × 3 noisy rotation matrices. This article classifies solution methods into three categories: nonlinear least squares, linear optimal, and linear suboptimal algorithms. Their performance is compared through simulation studies. It is shown that the linear suboptimal algorithms proposed in this article have an accuracy comparable to that of the optimal algorithms and are about five times faster. Furthermore, a particular nonlinear optimization algorithm is presented that has computational complexity similar to that of the linear optimal procedures. © 1992 John Wiley & Sons, Inc.     

On shortest-path algorithms in the topological design of computer networks: a comparative study

Built into several heuristics available for the topological design of computer networks, and inherent in the multicommodity nature of flow, is the determination of the shortest paths between pairs of nodes. Owing to the repeated requirement for shortest-path analyses during the course of optimization, the computational complexity of the heuristics depends upon the computational complexity of the shortest-path problem. This paper studies critically six shortest-path algorithms which are considered to be highly efficient and elegant, and presents a comparison of their computational complexity, simplicity, accessibility, applicability, capacity and speed.     

Antiviral therapy using a fuzzy controller optimized by modified evolutionary algorithms: a comparative study

Hepatitis is usually caused by a viral infection or metabolic diseases. Hepatitis type B virus (HBV) infection is among the most common causes of hepatitis and can result in serious liver diseases. Several dynamic models have been developed to mathematically describe the HBV infection and antiviral therapy. In addition, different control strategies have been reported in the literature to deal with optimal antiviral therapy problem of infectious diseases. In this paper, a set of optimized closed-loop fuzzy controllers are employed for optimal treatment of basic HBV infection. To optimize the proposed scheme, five modified and modern optimization algorithms are investigated. After designing the controller, some parameters of the HBV infection model are considered to be unknown, and the robustness of the optimized controller is studied. Experimental results show that the covariance matrix adaptation–evolution strategy-based optimized closed-loop fuzzy controller has the best performance in terms of total cost of an objective function defined based on maximization of uninfected target cells, minimization of free HBVs and minimization of drug usage. In addition, the execution time of this optimization algorithm is only 8 % more than the execution time of imperialist competition algorithm as the investigated algorithm with the best convergence speed.     

A Study on the use of ``self-generation' in memetic algorithms

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).     

Classification algorithms for interactive multimedia services: a review

Interactive multimedia services, which integrate and unify techniques from a variety of disciplines, have been an active research topic for many years. However, two major challenges need to be overcome to provide a better service: The first is that interactive multimedia systems have to provide the contents a user needs at the right time no matter where the user is located and what device the user is using; the second is that the performance of such systems needs to be improved. Apparently, classification and clustering (also called unsupervised classification) algorithms play an indispensable role in these respects. Thus, this paper contains a review of the classification algorithms for interactive multimedia systems. Also discussed in this paper are several important issues, open questions, and trends.     

The design of PID controllers for a Gryphon robot using four evolutionary algorithms: a comparative study

This paper compares performances of PID controllers designed for a Gryphon robot joints using four hybrid evolutionary algorithms. We try to reduce the transient state of the step response. To this end, a function of some specifications of the step response (i.e. overshoot, settling time, rise time and the steady state error) is defined. We minimize this function by using four approaches, i.e. Particle swarm optimization (PSO) algorithm, the queen-bee (QB) algorithm, the genetic algorithm (GA) (all hybridized with the Nelder-Mead (NM) algorithm), and the shuffled complex evolution (SCE), and the results are compared. For designing a PID controller we should test several methods and based on the obtained results we can select one of them as the best method. In our case, the queen-bee for joints 1, 2, and 4, the genetic algorithm for joint 3, and the shuffled complex evolution method for joint 5 produce better results.     

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.