毕业论文-遗传算法研究

遗传算法研究湖南工业大学毕业设计（论文）题目遗传算法研究学院湖南工业大学专业计算机应用技术学号12535901012401姓名谭玉婷指导教师二零一四年六月十日遗传算法研究-I-摘要遗传算法（GA）是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。作为一种有效的全局优化搜索算法，它具有简单、通用、鲁棒性（Robust）强和适于并行分布处理的特点。基本遗传算法提供了一种通用的算法框架，方便根据具体的问题提供改进策略或者和其它算法混合使用，因此具有广泛的应用潜力。本文中介绍的改良遗传算法改进了基本遗传算法的选择和变异操作，选择操作使用了最优保存策略，保证了当前产生最优个体不会因为交叉、变异而丢失，目的是提高算法的收敛速度；变异操作采用交换、倒序、插入三种变异算子混合的方式，增加种群的多样性，防止算法过早的陷入局部最优解而出现“早熟”现象，目的是提高解的质量。为了验证算法改进策略的有效性，以求解TSP为例，针对不同规模的TSP（eil51、eil76、eil101）做了大量的数据统计。通过对比交换、倒序、插入变异算子以及三种算子混合时解的质量来说明使用多种变异算子混合的优势。同时通过求解相同的问题（att48）与其它智能优化算法（基本遗传算法、模拟退火算法、基本蚁群算法）做了对比，验证算法改进策略的有效性。关键词：改良遗传算法旅行商问题最优保存策略混合变异算子遗传算法研究-II-AbstractThegeneticalgorithm(GA)isarandomsearchalgorithmlearnfrombiologicalnaturalselectionandnaturalgeneticmechanisms.Asakindofeffectiveglobalparalleloptimizationsearchalgorithm,Ithasasimple,universal,robustnessstrongandsuitablefortheparalleldistributedprocessingcharacteristics.Thebasicgeneticalgorithmprovidesageneralalgorithmframeworktofacilitatetheimprovementstrategiesormixedwithotheralgorithms,dependingontheproblem,andthereforehasbroadapplicationpotential.Improvedgeneticalgorithmdescribedinthisarticletoimprovethebasicgeneticalgorithmselectionandmutationoperations,selecttheoperationusingtheoptimalpreservationstrategytoensurethatthecurrenttoproducethebestindividualwillnotbelostbecauseofthecrossover,andmutation,thepurposeistoimprovetheconvergencespeed;mutationoperationusingexchange,reverse,insertthreevariationoperatormixedmethods,increasingthediversityofthepopulationtopreventthealgorithmintoalocaloptimalsolutiontotheprematuretoimprovethequalityofthesolution,inordertoverifytheeffectivenessofthestrategytosolvetheTSP,forexample,fordifferentsizesofTSP(eil51,eil76,eil101)havedonealotofstatisti.Bycontrast,exchange,reverse,insertthequalityofthesolutionwhenthemutationoperatorandthemixingofthethreeoperatorstouseavarietyofmutationoperatorisamixtureofadvantages.Comparedatthesametimebysolvingthesameproblem(att48)withtheothergroupofintelligentalgorithms(geneticalgorithms,simulatedannealingalgorithm,thebasicantcolonyalgorithm),Inordertoprovetheeffectivenessoftheimprovementstrategiesofalgorithm.Keywords:Improegeneticalgorithm,Travelingsalesmanproblem,Theoptimalpreservationstrategy,Mixedmutationoperator遗传算法研究-III-目录摘要.....................................................................................................................IAbstract..................................................................................................................II第一章遗传算法概论......................................................................................11.1遗传算法的产生和国内外研究现状.....................................................11.2遗传算法的基本原理.............................................................................21.3遗传算法的特点......................................................................................31.4遗传算法的应用......................................................................................41.5课题的任务..............................................................................................6第二章基本遗传算法........................................................................................72.1基本遗传算法简介.................................................................................72.2基本遗传算法描述.................................................................................72.3基本遗传算法的实现...........................................................................10第三章遗传算法求解TSP...............................................................................153.1旅行商问题概述...................................................................................153.2使用改进的遗传算法求解TSP............................................................16第四章求解TSP的实验结果及分析..............................................................274.1实验环境................................................................................................274.2算法在求解不同规模下的TSP的实验结果........................................274.3改良的遗传算法和其它智能优化算法的比较....................................284.4使用单一变异算子和混合变异算子的实验结果对比分析................29第五章总结..............................................................................................30参考文献..............................................................................................................33附录1改良遗传算法求解TSPJava源程序...................................................34附录2英文文献翻译.......................................................................................50致谢..................................................................................................................57遗传算法研究-1-第一章遗传算法概论1.1遗传算法的产生和国内外研究现状遗传算法（GeneticAlgorithm简称GA）美国的J.Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法[1]。遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体（优胜劣汰），利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。最后一代候选解群中的最优解就是所求得的最优解。1991年D.Whitey在他的论文中提出了基于领域交叉的交叉算子（Adjacencybasedcrossover），这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了（旅行商）TSP问题中，通过实验对其进行了验证。D.H.Ackley等提出了随机迭代遗传爬山法（StochasticIteratedGeneticHill-climbing，SIGH）采用