Document Detail


Estimating Meme Fitness in Adaptive Memetic Algorithms for Combinatorial Problems.
MedLine Citation:
PMID:  22129225     Owner:  NLM     Status:  Publisher    
Abstract/OtherAbstract:
Abstract Among the most promising and active research areas in heuristic optimisation is the field of Adaptive Memetic Algorithms. 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 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: one 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. 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. This contradicts recent findings from adapting the parameters of operators involved in global evolutionary search. 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.
Authors:
J E Smith
Related Documents :
22520935 - Statistical properties of interval mapping methods on quantitative trait loci location:...
22683275 - Making decisions through a distributed consensus.
22793785 - Guidance for a personal target value of feno in allergic asthma: case report and theore...
19233695 - The global prevalence of glucose-6-phosphate dehydrogenase deficiency: a systematic rev...
22337635 - A practical comparison of blinded methods for sample size reviews in survival data clin...
18808435 - Estimating fitness consequences of dispersal: a road to 'know-where'? non-random disper...
Publication Detail:
Type:  JOURNAL ARTICLE     Date:  2011-11-30
Journal Detail:
Title:  Evolutionary computation     Volume:  -     ISSN:  1530-9304     ISO Abbreviation:  -     Publication Date:  2011 Nov 
Date Detail:
Created Date:  2011-12-1     Completed Date:  -     Revised Date:  -    
Medline Journal Info:
Nlm Unique ID:  9513581     Medline TA:  Evol Comput     Country:  -    
Other Details:
Languages:  ENG     Pagination:  -     Citation Subset:  -    
Affiliation:
Department of Computer Science and Creative Technologies, University of the West of England, BS16 1QY, U.K. james.smith@uwe.ac.uk.
Export Citation:
APA/MLA Format     Download EndNote     Download BibTex
MeSH Terms
Descriptor/Qualifier:

From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine


Previous Document:  Seagrass as a potential source of natural antioxidant and anti-inflammatory agents.
Next Document:  Use of Raman spectroscopy and chemometrics for the quantification of metal ions attached to Lactobac...