Theory-inspired parameter control benchmarks for dynamic algorithm configuration

André Biedenkapp, Nguyen Dang, Martin Krejca, Frank Hutter, Carola Doerr

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)
13 Downloads (Pure)

Abstract

It has long been observed that the performance of evolutionary algorithms and other randomized search heuristics can benefit from a non-static choice of the parameters that steer their optimization behavior. Mechanisms that identify suitable configurations on the fly ("parameter control") or via a dedicated training process ("dynamic algorithm configuration") are thus an important component of modern evolutionary computation frameworks. Several approaches to address the dynamic parameter setting problem exist, but we barely understand which ones to prefer for which applications. As in classical benchmarking, problem collections with a known ground truth can offer very meaningful insights in this context. Unfortunately, settings with well-understood control policies are very rare.

One of the few exceptions for which we know which parameter settings minimize the expected runtime is the LeadingOnes problem. We extend this benchmark by analyzing optimal control policies that can select the parameters only from a given portfolio of possible values. This also allows us to compute optimal parameter portfolios of a given size. We demonstrate the usefulness of our benchmarks by analyzing the behavior of the DDQN reinforcement learning approach for dynamic algorithm configuration.
Original languageEnglish
Title of host publicationGECCO '22
Subtitle of host publicationProceedings of the genetic and evolutionary computation conference
EditorsJonathan E. Fieldsend
Place of PublicationNew York, NY
PublisherACM
Pages766–775
Number of pages10
ISBN (Print)9781450392372
DOIs
Publication statusPublished - 8 Jul 2022
EventGECCO'22: Genetic and Evolutionary Computation Conference - Boston, MA, United States
Duration: 9 Jul 202213 Jul 2022
https://gecco-2022.sigevo.org/homepage

Conference

ConferenceGECCO'22
Country/TerritoryUnited States
CityBoston, MA
Period9/07/2213/07/22
Internet address

Fingerprint

Dive into the research topics of 'Theory-inspired parameter control benchmarks for dynamic algorithm configuration'. Together they form a unique fingerprint.

Cite this