遗传算法论文

专业选修课期末考核（论文）遗传算法及其应用浅析学院：专业：班级：学号：学生姓名：指导教师：2015年6月1日贵州大学贵州大学论文（设计）诚信责任书本人郑重声明：本人所呈交的毕业论文（设计），是在导师的指导下独立进行研究所完成。毕业论文（设计）中凡引用他人已经发表或未发表的成果、数据、观点等，均已明确注明出处。特此声明。论文（设计）作者签名：日期：贵州大学第1页目录第一章绪论...........................................................4第二章遗传算法介绍.....................................................52.1遗传算法介绍......................................................52.2遗传算法的产生和发展..............................................52.3遗传算法的基本求解步骤............................................62.3.1编码：......................................................62.3.2初始化：.....................................................62.3.3估计适应度：.................................................62.3.4再生(选择):..................................................62.3.5交叉:.......................................................62.3.6变异：......................................................62.3.7重复：......................................................72.4遗传算法流程图：..............................................7第三章遗传算法的应用概述................................................83.1TSP问题描述.....................................................83.2遗传算法用于TSP问题.............................................93.2.1编码表示....................................................93.2.2初始化群体和适应度函数及其终止条件的设定....................93.2.3选择算子...................................................103.2.4交叉算子...................................................103.2.5变异算子...................................................113.2.6TSP问题的总结.............................................11第四章应用举例........................................................124．1问题陈述........................................................124．2详细解答过程....................................................124.2.1问题分析...................................................124.2.2实验原理与数学模型.........................................134.2.3MATLAB求解结果.............................................15贵州大学第2页4．3求解结果验证与反思..............................................16第五章附录............................................................175．1Matlab程序代码.................................................17参考文献................................................................22贵州大学第3页【摘要】：遗传算法（GeneticAlgorithm,GA）是近年来迅速发展起来的一种全新的随机搜索与优化算法，是一种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法。它的研究历史比较短，早期是一种试图解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型。近年来世界范围形成的进化计算热潮，计算智能已作为人工智能研究的一个重要方向，以及后来的人工生命研究兴起，使遗传算法受到广泛的关注。其基本思想基于Darwin的进化论和Mendel的遗传学。遗传算法的广泛使用和发展潜能使得很多学者深入研究遗传算法，并出版了很多关于它的书籍。TSP问题是古老的经典问题，有关的研究有几百年的时间。TSP旅行商问题是一类典型的NP完全问题，遗传算法是解决NP问题的一种较理想的方法。本论文首先介绍了遗传算法的基本原理、遗传算法的特点，遗传算法的发展方向和主要应用领域；接着针对问题论述了遗传算法在编码表示和遗传算子（包括选择算子，交叉算子、变异算子）等方面的应用情况，简单讨论几种编码方法,最后简单介绍了TSP问题。【关键词】遗传算法；TSP；遗传算子；编码【Abstract】GeneticAlgorithm(basedAlgorithm,GA)isdevelopedrapidlyinrecentyearsanewkindofrandomsearchandoptimizationAlgorithm,isakindofreferenceforbiologicalmechanismofnaturalselectionandevolutionofhighlyparallel,randomized,adaptivesearchAlgorithm.Itsresearchhistoryisshorter,theearlyisanattempttoexplaincomplexadaptiveprocessofcreaturesinnaturesystem,simulationoftheevolutionmechanismtoconstructthemodelofartificialsystem.Rangeofevolutionarycomputationintheworldinrecentyears,computationalintelligencehasasanimportantdirectionofartificialintelligenceresearch,andlatertheartificialliferesearch,geneticalgorithmhasbeenwidelyattention.ItsbasicideaisbasedonDarwin'stheoryofevolutionandMendel'sgenetics.Thewidespreaduseofgeneticalgorithmandthedevelopmentpotentialhasledmanyscholarsin-depthstudygeneticalgorithm,andhaspublishedmanybooksaboutit.TheTSPproblemisaclassicproblemofancient,studiesofhundredsofyears.TSPtravelingsalesmanproblemisatypicalNPcompleteproblem,geneticalgorithmisanidealmethodtosolvetheproblemofNP.Thispaperfirstlyintroducesthebasicprincipleofgeneticalgorithm,geneticalgorithm,thecharacteristicsofthedevelopmentdirectionofgeneticalgorithmandthemainapplicationfield;Theninviewoftheproblemsthispaperdiscussesthegeneticalgorithm(ga)saidincodingandgeneticoperators(includingselectionoperator,crossoveroperator,mutationoperator)andsoon,theapplicationofsimplediscussseveralencodingmethods,finallyintroducestheTSPproblem.【keywoeds】GeneticAlgorithm;TSP;geneticoperator;coding贵州大学第4页第一章绪论遗传算法(GeneticAlgorithm，GA)是近年来迅速发展起来的一种全新的随机搜索与优化算法。它是由美国密执安大学J．Holland教授提出的一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。它起源于达尔文的进化论，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。遗传算法的研究引起了国内外学者的关注。自1985年以来，国际上已召开了多次遗传算法的学术会议和研讨会，国际遗传算法学会组织召开的ICGA(InternationalConferenceonGeneticAlgorithms)会议和FOGA(WorkshoponFoundationofGeneticAlgorithms)会议，为研究和应用遗传算法提供了国际交流的机会。遗传算法的主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不以梯度信息为基础。它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。作为一种全局优化搜索算法，遗传算法以其简单通用、鲁棒性强、适于并行处理以及应用范围广等特点，使其成为21世纪智能计算核心技术之一。进入80年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的话题近年来，遗传算法已被成功地应用于经济答理、交通运输、工业设计等不同领域．解决了许多问题。例如，可靠性优化、流水车间调度、作业车间调度、机器调度、设备布局设计、图像处理以及数据挖掘等。贵州大学第5页第二章遗传算法介绍2.1遗传算法介绍遗传算法（geneticalgorithms，GA）是一种模拟自然选择和遗传机制的寻优方法，它是建立在达尔文的生物进化论和孟德尔的遗传学说基础上的算法。基因杂交和基因突变可能产生对环境适应性强的后代，通过优胜劣汰的自然选择，适应值高的基因结构就保存下来。遗传算法就是模仿了生物的遗传、进化原理，并引用了随机统计原理而形成的。2.2遗传算法的产生和发展50年代末