遗传算法求解TSP问题的计算机仿真毕业论文.docx

遗传算法求解TSP问题的计算机仿真毕业论文目录遗传算法求解TSP问题的计算机仿真IAbstractII1 绪论11.1 研究背景11.2 研究意义21.3 研究内容21.4 本文的结构32 遗传算法理论概述42.1 遗传算法的产生及发展42.2 遗传算法基本原理52.3 遗传算法基本步骤62.4 遗传算法算法流程图62.5 遗传算法的特点72.6 遗传算法的应用83 基于遗传算法求解TSP问题103.1旅行商问题的描述与建模103.2编码方式103.3遗传算子的设计（交叉、选择、变异）123.3.1 交叉算子123.3.2 选择算子133.3.3 变异算子143.4 适应度函数153.5 遗传算法求解TSP问题的具体流程图164 45个城市旅行商问题的仿真软件的设计174.1 系统设计模块174.2 系统详细设计174.2.1演示模块设计184.2.2帮助模块设计214.3 测试结果及分析224.3.1 测试一224.3.2 测试二244.3.3 测试三264.3.4 测试四284.3.5 测试五295 结论31参考文献32谢辞33附录一程序34附录二外文翻译55551绪论自20世纪60年代以来,一种模拟生物自然遗传与进化过程并将生物进化原理、最优化技术和计算机技术结合起来的优化方法遗传算法（Genetic Algorithm,简称GA）被提出并得到广泛研究，该算法特别适用于处理传统搜索方法难以解决的复杂和非线性问题，可以广泛应用于人工智能、机械设计、自适应控制等领域。遗传算法固有的并行性和并行计算的能力，使在搜索过程中不容易陷入局部最优。即使在所定义的适应度函数中是不连续的、不规则的情况下，也可以很大概率找到全局最优解。采用自然进化机制来表现复杂的现象，能够快速可靠地解决求解非常困难的问题，非常适用于本课题涉及的TSP问题的求解与研究。旅行商问题（Traveling Salesman Problem ,TSP）是一个非常经典的组合优化问题的NP难题，长期以来都没有一个十分有效的算法来解决它，但TSP本身在许多领域有着重要的应用，如连锁店的货物配送路线、计算机网络路由器遍历、印刷电路板的钻孔路线等问题都可以建模为旅行商问题。TSP问题其实是“哈密顿回路问题”中的“哈密顿最短回路问题”。在本系统就是要应用遗传算法求解45个城市的TSP问题。因为遗传算法本身是模拟生物自然选择和遗传的过程的，所以用遗传算法求解TSP最先要确定的是问题的建模，即如何用遗传学的算子来表示旅行商问题中的变量。必需要非常的了解，并熟悉每一个遗传学中的术语在遗传学中的具体作用，然后应用到求解具体问题当中来。应用遗传算法求解旅行商问题最关键的是编码方式、交叉、选择、变异算子的设计，直接关系到算法能否求出最优解或近似最优解。所以要在编码方式的确定上做好足够的功夫，以确定程序求解的精确度。本章主要论述本文所研究的主要内容，并对论文的章节结构进行规划。1.1 研究背景旅行商问题（Traveling Salesman Problem, TSP）,也称旅行推销员问题，具体的数学模型可以这样理解：现在给定以下几个城市的位置，旅行商从其中的某一个城市出发，不重复地访问其余的每一个城市，最后又返回到原出发点城市，要求找出这样一条路线，使旅行所付出的代价最小。虽然它是一个比较古老的问题，最早可以追溯到Euler提出的骑士旅行问题，但同时它也是一个新的问题，因为它的计算复杂度较高，虽然人们一直在尝试用新的方法来改进求解该问题的复杂度，但是这一类问题距今都没有能找到一个有效的算法来解决。TSP问题可以形式化描述为：设G=（V,A,D）是一个图，其中V是n个顶点的集合，A是弧线或边集,D=（dij）是与A关联的距离或费用矩阵。旅行商问题就是要解决一个最小回路问题，回路中所有顶点有且仅经过一次。对于具有一个城市的旅行商问题，其可能的路径数目为（n-1）！/2，5个城市的问题模型就对应120/10=12条路线，10个城市的问题模型对应3628800/20=181440条路线。所以当输入越大，则耗费的时间就是个天文数字了，因此旅行商问题至今都没有能找到一种有效的求解方法。寻求一种能短时间求解出高精度解的算法，已成为此问题研究的热门。尽管旅行商问题至今仍然没有找到最优解，但求解它的算法已经在不断的改进。目前，求解TSP问题常用的算法主要有遗传算法和蚁群算法，另外还有爬山法、模拟退火算法、神经网络方法、贪婪算法、禁忌搜索算法等。1980Crowder和Padberg求解了318个城市的TSP问题；1987年Padberg和Rinaldi成功将城市数量增加到了2392个；最大的成功求解的旅行商问题已经增加到24798个城市。1.2研究意义首先旅行商问题是用于求解N个城市存在（N-1）条闭合路径的排列方案，对于这一类问题很难用全局搜索法精确地求出最优解，这一问题已经困扰众多学者许多年，因此研究相应的算法寻找其最优或近似最优解是非常必要的。其次，随着旅游业的快速发展，大量的旅客在旅途中浪费了不必要的时间和金钱，而这些不必要的浪费完全可以通过对旅行路线的合理规划来避免。而在互联网继续扩大普及的时代，电子商务也迎来了期待已久的春天，同时物流产业也随之水涨船高。毫无疑问，高效、低成本、低能耗成了各个物流企业追求的目标，更加合理的配送路线能明显地为物流公司增大利润。再比如在装配线的流程中，对每个工件为完成装配过程节约的少许时间意味着一天的产量的相应增加。由于旅行商问题在计算机网络、物流、旅游业、交通运输等许多领域都有着十分广泛的应用，因此寻找一个求解这类问题的求解方法有很高的应用价值因此，对旅行商问题有效算法的研究不仅具有重要的理论意义，而且具有重大的实际应用价值。1.3研究内容本文采用遗传算法求解45个城市的旅行商问题，并对其实现计算机仿真。遗传算法（Genetic Algorithms,GA）又叫基因进化算法或进化算法，是一种通过模拟自然界生物适者生存、优胜劣汰的进化过程而形成的一种自适应、具有全局优化能力的随机搜索算法。应用遗传算法求解旅行商问题，最难得地方在于问题建模，如城市编码方式以及交叉、变异、选择算子的确定等。本文采用的是Grefenstette等提出的一种新的巡回路线编码方法，其可以在一定程度上克服常规巡回路线编码方法在交异操作时易产生不满足问题约束条件或无实际意义的巡回路线的缺点。交叉算法采用的是常规的单点交叉，之所以可以用这一常规的交叉法，是因为在编码方式上使用的是Grefenstette等提出的一种新的巡回路线编码方法，它可以最大化交叉后后代与其父代的性状差异，有利于算法的全局性。变异算法采用的是基本位变异法，即只是根据变异概率随机改变染色体中的某一段染色体，具体会在后文中做详细说明。在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率。本课题中以每条路径长度的倒数作为适应度函数值。在求出之后将其按照从大到小的顺序排列，以便于后面找出路径之和最小的城市序列。1.4 本文的结构本文一共分为5章，结构如下：第一章绪论。这一章主要论述旅行商问题的基本概念，以及本课题主要的研究方法及其研究意义，并对论文的章节结构加以论述。第二章遗传算法理论概述。这一章主要论述遗传算法的起源发展及其实际应用，重点介绍了遗传算法的算法原理及步骤。第三章基于遗传算法求解TSP问题。本章主要介绍了本系统具体使用什么方式实现求解过程，包括编码方式、选择、交叉、变异算子的具体选取。第四章45个城市旅行商问题的仿真软件的设计。本章主要对系统模块进行了介绍，而且对应用系统进行了多组试算，最后得出结论。第五章结论。对本文的内容进行总结。2 遗传算法理论概述2.1 遗传算法的产生及发展最早由美国Michigan(密执安大学)的Hollang教授提出，起源于60年代对自然和人工自适应系统的研究。1967年，他的学生Bagley J.D.首次提出“遗传算法”一词，并发展了复制、交叉、变异、显性、倒位等遗传算子。70年代De Jong基于遗传算法的思想在计算机上进行了大量纯数值函数优化计算实验，建立了著名的De.Jong五函数测试平台。在一系列研究工作的基础上80年代Goldberg进行总结归纳，形成了遗传算法的基本框架；Smith将遗传算法应用于机械学习领域；Bethke对函数优化的遗传算法进行了系统的研究。进入90年代，遗传算法进入了兴盛期，无论是理论研究还是实际应用都成了十分热门的课题。如今遗传算法已经被广泛的应用于计算机科学、人工智能、机械设计、图像处理等各个领域，不仅如此，利用遗传算法进行理论研究的优化和最优解问题的解决能力也显著提高。下面是一些在遗传算法发展进程中做出杰出贡献的人物：1 J.H.Holland60年代提出在研究和设计人工自适应系统时,可以借鉴生物遗传的机制；70年代初提出了遗传算法的基本定理模式定理(Schema Theorem)，从而奠定了遗传算法的理论基础；80年代实现了第一个基于遗传算法的机器学系统分类器系统(Classifier Systems),开创了基于遗传算法的机器学习的新概念。2 J.D.Bagley1967年在其博士论文中首次提出了：“遗传算法”一词，发展了复制、交叉、变异、显性、倒位等遗传算子，创立了自适应遗传算法的概念。3 K.A.De Jong1975年在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验，树立了遗传算法的工作框架，定义了评价遗传算法性能的在线指标和离线指标。4 D.J.Golgberg1989年出版了专著搜索、优化和机器学习中的遗传算法(Genetic Algorithms in Search，Optimization and Machine Learning)，系统总结了遗传算法的主要研究成果，全面而完整的论述了遗传算法的基本原理及其应用。5 L.Davis1991年编辑出版了遗传算法手册 (Handbook of Genetic Algorithms)书中包括遗传算法在科学计算、工程技术和社会经济中的大量应用实例。6J.R.Koza 1992年将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程 (Genetic Programming) 的概念，并成功的将其提出的遗传编程应用于人工智能、机器学习符号处理等方面。2.2 遗传算法基本原理遗传算法是受大自然的启发，模拟生物在自然环境中的遗传和进化过程而形成的一种自适应、具有全局优化能力的随机搜索算法。遗传算法的思路是通过从给定一个初始群体出发，利用选择算子、交叉算子以及变异算子来模拟自然进化的三种原则，逐步改进种群，越来越逼近最优解，以达到求解最优化问题的目的。在遗传算法中，种群中的每一个个体是问题的一个解，称为“染色体”，染色体是一串符号，比如二进制的01串。这些染色体在后续的迭代中不断的进化，称为遗传。在每一代中应用适应度（fitness）来测量染色体的优越性，适应度高的更容易在自然的选择中存活下来。生存下来的染色体被称为后代（offspring）。后代通常是前一代染色体通过交叉（crossover）或者变异（mutation ）形成。新的下一代再重复根据适应度选择部分后代，淘汰一部分后代，这样即可以保证种群染色体的优越性，也保持了种群大小的稳点性。遗传算法中每一条染色体，对应着遗传算法的一个解决方案，一般我们用适应性函数（fitness function）来衡量这个解决方案的优劣。所以也可以把遗传算法的过程看作是一个在多元函数里面求最优解的过程。在这个多维曲面里面也有数不清的“山峰”，而这些最优解所对应的就是这些山峰，这些山峰就是局部最优解。而其中也会有一个“山峰”的海拔最高的，那么这个就是全局最优解。而遗传算法的任务就是尽量爬到最高峰，而不是陷落在一些小山峰。（另外，值得注意的是遗传算法不一定要找“最高的山峰”，如果问题的适应度评价越小越好的话，那么全局最优解就是函数的最小值，对应的，遗传算法所要找的就是“最深的谷底”）。下面给出生物学的几个基本概念知识，这对于理解遗传算法很重要：1）遗传因子（gene）:DNA长链结构中占有一定位置的基本遗传单位，也称基因。生物的基因根据物种的不同而多少不一。2）个体（individual）:指染色体带有特征的实体。3）种群（population）:染色体带有特征的个体的集合。4）进化（evolution）;生物在其延续生命的过程中，逐渐适应其生存环境使得其品质不断得到改良，这种生命现象称为进化。生物的进化是以种群的形式进行的。5）适应度（fitness）:度量某个物种对于生存环境的适应程度。6）选择（selection）:指以一定的概率从种群中选择若干个体的操作。7）变异（musation）：复制时很小的概率产生的某些复制差错。8）编码（coding）:DNA中遗传信息在一个长链上按一定的模式排列，也即进行了遗传编码。遗传编码可以看成是从表现型到遗传子型的映射。9）串（String）:它是个体的形式，在算法中为二进制串，并且对应于遗传学中的染色体。10）串结构空间（ss）：在串中，基因任意组合所构成的串集合。基因操作是在结构空间中进行的。串结构空间对应用于遗传学中的基因型的集合。11）染色体：是生物细胞中含有的一种微小的丝状化合物，是遗传物质的主要载体，由多个遗传因子基因组成。2.3 遗传算法基本步骤步骤一：编码：把所需要选择的群体进行编号，每一个个体就是一条染色体，一个解就是一串基因的组合。步骤二：初始化：随机生成有N个个体的初始群体，这些个体一起组成了一个种群。遗传算法就是以这个初始群体为起点开始迭代。参数N可以根据具体的情况而定。步骤三：交叉算子：这是遗传算法最重要的操作。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。步骤四：适应度：确定个体适应度的量化评价方法，适应度用于衡量种群中个体的优劣性，是确定种群中个体留存的关键。步骤五：选择算子：选择的目的是为了从交换后的群体中选出优良的染色体携带者，使它们有机会作为父代繁殖出下一代群体。选择操作是建立在适应度之上的，适应度高的被选中的几率就大，选择操作体现出了生物适者生存的原则。步骤六：变异算子：变异是根据生物遗传中基因突变的原理，以变异概率对群体中的某一些个体的某些“位”执行变异。变异操作可以保证算法过程中不会产生无法进化的单一群体，避免算法早熟出现局部最优。步骤七：终止。给定最大的遗传代数，算法在计算到最大的遗传代数时，终止计算。2.4 遗传算法算法流程图图2-4遗传算法算法流程图2.5 遗传算法的特点遗传算法属于进化算法（Evolutionary Algorithms）的一种，它通过模仿自然界的选择与遗传的原理来求出最优解，遗传算法有三个最基本的算子：选择、交叉、变异。数值方法求解这一问题的主要手段是迭代运算。一般的迭代方法容易陷入局部极小的陷阱而出现“死循环”现象，使迭代无法进行。遗传算法很好地克服了这个缺点，是一种全局优化算法。遗传算法与传统的优化方法（枚举，启发式等）相比较，以生物进化为原型，具有很多的优点。主要有以下几点：（1）遗传算法的本质并行性。首先，遗传算法并行的方式是从问题解的串集开始搜索，而不是从单个解开始。这是遗传算法与传统优化算法的最大区别。传统优化算法从单个初始值迭代求最优解，容易早熟陷入局部最优解。遗传算法从串集开始搜索，覆盖面大，有利于全局最优。其次，算法内含并行性，遗传算法采用种群方式组织搜索，因而可同时搜索解空间的多个区域，并相互交流信息，能以较小的计算获得较大收益。（2）遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序.仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意的设定，故几乎可处理任何问题。（3）遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索方向，具有自组织、自适应和自学习性。遗传算法利用进化过程获得信息自行组织搜索时，适应度高的个体具有较高的生存率，并获得更加适应环境的染色体。这种通过自然选择与进化的机制消除了算法设计过程中的一个最大障碍，即需要事先描述问题的全部特点，并要说明针对所求问题的不同特点，我们设计的算法应该采用的具体措施。所以，遗传算法有很高的容错能力，我们可以利用遗传算法解决复杂的非结构化问题。（4）遗传算法可以直接用于实际应用当中，对于给定的问题，可以产生许多解，最终选择是根据用户自己的需求来选取，通用性高，实际应用性强，应用范围广。2.6 遗传算法的应用遗传算法为求解复杂系统问题提供了一种通用的算法框架，它不取决于问题的具体领域，有很强的鲁棒性，因而被广泛的使用于组合优化、机械设计、人工智能、数学建模、软件工程等领域。（1）函数优化函数优化是遗传算法经典的应用领域，也是使用最频繁的领域。尤其是在数学领域，科学家构造出了许许多多复杂的测试函数：连续函数、离散函数、凸函数、凹函数、单峰函数、多峰函数等等。对于这些非线性、求极值、多模型或多目标的函数优化问题，用传统的优化方法很难解决，而用遗传算法可以方便地得到较好的结果。（2）组合优化随着变量n的不断增大，问题的规模增大，组合优化问题的求解空间也急剧增大，应用传统的枚举法等就很难求出最优解。对于这一类复杂的问题，遗传算法已经被证实是十分有效的求解方式。遗传算法已经在求解TSP问题、01背包问题、图形划分问题等方面得到了成功的应用。(3)生产调度问题生产调度问题在很多情况下建立起来的传统数学模难以精确求解，虽然经过一些简化之后可以进行求解.也会因简化得太多而使得求解结果与实际相差太大。目前在现实生产中主要是靠一些经验来进行调度。现在遗传算法已成为解决复杂调度问题的有效措施。在单件生产车间调度、流水线生产间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。（4）机器人学机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于人工自适应系统的研究。所以，机器人学理所当然地成为遗传算法的一个重要应用领域。例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方而得到研究和应用。（5）数据挖掘数据挖掘是近几年出现的数据库技术，它能够从大型数据库中提取隐含的、先前未知的、有潜在应用价值的知识和规则。许多数据挖掘问题可看成是搜索问题，数据库看作是搜索空间，挖掘算法看作是搜索策略。因此，应用遗传算法在数据库中进行搜索，对随机产生的一组规则进行进化.直到数据库能被该组规则覆盖，从而挖掘出隐含在数据库中的规则。Sunil已成功地开发了一个基于遗传算法的数据挖掘下具。利用该工具对两个飞机失事的真实数据库进行了数据挖掘实验，结果表明遗传算法是进行数据挖掘的有效方法之一。（6）人工生命人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大主要特征。人工生命与遗传算法有着密切的关系。基于遗传算法的进化模型是研究人工生命现象的重要基础理论。虽然人工生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成，遗传算法为人工生命的研究提供一个有效的工具，人工生命的研究也必将促进遗传算法的进一步发展。3 基于遗传算法求解TSP问题3.1旅行商问题的描述与建模旅行商问题，即TSP问题又译为旅行推销员问题，属于NP完全问题，是数学领域中著名的问题之一。它可以大致描述为这样：有一个旅行商人要拜访n个城市，他必须要经过所有的城市，而且每个城市只能拜访一次，最后要回到原来出发的城市。要求得的路径路程为所有可能路径之中的最小值，即最优值问题。可以用如下公式表达:n-1f(T)= d(ti,ti+1)+d(nt,t1)i=1本系统是用遗传算法求解45个城市的旅行商问题，并对其进行计算机仿真，做出一个能在计算机上运行的软件。3.2编码方式编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤。因为编码方法将会影响到交叉算子、变异算子等遗传算子的运算方法，很大的程度上决定了遗传进化的效率。迄今为止人们已经提出了许多种不同的编码方法。总的来说，这些编码方法可以分为三大类：二进制编码法、浮点编码法、符号编码法。下面我们从具体实现角度出发介绍其中的几种主要编码方法。1.二进制编码方法：它由二进制符号0和1所组成的二值符号集。它有以下一些优点：(1）编码、解码操作简单易行(2)交叉、变异等遗传操作便于实现(3)符合最小字符集编码原则(4)利用模式定理对算法进行理论分析。二进制编码的缺点是：对于一些连续函数的优化问题，由于其随机性使得其局部搜索能力较差，如对于一些高精度的问题（如上题），当解迫近于最优解后，由于其变异后表现型变化很大，不连续，所以会远离最优解，达不到稳定。而格雷码能有效地防止这类现象。2.浮点编码法：对于一些多维、高精度要求的连续函数优化问题，使用二进制编码来表示个体时将会有一些不利之处。二进制编码存在着连续函数离散化时的映射误差。个体长度较知时，可能达不到精度要求，而个体编码长度较长时，虽然能提高精度，但却使遗传算法的搜索空间急剧扩大。所谓浮点法，是指个体的每个基因值用某一范围内的一个浮点数来表示。在浮点数编码方法中，必须保证基因值在给定的区间限制范围内，遗传算法中所使用的交叉、变异等遗传算子也必须保证其运算结果所产生的新个体的基因值也在这个区间限制范围内。浮点数编码方法有下面几个优点：（1)适用于在遗传算法中表示范围较大的数（2)适用于精度要求较高的遗传算法（3)便于较大空间的遗传搜索（4)改善了遗传算法的计算复杂性，提高了运算交率（5)便于遗传算法与经典优化方法的混合使用（6)便于设计针对问题的专门知识的知识型遗传算子（7)便于处理复杂的决策变量约束条件3.符号编码法：符号编码法是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集如A,B,C。符号编码的主要优点是：（1)符合有意义积术块编码原则（2)便于在遗传算法中利用所求解问题的专门知识（3)便于遗传算法与相关近似算法之间的混合使用。但对于使用符号编码方法的遗传算法，一般需要认真设计交叉、变异等遗传运算的操作方法，以满足问题的各种约束需求，这样才能提高算法的搜索性能。使用遗传算法第一件事情就是确定染色编码方式，它根据不同的问题模型使用不同的编码方式，本系统使用的是Grefenstette等提出的一种新的巡回路线编码方法，是一种整数编码的方式。对于每个城市用一个整数来编号，例如有45个城市，就用0到45来标识每一个城市，然后一个路径就是一条染色体编码，染色体长度为45，如：0,1,2,3,4.44就是一个染色体，它表达的意思就是旅行者从0号城市出发，依次访问1,2,.44号城市再回到0号城市；下面具体具体介绍一下这一种编码方法。对于给定的旅行商问题，设其城市列表W，假定对各个城市的访问顺序为T： T=（T1，T2，T3，.，Tn）规定每访问完一个城市，就从城市列表W中将该城市除去，则用第i（i=1,2,3n）个所访问的城市Ti在所有未访问城市列表W=T1，T2，T3，.，Ti-1中的对应位置序号Gi（1Gin-i+1）就可表示具体访问哪个城市，如此这样直到处理完W中所有的城市。将全部Gi顺序排列在一起所得到的一个列表：G=（G1，G2，G3，Gn）这样就可以表示一条巡回路线，它就是遗传算法中的一个个体基因。例如，假设现在有这样一个城市序列：W=(A,B,C,D,E,F,G,H,I,J)有如下两条巡回路线：T1=(A,D,B,H,F,I,J,G,E,C) T2=(B,C,A,D,E,J,H,I,F,G)则按本系统所用的编码方法，这两条巡回路线可以编码为：G1 =(1,3,1,5,3,4,4,3,2,1)G2 =(2,2,1,1,1,5,3,3,1,1)这种编码方式的优点在于任意的染色体都对应一条有实际意义的巡回路线，因此可以使用常规的交叉算子对它进行计算，有利于算法的实现。3.3遗传算子的设计（交叉、选择、变异）3.3.1 交叉算子交叉运算，一般指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。求解旅行商问题的遗传算法的交叉算法主要有：部分匹配交叉（PMX）、循环交叉（CX）、次序交叉（OX）、线性次序交叉（LOX）、边重组交叉（EX）等。本系统使用的是常规的单点交叉算子。由于在确定算法的编码方式的过程中使用的是Grefenstette等提出的编码方式，用这种编码方式表示个体时，个体的基因型和表现型之间是一一对应的，它使经过运算之后得到的每一个基因型都是一条有实际意义的巡回路线。因此，就可以使用常规的单点交叉算子。使用单点交叉，即在个体的编码串上随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。产生下一代个体在使用Grefenstette等提出的编码方式时，染色体编码串前面的一些基因发生变化时，会对后面的基因值产生巨大的影响，产生的新的个体与上一代的性状变化就会十分明显，有利于整个算法跳出局部最优解。如下是具体代码：for(i=0;itemp) parent1=temp; parent2=RandomInt(0,m_nGroupSize-1);temp=RandomInt(0,m_nGroupSize-1);if(parent2temp) parent2=temp; /复制用于交叉的基因对PopNode pop1;PopNode pop2;pop1.CopyNode(&oldpopparent1);pop2.CopyNode(&oldpopparent2); / 基因序列中用于交叉的基因位nPos=RandomInt(3,MAXCHROM-3); pop1.CrossTwo(&pop2, nPos); /交叉完成,保存结果newpopm_nGroupSize+2*i.CopyNode(&pop1);newpopm_nGroupSize+2*i+1.CopyNode(&pop2);3.3.2 选择算子选择操作是建立在对个体适应度进行评价的基础之上的。选择操作的目的是为了避免基因缺失、提高全局收敛性和计算效率。本课题采用最常用的选择算子比例选择算子（又称轮盘赌选择）。其基本思想是：各个个体被选中的概率与其适应度大小成正比。适应度越高的个体被选中的概率也越大；反之，适应度越低的个体被选中的概率也越小。具体操作如下：计算出群体中每个个体的适应度f(i=1，2，M)，M为群体大小；归一化适应度f的值将适应度f的值从大到小排列，查找其中最小费用的个体然后将其作为下一代选择出来。具体代码如下：for(int gen=0;genm_GANum;gen+) / 计算当前一代群体中个体的适应度数值Ffor(int i=0;im_nGroupSize;i+)TotalF+=1/oldpopi.CalcCost(m_distance); / 归一化F值for(i=0;im_nGroupSize;i+) oldpopi.fit=1/oldpopi.cost/TotalF*100; / 将当前一代群体中的个体按F值从大到小排序for(i=0;im_nGroupSize-1;i+) double max=0.0;int maxpos;for(int j=i;jmax)max=oldpopj.fit; maxpos=j;if(i!=maxpos) oldpopi.SwapNode(&oldpopmaxpos);m_CurGANum=gen;/ 查找当前一代中的最小费用个体m_MiniCost=oldpop0.cost;m_pop.CopyNode(&oldpop0);m_GAFitness=m_pop.fit;/AfxMessageBox(显示数据);UpdateData(false);UpdateWindow();if (m_CurGANum = m_GANum - 1)/ 绘制图形DrawNetwork();/继承所有父代基因for(i=0;im_nGroupSize;i+) newpopi.CopyNode(&oldpopi);3.3.3 变异算子变异运算，是指改变个体编码串中的某些基因值，从而形成新的个体。变异运算是产生新个体的辅助方法，决定遗传算法的局部搜索能力，保证了种群的多样性。交叉运算可以和变异运算相互配合，共同完成对搜索空间的全局搜索和局部搜索。本系统中变异算子采用基本位变异算子。基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。因为使用由Grefenstette等所提出的编译方法来表示个体，一个个体经过遗传运算后所得到的任意一个基因型个体与交叉后的情况相同，都能够对应于一条具有实际意义的巡回路线。对于二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则将其变为1；反之，若原有基因值为1，则将其变为0 。基本位变异算子的执行过程如下：（1）对个体的每一个基因座，依变异概率Pm指定其为变异点。（2）对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值来代替，从而产生出一个新个体。针对旅行商问题对变异算子的设计要求，基本位变异即交换变异。变异是单个个体内部发生变化，导致产生新个体，从而产生出一条新的巡回路线。例如：Tx=（B C A D E J H I F G）（B C A I E J H D F G）=Tx具体代码如下：for(i=0;im_VariNum;i+)int nPos1,nPos2,parent=0; /变异父代基因parent=RandomInt(0,m_nGroupSize-1) （定义变异范围） nPos1=RandomInt(3,MAXCHROM-3); （取其中第三位与倒数第三位做nPos2=RandomInt(3,MAXCHROM-3); 为变异结点）PopNode pop;pop.CopyNode(&oldpop0); pop.Varite(nPos1,nPos2);（执行结点操作） newpopm_nGroupSize+m_CrossNum*2+i.CopyNode(&pop);（保存变异结果）3.4 适应度函数在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率。个体的适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。因此适应度函数的选择至关重要，直接影响到遗传算法的收敛速度以及能否找到最优解。本系统中以每条路径长度的倒数作为适应度函数值，并对其进行统一化的操作，即按从大到小进行排序，为下一步选择操作做准备。为正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度必须为正数或零，不能是负数。具体代码如下所示：for(int i=0;im_nGroupSize;i+) （nGroupSize是城市之间的距离）TotalF+=1/oldpopi.CalcCost(m_distance);（父代结点的城市距离的倒数作为它的适应度）3.5 遗传算法求解TSP问题的具体流程图图3-5 遗传算法求解旅行商问题的具体流程图4 45个城市旅行商问题的仿真软件的设计4.1 系统设计模块本系统在Microsoft Visual C+环境下完成，根据需求设计了三大模块：算法设计模块、演示模块、帮助模块。算法设计模块完成群体规模M、交叉概率Pc、变异概率Pm和进化代数T的设置；具体的参数已经设置在了演示平台上，可以根据需要更改参数大小，但是尽量在设定的范围之内，这样可以保证算法的精确性；帮助模块则设置了关于软件和制作作者等查看项目。下图是系统的功能模块图。基于遗传算法的TSP问题仿真软件设计算法设计模块演示模块帮助模块群体规模交叉概率变异概率进化代数进化演示关于作者关于软件图4-1系统功能模块图4.2 系统详细设计由前文中介绍的个体编码方法及各种遗传算子可以构成许多种不同的求解旅行商问题的遗传算法，本系统主要利用这些遗传算子对含有45座城市的旅行商问题进行了试算。本系统中所使用的遗传算法是由以下要素所构成的：编码方法基本遗传算法使用由Grefenstette所提出的编码方法，详细设计见第四章编码方式一节。适应度函数系统中以每条路径长度的倒数作为适应度函数值。选择算子采用适应度比例法交叉算子采用常规单点交叉操作算子。变异算子使用基本位交换变异操作算子运行参数M，T，Pc，Pm=0500，0300，0.20.4，0.010.08，式中M为群体大小，T为终止代数，Pc为交叉概率，Pm为变异概率。本系统给出各个参数的参考范围，在此范围内执行搜索最佳，超出范围也可演示，但这会影响搜索效果，可能得不到最优解或近似最优解。极端情况不可执行。这些在上文中已作过详细介绍,这里就不再重复。4.2.1演示模块设计（1）主窗口设计：在VC工具栏insent中插入窗口IDD_CHINA45_DIALOG，再在上面设置变量，并进行初始化。具体变量及其窗口对话框设置如下表。表4.2.1为工程添加IDD_CHINA45_DIALOG的菜单选项ID说明文字功能描述IDC_EDIT1城市数目显示城市数量IDC_EDIT2群体规模显示群体规模IDC_EDIT3交叉概率显示交叉概率IDC_EDIT4 变异概率显示变异概率IDC_EDIT5遗传代数显示遗传代数IDC_EDIT6进化代数显示进化代数IDC_EDIT7最小费用显示最小费用IDC_EDIT8交叉数目显示交叉数目IDC_EDIT9变异数目显示变异数目IDC_EDIT10群体适应度显示群体适应度表4.2.2通过类查看（ClassView）选项卡，向主对话框添加成员变量变量类型变量名功能描述intm_GALen城市数量intm_nGroupSize群体规模大小doublem_GACrossProb交叉概率doublem_GAVariProb变异概率intm_GANum遗传代数intm_CurGANum进化代数doublem_MiniCost最小费用intm_CrossNum交叉数目intm_VariNum变异数目doublem_GAFitness群体适应度初始化参数设置代码如下：m_GALen = 45; m_nGroupSize = 100; m_GACrossProb = 0.6;m_GAVariProb = 0.03;m_GANum = 100;m_CurGANum = 0;m_MiniCost = 0.0;m_CrossNum = 0;m_VariNum = 0;m_GAFitness = 0.0;变量与对话框进行绑定：DDX_Text(pDX, IDC_EDIT1, m_GALen);DDX_Text(pDX, IDC_EDIT2, m_nGroupSize);DDX_Text(pDX, IDC_EDIT3, m_GACrossProb);DDX_Text(pDX, IDC_EDIT4, m_GAVariProb);DDX_Text(pDX, IDC_EDIT5, m_GANum);DDX_Text(pDX, IDC_EDIT6, m_CurGANum);DDX_Text(pDX, IDC_EDIT7, m_MiniCost);DDX_Text(pDX, IDC_EDIT8, m_CrossNum);DDX_Text(pDX, IDC_EDIT9, m_VariNum);DDX_Text(pDX, IDC_EDIT10, m_GAFitness);打开类向导（Class Wizard）对话框向主对话框类添加响应函数，用于显示新生成的群体规模、交叉变异数目等。具体代码如下：void CChina45Dlg:OnMenuGaset() / TODO: Add your command handler code hereCGASetDlg dlg;if(dlg.DoModal()=IDOK)m_nGroupSize=dlg.m_nGroupSize; （将新的群体规模赋值给对话框）m_GACrossProb=dlg