Runtime analysis of the (1+1) evolutionary algorithm for the chance-constrained knapsack problem

Frank Neumann, Andrew M. Sutton

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

Abstract

The area of runtime analysis has made important contributions to the theoretical understanding of evolutionary algoirthms for stochastic problems in recent years. Important real-world applications involve chance constraints where the goal is to optimize a function under the condition that constraints are only violated with a small probability. We rigorously analyze the runtime of the (1+1) EA for the chance-constrained knapsack problem. In this setting, the weights are stochastic, and the objective is to maximize a linear profit function while minimizing the probability of a constraint violation in the total weight. We investigate a number of special cases for this problem, paying attention to how the structure of the chance constraint influences the runtime behavior of the (1+1) EA. Our results reveal that small changes to the profit value can result in hard-to-escape local optima.

Original languageEnglish (US)
Title of host publicationFOGA 2019 - Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms
PublisherAssociation for Computing Machinery, Inc
Pages147-153
Number of pages7
ISBN (Electronic)9781450362542
DOIs
StatePublished - Aug 27 2019
Event15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA 2019 - Potsdam, Germany
Duration: Aug 27 2019Aug 29 2019

Publication series

NameFOGA 2019 - Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

Conference

Conference15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA 2019
CountryGermany
CityPotsdam
Period8/27/198/29/19

    Fingerprint

Keywords

  • Chance-constrained optimization
  • Evolutionary algorithms
  • Knapsack problem

Cite this

Neumann, F., & Sutton, A. M. (2019). Runtime analysis of the (1+1) evolutionary algorithm for the chance-constrained knapsack problem. In FOGA 2019 - Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (pp. 147-153). (FOGA 2019 - Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms). Association for Computing Machinery, Inc. https://doi.org/10.1145/3299904.3340315