MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

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
Conference URL::
http://events.cs.bham.ac.uk/foci07/
Downloading URL:
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
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 13:58:05
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

File Attachment Icon
foci2007.pdf