文档介绍：中国科学技术大学
硕士学位论文
多选择多约束背包问题的进化求解策略
姓名:周钱
申请学位级别:硕士
专业:计算机软件与理论
指导教师:罗文坚
2011-04
摘要
摘要
背包问题(Knapsack Problem,KP)是运筹学中经典的组合优化问题,是
NP 难问题。它有着极其广泛的应用背景,比如在网络资源分配等方面。多选择
多约束背包问题作为背包问题的一种复杂的变种,在现实应用中同样具有广泛的
研究价值。
现实社会中存在大量的动态优化问题,如果这类问题还有约束的话,就是动
态约束优化问题。动态的多选择多约束背包问题就是动态约束优化问题。
进化算法是模拟自然界生物进化机制而形成的自适应全局优化搜索算法,被
广泛的应用于求解组合优化问题。在静态环境和动态环境下,研究基于进化算法
的多选择多约束背包问题的求解策略意义重大。
本文的具体工作包括以下两个方面:
(1) 提出了一种新的多种群进化算法来解决多选择多约束背包问题。本文
通过提供两个进化种群和一个备用种群来平衡可行区域和不可行区域的搜索。两
个进化种群在以不同的目标进化的同时,通过可行解交换使两个进化种群既有独
立进化过程,又有信息交互。备用种群保存了算法在当前代数为止,发现的最好
的可行解和不可行解的个体种群。当发现种群陷入局部最优的时候,通过启用备
用种群来覆盖代替陷入局部最优的种群,从而保持了种群的多样性。实验结果表
明,该多种群进化算法的性能超过了现有的算法,特别是在约束较强的情况下。
(2) 提出了一种新的求解动态多选择多约束背包问题的进化策略。本文应
用进化策略来解决动态背包问题,主要在变异算子和选择算子两个方面进行了改
进。首先,提出了新的混合变异算子,在混合变异算子中针对个体是可行解还是
不可行解的状态,应用不同的物品分组顺序,然后进行组内物品的变异。在进化
过程中,如果发现个体是不可行解的时侯,启用与约束相关的物品分组顺序;如
果个体是可行解的时候,启用与价值相关的物品分组顺序,按照物品分组顺序进
行组内物品变换。其次,提出了一种新的动态随机排序策略作为选择算子。当算
法没有发现可行解时,动态随机排序策略中的比较概率(即 Pf)保持不变等于零;
当发现可行解个体时,算法的选择策略发生了改变,动态随机排序策略中的比较
概率呈逐渐上升趋势,逐步增强不可行区域的搜索。通过与两种处理约束技术(即
惩罚函数法和 Deb 准则)的实验对比,结果表明新的进化策略能更有效的求解
动态约束优化问题。本文还讨论了三种不同的动态随机排序策略在求解动态背包
问题时的表现,进一步证实了新的动态随机排序策略的性能的确更优秀,最后讨
论了不同物品分组顺序对算法性能的影响。
I
摘要
本论文通过对多选择多约束背包问题的研究,提出了用于解决静态多选择多
约束背包问题的多种群进化算法和用于解决动态多选择多约束背包问题的的进
化策略。本文工作不仅对解决静态环境下的背包问题的研究有着重要的意义,而
且对实际动态环境中背包问题的应用也有一定的参考价值。

关键词:组合优化背包问题进化算法多选择多约束背包问题
II
ABSTRACT
ABSTRACT
The Knapsack Problem (KP) is a classical NP-bination optimization
problem in Operations Research. It is widely used in financial arrangements, project
selection. The Multiple-choice Multidimensional Knapsack problem has extensive
research value as plex variant of the KP in real applications.
In real-world applications, there are a lot of dynamic optimization problems. It
will be dynamic constraint optimization problem if the dynamic optimization problem
constrained Dynamic Multiple-choice Multidimensional Knapsack problem belongs
to dynamic constraint optimization problems.
Evolutionary