2022/04/12 by Aneta Neumann, Neumann, Aneta, Yue Xie +3 · 2 citations
Business, Management and Accounting · Computer Science · Engineering · #Supply Chain and Inventory Management #Metaheuristic Optimization Algorithms Research #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.2204.05597
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.