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

Research output: Chapter in Book/Report/Conference proceeding › Conference Proceeding (Non-Journal item)

10 Citations (Scopus)

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.

Original language	English
Title of host publication	GECCO Companion '15
Subtitle of host publication	Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation
Editors	Sara Silva
Publisher	Association for Computing Machinery
Pages	1229-1232
Number of pages	4
ISBN (Print)	978-1-4503-3488-4
DOIs	https://doi.org/10.1145/2739482.2768487
Publication status	Published - 11 Jul 2015
Externally published	Yes
Event	16th Genetic and Evolutionary Computation Conference, GECCO 2015 - Madrid, Spain Duration: 11 Jul 2015 → 15 Jul 2015

Conference

Conference	16th Genetic and Evolutionary Computation Conference, GECCO 2015
Country/Territory	Spain
City	Madrid
Period	11 Jul 2015 → 15 Jul 2015

Keywords

black-box complexity
evolutionary algorithms
test generation
worst-case execution time

Access to Document

10.1145/2739482.2768487

Permanent link

Persistent link

Cite this

Mironovich, V., & Buzdalov, M. (2015). Hard Test Generation for Maximum Flow Algorithms with the Fast Crossover-Based Evolutionary Algorithm. In S. Silva (Ed.), GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation (pp. 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. in S Silva (ed.), GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation. Association for Computing Machinery, pp. 1229-1232, 16th Genetic and Evolutionary Computation Conference, GECCO 2015, Madrid, Spain, 11 Jul 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. ed. / Sara Silva. Association for Computing Machinery, 2015. p. 1229-1232.

Research output: Chapter in Book/Report/Conference proceeding › Conference Proceeding (Non-Journal item)

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/record/display.uri?eid=2-s2.0-84959376337&origin=resultslist

U2 - 10.1145/2739482.2768487

DO - 10.1145/2739482.2768487

M3 - Conference Proceeding (Non-Journal item)

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

Abstract

Conference

Keywords

Access to Document

Permanent link

Other files and links

Fingerprint

Cite this