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

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Chapitre › Revue par des pairs

Résumé

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.

langue originale	Anglais
titre	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
rédacteurs en chef	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
Editeur	Springer Verlag
Pages	21-30
Nombre de pages	10
ISBN (imprimé)	3540230920, 9783540230922
Les DOIs	https://doi.org/10.1007/978-3-540-30217-9_3
état	Publié - 1 janv. 2004
Modification externe	Oui

Série de publications

Nom	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3242
ISSN (imprimé)	0302-9743
ISSN (Electronique)	1611-3349

Accès au document

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

Autres fichiers et liens

Lien vers la publication dans Scopus

Contient cette citation

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. Dans 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) (p. 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). Editeur / 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)).

@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. Dans 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, p. 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).

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Chapitre › Revue par des pairs

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.

UR - https://www.scopus.com/pages/publications/35048866845

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. Dans Yao X, Bullinaria JA, Rowe J, Tino P, Kaban A, Burke E, Lozano JA, Smith J, Merelo-Guervos JJ, Schwefel HP, rédacteurs en chef, 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

Résumé

Série de publications

Accès au document

Autres fichiers et liens

Empreinte digitale

Contient cette citation