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