Paper Info
Title
Runtime analysis of the (1 + 1) evolutionary algorithm for the chance-constrained knapsack problem.
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.
Year
DOI
Venue
2019
10.1145/3299904.3340315
FOGA
Keywords
DocType
ISBN
Knapsack problem,chance-constrained optimization,evolutionary algorithms
Conference
978-1-4503-6254-2
Citations 
PageRank 
References 
0
0.34
0
Authors
2
Name
Order
Citations
PageRank
Frank Neumann11727124.28
Andrew Sutton2206.82