Hard Test Generation for Maximum Flow Algorithms with the Fast Crossover-Based Evolutionary Algorithm

Vladimir Mironovich; Maxim Buzdalov

doi:10.1145/2739482.2768487

Hard Test Generation for Maximum Flow Algorithms with the Fast Crossover-Based Evolutionary Algorithm

Vladimir Mironovich, Maxim Buzdalov

ITMO University

Allbwn ymchwil: Pennod mewn Llyfr/Adroddiad/Trafodion Cynhadledd › Trafodion Cynhadledd (ISBN)

10 Dyfyniadau (Scopus)

Crynodeb

Most evolutionary algorithms not only throw out insufficiently good solutions, but forget all information they obtained from their evaluation, which reduces their speed from the information theory point of view. An evolutionary algorithm which does not do that, the 1+(λ,β) EA was recently proposed by Doerr, Doerr and Ebel. We evaluate this algorithm on the problem of finding hard tests for maximum flow algorithms. Experiments show that the 1+(λ,β) EA is never the best, but is quite stable. However, its adaptive version, known for being superior for the OneMax problem, is shown to be one of the worst.

Iaith wreiddiol	Saesneg
Teitl	GECCO Companion '15
Is-deitl	Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation
Golygyddion	Sara Silva
Cyhoeddwr	Association for Computing Machinery
Tudalennau	1229-1232
Nifer y tudalennau	4
ISBN (Argraffiad)	978-1-4503-3488-4
Dynodwyr Gwrthrych Digidol (DOIs)	https://doi.org/10.1145/2739482.2768487
Statws	Cyhoeddwyd - 11 Gorff 2015
Cyhoeddwyd yn allanol	Ie
Digwyddiad	16th Genetic and Evolutionary Computation Conference, GECCO 2015 - Madrid, Sbaen Hyd: 11 Gorff 2015 → 15 Gorff 2015

Cynhadledd

Cynhadledd	16th Genetic and Evolutionary Computation Conference, GECCO 2015
Gwlad/Tiriogaeth	Sbaen
Dinas	Madrid
Cyfnod	11 Gorff 2015 → 15 Gorff 2015

Mynediad at Ddogfen

10.1145/2739482.2768487

Cysylltiad parhaol

Dolen barhaus

Ffeiliau eraill a chysylltiadau

https://www.scopus.com/pages/publications/84959376337

Dyfynnu hyn

Mironovich, V., & Buzdalov, M. (2015). Hard Test Generation for Maximum Flow Algorithms with the Fast Crossover-Based Evolutionary Algorithm. Yn S. Silva (Gol.), GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation (tt. 1229-1232). Association for Computing Machinery. https://doi.org/10.1145/2739482.2768487

@inproceedings{2b20a88fe92d4a3cb979d2c4c11b7c7f,

title = "Hard Test Generation for Maximum Flow Algorithms with the Fast Crossover-Based Evolutionary Algorithm",

abstract = "Most evolutionary algorithms not only throw out insufficiently good solutions, but forget all information they obtained from their evaluation, which reduces their speed from the information theory point of view. An evolutionary algorithm which does not do that, the 1+(λ,β) EA was recently proposed by Doerr, Doerr and Ebel. We evaluate this algorithm on the problem of finding hard tests for maximum flow algorithms. Experiments show that the 1+(λ,β) EA is never the best, but is quite stable. However, its adaptive version, known for being superior for the OneMax problem, is shown to be one of the worst.",

keywords = "black-box complexity, evolutionary algorithms, test generation, worst-case execution time",

author = "Vladimir Mironovich and Maxim Buzdalov",

year = "2015",

month = jul,

day = "11",

doi = "10.1145/2739482.2768487",

language = "English",

isbn = "978-1-4503-3488-4",

pages = "1229--1232",

editor = "Sara Silva",

booktitle = "GECCO Companion '15",

publisher = "Association for Computing Machinery",

address = "United States of America",

note = "16th Genetic and Evolutionary Computation Conference, GECCO 2015 ; Conference date: 11-07-2015 Through 15-07-2015",

}

Mironovich, V & Buzdalov, M 2015, Hard Test Generation for Maximum Flow Algorithms with the Fast Crossover-Based Evolutionary Algorithm. yn S Silva (gol.), GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation. Association for Computing Machinery, tt. 1229-1232, 16th Genetic and Evolutionary Computation Conference, GECCO 2015, Madrid, Sbaen, 11 Gorff 2015. https://doi.org/10.1145/2739482.2768487

Hard Test Generation for Maximum Flow Algorithms with the Fast Crossover-Based Evolutionary Algorithm. / Mironovich, Vladimir; Buzdalov, Maxim.
GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation. gol. / Sara Silva. Association for Computing Machinery, 2015. t. 1229-1232.

Allbwn ymchwil: Pennod mewn Llyfr/Adroddiad/Trafodion Cynhadledd › Trafodion Cynhadledd (ISBN)

TY - GEN

T1 - Hard Test Generation for Maximum Flow Algorithms with the Fast Crossover-Based Evolutionary Algorithm

AU - Mironovich, Vladimir

AU - Buzdalov, Maxim

PY - 2015/7/11

Y1 - 2015/7/11

N2 - Most evolutionary algorithms not only throw out insufficiently good solutions, but forget all information they obtained from their evaluation, which reduces their speed from the information theory point of view. An evolutionary algorithm which does not do that, the 1+(λ,β) EA was recently proposed by Doerr, Doerr and Ebel. We evaluate this algorithm on the problem of finding hard tests for maximum flow algorithms. Experiments show that the 1+(λ,β) EA is never the best, but is quite stable. However, its adaptive version, known for being superior for the OneMax problem, is shown to be one of the worst.

AB - Most evolutionary algorithms not only throw out insufficiently good solutions, but forget all information they obtained from their evaluation, which reduces their speed from the information theory point of view. An evolutionary algorithm which does not do that, the 1+(λ,β) EA was recently proposed by Doerr, Doerr and Ebel. We evaluate this algorithm on the problem of finding hard tests for maximum flow algorithms. Experiments show that the 1+(λ,β) EA is never the best, but is quite stable. However, its adaptive version, known for being superior for the OneMax problem, is shown to be one of the worst.

KW - black-box complexity

KW - evolutionary algorithms

KW - test generation

KW - worst-case execution time

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

U2 - 10.1145/2739482.2768487

DO - 10.1145/2739482.2768487

M3 - Conference Proceeding (ISBN)

SN - 978-1-4503-3488-4

SP - 1229

EP - 1232

BT - GECCO Companion '15

A2 - Silva, Sara

PB - Association for Computing Machinery

T2 - 16th Genetic and Evolutionary Computation Conference, GECCO 2015

Y2 - 11 July 2015 through 15 July 2015

ER -

Hard Test Generation for Maximum Flow Algorithms with the Fast Crossover-Based Evolutionary Algorithm

Crynodeb

Cynhadledd

Mynediad at Ddogfen

Cysylltiad parhaol

Ffeiliau eraill a chysylltiadau

Ôl bys

Dyfynnu hyn