Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Happ, Edda
Johannsen, Daniel
Klein, Christian
Neumann, Frank

dblp
dblp
dblp
dblp



Editor(s):

Ryan, Conor
Keijzer, Maarten

dblp
dblp

Not MPII Editor(s):

Ryan, Conor
Keijzer, Maarten

BibTeX cite key*:

HappJohannsenKleinNeumann2008a

Title, Booktitle

Title*:

Rigorous Analyses of Fitness-Proportional Selection for Optimizing Linear Functions


HappJohannsenKleinNeumann_2008_RigorousAnalysesOfFitness-ProportionalSelectionForOptimizingLinearFunctions.pdf (229.06 KB)

Booktitle*:

Genetic and Evolutionary Computation Conference 2008

Event, URLs

URL of the conference:

http://www.sigevo.org/gecco-2008/index.html

URL for downloading the paper:

http://doi.acm.org/10.1145/1389095.1389277

Event Address*:

Atlanta, USA

Language:

English

Event Date*
(no longer used):


Organization:

Association for Computing Machinery (ACM)

Event Start Date:

12 July 2008

Event End Date:

16 July 2008

Publisher

Name*:

ACM

URL:

http://www.acm.org

Address*:

New York, USA

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:


Pages:

953-960

Year*:

2008

VG Wort Pages:

8

ISBN/ISSN:

978-1-60558-130-9

Sequence Number:


DOI:

http://doi.acm.org/10.1145/1389095.1389277



Note, Abstract, ©


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

URL for the Abstract:

http://doi.acm.org/10.1145/1389095.1389277

Keywords:

Running Time Analysis, Selection, Theory



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{HappJohannsenKleinNeumann2008a,
AUTHOR = {Happ, Edda and Johannsen, Daniel and Klein, Christian and Neumann, Frank},
EDITOR = {Ryan, Conor and Keijzer, Maarten},
TITLE = {Rigorous Analyses of Fitness-Proportional Selection for Optimizing Linear Functions},
BOOKTITLE = {Genetic and Evolutionary Computation Conference 2008},
PUBLISHER = {ACM},
YEAR = {2008},
ORGANIZATION = {Association for Computing Machinery (ACM)},
PAGES = {953--960},
ADDRESS = {Atlanta, USA},
ISBN = {978-1-60558-130-9},
DOI = {http://doi.acm.org/10.1145/1389095.1389277},
}


Entry last modified by Daniel Johannsen, 03/03/2009
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Edda Happ
Created
01/19/2009 11:33:31 AM
Revisions
2.
1.
0.

Editor(s)
Daniel Johannsen
Edda Happ
Edda Happ

Edit Dates
02/15/2009 08:18:06 PM
01/19/2009 12:58:46 PM
01/19/2009 11:33:31 AM

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
HappJohannsenKleinNeumann_2008_RigorousAnalysesOfFitness-ProportionalSelectionForOptimizingLinearFunctions.pdf