毕业设计论文--基于遗传算法求解背包问题.doc

PAGE 本科生毕业设计（论文） ( 2010届 ) 题 目： 基于遗传算法求解背包问题 目 录 摘要 ……………………………………………………………………………………1 英文摘要 ………………………………………………………………………………1 1 引言 ………………………………………………………………………………1 2 背包问题概述 ……………………………………………………………………2 2.1 背包问题描述 ………………………………………………………………2 2.2 研究背包问题的意义 ………………………………………………………2 3 遗传算法概述 ……………………………………………………………………2 3.1 遗传算法的特点 ……………………………………………………………3 3.2 遗传算法的应用领域 ………………………………………………………3 4 遗传算法的基本原理 ……………………………………………………………4 4.1 基本流程 ……………………………………………………………………4 4.2 编码 …………………………………………………………………………5 4.3 适应度函数 …………………………………………………………………5 4.4 遗传算子 ……………………………………………………………………6 4.4.1 选择算子 …………………………………………………………………6 4.4.2 交叉算子…………………………………………………………………7 4.4.3 变异算子…………………………………………………………………7 4.5 参数控制 ……………………………………………………………………8 4.5.1 群体规模 ………………………………………………………………8 4.5.2 交叉概率 ………………………………………………………………8 4.5.3 变异概率 ………………………………………………………………8 4.6 算法结束条件控制 …………………………………………………………9 5 实现求解背包问题的遗传算法 ………………………………………………9 5.1 0_1背包问题中染色体的表示………………………………………………9 5.2 遗传算法求解0_1背包问题时用到的参数 ………………………………9 5.3 选择操作 ……………………………………………………………………9 5.4 交叉操作 ……………………………………………………………………10 5.5 精英策略 ……………………………………………………………………11 5.6 变异操作 ……………………………………………………………………11 5.7 代际更新 ……………………………………………………………………11 5.8 算法终止 ……………………………………………………………………11 5.9 仿真结果与测试 ……………………………………………………………12 5.9.1 不同交叉概率下所得测试结果 ………………………………………13 5.9.2 极端数据对结果的影响 ………………………………………………15 5.9.3 仿真结果总结 …………………………………………………………18 5.10 问题总结 ……………………………………………………………………18 6 展望 ………………………………………………………………………………18 致 谢 …………………………………………………………………………………19 参考文献 ……………………………………………………………………………20 附源程序 ……………………………………………………………………………21 基于遗传算法求解背包问题 摘 要 背包问题(Knapsack problem)是一种组合优化的NP完全问题,本文首先介绍了基本遗传算法的基本原理、特点及其基本实现技术，接着针对背包问题，论述了遗传算法在编码表示和遗传算子（包括选择算子、交叉算子变异算子这三种算子）等方面的应用情况。并且结合背包问题实例，给出了具体的编码方法，运行参数，群体大小，最大迭代次数，以及合适的遗传算子。最后，简单说明了遗传算法在求解背包问题中的应用并对遗传算法解决背包问题的前景提出了展望。 关键词：背包问题；遗传算法；遗传算子；编码 Genetic Algorithm for KP Jin Tian Tian Director: Prof. DaYong Deng (College of Mathematics Physics And Inf