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

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

1、学士学位论文基于遗传算法的0-1背包问题研究学院：信息工程与自动化学院专业年级:自动化2009级学生姓名：学号：指导教师：职务：实验师起止时间：2013年3月—2013年6月KunMingUniversityofScienceandTechnologyBachelor'sDegreeThesisGeneticAlgorithmfor0-1KnapsackProblemCollege：FacultyofInformationEngineeringandAutomationProfession：AutomationClassThree,G

2、rade2009Name：Number：Teacher：Position：ExperimentalistTime:March2013—June2013毕业设计（论文）任务书信自院自动化专业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页AbstractThispaperint

4、roducesthebasicconceptof0-1knapsackproblem,solving0-1knapsackproblem,thepapersummarizedthetraditionalmethods;Geneticalgorithmforthetheoreticalresearch,elaboratedthebasicprincipleofgeneticalgorithmindetail,theresearchtrendandapplicationinthe0-1knapsackproblem;UsingMatlab

5、simulationplatformfor2examplewastestedandprovedtheeffectivenessofthegeneticalgorithmforsolvingknapsackproblem;Analyzesthepopulationsize,numberofiterations,andtheinfluenceofthemutationprobabilityonthealgorithmresults;Designagraphicaluserinterface(GUI),realizetheinputpara

6、metersandthesimulationresultsshowKeyWords：0-1knapsackproblem；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

7、遗传算法的思想92.1.1遗传算法的数学基础102.1.2遗传算法基本原理122.1.3遗传算法的实现过程132.2使用遗传算法求解0-1背包问题162.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第V页致谢40参考文献41附录一源程序43MATLAB主程序43GUI界面设计程序51附录二外文文献翻译60附录三外文文献原文71第V页前

8、言背包问题(KnapsackProblem)是一种组合优化NP完全问题，相似的问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。背包问题可分为一维背包，二维背包问题，完全背包问题，多重背包问题、分组