Hard test generation for augmenting path maximum flow algorithms using genetic algorithms: Revisited

Maxim Buzdalov, A. A. Shalyto

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

Abstract


To estimate performance of computer science algorithms reliably, one has to create worst-case execution time tests. For certain algorithms this task can be difficult. To reduce the amount of human effort, authors attempt using search-based optimization techniques, such as genetic algorithms. Our previous paper addressed test generation for several maximum flow algorithms. Genetic algorithms were applied for test generation and showed promising results. However, one of the aspects of maximum flow algorithm implementation was missing in that paper: parallel edges (edges which share source and target vertices) were not merged into one single edge (which is allowed in solving maximum flow problems). In this paper, parallel edge merging is implemented and new results are reported. A surprising fact is shown that fitness functions and choices of genetic operators which were the most efficient in the previous paper are much less efficient in the new setup and vice versa. What is more, the set of maximum flow algorithms, for which significantly better tests are generated, changed completely as well.
Original languageEnglish
Title of host publication2015 IEEE Congress on Evolutionary Computation (CEC)
Subtitle of host publicationProceedings
PublisherIEEE Press
Pages2121-2128
Number of pages8
ISBN (Electronic)978-1-4799-7492-4
DOIs
Publication statusPublished - 14 Sept 2015
Externally publishedYes
EventIEEE Congress on Evolutionary Computation, CEC 2015 - Sendai, Japan
Duration: 25 May 201528 May 2015

Conference

ConferenceIEEE Congress on Evolutionary Computation, CEC 2015
Country/TerritoryJapan
CitySendai
Period25 May 201528 May 2015

Fingerprint

Dive into the research topics of 'Hard test generation for augmenting path maximum flow algorithms using genetic algorithms: Revisited'. Together they form a unique fingerprint.

Cite this