多选择多约束背包问题的进化求解策略

《多选择多约束背包问题的进化求解策略》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中国科学技术大学硕士学位论文多选择多约束背包问题的进化求解策略姓名：周钱申请学位级别：硕士专业：计算机软件与理论指导教师：罗文坚2011-04摘要摘要背包问题（KnapsackProblem，KP）是运筹学中经典的组合优化问题，是NP难问题。它有着极其广泛的应用背景，比如在网络资源分配等方面。多选择多约束背包问题作为背包问题的一种复杂的变种，在现实应用中同样具有广泛的研究价值。现实社会中存在大量的动态优化问题，如果这类问题还有约束的话，就是动态约束优化问题。动态的多选择多约束背包问题就是动态约束优化问题。进化算法是模拟自然界生物进化机制而形成的自适应全局优化搜索算法，被广泛的应用于求解组合

2、优化问题。在静态环境和动态环境下，研究基于进化算法的多选择多约束背包问题的求解策略意义重大。本文的具体工作包括以下两个方面：（1）提出了一种新的多种群进化算法来解决多选择多约束背包问题。本文通过提供两个进化种群和一个备用种群来平衡可行区域和不可行区域的搜索。两个进化种群在以不同的目标进化的同时，通过可行解交换使两个进化种群既有独立进化过程，又有信息交互。备用种群保存了算法在当前代数为止，发现的最好的可行解和不可行解的个体种群。当发现种群陷入局部最优的时候，通过启用备用种群来覆盖代替陷入局部最优的种群，从而保持了种群的多样性。实验结果表明，该多种群进化算法的性能超过了现有的算法，特别是在约束

3、较强的情况下。（2）提出了一种新的求解动态多选择多约束背包问题的进化策略。本文应用进化策略来解决动态背包问题，主要在变异算子和选择算子两个方面进行了改进。首先，提出了新的混合变异算子，在混合变异算子中针对个体是可行解还是不可行解的状态，应用不同的物品分组顺序，然后进行组内物品的变异。在进化过程中，如果发现个体是不可行解的时侯，启用与约束相关的物品分组顺序；如果个体是可行解的时候，启用与价值相关的物品分组顺序，按照物品分组顺序进行组内物品变换。其次，提出了一种新的动态随机排序策略作为选择算子。当算法没有发现可行解时，动态随机排序策略中的比较概率（即Pf）保持不变等于零；当发现可行解个体时，算

4、法的选择策略发生了改变，动态随机排序策略中的比较概率呈逐渐上升趋势，逐步增强不可行区域的搜索。通过与两种处理约束技术（即惩罚函数法和Deb准则）的实验对比，结果表明新的进化策略能更有效的求解动态约束优化问题。本文还讨论了三种不同的动态随机排序策略在求解动态背包问题时的表现，进一步证实了新的动态随机排序策略的性能的确更优秀，最后讨论了不同物品分组顺序对算法性能的影响。I摘要本论文通过对多选择多约束背包问题的研究，提出了用于解决静态多选择多约束背包问题的多种群进化算法和用于解决动态多选择多约束背包问题的的进化策略。本文工作不仅对解决静态环境下的背包问题的研究有着重要的意义，而且对实际动态环境中

5、背包问题的应用也有一定的参考价值。关键词：组合优化背包问题进化算法多选择多约束背包问题IIABSTRACTABSTRACTTheKnapsackProblem(KP)isaclassicalNP-HardcombinationoptimizationprobleminOperationsResearch.Itiswidelyusedinfinancialarrangements,projectselection.TheMultiple-choiceMultidimensionalKnapsackproblemhasextensiveresearchvalueasacomplexvarian

6、toftheKPinrealapplications.Inreal-worldapplications,therearealotofdynamicoptimizationproblems.ItwillbedynamicconstraintoptimizationproblemifthedynamicoptimizationproblemconstrainedDynamicMultiple-choiceMultidimensionalKnapsackproblembelongstodynamicconstraintoptimizationproblems.Evolutionaryalgori

7、thmismimicnaturalbiologicalevolutionmechanismandtheformationofadaptiveglobaloptimizationalgorithm,iswidelyusedinsolvingthecombinatorialoptimizationproblem.Instaticenvironmentanddynamicenvironment,theresearchonthe