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