《基于遗传算法的0-1背包问题研究》由会员分享，可在线阅读，更多相关《基于遗传算法的0-1背包问题研究（79页珍藏版）》请在金锄头文库上搜索。
1、 学士学位论文学士学位论文 基于遗传算法的基于遗传算法的 0-10-1 背包问题研究背包问题研究 学学 院：院： 信息工程与自动化学院 专业年级专业年级: : 自动化 2009 级 学生姓名：学生姓名： 学学 号：号： 指导教师：指导教师： 职职 务：务： 实验师 起止时间：起止时间： 2013 年 3 月2013 年 6 月 Kun Ming University of Science and Technology Bachelors Degree Thesis Genetic Algorithm for 0-1 Knapsack Problem College： Faculty of In
2、formation Engineering and Automation Profession： Automation Class Three, Grade 2009 Name： Number： Teacher： Position： Experimentalist Time: March 2013June 2013 毕业设计（论文）任务书 信自 院院 自动化 专业专业 09 级级 学生姓名：学生姓名： 毕业设计（论文）题目：毕业设计（论文）题目： 基于遗传算法的 0-1 背包问题研究 毕业设计（论文）内容：毕业设计（论文）内容： 1.0-1 背包问题的数学描述； 2.遗传算法原理与应用； 3.
3、运用遗传算法求解 0-1 背包问题，并在 matlab 环境中实现仿真； 4.在 matlab 环境中进行 GUI 界面设计，实现相关参数的输入与进化曲线的输出显示。 专题（子课题）题目：专题（子课题）题目： 专题（子课题）内容：专题（子课题）内容： 毕业设计（论文）指导教师（签字）：毕业设计（论文）指导教师（签字）： 主主 管管 教教 学学 院院 （部）（部） 长（签字）：长（签字）： 年年 月月 日日 第 I页 摘要摘要 本文介绍了 0-1 背包问题的基本概念，综述了求解 0-1 背包问题的传统方法； 对遗传算法进行了理论研究，详细的阐述了遗传算法的基本原理、研究趋势和在 0- 1 背包问
4、题中的应用；利用 Matlab 仿真平台对 2 个算例进行了测试，证明了遗传算 法求解背包问题的有效性；通过实例分析了种群规模、迭代次数以及变异概率对算 法结果的影响；设计了图形用户界面（GUI） ，实现了参数的输入与仿真结果显示。 关键词：0-1 背包问题；遗传算法；种群规模；Matlab；GUI 第 II页 Abstract This paper introduces the basic concept of 0-1 knapsack problem, solving 0-1 knapsack problem, the paper summarized the traditional me
5、thods; Genetic algorithm for the theoretical research, elaborated the basic principle of genetic algorithm in detail, the research trend and application in the 0-1 knapsack problem; Using Matlab simulation platform for 2 example was tested and proved the effectiveness of the genetic algorithm for so
6、lving knapsack problem; Analyzes the population size, number of iterations, and the influence of the mutation probability on the algorithm results; Design a graphical user interface (GUI), realize the input parameters and the simulation results show Key Words：0-1 knapsack problem；Genetic algorithm；P
7、opsize；Matlab；GUI 第 III页 目录目录 摘要摘要 .I ABSTRACTII 目录目录 III 前言前言V 第一章第一章 绪绪 论论.1 1.1 背包问题简介背包问题简介1 1.1.1 0-1 背包问题背景.1 1.1.2 背包问题的研究现状.1 1.21.2 遗传算法简介遗传算法简介2 1.2.1 遗传算法的研究现状与发展趋势 3 1.2.2 遗传算法的特点 5 1.2.3 遗传算法分类 6 1.2.4 遗传算法的应用.7 1.31.3 本文主要工作本文主要工作7 第二章第二章 基于遗传算法的基于遗传算法的 0-10-1 背包问题研究背包问题研究.9 2.12.1 遗传算
8、法的思想遗传算法的思想9 2.1.1 遗传算法的数学基础10 2.1.2 遗传算法基本原理12 2.1.3 遗传算法的实现过程13 2.22.2 使用遗传算法求解使用遗传算法求解 0-10-1 背包问题背包问题16 2.32.3 数值试验以及结果分析数值试验以及结果分析.20 2.3.1 算例 1 21 2.3.2 算例 2 24 第三章第三章 GUI 界面设计界面设计 29 3.13.1 概述概述29 3.23.2 GUIGUI 界面设计界面设计29 3.2.1GUI 界面设计步骤.29 3.2.2 界面运行结果33 第四章第四章 结论与展望结论与展望.36 4.1 结论结论.36 4.24
9、.2 展望展望36 总结与体会总结与体会.38 第 IV页 致谢致谢.40 参考文献参考文献.41 附录一附录一 源程序源程序.43 MATLAB 主程序.43 GUI 界面设计程序51 附录二附录二 外文文献翻译外文文献翻译.60 附录三附录三 外文文献原文外文文献原文.71 第 V页 前言前言 背包问题(Knapsack Problem)是一种组合优化NP完全问题，相似的问题经常出 现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。背包问题可 分为一维背包，二维背包问题，完全背包问题，多重背包问题、分组背包问题等等。 0-1背包问题作为最基础背包问题，它包含了背包问题的设计状态
10、，方程的最基本思 想，因此，其他背包问题也可以转化成为0-1背包问题进行求解。 遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优 胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年 首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限 定；具有内在的并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获 取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法 的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制 和人工生命等领域。它是现代有关智能计算中的关键技
11、术。 在论文首先详细介绍了遗传算法的数学基础、基本原理、实现过程，以及使用 遗传算法求解 0-1 背包问题的 2 个算例并得到相关仿真结果，并对仿真结果进行分 析。接着通过设置不同的种群规模、交叉概率和迭代次数来探讨这些算子对于遗传 算法求解背包问题性能的影响。最后在 matlab 环境中进行 GUI 界面设计，通过 GUI 界面可以直观的看到 0-1 背包问题的 2 个算例在不同参数设置下仿真曲线的变化情 况。 设计（论文）专用纸 1 第一章第一章 绪绪 论论 1.1 背包问题简介背包问题简介 1.1.1 0-1 背包问题背景 背包问题（Knapsack Problem）是由 Markel
12、和 Hellman1提出的一类具有实际 应用背景的经典 NP 问题。背包问题主要思路是假定一个人拥有大量物品，物品的重 量各不相同，他要选择一些物品放入背包中。物品的重量是已知的，所有可能的物 品也是已知的，但是背包中的物品是保密的，此外还附加了背包的重量限制。对于 大规模的背包问题要列出所有可能的物品在计算上是不可能实现的。在多种背包问 题类型中，0-1 背包问题是最基本的背包问题，其他背包问题往往也可以转化成 0-1 背包问题求解。 在我们的现实生活中许多问题都可以用背包问题来描述，例如工厂中的下料问 题、管理中的资源分配问题、装箱问题、资金预算问题等等都可以建模为背包问题。 此外背包问题
13、还常常作为其他复杂组合优化问题的一个子问题出现，对于由简单结 构组合而成的复杂结构体而言，对简单问题的深入探索往往可以使复杂的问题迎刃 而解。所以在前人研究经验的基础上开展对背包问题的研究具有重要意义。 1.1.2 背包问题的研究现状 Dantzing 在上世纪 50 年代首先进行了开创性的研究，利用贪婪算法2求得了 0-1 背包问题的最优解上界。此后 20 几年背包问题没有较大的发展，直到 1974 年， hoeowitz 和 salmi 利用分支节点法3解答背包问题，他们提出背包问题的可分性， 为该问题的求解指出了一条新型道路。随后 balas 和 zemel 提出了背包问题的“核” 思想
14、使得背包问题的研究获得了较大的发展。上世纪九十年代以后，随着生物仿生 技术和网络技术的飞速发展，各种模拟生物物理规律的并行近似算法不断涌现，例 如：遗传算法已经在 0-1 背包问题上得到了较好的应用，蚂蚁算法等仿生算法也很 设计（论文）专用纸 2 好的应用到了组合优化问题中。近几年还出现了许多将几种算法结合起来的混合算 法用来解决背包问题并取得了不错的效果。 传统求解背包问题的方法可以概括为精确算法和近似算法，其中精确算法有动 态规划法，回溯法和分支限界法，近似算法有遗传算法，贪婪算法和蚁群算法，由 于精确算法的时间复杂性和空间复杂性等缺点，近年来利用近似算法求解背包问题 已成为重点。 前人已
15、经对背包问题做了一些深入的研究，得到了一些经典的方法，有些方法 对于解决背包问题虽然能得到不错的结果，但是也存在着很多不足之处。首先，很 多算法的计算量都很大，迭代的时间很长。例如：穷举法和动态规划法简单易行,但 是效率很低、鲁棒性不强,只能用于较小规模的问题求解，但在现实问题中有时面对 的问题搜索空间可能非常大，慢慢求解效率就会很低。第二，贪婪算法速度快，爬 坡能力强，但是它适用于搜索局部最优解,可能会陷入局部极值而得不到全局最优解。 第三，蚁群算法可以得到近似最优解,但是当数据规模较大的时候收敛太慢；第四， 新出现的知识进化算法和 DNA 计算等方法也可以有效的解决背包问题，但这些理论 还不太完善，背包问题属于组合最优化问题，在严格意义上求取最优解非常困难， 所以研究高速近似的算法是一个重要的发展方向。与以上几种算法相比遗传算法具 有一定的优势。首先，遗传算法对所求解的优化问题没有太多的数学要求，由于他 的进
