## 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 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 |

Pages | 147-153 |

Number of pages | 7 |

ISBN (Electronic) | 9781450362542 |

DOIs | |

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 |

### Publication series

Name | FOGA 2019 - Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms |
---|

### Conference

Conference | 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA 2019 |
---|---|

Country/Territory | Germany |

City | Potsdam |

Period | 8/27/19 → 8/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