精品毕业论文基于遗传算法的TSP问题研究.doc

《精品毕业论文基于遗传算法的TSP问题研究.doc》由会员分享，可在线阅读，更多相关《精品毕业论文基于遗传算法的TSP问题研究.doc（37页珍藏版）》请在三一办公上搜索。

1、 目 录摘要IAbstractII第1章 绪论- 1 -1.1旅行商问题- 1 -1.2研究意义- 1 -1.3 论文的组织结构- 1 -第2章 遗传算法理论概述- 2 -2.1遗传算法的起源和发展- 2 -2.2遗传算法基本原理- 3 -2.3遗传算法的基本步骤- 4 -2.4 遗传算法的流程图- 4 -2.5遗传算法的特点- 5 -2.6遗传算法的应用- 6 -第3章 TSP问题及研究的基本方法- 8 -3.1 TSP问题概述- 8 -3.2 TSP的应用与价值- 8 -3.3 TSP问题的数学模型- 9 -3.4 TSP 问题的分类- 9 -3.5 现有的求解TSP问题的几种算法- 10

2、 -第4章 遗传算法在TSP的应用- 12 -4.1遗传算法在TSP上的应用- 12 -4.2算法的实现- 12 -4.3编码- 12 -4.4初始化种群- 13 -4.5适应度函数- 13 -4.6选择操作- 13 -4.7交叉操作- 15 -4.8变异操作- 17 -4.9实验结果- 18 -结 论- 20 -展望- 20 -参 考 文 献- 21 -致 谢- 22 -附录程序- 23 -摘 要TSP问题(Traveling Salesman Problem)是已知有n个城市，现有一推销员必须遍访这n个城市，且每个城市只能访问一次，最后又必须返回出发城市。要安排其访问次序，使其旅行路线的总

3、长度最短。TSP是经典的NP-hard组合优化问题之一，也是一个测试算法优劣性的标准问题，且现实中有很多应用问题都可归结或转化为TSP问题。故对此问题的求解具有理论与实用两方面的意义。传统的求解方法在面对较大规模的问题时，很不容易得到最优解。遗传算法(Genetic Algorithms，简称GA)是借鉴生物选择和进化机制发展起来的一种高度并行、随机和自适应搜索算法。特别适合于处理传统搜索算法解决不好的复杂和非线形问题。它的两个最大的显著特点是隐含并行性和全局搜索。对遗传算法及其应用的研究是目前智能计算的研究热点之一。关键词：遗传算法；TSP问题；交叉算子 AbstractThe TSP qu

4、estion is one of most classical NPhard combination optimization questions，and it is also a standard question to test algorithm performanceIn the reality,there al e many application questions can be summed up or converted intoTSP.Therefore solve this problem is significance with both the theory and p

5、racticalTo large-scale problems，the traditional solution method is too inadequate. Genetic Algorithm(GA)is all algorithm which is highly parallel，stochastic and autoadapted searchingIt is profits from one kind which the biological choice and the evolution mechanismEspecially,it qualifies in the ques

6、tions that complex and non-linear for tradition searching algorithmIts two most major outstanding features are conceal parallelism and the global searchTo the genetic algorithm and the application research ofit is one hot spot of the intelligent computation stratosphereKey words：genetic algorithm;TS

7、P; crossover opera第1章 绪论1.1旅行商问题旅行商问题 (Traveling Salesman Problem，TSP)，也称货郎担问题，是指对于给定的甩个城市，旅行商从某一个城市出发，不重复地访问其余每一个城市，最后又返回到原出发城市，要求找出一条旅行路线，使其的旅行所付出的代价最小。旅行商问题是一个比较古老的问题，最早可追溯到Euler提出的骑士旅行问题，同时它也是个“新问题，因为计算的复杂性较高，人们一直在尝试用新的方法来改进求解该问题的复杂度。TSP问题是一个具有广泛的应用背景和重要理论价值的组合优化问题，它是一个典型的NP问题。G=（V，E）为赋权图，V=1，2，

