Experimental supplements to the theoretical analysis of EAs on problems from combinatorial optimization

Patrick Briest; Dimo Brockhoff; Bastian Degener; Matthias Englert; Christian Gunia; Oliver Heering; Thomas Jansen; Michael Leifhelm; Kai Plociennik; Heiko Röglin; Andrea Schweer; Dirk Sudholt; Stefan Tannenbaum; Ingo Wegener

doi:10.1007/978-3-540-30217-9_3

Experimental supplements to the theoretical analysis of EAs on problems from combinatorial optimization

Patrick Briest
, Dimo Brockhoff
, Bastian Degener
, Matthias Englert
, Christian Gunia
, Oliver Heering
, Thomas Jansen
, Michael Leifhelm
, Kai Plociennik
, Heiko Röglin
, Andrea Schweer
, Dirk Sudholt
, Stefan Tannenbaum
, Ingo Wegener

University of Dortmund

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

Abstract

It is typical for the EA community that theory follows experiments. Most theoretical approaches use some model of the considered evolutionary algorithm (EA) but there is also some progress where the expected optimization time of EAs is analyzed rigorously. There are only three well-known problems of combinatorial optimization where such an approach has been performed for general input instances, namely minimum spanning trees, shortest paths, and maximum matchings. The theoretical results are asymptotic ones and several questions for realistic dimensions of the search space are open. We supplement the theoretical results by experimental ones. Many hypotheses are confirmed by rigorous statistical tests.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Xin Yao, John A. Bullinaria, Jonathan Rowe, Peter Tino, Ata Kaban, Edmund Burke, Jose A. Lozano, Jim Smith, Juan J. Merelo-Guervos, Hans-Paul Schwefel
Publisher	Springer Verlag
Pages	21-30
Number of pages	10
ISBN (Print)	3540230920, 9783540230922
DOIs	https://doi.org/10.1007/978-3-540-30217-9_3
Publication status	Published - 1 Jan 2004
Externally published	Yes

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3242
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Access to Document

10.1007/978-3-540-30217-9_3

Cite this

Briest, P., Brockhoff, D., Degener, B., Englert, M., Gunia, C., Heering, O., Jansen, T., Leifhelm, M., Plociennik, K., Röglin, H., Schweer, A., Sudholt, D., Tannenbaum, S., & Wegener, I. (2004). Experimental supplements to the theoretical analysis of EAs on problems from combinatorial optimization. In X. Yao, J. A. Bullinaria, J. Rowe, P. Tino, A. Kaban, E. Burke, J. A. Lozano, J. Smith, J. J. Merelo-Guervos, & H.-P. Schwefel (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 21-30). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3242). Springer Verlag. https://doi.org/10.1007/978-3-540-30217-9_3

