-
摘要：0-1背包问题是一个典型的组合优化问题，在计算理论中属于NP完全问题.它是在资源有限的条件下，追求总的最大收益的资源有效分配问题.遗传算法法是求解组合优化问题的一种方法，但用简单遗传算法解决不可行性和背包承重利用不足的可行解问题时效果并不理想，所以将遗传算法与其他算法结合进行该进求解.混合遗传算法大大提高了算法搜索效率，在求解问题上具有更好的稳定性、收敛性、计算效率，成为解决0-1背包问题的有效算法.38908
- 上一篇：C语言中数组名作函数参数的研究
- 下一篇：命题逻辑中的推理方法
毕业论文关键词：组合优化问题；混合遗传算法；约束条件处理；最优解
Based on Hybrid Genetic Algorithm to Solve 0-1
Knapsack Problem
Abstract:0-1 knapsack problem is a typical combinatorial optimization problem， in the computational theory belongs to NP-complete problems. It is under the condition of limited resources， the pursuit of total maximum gain effective resource allocation problem. Genetic algorithm method is a method for solving combinatorial optimization problem， the feasibility and backpack bearing with simple genetic algorithm to solve not feasible solution with insufficient when the effect is not ideal so combines genetic algorithm and other algorithms to the into the solution. Hybrid genetic algorithm greatly improve the efficiency of the algorithm search， on solving problems has better stability， convergence and computational efficiency， become the effective algorithm to solve 0-1 knapsack problems.
Keywords: Combinatorial optimization problems; Hybrid genetic algorithm; The constraint handling; The optimal solution
目 录
摘 要 1
引言 2
1.0-1背包问题 3
1.1问题描述 3
1.2建立数学模型 3
2.遗传算法 4
2.1遗传算法简介 4
2.2遗传算法一般步骤 4
2.3遗传算法特点 5
3.0-1背包问题的混合遗传算法求解 6
3.1基因编码 6
3.2约束条件的处理 6
3.3基本遗传算法求解背包问题的不足 6
3.4混合遗传算法 7
4.示例及结果分析 9
4.1示例 9
4.2结果分析 10
5.结束语 10
参考文献 12
致谢 13
基于混合遗传算法的0-1背包问题求解
引言
背包问题属于组合最优化问题.对于0-1背包NP完全问题，如何求解其最优解或近似最优解成为科学焦点之一，传统的优化方法在求解较大规模的0-1背包问题时都存在迭代时间长，计算量大的弱点.相比之下遗传算法法是求解组合优化问题的一种较好方法，并成为求解组合优化问题近似最优解的主要方式，通过模拟生物进化过程进行全局优化搜索.
1975年，“Adaptation in Nature and Artifical Systems”的发表，标志着遗传算法的诞生；由曾国清写的《0-1背包问题的遗传算法求解》一文中介绍了一种在当时相当流行的算法思想，借鉴了自然界的进化过程发展而来的遗传算法，按此思路运用到实际生活中，结果表明该算法不仅具有实际意义而且非常行之有效。随着科学进步，人们不断探索总结出必须严格执行遗传算法的法则和步骤，只有做到具体问题具体分析，设计正确的编码程序才能有效发挥它的用途.在遗传算法程序实际操作运行中，首先要对一些参数做出选择，再通过搜索位数相对较少，筛选长度最短，比较适应度并依据这种形式进行不断的选择，随机抽查和混合得到最合适的、最优质的点的范围，计算出这些点处的值就是最优解或近似最优解的候选值．但在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优，所以严格意义上通过一般的遗传算法很难得到在最优解，所以研究高速近似的算法成为一个重要的发展方向。因此，我们有必要改进该算法,尤其是背包问题作为其他复杂组合优化的一个子问题出现时，通过对遗传算法进行改进开展对0-1背包的研究具有重要意义.