Evolutionary Algorithms for Limiting the Effect of Uncertainty for the Knapsack Problem with Stochastic Profits
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Evolutionary AlgorithmsStochastic OptimizationSimilar Papers 제목 키워드 기반
Using 3-Objective Evolutionary Algorithms for the Dynamic Chance Constrained Knapsack Problem
Real-world optimization problems often involve stochastic and dynamic components. Evolutionary algorithms are particularly effective in these scenarios, as they can easily adapt to uncertain and changing environments but…
Evolutionary AlgorithmsOn the Use of Bi-Objective Evolutionary Algorithms for the Stochastic MKP under Dynamic Constraints
The multiple knapsack problem (MKP) generalizes the classical knapsack problem by assigning items to multiple knapsacks subject to capacity constraints. It is used to model many real-world resource allocation and schedul…
Evolutionary Multi-Objective Algorithms for the Knapsack Problems with Stochastic Profits
Evolutionary multi-objective algorithms have been widely shown to be successful when utilized for a variety of stochastic combinatorial optimization problems. Chance constrained optimization plays an important role in co…
Combinatorial OptimizationEvolutionary AlgorithmsA Theoretical Assessment of Solution Quality in Evolutionary Algorithms for the Knapsack Problem
Evolutionary algorithms are well suited for solving the knapsack problem. Some empirical studies claim that evolutionary algorithms can produce good solutions to the 0-1 knapsack problem. Nonetheless, few rigorous invest…
Evolutionary AlgorithmsSpecific Single- and Multi-Objective Evolutionary Algorithms for the Chance-Constrained Knapsack Problem
The chance-constrained knapsack problem is a variant of the classical knapsack problem where each item has a weight distribution instead of a deterministic weight. The objective is to maximize the total profit of the sel…
Evolutionary Algorithms