# Evolutionary Algorithms for Limiting the Effect of Uncertainty for the Knapsack Problem with Stochastic Profits

arXiv: https://arxiv.org/abs/2204.05597 · HTML: https://mlsanity.com/paper/2204.05597/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Apr 2022.

## Built on by (most cited first, 7 of 7)

- [Optimizing Cyber Defense in Dynamic Active Directories through Reinforcement Learning](https://mlsanity.com/paper/2406.19596/) (2024)
- [Using 3-Objective Evolutionary Algorithms for the Dynamic Chance Constrained Knapsack Problem](https://mlsanity.com/paper/2404.06014/) (2024)
- [Improving Confidence in Evolutionary Mine Scheduling via Uncertainty Discounting](https://mlsanity.com/paper/2305.17957/) (2023)
- [Benchmarking Algorithms for Submodular Optimization Problems Using IOHProfiler](https://mlsanity.com/paper/2302.01464/) (2023)
- [Bi-objective chance-constrained evolutionary optimization for large-scale open-pit mine scheduling under geological uncertainty](https://mlsanity.com/paper/2511.08275/) (2025)
- [On the use of evolutionary optimization for the dynamic chance constrained open-pit mine scheduling problem](https://mlsanity.com/paper/2604.13385/) (2026)
- [Sampling-based Pareto Optimization for Chance-constrained Monotone Submodular Problems](https://mlsanity.com/paper/2404.11907/) (2024)

## Abstract (arXiv)

Evolutionary algorithms have been widely used for a range of stochastic optimization problems in order to address complex real-world optimization problems. We consider the knapsack problem where the profits involve uncertainties. Such a stochastic setting reflects important real-world scenarios where the profit that can be realized is uncertain. We introduce different ways of dealing with stochastic profits based on tail inequalities such as Chebyshev's inequality and Hoeffding bounds that allow to limit the impact of uncertainties. We examine simple evolutionary algorithms and the use of heavy tail mutation and a problem-specific crossover operator for optimizing uncertain profits. Our experimental investigations on different benchmarks instances show the results of different approaches based on tail inequalities as well as improvements achievable through heavy tail mutation and the problem specific crossover operator.