《多选择多约束背包问题的进化求解策略》由会员分享，可在线阅读，更多相关《多选择多约束背包问题的进化求解策略（71页珍藏版）》请在金锄头文库上搜索。
1、中国科学技术大学 硕士学位论文 多选择多约束背包问题的进化求解策略 姓名：周钱 申请学位级别：硕士 专业：计算机软件与理论 指导教师：罗文坚 2011-04 摘 要 I 摘摘 要要 背包问题（Knapsack Problem，KP）是运筹学中经典的组合优化问题，是 NP 难问题。它有着极其广泛的应用背景，比如在网络资源分配等方面。多选择 多约束背包问题作为背包问题的一种复杂的变种， 在现实应用中同样具有广泛的 研究价值。 现实社会中存在大量的动态优化问题，如果这类问题还有约束的话，就是动 态约束优化问题。动态的多选择多约束背包问题就是动态约束优化问题。 进化算法是模拟自然界生物进化机制而形成的
2、自适应全局优化搜索算法， 被 广泛的应用于求解组合优化问题。在静态环境和动态环境下，研究基于进化算法 的多选择多约束背包问题的求解策略意义重大。 本文的具体工作包括以下两个方面： （1） 提出了一种新的多种群进化算法来解决多选择多约束背包问题。本文 通过提供两个进化种群和一个备用种群来平衡可行区域和不可行区域的搜索。 两 个进化种群在以不同的目标进化的同时， 通过可行解交换使两个进化种群既有独 立进化过程，又有信息交互。备用种群保存了算法在当前代数为止，发现的最好 的可行解和不可行解的个体种群。当发现种群陷入局部最优的时候，通过启用备 用种群来覆盖代替陷入局部最优的种群，从而保持了种群的多样性
3、。实验结果表 明，该多种群进化算法的性能超过了现有的算法，特别是在约束较强的情况下。 （2） 提出了一种新的求解动态多选择多约束背包问题的进化策略。本文应 用进化策略来解决动态背包问题， 主要在变异算子和选择算子两个方面进行了改 进。首先，提出了新的混合变异算子，在混合变异算子中针对个体是可行解还是 不可行解的状态，应用不同的物品分组顺序，然后进行组内物品的变异。在进化 过程中，如果发现个体是不可行解的时侯，启用与约束相关的物品分组顺序；如 果个体是可行解的时候，启用与价值相关的物品分组顺序，按照物品分组顺序进 行组内物品变换。其次，提出了一种新的动态随机排序策略作为选择算子。当算 法没有发现
4、可行解时， 动态随机排序策略中的比较概率 （即 Pf） 保持不变等于零； 当发现可行解个体时，算法的选择策略发生了改变，动态随机排序策略中的比较 概率呈逐渐上升趋势， 逐步增强不可行区域的搜索。 通过与两种处理约束技术 （即 惩罚函数法和 Deb 准则）的实验对比，结果表明新的进化策略能更有效的求解 动态约束优化问题。 本文还讨论了三种不同的动态随机排序策略在求解动态背包 问题时的表现，进一步证实了新的动态随机排序策略的性能的确更优秀，最后讨 论了不同物品分组顺序对算法性能的影响。 摘 要 II 本论文通过对多选择多约束背包问题的研究， 提出了用于解决静态多选择多 约束背包问题的多种群进化算法
5、和用于解决动态多选择多约束背包问题的的进 化策略。本文工作不仅对解决静态环境下的背包问题的研究有着重要的意义，而 且对实际动态环境中背包问题的应用也有一定的参考价值。 关键词：关键词：组合优化 背包问题 进化算法 多选择多约束背包问题 ABSTRACT III ABSTRACT ABSTRACT The Knapsack Problem (KP) is a classical NP-Hard combination optimization problem in Operations Research. It is widely used in financial arrangements,
6、project selection. The Multiple-choice Multidimensional Knapsack problem has extensive research value as a complex 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 o
7、ptimization problem constrained Dynamic Multiple-choice Multidimensional Knapsack problem belongs to dynamic constraint optimization problems. Evolutionary algorithm is mimic natural biological evolution mechanism and the formation of adaptive global optimization algorithm, is widely used in solving
8、 the combinatorial optimization problem. In static environment and dynamic environment, the research on the evolutionary algorithm to solve the Multiple-choice Multidimensional Knapsack problem has great significance. This paper includes the following two aspects. (1) A novel Multi-Population Geneti
9、c Algorithm (MPGA) is proposed to solve Multiple-choice Multidimensional Knapsack Problem (MMKP). The proposed MPGA has two evolutionary populations and an archive population to balance search biases between feasible space and infeasible space. As two evolutionary populations evolve in different tar
10、gets, two evolutionary populations not only evolve independently but also evolve mutually. Archive population preserves the best feasible and infeasible individual species when current algebra ceases. When evolutionary populations are discovered into a local optimal, enable archive population availa
11、ble in order to covering the local optimum population, so as to keep diversity. Experimental results show that the proposed MPGA is better than existing algorithms, particularly when the strength of constraints is stronger. (2) A novel Evolution Strategy is proposed to solve the Dynamic Multiple-cho
12、ice Multidimensional Knapsack Problem (DMMKP). In this algorithm, two points was improved. One is the mutation operator, and another is selection operator. Firstly, a new hybrid mutation operator is proposed. According to the state of the individual that is feasible or infeasible, different class or
13、derings are applied in the mutating process and searching to promote. At last, according to the class ordering, item is replaced in ABSTRACT IV class by probabilistic. In the evolutionary process, when the individual is an infeasible solution, the groups orders related to constraints are enabled; wh
14、en the individual is a feasible solution, the value related to groups orders are enabled. Secondly, a new strategy of dynamic stochastic ranking as selection operator is also proposed, if no feasible solutions of the algorithm exist , the probability of selection remains constant ,that is zero; If f
15、easible individual exists, the selection strategy algorithm changes and the probability of selection rises gradually, and then the searching for unfeasible space is expanded step by step. In contrast of constraint processing methods of technical penalty function method and Deb standards, the experim
16、ental results demonstrate that the new Evolution Strategy is more effective in solving dynamic constraint optimization problems. The paper discusses performance of three dynamic stochastic ranking in solving dynamic knapsack problem, and further the new dynamic stochastic ranking strategy is proved to be more excellent. Finally different merits and disadvantages of some heuristic class ordering are discussed. This paper is researching about Multiple-choice Multidimensional Knapsack Problem. A
