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

City | Potsdam |

Period | 8/27/19 → 8/29/19 |

### Fingerprint

### Keywords

- Chance-constrained optimization
- Evolutionary algorithms
- Knapsack problem

### Cite this

*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