8、N为顶点集，E为边集，Cij表示旅行商经过对应弧段（i，j）所花的费用，如时间、距离、花费等。TSP问题就是要决定一条经过图中所有顶点，当且仅当一次且代价最小的回路，即代价最小的Hamilton回路，为简化问题。1.2研究意义旅行商问题是一个理想化的问题，大多数对于此问题的研究都不是为了直接的实际应用，但这些研究可以经转化后用于许多现实的组合优化问题。在现实生活中，有许多问题都可以归结为TSP问题，如电路板钻孔路线选择、车辆路线问题、计划任务、连锁店货物配送路线、管道铺设、火炬接力等问题，这些问题的求解策略均可依据TSP问题的求解算法来加以实施。所以TSP问题在计算理论上和实际应用上都有很高的

9、价值，将直接带动整个组合优化领域新的发展。而遗传算法是一种的元启发式优化算法,基于遗传算法在许多方面有重要的应用空间。基于此原因，本文的主要是用遗传算法的基本算子解决TSP这个有意义的NP难问题。 1.3 论文的组织结构 第1章绪论。本章论述旅行商问题的基本概念，以及本课题的主要研究内容及其研究意义，并对本文的章节结构加以概述。第2章，概要介绍了遗传算法的起源和发展、思想及应用等问题，并重点介绍了基本遗传算法。第3章 概要介绍了TSP问题的定义和数学模型、研究现状及评价标准，现有的求解TSP问题的几种算法。第4章 本章论述如何用基于遗传算法求解TSP问题。详细论述了用遗传算法在TSP的实现方法

10、和主要参数设置、程序实现。第5章 总结第2章 遗传算法理论概述2.1遗传算法的起源和发展20世纪40年代以来，科学家努力从生物学中寻找用于计算机科学和人工系统的新思维、新方法和新途径，生命科学与工程科学相互交叉、相互渗透、相互促进成为近代科学发展的显著特点之一。遗传算法正是从大自然的杰作生物进化论中得到的灵感和启迪，其基本思想是Darwin进化论和Mendel的遗传学说。Darwin进化论最核心的是自然选择学说。他认为，生物进化是一个缓慢的变化过程，物种不是被创造出来的，而是自然选择的必然结果。“物竞天择，适者生存”。生物要想生存下来，就必须进行生存斗争。斗争是多方面的，有种内斗争、种间斗争以

11、及生物与无机环境间的斗争。只有适应性强的个体才能在斗争中存活下来，并且有更多的机会将有利变异传给后代；而不适应斗争环境、具有不利变异的个体将面临淘汰。Darwin把这种在生存斗争中适者生存、不适者淘汰的过程称为自然选择。Mendel遗传学说最重要的是基因遗传原理。他认为遗传以密码方式存在于细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质。所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。现代遗传学和细胞学的研究表明，生物的遗传物质主要保存在染色体中，染色体由DNA(脱氧核糖

12、核酸)和蛋白质组成；基因则是指携带有遗传信息的DNA序列，是控制性状的基本遗传单位。基因可以精确的复制，也可以发生突变，并可以通过控制蛋白质的合成而控制生物的性状。生物体自身通过对基因的复制和交叉即基因分离、基因自由组合和基因连锁互换的操作使其性状的遗传得到选择和控制。同时，通过基因重组、基因变异和染色体在结构和数目上的变异产生丰富多彩的变异现象。能否将生物进化论应用于科学研究和工程实践中的各种搜索和优化问题中?遗传算法正是从这一疑问开始的。上个世纪60年代，Michigan大学的JHHolland教授开始认识到生物的遗传和自然进化现象与人工自适应系统的相似关系，并将生物遗传机制引入人工自适应

13、系统的研究。1967年，他的学生Bagley JD首次提出“遗传算法”一词，并发展了复制、交叉、变异、显性、倒位等遗传算子。70年代，Holland教授出版了专著(Adaptation in Nature and Artificial Systems)，系统阐述了遗传算法的基本理论和方法，提出了遗传算法的基本定理模式定理，为遗传算法的发展奠定了理论基础。美国DeJong博士基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验，建立了著名的DeJong五函数测试平台。80年代，遗传算法开始在各个领域得到广泛应用。1980年，Smith将遗传算法应用于机器学习领域；Bethke对函数优化

