基于遗传算法的0-1背包问题研究_学士学位论文.doc
《基于遗传算法的0-1背包问题研究_学士学位论文.doc》由会员分享,可在线阅读,更多相关《基于遗传算法的0-1背包问题研究_学士学位论文.doc(81页珍藏版)》请在三一文库上搜索。
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 Information Engineering
2、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.运用遗传算法求解 0-1
3、 背包问题,并在 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 tradit
5、ional 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 for 2 example was tested and proved the effectiveness of the genetic algorith
6、m 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 parameters and the simulation results show Key Words:0-1 knapsack problem;Genetic alg
7、orithm;Popsize;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 背包问题研究背
8、包问题研究.9 2.12.1 遗传算法的思想遗传算法的思想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 第四章第四章 结论与展望结论与展望.3
9、6 4.1 结论结论.36 4.24.2 展望展望36 总结与体会总结与体会.38 设计(论文)专用纸 第 IV页 致谢致谢.40 参考文献参考文献.41 附录一附录一 源程序源程序.43 MATLAB 主程序.43 GUI 界面设计程序51 附录二附录二 外文文献翻译外文文献翻译.60 附录三附录三 外文文献原文外文文献原文.71 设计(论文)专用纸 第 V页 前言前言 背包问题(Knapsack Problem)是一种组合优化NP完全问题,相似的问题经常出 现在商业、组合数学,计算复杂性理论、密码学和应用数学等领域中。背包问题可 分为一维背包,二维背包问题,完全背包问题,多重背包问题、分组
10、背包问题等等。 0-1背包问题作为最基础背包问题,它包含了背包问题的设计状态,方程的最基本思 想,因此,其他背包问题也可以转化成为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 背
12、包问题背景 背包问题(Knapsack Problem)是由 Markel 和 Hellman1提出的一类具有实际 应用背景的经典 NP 问题。背包问题主要思路是假定一个人拥有大量物品,物品的重 量各不相同,他要选择一些物品放入背包中。物品的重量是已知的,所有可能的物 品也是已知的,但是背包中的物品是保密的,此外还附加了背包的重量限制。对于 大规模的背包问题要列出所有可能的物品在计算上是不可能实现的。在多种背包问 题类型中,0-1 背包问题是最基本的背包问题,其他背包问题往往也可以转化成 0-1 背包问题求解。 在我们的现实生活中许多问题都可以用背包问题来描述,例如工厂中的下料问 题、管理中的
13、资源分配问题、装箱问题、资金预算问题等等都可以建模为背包问题。 此外背包问题还常常作为其他复杂组合优化问题的一个子问题出现,对于由简单结 构组合而成的复杂结构体而言,对简单问题的深入探索往往可以使复杂的问题迎刃 而解。所以在前人研究经验的基础上开展对背包问题的研究具有重要意义。 1.1.2 背包问题的研究现状 Dantzing 在上世纪 50 年代首先进行了开创性的研究,利用贪婪算法2求得了 0-1 背包问题的最优解上界。此后 20 几年背包问题没有较大的发展,直到 1974 年, hoeowitz 和 salmi 利用分支节点法3解答背包问题,他们提出背包问题的可分性, 为该问题的求解指出了
14、一条新型道路。随后 balas 和 zemel 提出了背包问题的“核” 思想使得背包问题的研究获得了较大的发展。上世纪九十年代以后,随着生物仿生 技术和网络技术的飞速发展,各种模拟生物物理规律的并行近似算法不断涌现,例 如:遗传算法已经在 0-1 背包问题上得到了较好的应用,蚂蚁算法等仿生算法也很 设计(论文)专用纸 2 好的应用到了组合优化问题中。近几年还出现了许多将几种算法结合起来的混合算 法用来解决背包问题并取得了不错的效果。 传统求解背包问题的方法可以概括为精确算法和近似算法,其中精确算法有动 态规划法,回溯法和分支限界法,近似算法有遗传算法,贪婪算法和蚁群算法,由 于精确算法的时间复
15、杂性和空间复杂性等缺点,近年来利用近似算法求解背包问题 已成为重点。 前人已经对背包问题做了一些深入的研究,得到了一些经典的方法,有些方法 对于解决背包问题虽然能得到不错的结果,但是也存在着很多不足之处。首先,很 多算法的计算量都很大,迭代的时间很长。例如:穷举法和动态规划法简单易行,但 是效率很低、鲁棒性不强,只能用于较小规模的问题求解,但在现实问题中有时面对 的问题搜索空间可能非常大,慢慢求解效率就会很低。第二,贪婪算法速度快,爬 坡能力强,但是它适用于搜索局部最优解,可能会陷入局部极值而得不到全局最优解。 第三,蚁群算法可以得到近似最优解,但是当数据规模较大的时候收敛太慢;第四, 新出现
16、的知识进化算法和 DNA 计算等方法也可以有效的解决背包问题,但这些理论 还不太完善,背包问题属于组合最优化问题,在严格意义上求取最优解非常困难, 所以研究高速近似的算法是一个重要的发展方向。与以上几种算法相比遗传算法具 有一定的优势。首先,遗传算法对所求解的优化问题没有太多的数学要求,由于他 的进化特性,搜素过程中不需要问题的内在性质,对于任意形式的目标函数和约束, 无论是线性的还是非线性的,离散的还是连续的都可处理。其次,进化算子的各态 历经性使得遗传算法能够非常有效地进行概率意义的全局搜索。最后,遗传算法对 于各种特殊问题可以提供极大的灵活性来混合构造领域独立的启发式,从而保证算 法的有
17、效性。 本文将对遗传算法做进一步研究并结合应用于背包问题的求解,并通过实验证 明遗传算法对求解背包问题是比较有效的。 1.21.2 遗传算法遗传算法简介简介 遗传算法(Genetic Algorithms)是计算数学中用于解决最优化的搜索算法,是 设计(论文)专用纸 3 进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的, 这些现象包括遗传、突变、自然选择以及杂交等。 遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法,它 借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索 的方法,它能在搜索过程中自动获取和积累有关搜索空间的知识,并自适
18、应地控制 搜索过程以求得最优的方法。在遗传法操作使用适者生存的原则,在潜在的解决方 案种群中逐次产生一个近似的最优方案。在遗传算法的每一代中,根据个体在问题 领域中的适应度值和从自然遗传学中借鉴来的再造方法进行选择,产生一个新的近 似解。这个过程导致种群中个体的进化,得到新的个体比原来的个体更能适应环境, 就像自然界中的改造一样。 1.2.1 遗传算法的研究现状与发展趋势 查克斯达尔文的自然选择学说认为生物进化的动力和机制在于自然选择,生 物通过生存斗争,其中具有有利变异的个体容易存活下来,并有更多的机会将这种 变异遗传给后代,而具有不利变异的个体将被淘汰且产生后代的机会也会少。凡是 在生存斗
19、争中获胜的个体对环境的适应性都比较强,因此生物进化的过程就是这种 “物竞天择,适者生存”的过程,这种过程是一个缓慢的、连续和长期的过程。遗 传和变异是决定生物进化的内在因素,推动生物的进化和发展。 基于生物进化理论,从 20 世纪 60 年代起科学家们就尝试用计算的方法模拟生 物遗传和选择进化过程。美国的 Holland 教授于 1975 年出版了关于遗传算法的开创 性著作Adaptation in Natural and Artificial Systems4,开创性的提出了 遗传算法的概念,系统性的阐述了遗传算法的理论,奠定了遗传算法理论的数学基 础,并将其应用到了优化和机器学习的领域中。
20、他将遗传算法定义为适应算法,可 以广泛的应用于系统最优化的研究,1975 年 DeJone 做了大量实验,建立了著名的 DeJone 的测试函数5。1989 年 Goldberg 博士出版本了专著Genetic algorithm in search,optimization and machine learning 6,这是第一本关于遗传算法 的教科书,全面论述了遗传算法的原理与应用,并与实例结合给出了大量的可用的 设计(论文)专用纸 4 源程序,使技术专家可以借鉴参考并进行实际应用。在此之后世界范围内掀起了关 于遗传算法研究与应用的高潮。从 1985 年开始关于遗传算法及其应用的国际会议两
21、 年举办一次,很多人工智能领域的专家开始发表有关遗传算法的论文。1991 年 Davis 在他的Hand book of genetic algorithm7一书中介绍了大量的实例。 遗传算法由于能有效解决 NP 类型的组合优化问题和多目标函数优化问题,得到很多 学科的高度重视。在国内,武汉大学成立了一个软件工程国家重点实验室。以进化 计算作为一个重要的研究方向,他们的研究成果目前在国内处于领先水平;中国科 技大学的陈国良出版本了关于遗传算法的专著;此外,太原理工大学的谢克明教授 模拟人类思维进化过程提出的思维进化算法也成为进化计算领域的一个重要分支。 遗传算法在应用方面取得的丰硕成果,使人们
22、对它的发展前景充满信心。认识 到这一点,遗传算法的奠基人之一,Goldsberg D 戏言:“已不再需要水晶球”。今后 几年,可以预期,拓广更加多样的应用领域,其中包括各种遗传算法程序设计环境的开 发仍将是遗传算法发展的主流。事实上这也是本世纪高新技术迅速发展带有规律性 的特点,即面向应用。与此同时,这并不意味着理论研究会被忽视, 这方面同样有大 量工作要做。例如: 控制参数的选择;交换和突变这两类最重要的算子的确切作用; 并行遗传算法和分布式遗传算法的研究;其他类型生物机制的模仿,如免疫、 病毒、 寄生等,以丰富遗传算法的内容,等等。自然,不论从理论还是应用的角度看,最紧迫 的应是关于算法收
23、敛性问题的研究,特别是过早收敛的防止。这对遗传算法的实际应 用关系重大。 当前一个特别值得重视的趋势是一些面向对象的智能技术,其中主要是模糊逻 辑8(Fuzzy Logic, FL ),神经网络9(Neural Network, NN )以及遗传算法等的综 合应用。众所周知,FL 有较强的知识表达能力,NN 的长处在于自学习,它们与遗传算 法相结合形成新的集成化技术,即所谓的混合智能系统(Hybrid Intellectual System )。这一思想在 90 年代初逐步形成,而由模糊集论的创始人,美国 Zadeh LA 在 1993 年于汉城召开的国际模糊系统协会( IFSA )第五届世界
24、会议首先明确提出随 后在许多有关的国际学术会议上得到充分体现。应该指出,我国学者对这一趋势的认 识较早。例如,清华大学李衍达院士领导的研究集体在几乎同一时期开展了这一重要 设计(论文)专用纸 5 方向的研究 1995 年, Zadeh 在 IFSA 的第六届世界会议上再次强调了这一方向的重 要性,并且认为上述所谓的混合智能系统的应用将覆盖从消费品生产到核反应堆设计 以至证券管理,而“在未来几年中可能无处不在”。就遗传算法本身的研究而言,应 该说,我国起步较晚,近几年才陆续看到一些介绍性的文章、不多于两三部的专著以 及初步的研究报告,与国外工作比较,一个显著区别是,国内工作多只停留在论文这 一层
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 遗传 算法 背包 问题 研究 学士学位 论文
链接地址:https://www.31doc.com/p-3925122.html