Specific Single- and Multi-Objective Evolutionary Algorithms for the Chance-Constrained Knapsack Problem

2020-04-07 · Yue Xie, Aneta Neumann, Frank Neumann

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 selected items under the condition that the weight of the selected items only exceeds the given weight bound with a small probability of $\alpha$. In this paper, consider problem-specific single-objective and multi-objective approaches for the problem. We examine the use of heavy-tail mutations and introduce a problem-specific crossover operator to deal with the chance-constrained knapsack problem. Empirical results for single-objective evolutionary algorithms show the effectiveness of our operators compared to the use of classical operators. Moreover, we introduce a new effective multi-objective model for the chance-constrained knapsack problem. We use this model in combination with the problem-specific crossover operator in multi-objective evolutionary algorithms to solve the problem. Our experimental results show that this leads to significant performance improvements when using the approach in evolutionary multi-objective algorithms such as GSEMO and NSGA-II.

📄 PDF Abstract BibTeX arXiv:2004.03205

Code (0)

등록된 구현이 없습니다.

Tasks

Evolutionary Algorithms

Evolutionary Biparty Multiobjective UAV Path Planning: Problems and Empirical Comparisons

2026-03-23 · Kesheng Chen, Wenjian Luo, Xin Lin, Zhen Song 외 arxiv

Unmanned aerial vehicles (UAVs) have been widely used in urban missions, and proper planning of UAV paths can improve mission efficiency while reducing the risk of potential third-party impact. Existing work has consider…

R2 Indicator and Deep Reinforcement Learning Enhanced Adaptive Multi-Objective Evolutionary Algorithm

2024-04-11 · Farajollah Tahernezhad-Javazm, Debbie Rankin, Naomi Du Bois, Alice E. Smith 외

Choosing an appropriate optimization algorithm is essential to achieving success in optimization challenges. Here we present a new evolutionary algorithm structure that utilizes a reinforcement learning-based agent aimed…

Deep Reinforcement Learning reinforcement-learning Reinforcement Learning

Towards Self-adaptive Mutation in Evolutionary Multi-Objective Algorithms

2023-03-08 · Furong Ye, Frank Neumann, Jacob de Nobel, Aneta Neumann 외

Parameter control has succeeded in accelerating the convergence process of evolutionary algorithms. While empirical and theoretical studies have shed light on the behavior of algorithms for single-objective optimization,…

Benchmarking Evolutionary Algorithms

Balancing Common Treatment and Epidemic Control in Medical Procurement during COVID-19: Transform-and-Divide Evolutionary Optimization

2020-08-02 · Yu-Jun Zheng, Xin Chen, Tie-Er Gan, Min-Xia Zhang 외

Balancing common disease treatment and epidemic control is a key objective of medical supplies procurement in hospitals during a pandemic such as COVID-19. This problem can be formulated as a bi-objective optimization pr…

Evolutionary Algorithms Multiobjective Optimization

Using 3-Objective Evolutionary Algorithms for the Dynamic Chance Constrained Knapsack Problem

2024-04-09 · Ishara Hewa Pathiranage, Frank Neumann, Denis Antipov, Aneta Neumann

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…