45324898
A Memetic Algorithm With Self-Adaptive Local Search: TSP as a case study
In this paper we introduce a promising hybridization scheme for a Memetic Algorithm (MA). Our MA is composed of two optimization processes, a Genetic Algorithm and a Monte Carlo method (MC). In contrast with other GA-Monte Carlo hybridized memetic algorithms, in our work the MC stage serves two purposes: 
 
• when the population is diverse it acts like a local search procedure and 
 
• when the population converges its goal is to diversify the search. 
 
To achieve this, the MC is self-adaptive based on observations from the underlying GA behavior; the GA controls the long-term optimization process. 
 
We present preliminary, yet statistically significant, results on the application of this approach to the TSP problem. We also comment it successful application to a molecular conformational problem: Protein Folding. 
 
Paper Category: Genetic Scheduling and TSP
17502763
Alignment Of Protein Structures With A Memetic Evolutionary Algorithm
CATEGORY: Real-World Applications 
 
Structural comparison of proteins is a core problem in modern biomedical research. Identifying structural similarities is essential for the assessment of the relationship between structure and function in proteins, and structural comparison techniques play a key role in applications like rational drug design. In this paper we consider a technique for protein structure comparison known as the maximum contact map overlap problem. In this problem, the similarity between two protein structures is computed by aligning the proteins to maximize the number of shared contacts in their corresponding contact maps. 
 
