Evaluation of heavy-tailed mutation operator on maximum flow test generation problem

Vladimir Mironovich, Maxim Buzdalov

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

Abstract

The general recommendation for the mutation rate in standard-bit mutation is 1/n, which gives asymptotically optimal expected optimization times for several simple test problems. Recently, Doerr et al. have shown that such mutation rate is not ideal, and is far from optimal for multimodal problems. They proposed the heavy-tailed mutation operator fmutβ which significantly improves performance of the (1+1) evolutionary algorithm on Jump problem and yields similar speed-ups for the vertex cover problem in bipartite graphs and the matching problem in general graphs.

We evaluate the fmutβ mutation operator on the problem of hard test generation for the maximum flow algorithms. Experiments show that the fmutβ mutation operator greatly increases performance of the (1+1) evolutionary algorithm. It also achieves performance improvement, although less drastic, on a simple population based algorithm, but hinders performance of a crossover based genetic algorithm.
Original languageEnglish
Title of host publicationGECCO '17
Subtitle of host publicationProceedings of the Genetic and Evolutionary Computation Conference Companion
PublisherAssociation for Computing Machinery
Pages1423-1426
Number of pages4
ISBN (Print)978-1-4503-4939-0
DOIs
Publication statusPublished - 15 Jul 2017
Externally publishedYes
EventGECCO 2017: The Genetic and Evolutionary Computation Conference -
Duration: 15 Jul 201719 Jul 2017

Conference

ConferenceGECCO 2017
Period15 Jul 201719 Jul 2017

Keywords

  • evolutionary algorithms
  • maximum flow
  • mutation operators

Fingerprint

Dive into the research topics of 'Evaluation of heavy-tailed mutation operator on maximum flow test generation problem'. Together they form a unique fingerprint.

Cite this