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

2 Scopus citations

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

Bibliographical note

Funding Information:
This work has been supported by the Australian Research Council through grant DP160102401 and by the South Australian Government through the Research Consortium "Unlocking Complex Resources through Lean Processing".

Publisher Copyright:
© 2019 Copyright held by the owner/author(s).

Keywords

  • Chance-constrained optimization
  • Evolutionary algorithms
  • Knapsack problem

Fingerprint Dive into the research topics of 'Runtime analysis of the (1+1) evolutionary algorithm for the chance-constrained knapsack problem'. Together they form a unique fingerprint.

Cite this