We present a new approach to this problem that uses a Multimeme evolutionary algorithm. The best solution found by our algorithm provides a lower bound on the value of the optimal structural alignment between the proteins. We have evaluated the Multimeme algorithm on a range of benchmark problems and compared with previous heuristics. We apply a linear programming method, which provides an upper bound, to assess the accuracy of our solutions. Our experiments show that the Multimeme evolutionary algorithm represents a significant improvement on the current state of the art in metaheuristics for this problem.
3062981
Recombination strategy adaptation via evolution of gene linkage
Analyses recombination strategies resulting from evolving gene linkage on a variety of fitness landscapes with known properties. The evolution of "blocks" of linked genes within a gene-pool makes it possible for the recombination strategy to vary in both the amount of genetic material exchanged during the formation of a new individual and in the number of parents contributing genetic material. The strategies evolved are examined in the light of the known properties of the landscapes. The results obtained explain the previously recorded good performance of the algorithm as a self-adaptive mechanism for function optimisation, as the amount and type of recombination is able to adapt to suit the landscape being searched, unlike conventional "fixed" operators.
796697
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.
16182080
Self adaptation of mutation rates in a steady state genetic algorithm
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.
17447930
Incorporation of adaptive mutation based on subjective evaluation in an interactive evolution strategy
A rapidly emerging model in the field of adaptive computing is the symbiosis of human expertise with evolutionary algorithms for user controlled and directed search. The two aspects in any EA are the selection of individuals to reproduce based on some measure of their quality or fitness and the application of variation operators to produce new solutions. In the context of interactive evolution, these aspects are compounded by the need for rapid convergence to prevent user fatigue and to provide the user some control over the generation of new solutions. Elsewhere, in the work of the authors (2004), we have examined different policies for best incorporating the user into the evaluation and selection process. In this paper, we explore the hypothesis that user assigned fitness represents a source of information that can be used to control the variation process: effectively to broaden the search if none of the current solutions is promising, or focus the search and improve convergence speed in the vicinity of a good solution. The main aims of this study, therefore, are to analyse the advantages of using a user directed adaptive mutation strategy over fixed mutation step sizes in terms of time to converge and robustness of the resulting solution. We present results showing a qualitatively different type of search process can be obtained by using the user assigned fitness to control the nature of the mutation process. There is also a synergy between user-based selection and fitness-based mutation control which out performs either system on its own.
13476763
CPU/power-constrained mobile devices
Due to the limited processing capability, memory constraints, and the power budget of mobile clients, multimedia coders and/or decoders are often difficult to implement on wireless handheld PDAs. In this Universal Tuner project, we designed and implemented a wireless video streaming system that transcodes MPEG-1/2 videos or live TV broadcasting videos to the BW or indexed color Palm OS devices. In our system, the complexity of multimedia compression and decompression algorithms is adaptively partitioned between the encoder and decoder. A mobile client would selectively disable or reenable stages of the algorithm to adapt to the device's effective processing capability. Our variable-complexity strategy of selective disabling of modules supports graceful degradation of the complexity of multimedia coding and decoding into a mobile client's low-power mode, i.e. the clock frequency of its next-generation low power CPU has been scaled down to conserve power. We modified the structure of the standard motion-compensated DCT video codecs to implement a simplified the encoder on a PC server and the decoder on a complexity-constrained PDA viewing client.
45728102
Causal Identification in Design Networks
When planning and designing a policy intervention and evaluation, the policy maker will have to define a strategy which will define the (conditional independence) structure of the available data. Here, Dawid’s extended influence diagrams are augmented by including ‘experimental design’ decisions nodes within the set of intervention strategies to provide semantics to discuss how a ‘design’ decision strategy (such as randomisation) might assist the systematic identification of intervention causal effects. By introducing design decision nodes into the framework, the experimental design underlying the data available is made explicit. We show how influence diagrams might be used to discuss the efficacy of different designs and conditions under which one can identify ‘causal’ effects of a future policy intervention. The approach of this paper lies primarily within probabilistic decision theory.
17484895
Sequential processing for content-based retrieval of composite objects
It is becoming increasingly important for multimedia databases to provide capabilities for content-based retrieval of composite objects. Composite objects consist of several simple objects which have feature, spatial, temporal, semantic attributes, and spatial and temporal relationships between them. A content-based composite object query is satisfied by evaluating a program of content-based rules (i.e., color, texture), spatial and temporal rules (i.e., east, west), fuzzy conjunctions (i.e., appears similar AND is spatially near) and database lookups (i.e., semantics). We propose a new sequential processing method for efficiently computing content-based queries of composite objects. The proposed method evaluates the composite object queries by (1) defining an efficient ordering of the sub-goals of the query, which involve spatial, temporal, content-based and fuzzy rules, (2) developing a query block management strategy for generating, evaluating, and caching intermediate sub-goal results, and (3) conducting a best-first dynamic programming-based search with intelligent back-tracking. The method is guaranteed to find the optimal answer to the query and reduces the query time by avoiding the exploration of unlikely candidates.
16693115
An Experimental Performance Evaluation of Join Algorithms for Parallel Object Databases
Parallel relational databases have been successful in providing scalable performance for data intensive applications, and much work has been carried out on query processing techniques in such systems. However, although many applications associated with object databases also have stringent performance requirements, there has been much less work investigating parallel object database systems. An important feature for the performance of object databases is the speed at which relationships can be explored. In queries, this depends upon the effectiveness of different join algorithms into which queries that follow relationships can be compiled. This paper presents the results of empirical evaluations of four parallel join algorithms, two value based and two pointer based. The experiments have been run on Polar, a parallel ODMG object database system.
17174080
A memetic algorithm to schedule planned maintenance for the national grid
The combination of local search operators, problem specific information and a genetic algorithm has provided very good results in certain scheduling problems, particularly in timetabling and maintenance scheduling problems. The resulting algorithm from this hybrid approach has been termed a Memetic Algorithm. This paper investigates the use of such an algorithm for the scheduling of transmission line maintenance for a known problem that has been addressed in the literature using a combination of a genetic algorithm and greedy optimisers.This problem is concerned with the scheduling of maintenance for an electricity transmission network where every transmission line must be maintained once within a specified time period. The objective is to avoid situations where sections of the network are disconnected, and to minimise the overloading of lines which are in service.In this paper we look at scheduling maintenance for the South Wales region of the national transmission network. We present and discuss, in some detail, a memetic algorithm that incorporates local search operators including tabu search and simulated annealing. A comparison is made both with the results from previous work, and against a selection of optimising techniques.The approach presented in this paper shows a significant improvement over previously published results on previously tackled problems. We also present results on another problem which has not been tackled in the literature but which is closer to the real world maintenance scheduling problems faced by such companies as The National Grid Company plc using the South Wales region.