《遗传算法研究与应用论文.doc》由会员分享，可在线阅读，更多相关《遗传算法研究与应用论文.doc（37页珍藏版）》请在三一办公上搜索。
1、毕业设计（论文）设计论文题目： 遗传算法研究与应用 学生姓名：学生学号：专业班级：学院名称：指导老师：学院院长：5月 22 日遗传算法研究与应用摘要遗传算法（Genetic algorithms, GAs）是借鉴生物界自然选择和重组机制的随机的搜索算法。由于它简单易行、鲁棒性强，应用范围极为广泛，并且已在众多领域得到了实际应用，引起了广大学者和工程人员的关注。Traveling Salesman Problem（TSP）问题是一个典型NP难题，是衡量近似算法效率的主要标准，因此设计TSP问题的近似算法具有非常重要的意义。本文讨论遗传算法及其对于TSP问题的解决方法。论文首先介绍了遗传算法的基本
2、概念、原理、意义及发展现状。通过对遗传算法基本理论的学习和研究，提出了解决TSP问题的算法，并详细给出了算法中的编码方案、适应度函数、选择算子、交叉算子、变异算子。最后用C+语言设计并实现了该算法，结果表明该算法可以在较短的时间内得到TSP问题的近似最优解。关键词：遗传算法；TSP问题；适应度函数；交叉；变异Research and Application of Genetic AlgorithmsAbstractGenetic algorithms (GAs) are optimization search algorithms based on the mechanics of artif
3、icial selection and genetic recombination operators. They are simple, robust and easy to implement. They have been used in many fields. For these reasons now they are the hot research field which has got many scholars attention. Traveling Salesman Problem (TSP) is a classic NP problem, which is the
4、main standard of measuring the efficiency of approximative algorithms. So the solution of the problem has has very important significance. The paper discusses the basic genetic algorithms and their application.The essay first introduces the basic concepts, principle, procedure, significance and char
5、acteristics of genetic algorithms. By learning the basic theory of genetic algorithms one solution of TSP is given. The detailed coding scheme, fitness function, selection operator, cross operator and mutation operator of the solution are also given. Finally using C+ implement the solution. The resu
6、lt of the program show that the algorithm can get optimal solution of the problem quickly. Keywords: Genetic Algorithms(G A); Traveling Salesman Problem( TSP); fitness function; cross operator; mutation operator;目 录1绪论11.1课题背景11.2课题研究意义21.3国内外研究现状31.4论文内容52遗传算法简介62.1遗传算法基本概念62.2遗传算法基本原理72.3遗传算法的步骤83
7、遗传算法基本理论113.1模式定理113.2积木块假设与欺骗问题123.3收敛性分析134旅行商问题概述144.1旅行商问题的定义和数学模型144.1.1定义144.1.2数学模型144.2旅行商问题的计算复杂性154.3研究旅行商问题的意义165遗传算法在巡回旅行商问题中的应用185.1旅行商问题的建模185.1.1编码185.1.2适应度函数185.2遗传算法中三个算子的设计195.2.1选择算子的设计205.2.2交叉算子的设计215.2.3变异算子的设计255.3遗传算法求解旅行商问题的步骤275.4测试结果276结束语29致 谢30参考文献:311 绪论1.1 课题背景遗传算法（Ge
8、netic Algorithm，GA），是一类以达尔文的自然进化论与遗传变异理论为基础的求解复杂全局优化问题的仿生型算法。它借鉴生物界自然选择和自然遗传机制，以概率论为基础在解空间中进行随机化搜索，最终找到问题的最优解。遗传算法的兴起是在80年代末90年代初期，但是它的历史可以追溯到60年代初期。早期的研究大多以对自然遗传系统的计算机模拟为主。早期遗传算法的研究特点是侧重于对一些复杂的操作的研究。其中像自动博弈、生物系统模拟、模式识别和函数优化等给人以深刻的印象，但总的说来，这是一个无明确目标的发展时期，缺乏带有指导性的理论和计算工具的开拓。这种现象直到70年代中期由于Holland和DeJo
9、ng的创造性研究成果的发表才得到改观。1967年，Bagley在他的论文中首次提出了遗传算法 1这一术语，并讨论了遗传算法在自动博弈中的应用。1970年，Cavicchio把遗传算法应用于模式识别中。第一个把遗传算法应用于函数优化的是Hollstien，1971年他在论文计算机控制系统中的人工遗传自适应方法中阐述了遗传算法用于数字反馈控制的方法。1975年在遗传算法研究的历史上是十分重要的一年，Holland出版了他的著名专著自然系统和人工系统的适配，该书系统的阐述了遗传算法的基本理论和方法，并提出了对遗传算法理论研究和发展极为重要的模式理论（schemata theory），该理论首次确认了
10、结构重组遗传操作对于获得隐并行性的重要性。J. Holland教授和他的研究小组围绕遗传算法进行研究的宗旨有两个：一是抽取和解释自然系统的自适应过程，二是设计具有自然系统机理的人工系统。同年，DeJong完成了他的重要论文遗传自适应系统的行为分析，他把Holland的模式理论和他的计算实验结合起来，这可以看作遗传算法发展过程中的一个里程碑，尽管DeJong和Hollstien一样主要侧重于函数优化的研究，但他将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟（generation gap）等新的遗传操作技术，为遗传算法及其应用打下了坚实的基础。进入80年代，遗传算法迎来了兴盛发展时
11、期，理论研究和应用研究都成了十分热门的话题。可以认为，DeJong的研究工作为遗传算法及其应用打下了坚实的基础，他所得出的许多结论，迄今仍具有普遍的指导意义。1.2 课题研究意义由于遗传算法不受搜索空间的限制性假设的约束, 因此不必要求诸如连续性、导数存在和单峰等条件，同时遗传算法还具有以下特点：1、遗传算法是利用决策变量集的某种编码进行运算，而不是直接作用在决策变量集上，通用性强。2、遗传算法能同时使用多个搜索点的搜索信息。传统的优化算法往往是从解空间中的一个初始解开始最优解的迭代搜索过程。而遗传算法从一个解的种群开始搜索，而不是从单个解开始，就像在解空间撒网一样，可以对不同区域采样，并不断
12、交换信息。这使得它减少了陷入局部优解的风险，能以较大概率找到全局最优解。3、遗传算法在寻优过程中仅利用解的适应度函数信息作为寻优的依据。它对目标函数几乎无要求，也不涉及映射空间或函数的连续性，仅使用由目标函数值变换来的适应度函数值，就可确定进一步的搜索方向和搜索范围。而传统搜索算法不仅要利用目标函数值，而且往往需要目标函数的导数值等其他一些辅助信息才能确定搜索方向。4、遗传算法使用概率搜索技术，以一种概率的方式来进行搜索，从而增加了其搜索过程的灵活性。而很多传统的优化算法使用的是确定性的搜索方法，这种确定性往往可能使得搜索永远达不到最优点，因而也限制了算法的应用范围。5、遗传算法具有本质并行性
13、，包括内在并行性和隐并行性。内在并行性说明遗传算法非常适合大规模并行运算，而隐并行性使得遗传算法能以较少的计算获得较大的收益。遗传算法的这些特点使得它比传统搜索方法具有更大的优越性，适用范围更广并且能够应用于一些到目前为止人们知之甚少的困难问题领域。遗传算法提供了一种求解复杂、困难优化问题的通用框架，它不依赖于问题的具体领域，不要求目标函数有明确的解析表达，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面是遗传算法的一些主要应用领域6 7：函数优化问题。函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。很多人构造出了各种各样的复杂形式的测试函数来评价遗传算法的性能
14、。而且对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。组合优化问题。随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题，人们已意识到应把主要精力放在寻求其满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于求解组合优化问题非常有效。遗传算法已经在求解旅行商问题、图形划分问题等方面得到成功的应用。生产调度问题。生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以求解，也会因简化太多而使求解结果与实际相差甚远
15、。由于可以采用字符编码，而且不必使用恰好的目标函数估值，遗传算法也成为解决复杂调度问题的有效工具。在单件生产车间调度、流水线生产车间调度、生产规划、任务分配、虚拟企业中的伙伴选择方面遗传算法都得到了有效的应用。自动控制。在自动控制领域有很多与优化相关的问题需要求解，而且这些优化问题通常要么是通过积分表达的，要么是写不出明确而严格的解析表达式。遗传算法在求解这类自动控制问题方面已显示出其独特的优点。例如，用遗传算法进行航空控制系统的优化、用遗传算法优化设计透平机械、设计模糊控制器等，都取得了较好的效果。机器学习。学习能力是高级自适应系统所应具备的特征之一。基于遗传算法的机器学习在很多方面都得到成
16、功应用。例如，遗传算法被用于学习模糊控制规则、确定模糊集的隶属函数、改进模糊系统的性能；被用来调整人工神经网络的连接权及网络拓扑优化。此外，遗传算法还被应用到反问题求解、机器人学习、生物计算、图像处理、人工生命以及遗传编程等领域。1.3 国内外研究现状进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已
17、从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四
18、是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划（Evolution Programming ,EP）以及进化策略（Evolution Strategy ,ES）等进化计算理论日益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的只能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。1991年D.Whitey在
19、他的论文中提出了基于领域交叉的交叉算子（Adjacency based crossover），这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了TSP问题中，通过实验对其进行了验证。D.H.Ackley等提出了随即迭代遗传爬山法（Stochastic Iterated Genetic Hill-climbing，SIGH）采用了一种复杂的概率选举机制，此机制中由m个“投票者”来共同决定新个体的值（m表示群体的大小）。实验结果表明，SIGH与单点交叉、均匀交叉的神经遗传算法相比，所测试的六个函数中有四个表现出更好的性能，而且总体来讲，SIGH比现存的许多算法在求解速度方面更有竞争力。H
20、.Bersini和G.Seront将遗传算法与单一方法（simplex method）结合起来，形成了一种叫单一操作的多亲交叉算子（simplex crossover），该算子在根据两个母体以及一个额外的个体产生新个体，事实上他的交叉结果与对三个个体用选举交叉产生的结果一致。同时，文献还将三者交叉算子与点交叉、均匀交叉做了比较，结果表明，三者交叉算子比其余两个有更好的性能。 国内也有不少的专家和学者对遗传算法的交叉算子进行改进。2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解
21、决经典遗传算法的收敛到局部最优值问题2004年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现象，提出了一种用基因块编码的并行遗传算法（Building-block Coded Parallel GA，BCPGA）。该方法以粗粒度并行遗传算法为基本框架，在染色体群体中识别出可能的基因块，然后用基因块作为新的基因单位对染色体重新编码，产生长度较短的染色体，在用重新编码的染色体群体作为下一轮以相同方式演化的初始群体。2005年，江雷等针对并行遗传算法求解TSP问题,探讨了使用弹性策略来维持群体的多样性,使得算法跨过局部收敛的障碍,向全局最优解方向进化。1.4 论文内容本文内容安排
22、如下：第一章：绪论。介绍本课题的选题背景和研究现状以及文章结构。第二章：简要介绍了遗传算法的基本概念、原理、实现步骤。第三章：叙述了遗传算法的主要理论：模式定理、积木块假设，以及遗传算法的收敛性的简单说明。第四章：就在旅行推销商问题做了简要介绍，并对旅行推销商问题的数学模型，计算的复杂度和求解该问题的意义进行简单概要。第五章：提出了遗传算法求解旅行商问题的一种方式，并详细给出了算法中的编码方案、适应度函数、选择算子、交叉算子、变异算子及部分源码。第六章：结束语。文章的最后是参考致谢和参考文献。2 遗传算法简介2.1 遗传算法基本概念遗传算法的基本思想是基于Darwin进化论和Mendel的遗传
23、学说的。 Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些能适应环境的个体特征才能保留下来。 Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。 由于遗传算法是由进化论和遗传学机理产生的直接搜索优化方法，所以在这个算法中要用到各种进化
24、和遗传学的概念。这些概念如下： 1.串它是个体的形式，在算法中为二进制串，并且对应于遗传学中的染色体。 2.种群 个体的集合称为群体，串是种群中的元素 3.种群大小 在种群中个体的数量称为种群的大小。 4.基因 基因是串中的元素，基因用于表示个体的特征。例如有一个串S1011，则其中的1011这4个元素分别称为基因。 5.基因位置 一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置在串中由左向右计算，例如在串S1101中，0的基因位置是3。基因位置对应于遗传学中的地点。 6.基因特征值 在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基
25、因特征值为2；基因位置1中的1，它的基因特征值为8。7.串结构空间在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型的集合。 8.参数空间 这是串空间在物理系统中的映射，它对应于遗传学中的表现型的集合。九、适应度 表示某一个体对于环境的适应程度。 遗传算法还有一些其它的概念，这些概念在介绍遗传算法的原理和执行过程时，再进行说明。2.2 遗传算法基本原理遗传算法GA把问题的解表示成“染色体”，在算法中也就是二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也就是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选
26、择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代的进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串bi处，即求出最优解。 长度为L的n个二进制串bi(i1，2，n)组成了遗传算法的初始解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种： 1选择 这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生。由于在选择
27、用于繁殖下一代的个体时，是根据个体对环境的适应度来决定其繁殖量的，故而有时也称为非均匀再生。 2交叉 这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。交叉算子示意如图1.1。 图1.1 交叉算子示意图3变异 这是在选中的个体中，对个体中的某些基因按变异概率P执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反之亦然。2.3 遗传算法的步骤1初始化 选择一个群体，即选择一个串或个体的集合bi，i=1，2，.n。这个初始的群体也就是问题假设解的集合。一般取n30-160。 通常以随机方法产生串或个体的集合bi,i1，2，.n。问题的
28、最优解将通过这些初始假设解进化而求出。 2选择 根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。 给出目标函数f，则f(bi)称为个体bi的适应度。以公式（1-1） P选中bi (1-1) 为选中bi为下一代个体的次数。 显然。从上式可知： (1)适应度较高的个体，繁殖下一代的数目较多。 (2)适应度较小的个体，繁殖下一代的数目较少，甚至被淘汰。 这样，就产生了对环境适应能力较强的后代。从问题求解角度来讲，就是选择出和最优解较接近的中间解。 3交叉 对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中
29、的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。 例如有个体 S1=100101 S2=010111 选择它们的左边3位进行交叉操作，则有 S1=010101 S2=100111 一般而言，交叉概率P。取值为0.250.75。 4变异 根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。 例如有个体S101011。 对其的第1，4位置的基因进行变异，则有
30、S=001111 单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为当所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。 5全局最优收敛 当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。 图1.2中表示了遗传算法的执行过程 图1.2 遗传算法原理 3 遗传算法基本理论3.1 模式定理模式定理是由Holland 在1971 年提出的，它是GA
31、的基本定理。它将GA的运算过程理解为模式运算过程，并从模式运算的角度解释GA 的性能特点。模式是描述字符串集的模板，反映字符串集中串的某些位置上存在的相似性。在本节的叙述中，仅就二进制编码的情况进行讨论。【定义2.1】基于三值字符集0,1,*所产生的能描述具有某些结构相似性的0、1 字符串集的字符串称作模式。例如，模式S = 01*0*描述了所有在位置1 和位置4 上为0，在位置2 上为1的字符串，该模式描述的字符串集合为01000，01001，01100，01101。也就是：S = 01*0* = 01000，01001，01100，01101事实上，模式的概念使得我们可以简明地描述具有相似
32、结构特点的个体编码字符串。在引入模式的概念后，遗传算法的本质就是对模式所进行的一系列运算，遗传运算过程中的个体通过模式联系起来。通过这些遗传运算，一些比较差的模式逐渐被淘汰，而一些较好的模式逐步被遗传和进化。在进行遗传算法的理论分析时，往往需要定量地估计模式运算。因此，有必要引入以下两个概念：模式阶和模式定义距。【定义2.2】模式H 中确定位置的个数称为模式的模式阶(Schemata Order)，记作O(H)。模式H 中第一个确定位置和最后一个确定位置之间的距离称为模式的定义距(Schemata Defining Length)，记作(H)。根据定义2.2，O(101*0) = 4，(101
33、*0) = 4；O(0*1*) = 2，(0*1*) = 3。而对于H = *1、H = *0*之类的模式，由于他们只有一个确定位置，所以我们规定它们的定义距为0，如(*0*) = 0。当字符串的长度确定时，模式的阶数越高，与该模式相匹配的样本数目就越少，该模式的确定性也就越高。而模式的定义距越大，则在遗传运算中，该模式被遗传运算破坏的概率越大，生存概率越小。【定理2.1】模式定理在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中将得以指数级增长。模式定理可以用数学形式表示为： （21）其中，H 表示一个模式，m(H,t) 表示在第t 代种群中
34、存在的模式H 中串的个数。f (H) 表示在第t 代种群中模式H 串的平均适应度，表示第t 代种群的平均适应度，l 表示串的长度, p是串之间发生交叉的概率，p是一个串发生变异的概率，(H) 表示模式H 的定义距, o(H) 表示模式H 的阶。模式定理保证了遗传优化过程中较优解的样本呈指数级增长，在一定意义上可以解释基本遗传算法的优化本质，同时也给遗传算法的应用提供了指导作用。3.2 积木块假设与欺骗问题模式定理说明，低阶、短定义距、平均适应度高的模式被交叉切断的可能性低，随着世代交替其数量将增加。这种类型的模式称为积木块。【定义2.3】具有低阶、短定义距以及高适应度的模式称作积木块。【假设2
35、.1】积木块假设积木块在遗传算子的作用下相互结合，能生成高阶、长定义距、高平均适应度的模式，并最终生成全局最优解。模式定理说明了积木块的样本数呈指数级增长，亦即说明了用遗传算法寻求最优样本的可能性；而积木块假设说明了用遗传算法求解各种问题的基本思想，即通过积木块之间的相互拼接能够产生出问题更好的解，表明遗传算法具有全局寻优能力，能够寻求到最优样本。到目前为止，上述假设并未得到完整而严密的数学证明，但大量的实践对这一假设提供了强有力的支持。如果一个问题的编码满足积木块假设，那么用遗传算法求解的效率较高，否则用遗传算法求解的效率较低。应用实践表明，存在一类用遗传算法难以求解的问题，称为“GA-难”
36、问题。属于“GA-难”的问题一般包括有孤立的最优点，在搜索过程中，低阶积木块错误地引导搜索过程，不能发现高阶积木块，通过欺骗遗传算法，使其进化过程偏离最优解，最终使遗传算法发散，这种现象称为欺骗。实际上，目前尚未没有解决这类问题的较好的方法，也无法判断一个问题包含欺骗的多少与问题相对于遗传算法的难易程度。不过，现实中遇到的各种应用问题中，遗传算法大部分是适用的。3.3 收敛性分析模式定理虽然指出了具有优良结构的模式在算法的进化过程中的演变趋势，但是，它并未回答了遗传算法最终收敛于最优解的概率为多少。积木块假设虽然指明了遗传算法能够收敛于全局最优解，但是仅仅是通过大量的应用数据来证明其有效性，还
37、没有完整而严密的数学证明。利用马尔可夫链对遗传算法的分析严格论证了遗传算法收敛性方面的一些重要性质，有力地支撑了遗传算法的理论基础。下面是由马尔可夫链推导出来的一些结论，具体证明可以参考文献8。【定理2.3】基本遗传算法收敛于最优解的概率小于1。【定理2.4】使用保留最佳个体策略的遗传算法够收敛于最优解的概率为1。通过上述定理可以看出，基本遗传算法收敛于最优解的概率小于1，而通过对基本遗传算法进行改进，修正它的选择策略，就能使算法一定收敛于最优解。这两个定理不仅在理论上是模式定理和积木块假设的有力补充，更为实际的应用中的算法收敛提供了保证。4 旅行商问题概述4.1 旅行商问题的定义和数学模型4
38、.1.1 定义旅行商问题是组合数学中一个古老而又困难的问题，它易于描述但至今尚未彻底解决，现己归入所谓的NP完全问题类，经典提法为:有一货物推销员要去若干个城市推销货物，从城市1出发，经其余各城市一次，然后回到城市1，问选择怎样的行走路线，才能使总行程最短(各城市间距离为己知)。该问题在图论的意义下就是所谓的最小Hamilton圈问题，由于在许多领域中都有着广泛的应用，因而寻找其实际而有效的算法就显得颇为重要了。遗憾的是，计算复杂性理论给予我们的结论却是，这种可能性尚属未知。若设城市数目为n时，那么组合路径数则为(n-1)!。很显然，当城市数目不多时要找到最短距离的路线并不难，但随着城市数目的
39、不断增大，组合路线数将呈指数级数规律急剧增长，以至达到无法计算的地步，这就是所谓的“组合爆炸问题”。假设现在城市的数目增为20个，组合路径数则为(20-1)!，如此庞大的组合数目，若计算机以每秒检索1000万条路线的速度计算，也需要花上386年的时间。尽管现在计算机的计算速度大大提高，而且己有一些指数级的算法可精确地求解旅行商问题，但随着它们在大规模问题上的组合爆炸，人们退而求其次，转向寻找近似算法或启发式算法，经过几十年的努力，取得了一定的进展。4.1.2 数学模型设G=(V, E)为赋权图，V=l ,2,. .n为顶点集，E为边集，各顶点间距离为c。已知(c 0, c=,i,j V )，并
40、设 x= （31）则旅行商问题的数学模型可写成如下的线性规划形式：MinZ s.t这里，K为V的所有非空子集，为集合K中所含图G的顶点个数。前两个约束意味着对每个顶点而言，仅有一条边进出，后一约束则保证了没有任何子回路解的产生。于是，满足上述约束的解构成了一条Hamilton回路。除此之外，模型还有其它一些等价的书写形式。4.2 旅行商问题的计算复杂性一般的，我们定义一个组合优化问题:设，其中S为一个有限集，f为映射函数，对每个产生唯一的实数f(x)，则最大(小)化问题即找一个，使得对于任何其它有。此组合优化问题的一个基本算法是:对于每个，求f(x)的值，挑选，使对于所有的，。这就是穷举搜索法
41、，它在理论上可以解决任何有限的组合最优化问题。但对于n个城市的TSP，可能的回路数有条，计算每一条路径需求n个距离之和，故计算量将正比于。表41显示了运算速度亿次/秒的CrayXT3巨型计算机按穷举搜索法计算TSP所需的时间，这里还未考虑算法所需的巨大存贮空间。由此足见TSP时空复杂度之高。城市数N回路数加法量搜索时间51260秒10秒20秒40年100年200年表4.14.3 研究旅行商问题的意义旅行商问题是一个NP完全问题，目前任何NP完全问题都不能用任何已知的多项式算法求解；若任何一个NP完全问题有多项式算法，则一切NP完全问题都有多项式算法。由此，不少人猜测任何NP完全问题都没有多项式
42、算法，但至今无人证明。事实上，人们普遍认为，不发展全新的数学技术就证明不了这个猜想。这样一种认识的实际意义就在于许多人相信，难计算是这样一类问题的固有性质，因此它们不可能用有效算法求解，而所有能精确求解NP完全问题的算法，在最坏情况下都需要指数级的时间。另外，旅行商问题是一个理想化的问题，大多数对于此问题的研究都不是为了直接的实际应用，但这些研究可以经转化后用于许多现实的组合优化问题。很自然地可以想到，旅行商问题的成果可以应用于运输和物流问题。旅行商问题最早的应用是在上个世纪的四十年代，应用于校车路线的优化。现在，旅行商问题在越来越多的领域得到应用。1电路板钻孔进度的安排。在这个应用当中，电路
43、板上的孔代表旅行商问题中的城 市，钻头从一个钻孔移动到另一个钻孔。寻找最短路径变成了寻找最省时的钻头移动时间。尽管目前钻机的工艺技术发展很块，但钻头的移动时间仍然是一个令人头疼的问题。2基因测序。Concorde是一种求解旅行商问题的程序。美国国家卫生机构的研究人 员利用这一程序来进行基因测序。在这一应用中，局部的基区图谱作为城市，城市与城市的距离代表某张图谱与其它图谱相连的可能性。研究人员试图寻找一种可能性最高的连接方式把这些局部的图谱合成为整张基因图谱。3半导体的线路设计。一家半导体生产厂家应用Concorde程序来优化半导体的线路 设计，这样可以节省刻制半导体的时间，也能减少半导体电路消
44、耗的能量。4光缆的线路设计。贝尔电话公司利用Concorde程序来设计光缆的铺设线路，同样 的方法也应用于电话和电力线路的铺设当中。5在机器人控制等其它方面，旅行商问题也有许多应用。5 遗传算法在巡回旅行商问题中的应用5.1 旅行商问题的建模5.1.1 编码在遗传算法中，染色体通常采用简单的二进制串编码，但这种简单的编码方式不能较好的适用于TSP和其它组合优化问题。TSP常用的编码表达方式主要有邻接表达、矩阵表达、边表达、随机键表达和序表达等。其中，序表达和随机键表达不仅适用于TSP，也适用于其它组合优化问题。本文使用序表达形式。序表达是TSP问题的最自然的表达，其中城市是按访问的顺序排列的。
45、例如，对于9个城市的TSP:325471698可简单表示为向量3 2 5 4 7 1 6 9 8，表示从城市3出发依次经过城市2，5，4，7，1，6，9，8然后返回城市3的一条路径。序表达方式满足完全无向图TSP问题的约束条件。保证了每个城市经过且只经过一次，并且保证在任何一个城市子集中不形成回路.5.1.2 适应度函数适应度是生物学家在研究自然界中生物的遗传与进化现象时用以度量某个物种对其生存环境的适应程度。在遗传算法中适应度用来度量个体作为全局最优解的可接受程度，它是模拟进化算法评价和选择个体的度量依据。适应度的取值与适应度函数成正比。适应度函数的确定通常反映应用者对个体的评价标准和搜索机
46、理。适应度函数是遗传进化操作的基础，它的构造是遗传算法的关键。合理的适应度函数能引导搜索朝最优化方向进行。本文构造基于序的适应度函数。它的特点是个体被选择的概率与目标函数的具体值无关。将种群中的所有个体按其目标函数值的大小降序排列，设参数，定义基于序的适应度函数 e i1，2，3，p （32）式中：x种群排序后第i个个体；p种群中个体总数。程序源码：void CreateFitnessofPop( )std:vector:iterator iter_router; double alpha = EVAL_BASE;std:vector vecSort;for( iter_router=vecPop.begin();iter_router!=vecPop.end();iter_router+ ) vecSort.push_back( iter_router-m_fTotalDistance ); iter_router-m_fFitness = -100.0; std:sort( vecSort.begin(), vecSort.end() ); std:vectordoub
