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

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

1、摘要旅行商问题(TSP)是著名的NP完全难题，也是组合优化、计算机科学界经典的问题之一。因此对TSP寻找出实际而又有效的算法，就具有重要的理论意义和实际应用价值。而遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法，具有简单、通用、稳健等特性，能依概率收敛到问题的全局最优解。这就是本文提出的改进遗传算法求解TSP的目的和意义。本文从旅行商问题的概还出发，介绍了TSP的数学描述与分类，在原有的基础上，对TSP作了更细致的分类;介绍了遗传算法的基本概念、原理、步骤及意义，将遗传算法的一些主要的操作过程用数学形式表示，使其变得简单而又公式化

2、;通过依赖于遗传操作的基本遗传机理的叙述，为以后算法的改进打下理论基础。本文主要工作如下:(1)分析了影响遗传算法性能的一些重要参数，通过基本遗传算法(SGA)对不同种群规模的TSP问题分别进行计算机模拟仿真，讨论了基本遗传算法在求解TSP中存在的不足。(2)针对现有的遗传算法的不足和铭P本身的特点，提出了三种改进的混合遗传算法(HGA)。首先提出了混合遗传算法1(HGAI)，在HGAI中采用了依概率近邻法，用其生成的初始种群优于随机产生初始种群，较近邻法略差，但个体多样性水平优于近邻法，而且生成的初始种群的随机路径的总长度服从正态分布。将依概率

3、的近邻法和边重组交叉算子与启发式变异算子结合起来得到HGAI。其次为了进一步改进其性能，保证算法的全局收敛性，混合遗传算法n(HGAn)应用改良圈算法及最大容许停滞代数，不仅避免了HGAI中终止进化代数的选取问题，而且大大加快了算法的收敛速度，使算法具有很好的鲁棒性。同时在HGAn中采取杰出者记录与“父子混合”选择策略以及随机因素控制参数a，从理论上保证了算法的全局收敛性。最后在混合遗传算法m(HGA[I)中引入多元回归分析中的三均值的概念对遗传算法的控制参数进行动态调整，从而克服用不变的控制参数来控制遗传进化引起的“早熟”，提高了算法的搜索效率

4、，使得算法的性能得到更好的改善。(s)对设计出的三种混合遗传算法通过数据进行了计算机仿真模拟，对算法的性能进行了分析测试。关键词:遗传算法旅行商问题混合遗传算法NPCMasterDegn沈D七seriationAPPUca幼onaudl口P研恤entofC掩ueticAlgorithminsolvingTSPCandidate:XueHongZ址comPutin目Di碑凶ed勿Zha此Ba切比ang，anUnlve“ity，刀，an710069ABSTRACT肠avelingsalesmanProblem(铭玛hasbeCOmcthewell·如

5、。wnnondelen刀加sticpolynomialcomPletenessPuzzle，itisalsooneofthewoildtyPicalcombination0Ptiln七ationandcomPuterSCien沈Problem.Therefore，细dingoutpractica1andeficieniaigorithmbaSanimPortanttbe0retica1aswel1asPract」cal叩plicatlonsignifcance.TheGeueticaigorithmisakindofrandomsea代hingm

6、ethod5汕ulatingbfologica1naturalselectionandgeneticmecb耐sm，whichnotonlyhasthecharacleristicofbeingslinPle，u苗versal，andstable，botalsoconvergetheglobalsolutfonbascdonProbability.Thisist加veryPurposeofmentioningtheimProvodgeneticalgorithmtosolveTSP恤thisossay.Theessaystartswiththcg

7、eneralacc0untofTSP，exPlainsthemathematicaldescriPtionandclassificationofTSP.0ntheOriginaibasis，theessaymadethoroughdassificationofTSP;TheessayintroducedthebasiccoocePt，PrinciPle，Procedurcandsigni石can“ofthegeneticalgoril肠m.ItaisodisPlayedsomcmajorProcessinmathematicways，makiDg

8、thegenetica1goritbmcomPrehensibleandfonnul让ed.T五roughthedescrjPtiono