.png){kind=icon}
返回
A threshold search based memetic algorithm for the disjunctively constrained knapsack problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.cor.2021.105447.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The disjunctively constrained knapsack problem consists in packing a subset of pairwisely compatible items in a capacity-constrained knapsack such that the total profit of the selected items is maximized while satisfying the knapsack capacity. DCKP has numerous applications and is however computationally challenging (NP-hard). In this work, we present a threshold search based memetic algorithm for solving the DCKP that combines the memetic framework with threshold search to find high quality solutions. Extensive computational assessments on two sets of 6340 benchmark instances in the literature demonstrate that the proposed algorithm is highly competitive compared to the state-of-the-art methods. In particular, we report 24 and 354 improved best-known results (new lower bounds) for Set I (100 instances) and for Set II (6240 instances), respectively. We additionally apply the approach to solve a real-life daily photograph scheduling problem of an earth observation satellite. We analyze the key algorithmic components and shed lights on their roles for the performance of the algorithm.
Keyword:
Knapsack problems
Disjunctive constraint
Threshold search
Heuristics
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
暂无机构信息
引用论文
.png){kind=icon}
Traces of Conflict: Environment and Eviction in British Military Training Areas, 1943 to Present
PREAI
分享收藏
查看更多内容