Abstract
背包问题（knapsack problem,简称KP）是一类著名的组合优化问题，也是一类NP难问题，它包括0-1背包问题、有界背包问题、多维背包问题、多背包问题、多选择背包问题、二次背包问题、动态背包问题和折扣背包问题等多种形式，在众多领域有着广泛的应用。演化算法（EAs）是一类有效的快速近似求解KP的算法。对近10余年来利用EAs求解KP的研究情况进行了较为详细的总结，一方面讨论了利用EAs求解各种KP问题时个体的编码方法与处理不可行解的有效方法，另一方面，为今后进一步利用最新提出的EAs求解KP问题提供了一条可借鉴的思路。
Knapsack problem (KP) is a well-known combinatorial optimization problem which includes 0-1 KP, bounded KP, multi-constraint KP, multiple KP, multiple-choice KP, quadratic KP, dynamic knapsack KP, discounted KP and other types of KPs. KP can be considered as a mathematical model extracted from variety of real fields and therefore has wide applications. Evolutionary algorithms (EAs) are universally considered as an efficient tool to solve KP approximately and quickly. This paper presents a survey on solving KP by EAs over the past ten years. It not only discusses various KP encoding mechanism and the individual infeasible solution processing but also provides useful guidelines for designing new EAs to solve KPs.
| Translated title of the contribution | Evolutionary algorithms for knapsack problems |
|---|---|
| Original language | Chinese (Simplified) |
| Pages (from-to) | 1-16 |
| Number of pages | 16 |
| Journal | Ruan Jian Xue Bao/Journal of Software |
| Volume | 28 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 2017 |
| Externally published | Yes |
Bibliographical note
Publisher Copyright:© Copyright 2017, Institute of Software, the Chinese Academy of Sciences. All rights reserved.
Keywords
- 背包问题
- 数学模型
- 演化算法
- 个体编码
- 不可行解
- Evolutionary algorithm
- Individual coding
- Infeasible solution
- Knapsack problem
- Mathematical model