Briest, Patrick ; Brockhoff, Dimo ; Degener, Bastian et al. / Experimental supplements to the theoretical analysis of EAs on problems from combinatorial optimization. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Xin Yao ; John A. Bullinaria ; Jonathan Rowe ; Peter Tino ; Ata Kaban ; Edmund Burke ; Jose A. Lozano ; Jim Smith ; Juan J. Merelo-Guervos ; Hans-Paul Schwefel. Springer Verlag, 2004. pp. 21-30 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{9b593207270e4a29ac46e75ae29c32db,

title = "Experimental supplements to the theoretical analysis of EAs on problems from combinatorial optimization",

abstract = "It is typical for the EA community that theory follows experiments. Most theoretical approaches use some model of the considered evolutionary algorithm (EA) but there is also some progress where the expected optimization time of EAs is analyzed rigorously. There are only three well-known problems of combinatorial optimization where such an approach has been performed for general input instances, namely minimum spanning trees, shortest paths, and maximum matchings. The theoretical results are asymptotic ones and several questions for realistic dimensions of the search space are open. We supplement the theoretical results by experimental ones. Many hypotheses are confirmed by rigorous statistical tests.",

author = "Patrick Briest and Dimo Brockhoff and Bastian Degener and Matthias Englert and Christian Gunia and Oliver Heering and Thomas Jansen and Michael Leifhelm and Kai Plociennik and Heiko R{\"o}glin and Andrea Schweer and Dirk Sudholt and Stefan Tannenbaum and Ingo Wegener",

year = "2004",

month = jan,

day = "1",

doi = "10.1007/978-3-540-30217-9\_3",

language = "English",

isbn = "3540230920",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "21--30",

editor = "Xin Yao and Bullinaria, \{John A.\} and Jonathan Rowe and Peter Tino and Ata Kaban and Edmund Burke and Lozano, \{Jose A.\} and Jim Smith and Merelo-Guervos, \{Juan J.\} and Hans-Paul Schwefel",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

Briest, P, Brockhoff, D, Degener, B, Englert, M, Gunia, C, Heering, O, Jansen, T, Leifhelm, M, Plociennik, K, Röglin, H, Schweer, A, Sudholt, D, Tannenbaum, S & Wegener, I 2004, Experimental supplements to the theoretical analysis of EAs on problems from combinatorial optimization. in X Yao, JA Bullinaria, J Rowe, P Tino, A Kaban, E Burke, JA Lozano, J Smith, JJ Merelo-Guervos & H-P Schwefel (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3242, Springer Verlag, pp. 21-30. https://doi.org/10.1007/978-3-540-30217-9_3

Experimental supplements to the theoretical analysis of EAs on problems from combinatorial optimization. / Briest, Patrick; Brockhoff, Dimo; Degener, Bastian et al.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Xin Yao; John A. Bullinaria; Jonathan Rowe; Peter Tino; Ata Kaban; Edmund Burke; Jose A. Lozano; Jim Smith; Juan J. Merelo-Guervos; Hans-Paul Schwefel. Springer Verlag, 2004. p. 21-30 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3242).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

TY - CHAP

T1 - Experimental supplements to the theoretical analysis of EAs on problems from combinatorial optimization

AU - Briest, Patrick

AU - Brockhoff, Dimo

AU - Degener, Bastian

AU - Englert, Matthias

AU - Gunia, Christian

AU - Heering, Oliver

AU - Jansen, Thomas

AU - Leifhelm, Michael

AU - Plociennik, Kai

AU - Röglin, Heiko

AU - Schweer, Andrea

AU - Sudholt, Dirk

AU - Tannenbaum, Stefan

AU - Wegener, Ingo

PY - 2004/1/1

Y1 - 2004/1/1

N2 - It is typical for the EA community that theory follows experiments. Most theoretical approaches use some model of the considered evolutionary algorithm (EA) but there is also some progress where the expected optimization time of EAs is analyzed rigorously. There are only three well-known problems of combinatorial optimization where such an approach has been performed for general input instances, namely minimum spanning trees, shortest paths, and maximum matchings. The theoretical results are asymptotic ones and several questions for realistic dimensions of the search space are open. We supplement the theoretical results by experimental ones. Many hypotheses are confirmed by rigorous statistical tests.

AB - It is typical for the EA community that theory follows experiments. Most theoretical approaches use some model of the considered evolutionary algorithm (EA) but there is also some progress where the expected optimization time of EAs is analyzed rigorously. There are only three well-known problems of combinatorial optimization where such an approach has been performed for general input instances, namely minimum spanning trees, shortest paths, and maximum matchings. The theoretical results are asymptotic ones and several questions for realistic dimensions of the search space are open. We supplement the theoretical results by experimental ones. Many hypotheses are confirmed by rigorous statistical tests.

U2 - 10.1007/978-3-540-30217-9_3

DO - 10.1007/978-3-540-30217-9_3

M3 - Chapter

AN - SCOPUS:35048866845

SN - 3540230920

SN - 9783540230922

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 21

EP - 30

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Yao, Xin

A2 - Bullinaria, John A.

A2 - Rowe, Jonathan

A2 - Tino, Peter

A2 - Kaban, Ata

A2 - Burke, Edmund

A2 - Lozano, Jose A.

A2 - Smith, Jim

A2 - Merelo-Guervos, Juan J.

A2 - Schwefel, Hans-Paul

PB - Springer Verlag

ER -

Briest P, Brockhoff D, Degener B, Englert M, Gunia C, Heering O et al. Experimental supplements to the theoretical analysis of EAs on problems from combinatorial optimization. In Yao X, Bullinaria JA, Rowe J, Tino P, Kaban A, Burke E, Lozano JA, Smith J, Merelo-Guervos JJ, Schwefel HP, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2004. p. 21-30. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-30217-9_3

Experimental supplements to the theoretical analysis of EAs on problems from combinatorial optimization

Abstract

Publication series

Access to Document

Fingerprint

Cite this