基于遗传算法的0-1背包问题研究

《基于遗传算法的0-1背包问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于遗传算法的0-1背包问题研究专业年级:自动化摘要本文介绍了0-1背包问题的基本概念，综述了求解0-1背包问题的传统方法；对遗传算法进行了理论研究，详细的阐述了遗传算法的基本原理、研究趋势和在0-1背包问题中的应用；利用Matlab仿真平台对2个算例进行了测试，证明了遗传算法求解背包问题的有效性；通过实例分析了种群规模、迭代次数以及变异概率对算法结果的影响；设计了图形用户界面（GUI），实现了参数的输入与仿真结果显示。关键词：0-1背包问题；遗传算法；种群规模；Matlab；GUI第I页AbstractThispaperintroducesthebasicconcep

2、tof0-1knapsackproblem,solving0-1knapsackproblem,thepapersummarizedthetraditionalmethods;Geneticalgorithmforthetheoreticalresearch,elaboratedthebasicprincipleofgeneticalgorithmindetail,theresearchtrendandapplicationinthe0-1knapsackproblem;UsingMatlabsimulationplatformfor2examplewastesteda

3、ndprovedtheeffectivenessofthegeneticalgorithmforsolvingknapsackproblem;Analyzesthepopulationsize,numberofiterations,andtheinfluenceofthemutationprobabilityonthealgorithmresults;Designagraphicaluserinterface(GUI),realizetheinputparametersandthesimulationresultsshowKeyWords：0-1knapsackprob

4、lem；Geneticalgorithm；Popsize；Matlab；GUI第II页目录摘要IABSTRACTII目录III前言V第一章绪论11.1背包问题简介11.1.10-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遗传算法的数学基础102.1.2遗传算法基本原理122.1.3遗传算法的实现过程132.2使用遗传算法求解0-1背包问题16

5、2.3数值试验以及结果分析202.3.1算例1212.3.2算例224第三章GUI界面设计293.1概述293.2GUI界面设计293.2.1GUI界面设计步骤293.2.2界面运行结果33第四章结论与展望364.1结论364.2展望36总结与体会38致谢40参考文献41附录一源程序43第V页MATLAB主程序43GUI界面设计程序51附录二外文文献翻译60附录三外文文献原文71第V页前言背包问题(KnapsackProblem)是一种组合优化NP完全问题，相似的问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。背包问题可分为一维背包，二维背包问题

6、，完全背包问题，多重背包问题、分组背包问题等等。0-1背包问题作为最基础背包问题，它包含了背包问题的设计状态，方程的最基本思想，因此，其他背包问题也可以转化成为0-1背包问题进行求解。遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这

7、些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。在论文首先详细介绍了遗传算法的数学基础、基本原理、实现过程，以及使用遗传算法求解0-1背包问题的2个算例并得到相关仿真结果，并对仿真结果进行分析。接着通过设置不同的种群规模、交叉概率和迭代次数来探讨这些算子对于遗传算法求解背包问题性能的影响。最后在matlab环境中进行GUI界面设计，通过GUI界面可以直观的看到0-1背包问题的2个算例在不同参数设置下仿真曲线的变化情况。第V页第一章绪论1.1背包问题简介1.1.10-1