14、的遗传算法进行了系统的研究。1989年，David Goldberg出版了(GeneticAlgorithm in Search,Optimization and Machine Leaming一书，成为论述遗传算法的第一本专著。进入90年代，遗传算法进入了兴盛期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，被广泛地应用于组合优化、生产调度、机器学习、图像处理、人工生命等领域，不仅如此，利用遗传算法进行优化和规则学习的能力也显著提高。1985年，美国召开了第一届遗传算法国际会议(ICGA)，在遗传算法发展史上具有里程碑式的意义。此后ICGA每隔一年举行

15、一次，1999年期，ICGA与GP的系列会议合并为一年一次的遗传与进化国际会议(GECCO)。1994年1月，IEEE神经网络委员会出版了第一本进化计算专集，同年6月组织召开第一届“进化计算”国际会议，以后每年举行一次。2.2遗传算法基本原理遗传算法是从代表问题可能潜在解集的一个种群(Population)开始的，而一个种群则由经过基因(Gene)编码(Coding)的一定数目的个体(Individual)组成。每个个体实际上是染色体(Chromosome)带有特征的实体。作为多个基因的集合，单个染色体是遗传物质的主要载体，其在种群中的命运由其基因组合决定。初始种群产生以后按照优胜劣汰、适者生

16、存的原理，逐代演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度(fitness)大小挑选个体，并借助代表于自然遗传学的遗传算子(Genetic Operators)进行交叉(Grossover)和变异(Mutation)，产生出代表新的解集的种群。这个过程导致种群象自然进化一样，后代种群比前代更加适应于环境，末代种群中最优个体经过解码(Decoding)，可以作为问题的近似最优解。遗传算法采纳了自然进化模型，如选择、交叉、变异、迁移、局域与邻域等。与传统搜索算法不同，遗传算法是从一组随机产生的初始解开始搜索过程。种群中的每个个体是问题的一个解，称为“染色体，染色体是一串符号，比如

17、二进制01串。这些染色体在后续迭代中不断进化，称为遗传。在每一代中用适应度(fitness)来测量染色体的好坏。生成的下一代染色体称为后代(offspring)。后代是由前一代染色体通过交叉(crossover)或者变异(mutation)运算形成的。新一代形成中，根据适应度的大小选择部分后代，淘汰部分后代，从而保持种群大小的稳定性。适应度高的染色体被选中的概率高，这样，经过若干代之后，算法收敛于最好的染色体，它很可能就是问题的最优解或次优解。列出了表2-1生物遗传与遗传算法部分概念的对照表2-1生物遗传与遗传算法的概念对照生物遗传遗传算法基因解中每一分量的特征染色体解的编码个体解种群一组解交

18、配交叉操作变异编码的某一个分量发生变化的过程适应性编码解码后得到的适应度函数值适者生存选择操作 2.3遗传算法的基本步骤 步骤一:确定参变量及其各种约束条件.即确定个体的表现形式和问题的解空间.步骤二: 建立优化模型. 即确定出求解问题的目标函数和数学描述形式及量化方法. 步骤三:确定染色体的编码方法.即确定个体的基因形式. 步骤四:确定解码方法.即确定出个体的基因形式到个体的表现形式的对应关系和转化方式. 步骤五: 确定个体适应度的量化评价方法.即确定出目标函数值同个体适应度的转化规则. 步骤六: 设计遗传算子.即确定出选择算子,交叉算子和变异算子等遗传算子的具体操作方法. 步骤七: 确定遗

19、传算法的有关运行参数.即确定出遗传算法2.4 遗传算法的流程图 图2-1遗传算法流程图 2.5遗传算法的特点传统的优化方法主要有三种：枚举法、启发式算法和搜索算法。随着问题种类的不同以及问题规模的扩大，需要寻求一种能以有限的代价来解决搜索和优化的通用方法，遗传算法正是为我们提供了一个有效途径，它不同于传统的搜索和优化方法。主要区别在于(1)自组织、自适应和自学习性。应用遗传算法求解问题时，在编码方案、适应度函数及遗传算子确定后，算法将利用进化过程中获得的信息自行组织搜索。由于自然选择策略为“适者生存，不适应淘汰，因而适应度大的个体具有较高的生存概率。通常，适应度大的个体具有更适应环境的基因结构

20、，在通过基因重组和基因突变等遗传操作，就可能产生更适应环境的后代。进化算法的这种自组织、自适应特征，使它同时具有能根据环境变化来自动发现环境的特性和规律的能力。自然选择消除了算法设计过程中的一个最大障碍，即需要事先描述问题的全部特点，并要说明针对问题的不同特点算法应采取的措施。因此，利用遗传算法的方法，我们可以解决那些复杂的非结构化的问题。 (2)遗传算法的本质并行性。遗传算法按并行方式搜索一个种群数目的点，而不是单点。它的并行性表现在两个方面，一是遗传算法的内在并行性(inherentparallelisml，即遗传算法本身非常适合大规模并行。最简单的并行方式是让几百甚至上千台计算机各自进行

21、独立种群的演化计算，运行过程中甚至不进行任何通信(独立的种群之间若有少量的通信一般会带来更好的结果)，等到运算结束才通信比较，选取最佳个体。这种并行处理方式对并行系统结构没有什么限制和要求，可以说，遗传算法适合在目前所有的并行机或分布式系统上进行并行处理，而且对运行效率没有太大的影响。二是遗传算法的内含并行性(implicitparallelism)。由于遗传算法采用种群的方式组织搜索，因而可同时搜索解空间内的多个区域，并相互交流信息。使用这种搜索方式，虽然每次只执行与种群规模n成比例的计算，但实质上已经进行了大约O(n3)次有效搜索，这就使遗传算法能以较少的计算获得较大的收益。(3)遗传算法

22、不需要求导或其他辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数。(4)遗传算法强调概率转换规则，而不是确定的转化规则。(5)遗传算法可以更加直接的应用。 (6)遗传算法对给定的问题，可以产生许多的潜在解，最终选择可以由使用者确定。 2.6遗传算法的应用遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学。(1)函数优化函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些

23、非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。 (2) 组合优化随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP问题非常有效。例如遗传算法已经在求解旅行商问题、 背包问题、装箱问题、图形划分问题等方面得到成功的应用(3) 自动控制在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已在其中得到了初步的应用，并显示了良好的效果。基于遗传算法的参数辨识，基

24、于遗传算法的模糊控制规则的学习，利用遗传算法进行人工神经网络的结构优化设计和权值学习等，都显示出了遗传算法在这些领域中应用的可能性。 (4)人工生命 人工生命是用计算机，机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统，自组织能力和自学能力是人工生命的两大主要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要基础理论。第3章 TSP问题及研究的基本方法 3.1 TSP问题概述旅行商问题(Travelling Salesman Problem，简记TSP) 经典说法为：有一名旅行商要从一个城市去若干个城市推销货物，从城市A出发，经其余各城市且每个

25、城市只能访问一次，然后回到城市A，问选择怎样的旅行路线，才能使旅行的总长度最短(各城市间距离为已知)。旅行商问题是组合数学中一个古老而又困难的问题，它易于描述但至今尚未彻底解决，现己归入经典的NP-hard组合优化问题之一，。该问题在图论的意义下就是所谓的最小Hamilton圈问题，由于可以广泛应用在许多领域，所以寻找出实际而有效的算法就显得比较重要了。但是遗憾的是，计算复杂性理论给予我们的结论却是，这种可能性尚属未知。3.2 TSP的应用与价值TSP在现实生活中有很多应用。直观上，最普通的TSP的运用莫过于找出旅行商为遍历每个地理位置上的点的顺序，使他所经历的路径最短。了解了对每个城市访问一

26、次的最优旅行路径能够为旅行节约很多潜在的时间。对提到的实例，图中的节点将通过地理位置顺序连接，而且连接两节点的路径的长度是公制的。在当前，很多的现实事物，包括城市，建筑和地标都已经有了平面电子地图。为解决以上提及的实例，仅需要把期望访问的地理位置具体化，然后用旅行商问题的算法进行求解就行了。TSP在其他领域还有很多重要的实际应用。例如在组装线上的机器。一些机器的目标就是为了在某种材料片上钻削不同的孔。材料可能是电路板、汽车底盘甚至是用来做书架的木板。钻头通过定位装置在材料片上重定位。在某个局部的区域，钻头可以沿着轨迹移动到任何位置。钻头的重定位所消耗的时间依赖于钻头需要移动的距离。旅行商问题的

27、解可以用来找出孔被加工的最优顺序。在装配线的实例中，对每个工件为完成装配过程节约的少许时间意味着一天的产量的相应增加。为了通过TSP解决这个时间的节约问题，对每个节点做了简化，用需要钻孔的位置来代替，而边用节点之间的距离来代替。3.3 TSP问题的数学模型TSP问题的数学模型如下：设有n个城市，寻找一条巡回路径T=(t1，t2，tn)，使得下列目标函数最小：f(T)=(ti,ti+1)+d(tn,t1) 其中ti为城市号，取值为1到n之间的自然数，d(i,j)为城市i和城市j之间的距离，对于对称式TSP，有d(i，j)=d(j，i)。除此之外，模型还有其它一些等价的书写形式，这就不一一列举。

28、TSP问题是组合优化领域中的一个典型问题，涉及求多个变量的函数的最小值。虽然陈述起来很简单，但求解却很困难，它一直是运筹学中最富挑战性的问题之一，且已经被证明是NP完全问题。对于具有一个城市的TSP问题，其可能的路径数目为(n-1)!2，5个城市的情形对应12010=12条路线，10个城市的情景对应362880020=181440条路线。所以对于输入规模为n个城市TSP找到最优解的时间复杂性函数的数量级是O(n!)，当n比较大时，耗费的时间己经是个天文数字，至今尚未找到有效的求解方法。在理论上虽然枚举法可以解这一问题，但是当n较大时，解题的时间消耗会使枚举法显得没有任何实际价值。因此寻求一种求

29、解时间短，能满足实际问题精度要求的解，成为解决该问题的主要途径。快速、有效地解决TSP问题有着极高的实际应用价值，也就吸引了众多领域的学者对它进行研究。尽管TSP仍未找到最优解，但是求解它的算法逐渐在改进。1954年Dantzig，Fulkerson和Johnson解决了49个城市数目的TSP问题，经过半个世纪的研究，目前，最大的已成功求解的旅行商问题有24798个城市。3.4 TSP 问题的分类从 TSP问题映射到图的类型,可以分为两类: (1)城市间的距离都是对称的,它对应的是图论中的无向图; (2)两个城市间的距离是非对称的,它所对应的是图论中的有向图. 从问题本身的限制条件的强弱,可分

30、为三类: 1.不做任何限制(但是一般都要求城市间的费用不为负数),只是给出距离矩阵,求最小回路; 2.要求距离间要满足三角不等式; 3.定义在欧式平面上的 TSP问题,即 EuclidTSP,它给出每个点在欧式平面 上的坐标,而城市间的距离就是以他们的欧式距离来定义.3.5 现有的求解TSP问题的几种算法在求解TSP的算法的过程中，人们一直在寻找切实有效的方法，按招时间出现的顺序大致可分为：传统算法和智能演化算法。传统算法有精确算法和近似优化算法，精确算法又有线性规划方法、动态规划方法、分支定界方法等，而近似算法有插入法、最近邻算法、r-opt算法、混合算法、概率算法等。虽然传统算法能够找TS

31、P问题的最优解，但随着问题规模的不断增长，算法所需要的时间非常巨大，因此只适用于求解规模较小的TSP问题。20世纪80年代以来，一些新颖的智能优化算法，如模拟退火、遗传算法、禁忌搜索、人工神经网络、蚁群算法、粒子群算法、郭涛算法、免疫算法等，通过模拟或揭示某些自然现象(或过程)而得到发展，其思想和内容涉及数学、物理学、生物进化、人工智能、神经科学和统计力学等方面，为解决复杂问题提供了新的思路和手段由于这些算法构造的直观性和自然机理，通常称作智能演化算法，或称为现代启发式算法。引入智能演化算法的原因在于避免陷人局部最优解，希望得到更好的解上界。(1)禁忌搜索算法禁忌搜索算法是局部领域搜索算法的推

32、广，主要思想是标记已经得到的局部最优解，并在进一步的迭代中避开这些局部最优解。此方法需较强技术性，禁忌长度较难取。若禁忌长度过长，则所需内存较大，否则，易陷入局部最优解。(2)模拟退火算法 这是一种源于五十年代、基于Monte Carlo迭代求解思想的随机搜索算法，八十年代才开始应用于组合优化领域，其出发点是将组合优化问题与统计力学的热平衡作类比，把优化的目标函数视作能量函数，模仿物理学中固体物质的退火处理，先加温使之具有足够高的能量，然后再逐渐降温，其内部能量也相应下降，在热平衡条件下，物体内部处于不同状态的概率服从Boltzmann分布，若退火步骤恰当，则最终会形成最低能量的基态。这种算法

33、思想在求解优化问题时，不但接受对目标函数(能量函数)有改进的状态，还以某种概率接受使目标函数恶化的状态，从而可使之避免过早收敛到某个局部极值点，也正是这种概率性的扰动能够使之跳出局部极值点，故而得到的解常常很好。(3)蚁群算法 又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，过模拟蚂蚁的觅食行为， 蚂蚁觅食的时候会在所走过的路径上留下信息激素， 同时信息激素会随时间而挥发.一条路径走过的蚂蚁越多， 留下的信息激素越多; 反过来， 信息激素浓度高的路径上会吸引更多的蚂蚁。通过这种正向反馈， 最终将找到一条最优路径。为了避免蚂蚁

34、两次走上同一条路径( 非法路径) ， 为每个蚂蚁设置一个禁忌表以记录它已走过的路径。该算法的优点是: 它是一种自 适应度、自组织、本质上并行的方法，而且是一种正向反馈的方法，可以促使整个系统向最优解进化，而且参数少、易于调整，易于移植到其他组合优化问题。 但是，它存在收敛慢、易于陷人局部最优的缺点。 (4)人工神经网络人工神经网络(Artificial Neural Network，ANN)，是由大量处理单元即神经元(Neurons)互相连接而成的网络，对人脑进行抽象，简化和模拟的一种工程系统，反映人脑的基本特性。人工神经网络算法成为近年来的热点研究领域，涉及到数学、电气工程、计算机工程、物理

35、学等诸多学科，其应用领域包括了建模、时间序列分析、模式识别和控制等，并且仍然在一断扩展。作为神经网络的基本单元，神经元模型具备三个基本要素。其一是有一组突触或连接，常用表示内部神经元的联接强度，或者称为权值，取值范围可在负值和正值之间，其二是可以反映生物神经元时空整合功能的输入信号累加器，其三是具有一个激励函数用于限制神经元的输出。第4章 遗传算法在TSP的应用4.1遗传算法在TSP上的应用 在遗传算法研究中，TSP问题已被广泛地用于评价不同的遗传操作及选择机制的性能。TSP问题因其典型性已成为各种启发式的搜索，优化算法的间接比较标准，而遗传算法方法就本质来说，主要处理复杂问题的一个鲁棒性强的

36、启发式随机搜索算法。因此遗传算法在TSP问题求解方面的应用研究，对于构造合适的遗传算法框架，建立有效的遗传操作以及有效地解决TSP等有着多方面的重要意义。4.2算法的实现图4-1遗传算法运用在TSP上的流图程4.3编码遗传算法的进化过程是建立在编码机制基础上的，编码对于算法的性能，如搜索能力和种群多样性等影响很大。如何将问题的解转换为编码表达的染色体是遗传算法的关键问题。编码机制的主要工作是把对象抽象为由特定符号按一定顺序排成的串。这就如同研究生物遗传是从染色体着手，而染色体则是由基因排成的串。遗传算法中经常使用二进制串进行编码，其优点是编码、解码操作简单，交叉、变异等操作也易于实现，且便于应

37、用模式定理进行理论分析；其缺点主要是处理连续函数的优化问题时存在映射误差：编码长度较小时达不到精度要求，度较大时又会使算法搜索空间过大。4.4初始化种群选择一个群体，就是选择一个个体的集合。这个初始群体也就是问题假设解得集合。在遗传算法求解TSP问题中通常以随机方式产生串或者个体的集合。初始种群个数越多，得到最优解的希望越大，但个数过多会导致每进行一轮的机器时间变长，致使算法效率低下。4.5适应度函数在研究自然界中生物的遗传和进化现象时，生物学家常常使用适应度这个术语来衡量某个物种对环境的适应率。适应度较高的物种将会得到更多的繁殖的机会；从而导致适应度低的物种被淘汰。度量物种适应度的函数就被称

38、为适应度函数。本文中适应度函数取为哈密尔顿圈的长度的倒数。void CalFitness(PTSP city)int i,j;int start,end;for(i=0;iDistancei=0;for(j=1;jcolonyij-1;end=city-colonyij;city-Distancei=city-Distancei+CityDistancestartend;city-fitnessi=N/(city-Distancei);4.6选择操作遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群体中的一种遗传运算。选择操作的目的是为了避免基因缺失，提高全局

39、收敛性和计算效率。常用的选择可略包括以下几种：(1) 轮盘赌法。(2) 锦标赛选择。(3) 最优保存策略。(4) 期望值方法。(5) 排序选择方法。比较常用的就是轮盘赌法，以及最优策略保留法。本文采用的是轮盘赌法。在轮盘赌法中，各个个体的被选择概率和其适应度值成比例。设群体大小为N，个体i的适应度值Fi，则个体i被选择的概率Psi为：Psi=Fi (n=l，2n) 显然，概率Psi反映了个体i的适应度在整个群体的个体适应度总和中所占的比例。根据个体适应度值的大小，适应度值越大的，其概率Psi越大，被选择到的机会也越多，从而其基因结构被遗传到下一代的可能性也越大，反之亦然。轮盘赌的具体执行过程如

40、下：a)先计算出种群中所有个体的适应度的总和。b)其次计算出每个个体的相对适应度的大小，作为被选中的概率。void Select(PTSP city) /选择算子 double tempRand,tempflag1;int i,j;for(i=0;iPOPSIZE;i+)/选POPSIZE次tempRand=(rand()%100000)/100000.0*3;tempflag1=0;for(j=0;jPOPSIZE&tempflag1=0;j+)if(tempRandaddFitnessj)/轮盘赌选中第j个tempflag1=1;/if(i!=city-BestFitCityXuh)if(

41、city-fitnessj=city-fitnessi&i!=j)copyColony(i,j,city);return; 4.7交叉操作 基于TSP问题的顺序编码，若采取简单的一点交叉或多点交叉策略，必然以极大的概率导致未能完全遍历所有城市的非法路径 1 2 3 4| 5 6 7 8 8 7 6 5 |4 3 2 1若采取一点交叉，且交叉点随机选为4，则交叉后产生的两个后代为 8 7 6 5 5 6 7 8 1 2 3 4 4 3 2 1显然，这两个子路径均未能遍历所有8个城市，都违反了TSP的约束条件。针对这一问题，当然可以采取上述构造惩罚函数的方法，但是实验效果不佳。解决这一约束问题的另

42、一种处理方法是对交叉，变异等遗传操作作适当的修正，使其自动满足TSP的约束条件，本文采用部分匹配交叉法 ： 部分匹配交叉中先依据均匀随机分布产生两个位串交叉点，定义这两点之间的区域为一匹配区域，并使用位置交换操作交换两个父串的匹配区域，两父串及匹配区域为 A=9 8 4 |5 6 7| 1 3 2 0 B=8 7 1 |2 3 0| 9 5 4 6 首先交换A 和B的两个匹配区域，得到 A1=9 8 4 |2 3 0| 1 3 2 0 B1=8 7 1 |5 6 7| 9 5 4 6对于A1，B1两个串中匹配区域以外出现的遍历重复，依据匹配区域内的位置映射关系，逐一进行交换，对于A1有2到5,

43、3到6,0到7的位置符号映射，对A1的匹配区以外的2，3，0分别以5,6,7替换，则得 A2=9 8 4 |2 3 0 |1 6 5 7 B2=8 0 1| 5 6 7 |9 2 4 3 这样，每个子串的次序部分有其父串确定。 这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体，也即对两个父染色体的部分结构进行重组，以产生新一代子染色体。遗传交叉的主要目的是子代尽可能地继承父代的优秀基因。 void Cross(PTSP city,double pc)/交叉概率是pcint crossNum,i;int cityCross2CITY_NUM+1;int

44、 tempXuh2;crossNum=int(POPSIZE*pc);for(i=0;icrossNum/2;i+)tempXuh0=rand()%(POPSIZE-1);dotempXuh1=rand()%(POPSIZE-1);while(tempXuh0=tempXuh1);copyCityXuhTo(city,tempXuh,cityCross);crossTwo(city,tempXuh,cityCross);/Cross()4.8变异操作是指将个体染色体编码串中的某些基因座上的值用其它的等位基因来替换，从而形成新的个体。在遗传算法中，变异操作并不是最主要的。遗传算法强调的是杂交功能。变异操作是改善遗传算法的局部搜索能力和维持群体的多样性防止早熟现象。如图4-2所示： 4-2 变异操作示意图代码：void Mutation(PTSP city,double pm)/变异概率是pmint changePoint2,temp,j;int selCity;for(j=1;jBestFitCityXuh);dochangePoint0=rand()%(CITY_NUM-1);changePoint1=rand()%(CITY_NUM-1)+1;while(changePoint0=changePoint1|changePoint0=0|