探析遗传算法在tsp上的应用及改进

《探析遗传算法在tsp上的应用及改进》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：-】堕生LY978327长安大学硕士学位论文遗传算法在TSP上的应用及改进指导教师姓名．益塞盘堂盔鱼二到整蕉申请学位级别亟±学科名称銮通信息工程丞蕉剑论文提交日期塑!：!论文答辩日期型生!且!目答辩委员会主席：学位论文评阅人：摘要旅行商问题(TSP)是著名的NP完全难题，也是组合优化、计算机科学界经典的问题之一。因此对TsP寻找出实际而又有效的算法，就具有重要的理论意义和实际应用价值。而遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法，具有简单、通用、稳健等特性，能依概率收敛到问题的全局最优解。这就是本文提出的改进遗传算法求解TSP的目的

2、和意义。本文从旅行商问题的概述出发，介绍了TsP的数学描述与分类，在原有的基础上，对TSP作了更细致的分类；介绍了遗传算法的基本概念、原理、步骤及意义，将遗传算法的一些主要的操作过程用数学形式表示，使其变得简单而又公式化；通过依赖于遗传操作的基本遗传机理的叙述，为以后算法的改进打下理论基础。本文主要工作如下：(1)分析了影响遗传算法性能的一些重要参数，通过基本遗传算法(SGA)对不同种群规模的砖P问题分别进行计算机模拟仿真，讨论了基本遗传算法在求解TsP中存在的不足。(2)针对现有的遗传算法的不足和髑P本身的特点，提出了三种改进的混合遗传算法(HGA)。首先提

3、出了混合遗传算法I(HGAI)，在HGAI中采用了依概率近邻法，用其生成的初始种群优于随机产生初始种群，较近邻法略差，但个体多样性水平优于近邻法，而且生成的初始种群的随机路径的总长度服从正态分布。将依概率的近邻法和边重组交叉算子与启发式变异算子结合起来得到HGAI。其次为了进一步改进其性能，保证算法的全局收敛性，混合遗传算法Ⅱ(HGAⅡ)应用改良圈算法及最大容许停滞代数，不仅避免了HGAI中终止进化代数的选取问题，而且大大加快了算法的收敛速度，使算法具有很好的鲁棒性。同时在HGAII中采取杰出者记录与“父子混合”选择策略以及随机因素控制参数口，从理论上保证了算

4、法的全局收敛性．最后在混合遗传算法Ⅲ(HGAⅢ)中引入多元回归分析中的三均值的概念对遗传算法的控制参数进行动态调整，从而克服用不变的控制参数来控制遗传进化引起的“早熟”，提高了算法的搜索效率，使得算法的性能得到更好的改善。(3)对设计出的三种混合遗传算法通过数据进行了计算机仿真模拟，对算法的性能进行了分析测试。关键词：遗传算法旅行商问题混合遗传算法NPCMasterDegreeDissenati佃AppHcaHOnandImprOV哪entofGene6cAJgOrithminSoIVingTSPCandidate：XueH蛆弘址供e细ork∞mputin曲D

5、irect脚byZhangBaiyich粕g’姐Unive腭i饥】

6、【i’an7l00691hvelingsalesm姐Problem∞P)h觞becomethewell·lmo、】l，nnondete锄jnisticpolynomialcompletenessp叱zle，itisalsOoncoftheworldtypical锄binationoptimization卸dcomputersdenccprObl锄．Therefore，句1dingoutp删cal锄dcffidenta190ritllmh丛翘imponantthcoretical勰wcll觞pr

7、actical印pli龃tionsi口ificancc．neG∞eticalgoritllmiSaldndofmdomse砌ingme∞dsimulatiIlgbiolo百calnaturalselectionaIldgencticmechanism，whicbnotonlyh舔mecharacteristicofbeingsinIple，ullivers吐粕dsklble，butalsoconVcrgcthegIobalsoIutionb龉edonprobability．ThisistheVer)，purposeofmcntiollingtheimpraVe

8、dg∞etica190ritlIIIltosolveTSPiIIthisessay．TheessaystanswiththcgeneralaccoumofTSP，explainsthemathematicaldescription卸dd舔sificationofTSP．0ntheorigiIIaIb嬲is，mcessaymdethorou曲d勰si丘cati∞ofTsP；neessayill仃0ducedtlleb嬲icc0Ⅱ唧t，principle，p烈剃ureandsi印访啪ccofthcgcneticalgorithm．Italsodisplaycd∞m

9、emajorpmccssinmatll