遗传算法在求解TSP问题毕业论文毕业设计毕业论文

目 录 摘要 I Abstract II 引 言 1 第一章 基本遗传算法 2 1.1 遗传算法的产生及发展 3 1.2 基本原理 3 1.3 遗传算法的特点 3 1.4 基本遗传算法描述 5 1.5 遗传算法构造流程 6 第二章 遗传算法的实现技术 6 2.1 编码方法 7 2.1.1 二进制编码 7 2.1.2 格雷码编码 7 2.1.3 符点数编码 8 2.1.4 参数编码 8 2.2 适应度函数 10 2.3 选择算子 10 2.4 交叉算子 10 2.4.1 单点交叉算子 10 2.4.2 双点交叉算子 11 2.4.3 均匀交叉算子 11 2.4.4 部分映射交叉 11 2.4.5 顺序交叉 12 2.5 变异算子 12 2.6 运行参数 12 2.7 约束条件的处理方法 13 2.8 遗传算法流程图 14 第三章 遗传算法在TSP上的应用 15 3.1　TSP问题的建模与描述 15 3.2 对TSP的遗传基因编码方法 16 3.3 针对TSP的遗传操作算子 17 3.3.1 选择算子 17 3.3.1.1　轮盘赌选择 17 3.3.1.2　最优保存策略选择 17 3.3.2 交叉算子 20 3.3.2.1 单点交叉 20 3.3.2.2 部分映射交叉 21 3.3.3 变异算子 23 3.4 TSP的混和遗传算法 26 第四章 实例 27 4.1 测试数据 27 4.2 测试结果 27 4.3 结果分析 27 摘 要 TSP (Traveling Salesman Problem)旅行商问题是一类典型的NP完全问题，遗传算法是解决NP问题的一种较理想的方法。文章首先介绍了基本遗传算法的基本原理、特点及其基本实现技术；接着针对TSP 问题，论述了遗传算法在编码表示和遗传算子（包括选择算子、交叉算子变异算子这三种算子）等方面的应用情况，分别指出几种常用的编码方法的优点和缺点，并且结合TSP的运行实例详细分析了基本遗传算法的4个运行参数群体大小、遗传算法的终止进化代数、交叉概率、变异概率，对遗传算法的求解结果和求解效率的影响，经过多次的测试设定出了它们一组比较合理的取值。最后，简单说明了混合遗传算法在求解TSP问题中的应用并对遗传算法解决TSP问题的前景提出了展望。 关键词：TSP 遗传算法 遗传算子 编码 Abstract TSP (Traveling Salesman Problem) is a typical NP - complete problem and genetic algorithm (GA) is the perfect method for solving NP - complete problem. The basic theories, characteristics and the basic techniques of GA are first introduced. Then the encoding model and genetic operators (including selection operation, crossover operation and mutation operation) about GA in solving TSP are discussed. The advantages and disadvantages of various encoding method are respectively indicated, and the application of the three basic genetic operators is elaborated. According to the given data, the results and efficiencies are influenced by four parameters in the basic genetic algorithm: the size of population, terminate generation, crosser probability and mutation probability. Adjust the parameters, run and try for better ones. At last, the application of hybrid genetic algorithm is briefly presented. It is pointed out that a better crossover or mutation routine can be found out which retains the structure from the parent chromosomes and still ends up with a legal tour in the child chromosomes, which leads to a better solution than ever before. And the prospect for the future of genetic algorithm in solving TSP is made. Keywords: TSP genetic algorithm genetic operators encoding 引 言 现代科学理论研究与实践中存在着大量与优化、自适应相关的问题，但除了一些简单的情况之外，人们对于大型复杂系统的优化和自适应问题仍然无能为力。然而，自然界中的生物却在这方面表现出了其优异的能力，它们能够以优胜劣汰、适者生存的自然进化规则生存和繁衍，并逐步产生出对其生存环境适应性很高的优良物种。遗传算法正是借鉴生物的自然选择和遗传进化机制而开发出的一种全局优化自适应概率搜索算法。 遗传算法使用群体搜索技术，它通过对当前群体施加选择、交叉、变异等一系列遗传操作，从而产生出新一代的群体，并逐步使群体进化到包含或接近最优解的状态。由于其具有思想简单、易于实现、应用效果明显等优点而被众多应用领域所接受，并在自适应控制、组合优化、模式识别、机器学习、人工生命、管理策略等领域得到了广泛应用。遗传算法给我们呈现出的是一类通用的算法框架，该框架不依赖于问题的种类。遗传算法是一类具有较强鲁棒性的优化算法，特别是对于一些大型、复杂非线性系统，它更表现出了比其他传统优化方法更加独特和优越的性能。隐含并行性和全局搜索特性是遗传算法的两大显著特征。 遗传算法是新发展起来的一门学科，各种理论、方法尚未成熟，有待于进一步地发展和完善，但它却为我们解决许多复杂问题提供了希望。尽管在遗传算法的研究和应用过程中出现许多难题，同时也会产生许多不同的算法设计观点，然而，目前遗传算法的各种应用实践已经展现出了其优异的性能和巨大的发展潜力，它的发展前景激励着各类专业技术人员把遗传算法的理论和方法运用于自己的工作实践中。我们相信，随着研究工作的进一步深入和发展，遗传算法必将在智能计算领域中起到关键作用。 货郎担问题(Traveling Salesman Problem ,TSP)，也称为巡回旅行商问题，是一个较古的问题。最早可以追溯到1759年Euler提出的骑士旅行问题。TSP问题是一个典型的、容易描述但是难以处理的NP完全问题，同时TSP问题也是诸多领域内出现的多种复杂问题的集中概括和简化形式。目前求解TSP问题的主要方法有启发式搜索法、模拟退火算法、遗传算法、Hopfield神经网络算法、二叉树描述算法。所以，有效解决TSP问题在计算理论上和实际应用上都有很高的价值，而且TSP问题由于其典型性已经成为各种启发式的搜索、优化算法的间接比较(如遗传算法、神经网络优化、列表寻优(TABU)法、模拟退火法等)。遗传算法就其本质来说，主要是解决复杂问题的一种鲁棒性强的启发式随机搜索算法。因此遗传算法在TSP问题求解方面的应用研究，对于构造合适的遗传算法框架、建立有效的遗传操作以及有效地解决TSP问题等有着多方面的重要意义。 第一章 基本遗传算法 1.1 遗传算法的产生及发展 最早美国Ｍichigan(密执安大学)的Holland教授提出，起源于60年代对自然和人工自适应系统的研究。70年代De Jong基于遗传算法的思想在计算机上进行了大量纯数值函数优化计算实验。在一系列研究工作的基础上80年代Goldberg进行总结归纳，形成了遗传算的基本框架。 主要以一些关键人物所做出的主要贡献见证了遗传算法的发展进程: 1 J.H.Holland 60年代提出在研究和设计人工自适应系统时,可以借鉴生物遗传的机制； 　 70年代初提出了遗传算法的基本定理－模式定理(Schema Theorem)，从而奠定了遗传算法的理论基础；　 80年代实现了第一个基于遗传算法的机器学系统－分类器系统(Classifier Systems),开创了基于遗传算法的机器学习的新概念。 2 J.D.Bagley 1967年在其博士论文中首次提出了：“遗传算法”一词，发展了复制、交叉、变异、显性、倒位等遗传算子，创立了自适应遗传算法的概念。 3 K.A.De Jong 1975年在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验，树立了遗传算法的工作框架，定义了遗传算法性能的在线指标和离线指标。 4 D.J.Golgberg 1989年出版了专著《搜索、优化和机器学习中的遗传算法(Genetic Algorithms in Search，Optimization and Machine Learning)》，系统总结了遗传算法的主要研究成果，全面而完整的论述了遗传算法的基本原理及其应用。 5 L.Davis 1991年编辑出版了《遗传算法手册 (Handbook of Genetic Algorithms)》中包括遗传算法在科学计算、工程技术和社会经济中的大量应用实例。 6 J.R.Koza 1992年将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程 (Genetic Programming) 的概念，并成功的将其提出的遗传编程应用于人工智能、机器学习符号处理等方面。 1.2 基本原理 遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机化搜索算法，由美国J.Holland教授提出，其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。它是一种全局化搜索算法，尤其适用于传统搜索算法难于解决的复杂和非线性问题。 选择(selection)算子、交叉(crossover)算子和变异(mutation)算子是遗传算法的3个主要操作算子。遗传算法中包含了如下5个基本要素: (1) 对参数进行编码； (2) 设定初始种群大小； (3) 适应度函数的设计； (4) 遗传操作设计； (5) 控制参数设定(包括种群大小、最大进化代数、交叉率、变异率等)。 1.3 遗传算法的特点 (1) 遗传算法对优化问题没有太多的数学要求，而且只要知道目标函数的信息即可； (2) 遗传算法采用的是启发性的知识智能搜索算法，在搜索高度空间复杂问题上比以往有更好的效果； (3) 遗传算法是对问题参数或者变量编码群进行优化，而不是参数或变量本身； (4) 遗传算法使用的选择、交叉、变异算子都是随机的； 1.4 基本遗传算法描述 基于对自然界中生物遗传与进化机理的模仿，针对不同的问题，很多学者设计了许多不同的编码方法来表示问题的可行解，开发出了许多种不同的遗传算子来模仿不同环境下生物遗传特性。这样，由不同的编码方法和不同的遗传算子就构成了各种不同的遗传算法。但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。基于这个特点，Goldberg总结出了一种统一的最基本的遗传算法——基本遗传算法（Simple Genetic Algorithms，简称SGA）。基本遗传算法只使用选择算子、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。 基本遗传算法描述： 基本遗传算法只使用选择算子 ( Selection Operator)、交叉算子(Crossover Operator)、变异算子(Mutation Operator)这三种算子。 基本遗传算法可以形式化定义为一个八元组：SGA=(C,E,Po,M,φ,τ,ψ,T) C ——个体的编码方法； E ——个体适应度评价函数； Po——初始群体； M ——群体大小； φ ——选择算子； τ ——交叉算子； ψ ——变异算子； T ——遗传运算终止条件。 遗传算法的应用步骤： 第一步： 确定决策变量及其各种约束条件，即确定出个体的表现型X和问题的解空间。 第二步： 建立优化模型，即确定出目标函数的类型(是求目标函数的最大值还是求目标函数的最小值？)及其数学描述形式或量化方法。 第三步：确定表示可行解的染色体编码方法，也即确定出个体的基因型X及遗传算法的搜索空间。 第四步：确定解码方法，即确定出个体基因型X到个体表现型X的对应关系转换方法。 第五步：确定个体适应度的量化评价方法，即确定出由目标函数值f(X)到个体适应度F(X)的转换规则。 第六步：设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法。 第七步：确定遗传算法的有关运行参数，即确定出遗传算法的M、T、Pc、Pm等参数。 1.5 遗传算法构造流程 遗传算法的构造过程可以用下图进行描述： 图1－1 遗传算法的主要构造过程示意图 第二章 遗传算法的实现技术 2.1 编码方法 在遗传算法中如何描述问题的可行解，即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称为编码。 编码是应用遗传算法时要解决的主要问题，也是设计遗传算法的一个关键步骤。编码方法除了决定个体染色体排列形式之外，还决定了个体从搜索空间的基因型变换到解空间的表现型时的解码方法，编码方法也影响到交叉算子、变异算子等遗传算子的运算方法。 针对一个具体问题，如何设计一个完美的编码一直是遗传算法的应用难点之一，也是遗传算法的一个重要研究方向。目前还没有一套既严密有完整的指导理论及评价准则能够指导我们设计编码方案。De Jong曾提出了两条操作性较强的实用编码原则： 编码原则一(有意义积木块编码原则):应使用能易于产生与所求问题相关的且具有低阶，短定义长度的编码方案。 编码原则二(最小字符集编码原则):应使用能使问题得到自然表示或描述的具有最小字符集的编码方案。 迄今为止人们已经提出了许多的编码方法，总的来说，可以分为三类：二进制编码方法，浮点数编码方法，符号编码方法。 2.1.1 二进制编码 二进制编码方法是遗传算法中最常用的一种编码方法，它使用的编码符号集是由二进制符号0和0组成的二值符号集｛0，1｝，它所构成的个体基因型是一个二进制编码符号串。它有如下几个优点： (1)编码，解码简单易行。 (2)交叉，变异等遗传操作便于实现。 (3)符合最小字符集编码原则。 (4)便于利用模式定理对算法进行理论分析。 二进制编码符号串的长度与问题所要求的精度有关。 由于二进制不便于反映所求问题的结构特征，对于一些连续函数的优化问题等，也由于遗传运算的随机特性而使得其局部搜索能力较差，因而人们提出了用格雷码来对个体进行编码。 2.1.2 格雷码编码 格雷码，连续的两个整数所对应的编码值之间只有一个码位不相同。格雷码有这样一个特点：任意两个整数的差是这两个整数所对应的海明距离（Hamming distance）。这个特点是遗传算法中使用格雷码进行个体编码的主要原因。格雷码编码方法的主要优点是： (1)便于提高遗传算法的局部搜索能力。 (2)交叉，变异等遗传操作易于实现。 (3)符合最小字符集编码原则。 (4)便于用模式定理对算法进行理论分析。 假设一个二进制编码为 B=bnbn-1…b2b1，其对应的格雷码为 G=gngn-1…g2g1。格雷码到二进制码的转换公式： 格雷码编码方法是二进制编码方法的一种变形，其编码精度与相同长度二进制编码方法的精度相同。 由于二进制编码存在着连续函数离散化时的映射误差，而且不便于反映所求问题的特定知识，因而人们提出了用符点数来对个体进行编码。 2.1.3 符点数编码 符点数编码方法:指个体的每个基因值用某一范围内的一个浮点数来表示个体的编码长度等于其决策变量的个数，个体变量的长度等于去决策变量的真实值，所以也叫真值编码方法．它有以下几个优点： (1)适合于在遗传算法中表示范围较大的数。 (2)适合于精度较高的遗传算法。 (3)便于较大空间的遗传搜索。 (4)改善了遗传算法的复杂性，提高了运算效率。 (5)便于遗传算法与经典优化方法的混合使用。 (6)便于设计针对问题的专门知识的知识型遗传算子。 (7)便于处理复杂的决策变量约束条件。 符号编码方法是指个体染色体编码串中的基因值取自一个无数值含义，而只有代码含义的符号集．它的主要优点如下： (1)符合有意义积木块编码原则。 (2)便于在遗传算法中利用所求解问题的专门知识。 (3)便于遗传算法与相近似算法之间的混合使用。 但对于使用符号编码方法的遗传算法，一般需要认真设计交叉、变异等遗传运算的操作方法，以满足问题的各种约束要求，这样才能提高算法的搜索性能。 最后，简要介绍一下参数编码方法。 2.1.4 参数编码 参数编码方法是对含有多个变量的个体进行编码的方法，包含两种编码方法： 多参数级联编码方法：将各个参数分别以某种编码方法进行编码，然后再将它们的编码按一定顺序联接在一起就组成了表示全部参数的个体编码。 多参数交叉编码方法：将各个参数中起主要作用的码位集中在一起。 2.2 适应度函数 在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某个物种对其生存环境的适应程度。对生存环境适应程度较高的物种将有更多的繁殖机会；而对生存环境适应度较低的物种，其繁殖的机会就相对较少，甚至会逐渐灭绝。适应度较高的个体遗传到下一代的概率就相对大一些；而适应度较低的个体遗传到下一代的概率就相对较小一些。度量个体适应度的函数就称为适应度函数。 根据个体的适应值，就可决定在此环境下的生存能力。个体适应度大小决定该个体被遗传到下一代群体中的概率。遗传算法仅使用所求问题的目标函数值就可以得到下一步的有关搜索信息。目标函数值的使用是通过评价个体适应度来体现的。 由于个体适应度大小决定该个体被遗传到下一代群体中的概率。评价个体适应度的一般过程： (1)对个体编码串进行解码处理后，可得到个体的表现型。 (2)由个体的表现型可计算出对应个体的目标函数值。 (3)根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应度。 但是，在仅用适应度函数来计算个体适应度时,有些遗传算法收敛很快,有些遗传算法收敛很慢，因此在运行到不同的阶段时须对个体的适应度进行适当的扩大或缩小。 适应度尺度变换(Fitness Scaling):对个体的适应度进行适当的扩大或缩小变换。 个体适应度尺度变换的三种方法： 线性尺度变换公式如下： F＇=aF+b F—原适应度； F＇—尺度变换后的新适应度； a和b—系数。 乘幂尺度变换公式如下： F＇=F ⁿ 幂指数n与所求解的问题有关。 指数尺度变换公式如下： F＇=exp(-βF) 系数β决定了选择的强制性。 2.3 选择算子 遗传算法中使用选择算子（也叫复制算子Reproduction Operator）来对群体中的个体进行优胜劣汰操作：适应度较高的个体被遗传到下一代的概率较大；适应度较低的个体被遗传到下一代的概率较小。遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群体中的一种遗传运算。 选择操作建立在对个体的适应度进行评价的基础上。选择的主要目的为了避免基因缺失、提高全局收敛性和计算效率。有以下几种常用的选择算子的操作方法：比例选择、最优保存策略、确定式采样选择、无放回随机选择、无放回余数随机选择、排序选择和随机联赛选择等。 最常用的几种选择策略有以下几种： (1) 轮盘赌选择(Roulette Wheel Selection) 个体适应度按比例转换为选中概率，将轮盘分成n个扇区进行n次选择，产生n个0～1之间的随机数相当于转动n次轮盘，可以获得n次转盘停止时指针位置，指针停放在某一扇区，该扇区代表的个体被选中。概率越大所占转盘面积越大，被选中的机率越大。 (2) 最优保存策略选择(Elitist selection) 在遗传算法的运行过程中，通过对个体进行交叉、变异等遗传操作而不断产生新的个体，虽然随着群体的进化过程会产生出越来越多的优良个体，但由于遗传操作的随机性，它们也有可能破坏掉当前群体中适应度最好的个体。我们希望适应度最好的个体要尽可能的保存到下一代群体中，为达到这个目的我们使用最优保存策略进化模型。 (3) 排序选择方法（Rank-based selection） 主要思想是：对群体中的所有个体按其适应度大小进行排序，基于这个排序来分配各个个体被选中的概率。 (4) 比例选择(proportional selection) 个体被选中的概率与其适应度大小成正比。由于随机操作的原因，这种选择方法的选择误差较大，有时连适应度高的个体也选不上。 (5) 确定式采样选择（Determinstic Sampling selection） 基本思想是按照一种确定的方式进行选择操作。 (6) 无回放随机选择（Expected value selection） 根据每个个体在下一代群体中的生存期望值来进行随机选择运算。 (7) 随机联赛选择(Stuchastic Tournament Selection) 每次选取几个适应度最高的一个个体遗传到下一代群体中。 2.4 交叉算子 在生物的自然进化中，两个同源染色体通过交配而重组，形成新的染色体，从而产生新的个体或物种。模仿这个环节，在遗传算法中也使用交叉算子来产生新个体。交叉运算是指两个相互配对的染色体按某种方式交换其部分基因，从而形成新个体。交叉运算是遗传算法区别于其他进化算法的重要特征，在遗传算法中起关键作用，是产生新个体的主要方法。 2.4.1 单点交叉算子 最常用的交叉算子是单点交叉算子。它是在个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。 例如：以下两个个体在第四个基因座之后进行单点交叉运算，得到两个新个体： 单点交叉的重要特点是：若邻接基因座之间的关系能够提供较好的个体性状和较高的个体适应度的话，则单点交叉操作破坏这种个体性状和降低个体适应度的可能性最小。 2.4.2 双点交叉算子 双点交叉(Two-point Crossover)：是指在个体编码串中随机设置了两个交叉点，然后进行部分基因交换。 双点交叉的具体操作过程是： (1) 在相互配对的两个个体编码中随机设置两个交叉点。 (2) 交换两个个体在所设定的两个交叉点之间的部分染色体。 例如：以下两个个体在第二、四个基因座之间进行交叉运算，得到两个新个体： 2.4.3 均匀交叉算子 均匀交叉(Uniform Crossover)：是指两个配对个体的每个基因 座上的基因都以相同的交叉概率进行交换，从而形成两个新的个体。 例如：以下两个个体进行交叉运算，得到两个新个体： 2.4.4 部分映射交叉(PMX)算子 整个交叉操作由两步来完成:首先对个体编码串进行常规的双点交叉操作。然后根据交叉区域内各个基因值之间的映射关系来修改交叉区域之外的各个基因座的基因值。交叉对象一般是符号编码表示的个体。 例如：以下两个个体选取第三、六个基因座之后进行交叉运算，得到两个新个体： 2.4.5 顺序交叉（Order Crossover）算子 主要思想：先进行常规的双点交叉，然后进行个体巡回顺序的有效顺序修改，修改时 要尽量维持个点原有的相对访问顺序。 例如:以下两个个体选取第三、六个基因座之后进行交叉运算，得到两个新个体： 2.5 变异算子 在生物的遗传和自然进化中，其细胞分裂复制环节有可能会因为某些偶然因素的影响而产生一些复制差错，就会导致生物的某些基因发生某种变异，从而产生新的染色体，表现出新的生物性状。在遗传算法中的变异运算，是指将基因座上的基因值用该基因座的等位基因来替换，从而产生新个体。从遗传运算过程中产生新个体的能力方面来说，交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索能力；而变异运算只是产生新个体的辅助方法，但它也是一个必不可少的运算步骤，因为它决定了遗传算法的局部搜索能力。它们共同完成对搜索空间的全局搜索和局部搜索，使遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。 变异算子有以下两个作用： (1) 改善遗传算法的局部搜索能力。 (2) 维持群体多样性，防止早熟现象。 较常用的基本位变异、均匀变异、边界变异、非均匀变异和高斯变异等。 2.6 运行参数 在遗传算法中需要选择的运行参数主要有个体编码串长度l、群体大小M、交叉概率pc、变异概率pm、、终止代数T、代沟G等。 (1) 编码串长度L。使用二进制编码时，编码串长度l的选取与问题所要求的求解精度有关；使用浮点数编码时，编码串长度l与决策变量的个数n相等；使用符号变量来表示个体时。编码串长度l由问题的编码方式来确定；另外，也可以使用变长度的编码来表示个体。 (2) 群体大小M表示群体中所含个体的数量。当M较小时，可提高遗传算法的运算速度，却降低了群体的多样性，有可能会引起遗传算法早熟现象；而当M较大时，又会使得遗传算法的运行效率降低。一般的建议范围是20～100。 (3) 交叉概率pc。交叉操作是产生新个体的主要方法，一般应取较大值，但取值过大的话，它会破坏群体中的优良模式，对进化运算反而产生不利影响；取值过小的话，产生新个体的速度较慢。一般取0.4～0.99。 (4) 变异概率pm。取值较大，虽然能产生较多的新个体，但有可能破坏掉很多的较好模式，使得遗传算法的性能近似于随机搜索算法的性能；取值过大的话，则变异操作产生新个体的能力和抑制早熟的能力就差。一般取0.0001～0.1。 (5) 终止代数T。表示遗传算法运行到指定的进化代数之后就停止，并将当前群体中的最佳个体作为所求问题的最优解输出。一般为100～1000。 (6) 代沟G。表示每一代群体中被替换掉的个体中所占的百分率，即每一代中有(M×G个个体被替换掉)。 2.7 约束条件的处理方法 主要有搜索空间限定法、可行解变换法、罚函数法。 2.8 遗传算法流程图 通过前几节的了解，容易看出遗传算法的流程可用下图进行描述： 图2-1遗传算法流程图 第3章 　遗传算法在TSP上的应用 3.1　TSP问题的建模与描述 TSP问题属于NP完全问题，给定一组n个城市和他们两两之间地直达距离，寻找一条闭合的旅程，使得每个城市刚好经过一次而且总的旅行距离最短。TSP问题的描述很简单，简言之就是寻找一条最短的遍历n个城市的路径，或者说搜索整数子集X = { 1，2， …， n} ( X 的元素表示对n个城市的编号) 的一个排列л( X) = { v1，v2， …， vn},使 　　　　　　T = ∑d( vi，vi + 1) + d( vi，vn) 取最小值。式中的d ( vi，vi + 1) 表示城市vi 到城市vi + 1 的距离。 产生初始种群的方法通常有两种。一种是完全随机的方法产生，它适合与对问题的解无任何先验知识的情况。另一种是某些先验知识可转变为必须满足一组要求，然后在满足这些要求的解中再随机地选取样本。这样选择初始种群可使遗传算法更快地到达最优解。下面给出了C语言描述的完全随机产生新种群的函数。 GenerateInitialPopulation() /*random*/ { int x,y; /* Seed the random-number generator with current time so that * the numbers will be different every time we run. */ srand( (unsigned)time( NULL) ); for(x=0;xpopulation[i].value) { temp_value=population[j].value; population[j].value=population[i].value ; population[i].value=temp_value; temp_fitness=population[j].fitness; population[j].fitness=population[i].fitness ; population[i].fitness=temp_fitness; for(x=0;xp2) { temp=p1; p1=p2; p2=temp; } for(i=p1+1;i<=p2;i++) { for(j=0;jp2) { temp=p1; p1=p2; p2=temp; } for(i=p1+1;i<=p2;i++) { insert[i-p1-1]=population[x].Path[i]; } for(i=p2;i>=p1+1;i--) { population[x].Path[i]=insert[p2-i]; } } (3) 对换变异，随机选择串中的两点，交换其码值。 change_mutation() { int i; int x,temp,p1,p2; int insert[MaxPathlength]; x=rand()%(POPSIZE); p1=rand()%Pathlength; p2=rand()%(Pathlength-1)+1; while(abs(p2-p1)<1) { p2=rand()%Pathlength; } if(p1>p2) { temp=p1; p1=p2; p2=temp; } temp=population[x].Path[p1]; population[x].Path[p1]=population[x].Path[p2]; population[x].Path[p2]=temp; } (4) 插入变异，从串中随机选择1个码，将此码插入随机选择的插入点之后。 insert_mutation() { int i; int x,temp,p1,p2; int insert[MaxPathlength]; x=rand()%(POPSIZE); p1=rand()%Pathlength; p2=rand()%(Pathlength-2)+2; while(abs(p2-p1)<2) { p2=rand()%Pathlength; } if(p1>p2) { temp=p1; p1=p2; p2=temp; } temp=population[x].Pat