English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Rigorous Analyses of Fitness-Proportional Selection for Optimizing Linear Functions

Happ, E., Johannsen, D., Klein, C., & Neumann, F. (2008). Rigorous Analyses of Fitness-Proportional Selection for Optimizing Linear Functions. In M. Keijzer, G. Antoniol., C. B. Congdon, K. Deb, B. Doerr, N. Hansen, et al. (Eds.), Genetic and Evolutionary Computation Conference 2008 (pp. 953-960). New York, NY: ACM. doi:10.1145/1389095.1389277.

Item is

 

show all

Basic

hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-1CD9-9 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0028-E4EF-1
Genre: Conference Paper

Files

show Files

Locators

show

Creators

hide
 Creators:
Happ, Edda1, Author           
Johannsen, Daniel1, Author           
Klein, Christian1, Author           
Neumann, Frank1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

hide
Free keywords: -
 Abstract: Rigorous runtime analyses of evolutionary algorithms (EAs) mainly investigate algorithms that use elitist selection methods. Two algorithms commonly studied are Randomized Local Search (RLS) and the (1+1)~EA and it is well known that both optimize any linear pseudo-Boolean function on $n$ bits within an expected number of $\ensuremath{{O}}(n \log n)$ fitness evaluations. In this paper, we analyze variants of these algorithms that use fitness proportional selection. A well-known method in analyzing the local changes in the solutions of RLS is a reduction to the gambler's ruin problem. We extend this method in order to analyze the global changes imposed by the (1+1)~EA. By applying this new technique we show that with high probability using fitness proportional selection leads to an exponential optimization time for any linear pseudo-Boolean function with non-zero weights. Even worse, all solutions of the algorithms during an exponential number of fitness evaluations differ with high probability in linearly many bits from the optimal solution. Our theoretical studies are complemented by experimental investigations which confirm the asymptotic results on realistic input sizes.

Details

hide
Language(s): eng - English
 Dates: 2009-03-2520082008
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 428100
DOI: 10.1145/1389095.1389277
URI: http://doi.acm.org/10.1145/1389095.1389277
Other: Local-ID: C125756E0038A185-773559694ACCE547C1257543003A0035-HappJohannsenKleinNeumann2008a
 Degree: -

Event

hide
Title: 10th Annual Conference on Genetic and Evolutionary Computation Conference
Place of Event: Atlanta, GA, USA
Start-/End Date: 2008-07-12 - 2008-07-16

Legal Case

show

Project information

show

Source 1

hide
Title: Genetic and Evolutionary Computation Conference 2008
  Abbreviation : GECCO 2008
Source Genre: Proceedings
 Creator(s):
Keijzer, Maarten1, Editor
Antoniol., Giuliano1, Editor
Congdon, Clare Bates1, Editor
Deb, Kalyanmoy1, Editor
Doerr, Benjamin2, Editor           
Hansen, Nikolaus1, Editor
Holmes, John H.1, Editor
Hornby, Gregory S.1, Editor
Howard, Daniel1, Editor
Kennedy, James1, Editor
Kumar, Sanjeev1, Editor
Lobo, Fernando G.1, Editor
Miller, Julian Francis1, Editor
Moore, Jason1, Editor
Neumann, Frank2, Editor           
Pelikan, Martin1, Editor
Pollack, Jordan1, Editor
Sastry, Kumara1, Editor
Stanley, Kenneth1, Editor
Stoica, Adrian1, Editor
Talbi, El-Ghazali1, Editor
Wegener, Ingo1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
2 Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019            
Publ. Info: New York, NY : ACM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 953 - 960 Identifier: -