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):

Doerr, Benjamin
Klein, Christian
Storch, Tobias

dblp
dblp
dblp

Not MPG Author(s):

Storch, Tobias

Editor(s):





BibTeX cite key*:

bks07

Title, Booktitle

Title*:

Faster Evolutionary Algorithms by Superior Graph Representation


foci2007.pdf (135.34 KB)

Booktitle*:

First IEEE Symposium on Foundations of Computational Intelligence (FOCI-2007)

Event, URLs

URL of the conference:

http://events.cs.bham.ac.uk/foci07/

URL for downloading the paper:


Event Address*:

Honolulu, USA

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

1 April 2007

Event End Date:

5 April 2007

Publisher

Name*:

IEEE

URL:

http://www.ieee.org/

Address*:

Washington, D.C.

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:


Pages:

245-250

Year*:

2007

VG Wort Pages:

15

ISBN/ISSN:

1-424-40698-6

Sequence Number:


DOI:

10.1109/FOCI.2007.372176



Note, Abstract, ©


(LaTeX) Abstract:

We present a new representation for individuals in problems that have cyclic permutations as solutions.
To demonstrate its usefulness, we analyze a simple randomized local search and a (1+1) evolutionary algorithm for the Eulerian cycle problem utilizing this representation.
Both have an expected run-time of $\Theta(m^2 \log(m))$, where $m$ denotes the number of edges of the input graph.
This clearly beats previous solutions, which all have an expected optimization time of $\Theta(m^3)$ or worse (PPSN~'06, CEC~'04).
We are optimistic that our representation also allows superior solutions for other cyclic permutation problems.
For NP-complete ones like the TSP, however, other means than theoretical run-time analyses are necessary.



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

External Affiliations:

Department of Computer Science II, University of Dortmund, D-44221 Dortmund, Germany

Audience:

popular

Appearance:

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



BibTeX Entry:

@INPROCEEDINGS{bks07,
AUTHOR = {Doerr, Benjamin and Klein, Christian and Storch, Tobias},
TITLE = {Faster Evolutionary Algorithms by Superior Graph Representation},
BOOKTITLE = {First IEEE Symposium on Foundations of Computational Intelligence (FOCI-2007)},
PUBLISHER = {IEEE},
YEAR = {2007},
PAGES = {245--250},
ADDRESS = {Honolulu, USA},
ISBN = {1-424-40698-6},
DOI = {10.1109/FOCI.2007.372176},
}


Entry last modified by Benjamin Doerr, 01/02/2012
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)
Christian Klein
Created
02/23/2007 01:58:05 PM
Revisions
9.
8.
7.
6.
5.
Editor(s)
Benjamin Doerr
Benjamin Doerr
Anja Becker
Süntje Böttcher
Süntje Böttcher
Edit Dates
01/02/2012 02:48:47 PM
05/05/2009 12:53:13 AM
22.02.2008 13:30:31
20.01.2008 10:26:58
24.07.2007 11:43:13
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
foci2007.pdf