Blending Dynamic Programming with Monte Carlo Simulation for Bounding the Running Time of Evolutionary Algorithms

Kirill Antonov, Maxim Buzdalov, Arina Buzdalova, Carola Doerr

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

3 Citations (SciVal)
35 Downloads (Pure)

Abstract

With the goal to provide absolute lower bounds for the best possible running times that can be achieved by (1 + λ)-type search heuristics on common benchmark problems, we recently suggested a dynamic programming approach that computes optimal expected running times and the regret values inferred when deviating from the optimal parameter choice. Our previous work is restricted to problems for which transition probabilities between different states can be expressed by relatively simple mathematical expressions. With the goal to cover broader sets of problems, we suggest in this work an extension of the dynamic programming approach to settings in which it may be difficult or impossible to compute the transition probabilities exactly, but it is possible to approximate them numerically, up to arbitrary precision, by Monte Carlo sampling. We apply our hybrid Monte Carlo dynamic programming approach to a concatenated jump function and demonstrate how the obtained bounds can be used to gain a deeper understanding into parameter control schemes.

Original languageEnglish
Title of host publicationProceedings of IEEE Congress on Evolutionary Computation
PublisherIEEE Press
Pages878-885
Number of pages8
ISBN (Electronic)9781728183923
DOIs
Publication statusPublished - 28 Jun 2021
Event2021 IEEE Congress on Evolutionary Computation, CEC 2021 - Virtual, Krakow, Poland
Duration: 28 Jun 202101 Jul 2021

Publication series

Name2021 IEEE Congress on Evolutionary Computation, CEC 2021 - Proceedings

Conference

Conference2021 IEEE Congress on Evolutionary Computation, CEC 2021
Country/TerritoryPoland
CityVirtual, Krakow
Period28 Jun 202101 Jul 2021

Fingerprint

Dive into the research topics of 'Blending Dynamic Programming with Monte Carlo Simulation for Bounding the Running Time of Evolutionary Algorithms'. Together they form a unique fingerprint.

Cite this