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 language||English (US)|
|Title of host publication||FOGA 2019 - Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms|
|Publisher||Association for Computing Machinery, Inc|
|Number of pages||7|
|State||Published - Aug 27 2019|
|Event||15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA 2019 - Potsdam, Germany|
Duration: Aug 27 2019 → Aug 29 2019
|Name||FOGA 2019 - Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms|
|Conference||15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA 2019|
|Period||8/27/19 → 8/29/19|
Bibliographical noteFunding 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".
© 2019 Copyright held by the owner/author(s).
- Chance-constrained optimization
- Evolutionary algorithms
- Knapsack problem