遗传算法解决TSP问题C++、MFC界面编程.doc

南 京 理 工 大 学毕业设计说明书(论文)作 者:杨敏学 号：0606230236学院(系):计算机科学与技术学院专 业:计算机科学与技术题 目:基于遗传算法的TSP问题求解方法的研究与实现副教授朱保平指导者： (姓 名) (专业技术职务)评阅者： (姓 名) (专业技术职务)2010年 5 月毕业设计说明书（论文）中文摘要 旅行商问题是一个典型的NP完全问题，遗传算法是解决这类问题一个比较理想的算法。遗传算法是近年来迅速发展起来的一种全新的随机搜索与优化方法。它的基本思想来自于Darwin的进化论和Mendel的遗传学。论文首先对遗传算法和旅行商问题进行了简单的描述。接着用数学的方式描述了TSP问题。然后，阐述了遗传算法在编码表示和遗传算子（包括选择算子、交叉算子、变异算子）等其他方面的应用情况，最后通过对初始种群、交叉率、变异率、遗传代数等参数进行修改、测试、对比、来验证这些参数对算法的求解结果和求解效率的影响。关键字 遗传算法 旅行商问题 遗传算子 编码毕业设计说明书（论文）外文摘要Title Solving Traveling Salesman Problem by Genetic Algorithm AbstractTSP (Traveling Salesman Problem) is a typical NP - complete problem and genetic algorithm (GA) is the perfect method for solving NP - complete problem. Genetic Algorithm (Genetic Algorithm, GA) is a new random search and optimization algorithm ，develop rapidly in recent years, the basic idea of the theory is Darwin and Mendels genetics. Paper first introduces genetic algorithm and Tsp. Then paper describes the mathematical approach the problem of TSP，and then paper explains that genetic algorithm coding and genetic operators(including selection operator, crossover operator, mutation operator) and other aspects of the application。Finally, the initial population, crossover rate, mutation rate, genetic algebra modifies the parameters, testing, comparison, To verify these parameters on the algorithm results and efficiency.Keywords genetic algorithm TSP genetic operator coding 本科毕业设计说明书（论文） 第 I 页 共 I 页目 次1 引言11.1 研究背景11.2 国内外发展现状11.3 本文研究的内容31.4 本文结构32 遗传算法与TSP问题介绍521 遗传算法介绍52.1.1遗传算法简介52.1.2 遗传算法应用中的关键问题62.1.2 遗传算法特点82.1.3 遗传算法的应用步骤92.1.4 遗传算法的流程图102.2 TSP问题介绍103 遗传算法在TSP上的应用与实现123.1 算法的实现123.1.1 遗传算法运用在TSP上的流程图123.1.2 编码133.1.3 初始化种群133.1.4 适应度函数143.1.5 选择操作143.1.6 交叉操作173.1.7 变异操作2132 不同参数下的计算结果对比213.2.1 初始种群10和100的对比213.2.2 不同交叉率和变异率的对比2433 程序计算过程截图254 混合遗传算法的展望28结 论30致 谢31参 考 文 献32 本科毕业设计说明书（论文） 第 33 页 共 32 页1 引言在过去,人们往往只能够处理一些简单的问题，对于大型复杂系统的优化和自适应仍然无能为力。但是在自然界中，生物在这方面表现出了其优异的能力，他们能够通过优胜劣汰、适者生存的自然进化规则进行生存和繁衍，并且慢慢的产生对其生存环境适应性越来越高的优良物种。遗传算法就是模拟自然进化的一种高效的算法。其基本思想就是模拟自然界进化机制和生物进化论而形成的一种过程搜索最优解得算法。遗传算法是一门新的学科，各种理论、方法都尚未成熟，有待于进一步地发展和完善，但它却让我们看到了解决许多复杂问题的希望。尽管在遗传算法的研究和应用过程中出现过许多难题，同时也会产生许多不同的算法设计，但是，目前遗传算法的运用过程中已经展现出了其优异的性能和巨大的发展前景。我们相信，随着研究工作的进一步深入和发展，遗传算法一定能够在智能计算领域中起到关键性作用。巡回旅行商问题(Traveling Salesman Problem, TSP),是一个著名的组合优化问题1,该类问题具有很强的运用背景。如数控机床上的最优钻孔路线的选取、电路板的焊接、物流的调度问题都属于旅行商问题。因此旅行商问题受到了各方面的关注。目前解决TSP问题的主要方法有启发式搜索法、模拟退火算法、遗传算法、Hopfield神经网络算法、二叉树描述算法。有效解决TSP问题在计算理论和实际应用上都有很高的价值。本文主要介绍了运用遗传算法来解决TSP问题。1.1 研究背景如今的科学技术正在步入多学科相互交叉、互相渗透、互相影响的时代、生命科学与工程科学的交叉、渗透和相互促进是其中一个典型的例子，也是近代科学技术发展的一个显著点。遗传算法从此诞生。TSP问题，也称为巡回旅行商问题，就是为人们所广泛研究的典型的组合优化为题。而且TSP问题由于其典型性已经成为各种启发式的搜索、优化算法(如遗传算法、神经网络优化法、列表寻优法、模拟退火法等234)的间接比较标准。遗传算法在此体现出了不俗的表现5。1.2 国内外发展现状最早美国ichigan(密执安大学) 6 7的Holland教授提出，起源于60年代对自然和人工自适应系统的研究。70年代De Jong基于遗传算法的思想在计算机上进行了大量纯数值函数优化计算实验。在一系列研究工作的基础上80年代Goldberg进行总结归纳，形成了遗传算的基本框架。进入八十年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。1985年，在美国召开了第一届遗传算法国际会议（International Conference on Genetic Algorithms ，ICGA），并且成立国际遗传算法学会（International Society of Genetic Algorithms ，ISGA），以后每两年举行一次。1989年，Holland的学生D.E.Goldberg出版了专著搜索、优化和机器学习中的遗传算法（Genetic Algorithms in Search , Optimization, and Machine Learning）。该书总结了遗传算法研究的主要成果，对遗传算法及其应用作了全面而系统的论述。同年，美国斯坦福大学的Koza基于自然选择原则创造性地提出了用层次化的计算机程序来表达问题的遗传程序设计( genetic programming, GP)方法，成功地解决了许多问题。在欧洲，从1990年开始每隔一年举办一次Parallel Problem Solving from Nature 学术会议，其中遗传算法是会议主要内容之一。此外，以遗传算法的理论基础为中心的学术会议还有Foundations of Genetic Algorithms，该会也是从1990年开始隔年召开一次。这些国际会议论文，集中反映了遗传算法近些年来的最新发展和动向。1991年，L.Davis编辑出版了遗传算法手册（Handbook of Genetic lgorithms），其中包括了遗传算法在工程技术和社会生活中的大量应用实例。 1992年，Koza发表了他的专著遗传程序设计:基于自然选择法则的计算机程序设计。1994年，他又出版了遗传程序设计，第二册:可重用程序的自动发现深化了遗传程序设计的研究，使程序设计自动化展现了新局面。有关遗传算法的学术论文也不断在Artificial Intelligence、Machine Learning、Information science、Parallel Computing、Genetic Programming and Evoluable Machines、IEEE Transactions on Neural Networks、IEEE Transactions on Signal Processing等杂志上发表。1993年，MIT出版社创刊了新杂志Evolutionary Computation。1997年，IEEE又创刊了Transactions on Evolutionary Computation。Advanced Computational Intelligence杂志即将发刊，由模糊集合创始人L.A.Zadeh教授为名誉主编。目前，关于遗传算法研究的热潮仍在持续，越来越多的从事不同领域的研究人员已经或正在置身于有关遗传算法的研究或应用之中。遗传算法(Genetic Algorithm, GA)是近三十年来迅速发展起来的一种全新的随机搜索与优化算法,其基本思想是基于Darwin的进化论和Mendel的遗传学说。该算法由密执安大学教授Holland及其学生于1975年创建。此后，遗传算法的研究引起了国内外学者的关注。自1985年以来.国际上已召开了多次遗传算法的学术会议和研讨会.国际遗传算法学会组织召开的ICGA( International Conference on Genetic Algorithms)会议和FOGA( Workshop on Foundation of Genetic Algorithms)会议。为研究和应用遗传算法提供了国际交流的机会。作为一种通用的问题求解方法，遗传算法采用简单的编码技术来表示各种复杂的结构并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。近年来，遗传程序设计运用遗传算法的思想自动生成计算机程序解决了许多问题，如预测、分类、符号回归和图像处理等，作为一种新技术，它已经与遗传算法并驾齐驱。 1996年，举行了第1次遗传程序设计国际会议，该领域己引起越来越多的相关学者们的兴趣。现在的基因表达式算法应该算是遗传算法的继承者。1.3 本文研究的内容本文通过对遗传算法的研究来解决TSP问题。在运用遗传算法成功解决TSP问题基础上，再通过采用不同的初始种群数目、遗传代数、交叉率、变异率来比较算法的质量与效率。从而观察、验证这类参数对算法质量和效率的影响程度。1.4 本文结构第一章引言,首先对本文的研究背景、遗传算法在国内外的发展情况进行了简单的描述。然后再对本文研究的大致内容进行了阐述。第二章：遗传算法与TSP问题的介绍,首先对遗传算法和TSP问题进行了简单的介绍。然后对遗传算法的基本术语、个体的编码方式、初始化种群、适应度函数、选择算子、交叉算子、变异算子、运行参数和全局最优收敛以及TSP问题的数学模型进行了阐述。第三章：遗传算法在TSP上的应用与实现,首先通过选取10个城市的TSP问题为例，运用遗传算法求解该TSP问题。然后通过选取不同参数进行结果对比，从而验证遗传算法的各参数对算法质量和效率的影响程度。第四章：混合遗传算法的展望,简单介绍了一些近年来与遗传算法想结合的高效算法。如模拟退火遗传算法、免疫遗传算法、小生境遗传算法、模糊遗传算法、混沌遗传算法、量子遗传算法。第五章：结论,对第三章的计算结果进行了总结与归纳。验证了种群大小、遗传代数、交叉率、变异率等参数对算法质量和效率的影响程度。2 遗传算法与TSP问题介绍2.1 遗传算法介绍2.1.1 遗传算法简介遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机化搜索算法，由美国Holland 教授提出。与自然界相似，遗传算法对求解问题的本身一无所知，它需要的仅仅是对算法产生的每个染色体进行评价，并基于适应度值来选择染色体，使适应性好的染色体有更多的繁殖机会。在遗传算法中，通过随机方式产生若干个所求问题的数字编码（即染色体），形成初始种群；根据所要解决的问题设定一个适应度函数，并且给每一个个体一个适应度的评价，淘汰适应度低的个体，选择适应度高的个体进行遗传操作，经过遗传操作后形成新一代的种群，对新一代的种群进行下一轮进化。直到产生近似最优解。这就是遗传算法的基本原理。这种算法是1960年由Holland提出来的,其最初的目的是研究自然系统的自适应行为，并且设计了具有自适应功能的软件系统。遗传算法的3个主要操作算子是：选择(selection)算子、交叉(crossover)算子和变异(mutation)算子8，遗传算法中包含了如下5个基本要素: (1) 对参数进行编码； (2) 设定初始种群大小；(3) 适应度函数的设计；(4) 遗传操作设计；(5) 控制参数设定(包括种群大小、最大进化代数、交叉率、变异率等)。为了读者能够更好的阅读本文，下面介绍一下遗传算法中的一些基本概念9：串：它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。群体：个体的集合称为群体，“串”是群体的元素。群体大小：在群体中个体的数目被称为群体的大小。基因：基因是串中的元素，基因用于表现个体的特征。列入一个串1,2,3，其中1，2,3这3个元素都是基因。基因位置：一个基因在串中的位置被称为基因位置。基因位置从左到右,开始计算。串结构空间：在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。参数空间：这是“串空间”在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。适应度：表示某个个体对环境的适应程度。2.1.2 遗传算法应用中的关键问题(1) 个体的编码方式：编码：在遗传算法中如何把一个问题的可行解从其空间中转换到遗传算法所能处理的搜索空间的转换方法称为编码。编码是应用遗传算法时要解决的主要问题，也是设计遗传算法时的一个关键步骤。编码方法除了决定个体染色体的排列形式之外，还决定了个体从搜索空间的基因型变成解决空间的表现型的编码方法，编码方法也影响到了交叉算子、变异算子的运算方法。通常编码方法有二进制编码、格雷码编码、浮点数编码、参数编码等。在TSP问题中常用：访问路径顺序进行编码。二进制编码：二进制编码是遗传算法中最常用的一种编码方式，它使用的编码符号集是由二进制符号0和1组成的二值符号集0,1，它所构成的个体是一个二进制编码符号串。二进制编码符号串长度与问题所要求的精度有关。由于二进制不便于反应所求问题的结构特征，对于一些连续函数的优化问题等，也由于遗传运算的随机特性二使得其局部搜索能力较差，因而人们提出了用格雷码来对个体进行编码。格雷码：连续两个整数所对应的编码值之间只有一个编码位不相同。格雷码有这样一个特点：任意两个整数的差事这两个整数所对应的海明距离（Hamming distance）。这个特点是遗传算法中使用格雷码进行个体编码的主要原因。浮点数编码：个体的每个基因值用某一范围内的一个浮点数来表示，个体的编码长度等于其决策变量的个数，个体变量的长度等于其决策变量的真实值，所以也叫真实值编码方法。参数编码：参数编码方法是对含有多个变量的个体进行编码的方法，包含两种编码方法多参数级联编码方法，多参数交叉编码方法。以访问路径顺序进行编码是如今解决TSP问题的一种常用的编码方式。在第三章中会重点介绍。(2) 初始化种群：选择一个群体，就是选择一个个体的集合。这个初始群体也就是问题假设解得集合。在遗传算法求解TSP问题中通常以随机方式产生串或者个体的集合10。初始种群个数越多，得到最优解的希望越大，但个数过多会导致每进行一轮的机器时间变长，致使算法效率低下。(3) 适应度函数：在研究自然界中生物的遗传和进化现象时，生物学家常常使用适应度这个术语来衡量某个物种对环境的适应率。适应度较高的物种将会得到更多的繁殖的机会；从而导致适应度低的物种被淘汰。度量物种适应度的函数就被称为适应度函数。在遗传算法中，根据个体的适应值，就可决定在此环境下的生存能力。个体适应度大小决定该个体被遗传到下一代群体中的概率。遗传算法仅仅使用所求问题的目标函数就可以得到下一步的有关搜索信息。目标函数值的使用是通过评价个体适应度来体现的。由于个体适应度大小决定该个体被遗传到下一代群体中的概率。所以评价个体适应度在遗传算法中也是一个重要的步骤。其一般过称为：1.对个体编码的串，进行解码处理后，可以得到个体的表现型。2.由个体的表现型计算出对应的个体的目标函数值。3.根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应度。(4) 选择算子：选择算子是遗传算法中的又一个关键步骤。遗传算法通过它来对群体中的个体进行优胜劣汰操作。适应度值高的个体被选中的几率高。适应度低的个体选中的概率低。遗传算法的选择操作就是用来确定如何从父代群体中按某种方式选取一些较优的个体进行杂交、变异操作。选择操作建立在对个体适应度值进行评价的基础上。选择的目的是为了避免基因缺失、提高收敛率和计算效率。有以下几种常用的选择算子的操作方法：比例选择（轮盘赌选择）、最优保存策略、确定式采样选择、无放回随机选择、排序选择等。(5) 交叉算子：在生物的自然进化中，两个同源染色体通过交配而重新组合，形成新的染色体，从而产生新的个体或物种。遗传算法通过模仿这个过程，使用交叉算子来产生新的个体。交叉运算是建立在选择运算之后，两个相互配对的染色体按某种方式交换其部分基因，从而形成新的个体。交叉运算是遗传算法区别与其他算法的重要特征，在遗传算法中充当着重要的作用，是产生新个体的主要方式。交叉算子有：单点交叉算子、双点交叉算子、均匀交叉算子、部分映射交叉算子（PMX）、顺序交叉算子（OX）等。(6) 变异算子：在生物的遗传和自然进化中，其细胞的分裂复制环节有可能会因为某些偶然因素的影响而产生一些复制差错，就会导致生物的某些基因发生变异，从而产生新的个体。在遗传算法中，变异操作也是如此。交叉操作是产生新个体的主要方式。它决定了遗传算法的全局搜索能力。而变异操作就是起着辅助作用，它提高了算法的局部搜索能力，避免算法陷入局部最优。两种算子的理想结合，才大大的提高了整个算法可行性。使计算结果大大的接近了全局最优解。变异算子的2个重要作用：1.改善遗传算法的局部搜索能力。2.维持群体多样性防止早熟现象。(7)运行参数:在遗传算法中需要选择的参数主要有个体的编码长度、群体大小、交叉概率、变异概率、遗传代数。个体编码长度：根据具体问题进行设定。群体大小：表示群体中所含个体数量。当群体较小的时候，可以提高遗传算法的运算速度，却降低了群体的多样性，从而导致遗传算法早熟现象；而当群体较大的时候，又会增大机器的开销、降低了算法的效率。交叉率：交叉是产生新个体的主要方式，一般应取较大值，但取值过大会破坏群体的中优秀的个体，对进化反而产生不利影响；取值过小的话，会导致收敛速度过慢所以一般取0.4到0.9。变异概率:取值较大，虽然能帮助种群产生较多的新的个体，但同时也可能破坏了很多较好的个体，使得遗传算法的性能靠近随机搜索算法的性能；取值过小的话，变异操作产生新个体的能力和抑制早熟的能力就变差。一般取值0.0001到0.1。(8) 全局最优收敛当指定的遗传代数循环结束，计算得到的最优个体就是全局最优解，就说明算法全局最优收敛。但如果得到的解并不是全局最优解，同时计算得到的解，已经过早的不发生变化，说明算法陷入了局部最优解。另外当循环结束的时候，最优解还在缓慢的变优，则需要提高遗传代数，从而得到全局最优解。2.1.2 遗传算法特点（1）遗传算法从问题解的部分集合开始搜索。传统的优化算法是从单个解，开始搜索。这是遗传算法和传统优化算法的几大区别。传统优化算法从单个个体开始迭代，很容易陷入局部最优。遗传算法从“串集”开始搜索覆盖面积大，利于全局最优。（2）遗传算法对优化问题没有太多的要求，只需要知道目标函数的信息即可，容易形成通用的算法。（3）遗传算法使用的选择、交叉、变异算子都是随机产生的，这样能帮助整个算法来慢慢的接近全局最优解。选择体现了向最优解靠近、交叉体现了最优解的产生、变异体现了全局最优解得覆盖。2.1.3 遗传算法的应用步骤第一步：确定决策变量，即确定出个体的表现型和问题的解得空间。第二步：建立目标函数，即根据问题确定是求最大值还是最小值，然后建立相应数学表达式来确定目标函数。第三步：确定个体的编码方式。第四步：确定解码方式，即确定个体基因型到表现型的对应关系的转换方式，在TSP 问题中，用最短距离为目标函数，访问路径为编码方式，所以不需要解码。第五步：设计遗传算子（即确定选择、交叉、变异等遗传算子的具体操作方法）。第六步：确定遗传算法的相关运行参数，如：种群大小、遗传代数、交叉率、变异率等。2.1.4 遗传算法的流程图开始初始化种群计算适应度值选择操作交叉操作变异操作停止条件否输出适应度最高的个体是结束图2.1 遗传算法流程图2.2 TSP问题介绍TSP问题，也称为巡回旅行商问题。已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他的访问次序，可使其旅行的总长度最短11。用图论的术语来说，假设有一个图g=(v,e),其中v是顶点集，e是边集，设d=是由顶点i和顶点j之间的距离所组成的距离举证，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。这个问题可分为对称旅行商问题(=)任意（i,j=1,2,3，,n)和非对称旅行商问题()任意i,j=（1,2,3，,n)。城市的一个访问顺序为,其中v(i=1,2,3,n)，且记，则旅行商问题的数学模型为：min =d(t(i),t(i+1) （i=0,9）本文讨论的是对称性旅行商问题。3 遗传算法在TSP上的应用与实现本文通过遗传算法来解决10个城市的旅行商问题。即一个商人需要经过10个城市去交易，每个城市必须且仅能经过一次。最后回到初始点。然后求出最短路径。 首先，本文运用基本遗传算法解决了TSP问题。然后通过改变各参数的值来观察计算结果，接着对计算结果的进行对比分析，从而验证了各参数对遗传算法的影响。主程序分为两个主模块。分别为初始种群10和100的模块。同时各模块还可以设定遗传代数、交叉率、变异率。以下对初始种群为100的模块进行代码分析。模块10代码类似，固不做分析。然后进行各参数设定后的结果对比。3.1 算法的实现以访问路径顺序进行编码3.1.1 遗传算法运用在TSP上的流图程采用随机方式初始化种群外部输入初始化种群个数、遗传代数、交叉率、变异率以每次访问总距离的倒数作为评估函数，对每个个体进行评估，初始化代数p=0P=遗传代数输出结果不成立成立结束选择操作P=p=1交叉操作变异操作图3.1 遗传算法运用在tsp上的流程图3.1.2 编码遗传算法设计的第一个重点就是编码。上文已经阐述过编码的各种主要方式。如：二进制表示、浮点编码、格雷码、参数编码等。由于二进制表示不自然且需要额外的修正算子，以保证个体的合法性，在实际运用中很少出现。在TSP问题中，路径表示可能是最自然、最直接的表示方式。它直接采用城市在整个路径中的相对位置来表示。遗传算法中的每个个体，就是一次访问的顺序。如有10个城市：0,1，2,3,4,5,6,7,8,9。商人的一次访问顺序为（4,2,1,0,5,8,3,9,6,7,4）。就用（4,2,1,0,5,8,3,9,6,7）作为种群中的一个个体的编码。表示商人从城市4出发路径为4,2,1,0,5,8,3,9,6,7最后回到城市4。这显然是一种非常自然的编码方式。其主要的缺点在于普通的单点、双点交叉操作后往往会引起非法路径的访问（在整个访问过程中有些城市访问了不止1次）。为了消除这一缺点，本文采用次序交叉方法代替了传统的单点、双点交叉。本文采用数组a10来存放群众中的一个个体的访问顺序。City10010存放种群中100个个体各自的访问顺序。3.1.3 初始化种群初始化种群：采用随机方式获得初始化种群。它适合与对问题的解无任何先验知识的情况。代码如下：void CTestDlg2:chushi(int a10,int city10010) int trsf; int ii,jj; for ( ii=0;ii=1;jj-) int n = rand()%(jj+1); trsf=ajj; ajj=an; an=trsf; cityiijj=ajj; cityii0=a0; 3.1.4 适应度函数为了体现种群中个体的适应能力，引入了对种群中每个个体进行度量的函数，叫做适应度函数。通过它来决定个体的优劣。它体现了自然进化中优胜劣汰的原则。对于优化问题，适应度函数就是目标函数。TSP问题的目标就是访问路径最短。本文采用路径距离和的倒数作为适应函数。本文用数组存放eval100每个个体的总路程。eval1100每个个体总路程的倒数，作为适应度函数。for(i=0;i=99;i+)eval1i=1/(evali);3.1.5 选择操作选择操作也称为复制操作。根据个体适应度函数所度量的优劣程度来决定个体是被淘汰还是遗传。对于求解TSP问题，常用的选择机制有轮盘赌选择、最佳个体保存选择，期望值模型机制，排序模型选择机制等。在遗传算法中，算法“早熟”是一个需要关注的问题。为了避免算法进入局部收敛，保证全局收敛性，就要维持种群个体的多样性，避免有效个体的丢失。Rudolhp C12提出采用精英选择策略即保持群体中最好的个体不丢失，以保证算法的收敛性。Konstantin Boukreev14采用联赛选择方法和最优个体保存方法相结合的方法。为了保证最好个体不丢失，本文采用轮盘赌算法和最优保存算法的结合。(1) 轮盘算法：将个体的适应度值按比例转换为选中的概率。使得适应度值高的个体的被选中的概率也高。令for(i=0;i=99;i+)gailvi=eval1i/total;。在将轮盘分成100个扇区进行100次选择。产生100个0到1之间的随机数。相当于轮盘转动100次，可以获得n次转盘停止时的指针位置，指针停放在某一个扇区。就代表选中了该扇区的个体。所以概率越大面积越大，被选中的几率越大。(2) 最优保存算法：在遗传算法的过程中，通过对个体进行交叉、变异等遗传操作不断产生新一代的种群个体，虽然随着不断的进化，会产生越来越多的优秀个体。但是由于遗传操作的随机性，可能破坏掉当代种群中最优秀的个体。我们希望适应度最好的个体要尽可能的保存到下一代群体中。为了实现这一目标，我们使用最优保存策略辅助轮盘算法来进行选择操作。最优保存的具体过程：首先找出当代个体中的最优个体和最差个体。如果当代个体中的最优个体比总优个体（也就是第一代种群到今的最优个体）的适应度值还要高的时候。则以当代最优个体来替换总最优个体中保存的个体。如果当代个体的最优个体比总最优个体要差，则说明最优个体被破坏，则用总最优个体替换掉当代个体中的最差个体。总最优个体不变。下面为轮盘算法和最有保存算法代码:轮盘算法:int CTestDlg2:select(double gailv100,int city10010)/选择函数 int q=0; double suiji=(double)rand()/RAND_MAX; while(suiji=0) suiji=(double)rand()/RAND_MAX; double leiji=0.0; while(leijisuiji)&(q100) leiji=leiji+gailvq; q+; q-; return(q); 最优保存算法： mi=int(Min(eval);/存放最优个体序号for(i=0;i=9;i+)/存放最优个体mi1i=(citymii);milen=int(evalmi);/存放当代最优路劲距离ma=int(Max(eval);/存放当代最差个体序号for(i=0;i=9;i+)ma1i=citymai;/存放最差个体malen=int(evalma);/存放当代最差路径距离if(tmilen=0)tmilen=milen;/存储首代最优路径距离for(i=0;i=9;i+)/存储首代最优路径顺序tmi1i=( mi1i);elseif(milen=tmilen)tmilen=milen;/更改总最优路径距离for(i=0;i=9;i+)/存储首代最优路径的访问顺序tmi1i=( mi1i);else for(i=0;i=9;i+)citymai=( tmi1i);/上代最优个体被破坏，用上代最优个体替换本代的最差个体.总最优路径不变其中的Min（）为求最优路径，Max（）求最差路径int CTestDlg2:Min(double eval100) int n =0; int ii=0; double comp100; for(ii=0;ii=99;ii+)compii=evalii; for(ii=1;iicompii)comp0=compii; for(ii=0;ii=99;ii+)if(comp0=evalii)n=ii;break; return n;int CTestDlg2:Max(double eval100) int n; int ii=0; double comp100; for(ii=0;ii=99;ii+)compii=evalii; for(ii=1;ii=99;ii+)if(comp0compii)comp0=compii; for(ii=0;ii=99;ii+)if(comp0=evalii)n=ii;break; return n; 3.1.6 交叉操作采用访问顺序编码后。如果采用简单的一点杂交或者多点杂交，就会产生非法路径。如：若采用一点杂交，随机杂交处为4：0 1 2 3 4| 5 6 7 8 9； 9 8 7 6 5| 4 3 2 1 0。杂交后的个体为：0 1 2 3 4 4 3 2 1 0；9 8 7 6 5 5 6 7 8 9。导致某些城市访问了不止1次。不符合TSP问题的定义。所以本文采用次序交叉来弥补这一缺陷。次序交叉(OX,ORDER CROSSOVER):由Davis等人提出OX算法。次序杂交算法首先随机地在上代群体中选择两个杂交点，再交换杂交段，其他位置根据保持上代城市的相对次序来确定。例如：A110=0,1,2,3,4,5,6,7,8,9 A210=9,8,7,6,5,4,3,2,1,0随机杂交点为3和5。首先交换杂交段。B110=#,#,#|6,5,4|#,#,#,#B210=#,#,#|3,4,5|#,#,#,#从B1的第二个杂交点开始6-7-8-9-0-1-2-3-4-5，去除杂交段中的6,5,4。变成7-8-9-0-1-2-3。一次顺序从第二个杂交点开始填入得:B110=1,2,3,6,5,4,7,8,9,0同理得:B210=8,7,6,3,4,5,2,1,0,9本文采用上述交叉算法，代码如下：double ww=0;ww=(double)rand()/RAND_MAX;o=select(gailv,city);p=select(gailv,city);while(o=p)p=select(gailv,city);/由于2次选择了同一个个体重新选择一个个体p;for(i=0;i=9;i+)A1i=cityoi;for(i=0;i=9;i+)A2i=citypi;if(wwp2)temp1=p1;p1=p2;p2=temp1;for(i=p1; i=p2;i+)B1i = A2i;B2i = A1i;convert(p1,p2,A1,B1);convert(p1,p2,A2,B2);int xy=0;for( xy=0;xy=9;xy+)city1kxy=B1xy;for( xy=0;xy=9;xy+)city1k+1xy=B2xy;else int xy=0;for( xy=0;xy=9;xy+)city1kxy=A1xy;for( xy=0;xy=9;xy+)city1k+1xy=A2xy; 其中的convert(p1,p2,A1,B1)函数打代码如下：void CTestDlg2:convert(int pos1,int pos2,int *so,int *dest) int temp10;int ii = 0;int jj = 0;int kk = 0;for(ii=0; ii10; ii+)tempii = so(ii+pos2+1)%10;for(ii=0; ii10; ii+)for(jj=pos1; jj=pos2; jj+)if(tempii = destjj)tempii = 100;break;jj = 0;ii = 0;while(jj10)if(tempjj != 100)tempii = tempjj;ii+;jj+;for(kk=0; kk(10-(pos2-pos1)-1); kk+)dest(kk+pos2+1)%10 = tempkk;3.1.7 变异操作在遗传算法中，变异操作并不是最主要的。遗传算法强调的是杂交功能。变异操作是改善遗传算法的局部搜索能力和维持群体的多样性防止早熟现象。针对TSP问题，陈国良等介绍了四种主要的变异技术：（1）点位变异，变异仅以某一很小的概率对串的某些位值变异；（2）逆转变异，在串中随机选择两点，再将这两点内的内容按反序插入到原来的位置中。（3）对换操作，随机选择两个交换点，使交换点处的码值交换。这种变异操作在TSP问题中常被采用.(4) 插入变异，从串中随机选择1个码，将此码插入随机选择的插入点之后。本文采用对换变异操作，代码如下：void CTestDlg2:bianyi(int bianyi10) int trasfs;int ii=0;int jj=0;int kk=0;for(kk=1;kk=2;kk+) ii=rand()%10; jj=rand()%10;while(ii=jj) jj=rand()%10;trasfs=bianyijj; bianyijj=bianyiii;bianyiii=trasfs;此外，对于变异操作还有一些变体形式，如Sushil Jouis提出的贪心对换变异、谢胜利15等提出倒位变异算子。3.2 不同参数下的计算结果对比3.2.1 初始种群10和100的对比理论上，在遗传算法中初始种群的个数决定了种群个体的多样性。初始种群过少会导致程序陷入局部最优，而无法得到近似最优解。增加种群个数可以避免进入局部最优，但是种群过大会减慢程序的运算速度，导致算法效率的低下。下面是2个模块的结果对比。本文采用网络上已有的城市距离矩阵来验证所写程序的正确性: int length1010= 0, 23, 93, 18, 40, 34, 13, 75, 50, 35, 23, 0, 75, 4, 72, 74, 36, 57, 36, 22, 93, 75, 0, 64, 21, 73, 51, 25, 74, 89, 18, 4, 64, 0, 55, 52, 8, 10, 67, 1, 40, 72, 21, 55, 0, 43, 64, 6, 99, 74, 34, 74, 73, 52, 43, 0, 43, 66, 52, 39, 13, 36, 51, 8, 64, 43, 0, 16, 57, 94, 75, 57, 25, 10, 6, 66, 16 , 0, 23, 11, 50, 36, 74, 67, 99, 52, 57 ,23, 0, 42, 35, 22, 89, 1