C语言遗传算法在求解TSP问题设计论文

1毕 业 设 计(论 文)学院 信息工程学院专业 计算机科学技术与应用班级 1625姓名 徐东2007年 4月 15日2目 录摘要 1第一章 基本遗传算法 .基本原理.遗传算法的特点.基本遗传算法描述.遗传算法构造流程.传算法的实现技术 码方法. 适应度函数. 选择算子. 交叉算子. 变异算子. 运行参数. 约束条件的处理方法.遗传算法流程图.传算法在. 对. 针对. 轮盘赌选择. 最优保存策略选择.单点交叉.部分映射交叉.例分析 试数据. 测试结果. 结果分析.行商问题是一类典型的传算法是解决章首先介绍了基本遗传算法的基本原理、特点及其基本实现技术；接着针对述了遗传算法在编码表示和遗传算子（包括选择算子、交叉算子变异算子这三种算子）等方面的应用情况，分别指出几种常用的编码方法的优点和缺点，并且结合传算法的终止进化代数、交叉概率、变异概率，对遗传算法的求解结果和求解效率的影响，经过多次的测试设定出了它们一组比较合理的取值。最后，简单说明了混合遗传算法在求解键词：传算法 遗传算子 编码is a P - is P - of to by of is It is a or be up a in to SP 现代科学理论研究与实践中存在着大量与优化、自适应相关的问题，但除了一些简单的情况之外，人们对于大型复杂系统的优化和自适应问题仍然无能为力。然而，自然界中的生物却在这方面表现出了其优异的能力，它们能够以优胜劣汰、适者生存的自然进化规则生存和繁衍，并逐步产生出对其生存环境适应性很高的优良物种。遗传算法正是借鉴生物的自然选择和遗传进化机制而开发出的一种全局优化自适应概率搜索算法。遗传算法使用群体搜索技术，它通过对当前群体施加选择、交叉、变异等一系列遗传操作，从而产生出新一代的群体，并逐步使群体进化到包含或接近最优解的状态。由于其具有思想简单、易于实现、应用效果明显等优点而被众多应用领域所接受，并在自适应控制、组合优化、模式识别、机器学习、人工生命、管理策略等领域得到了广泛应用。遗传算法给我们呈现出的是一类通用的算法框架，该框架不依赖于问题的种类。遗传算法是一类具有较强鲁棒性的优化算法，特别是对于一些大型、复杂非线性系统，它更表现出了比其他传统优化方法更加独特和优越的性能。隐含并行性和全局搜索特性是遗传算法的两大显著特征。遗传算法是新发展起来的一门学科，各种理论、方法尚未成熟，有待于进一步地发展和完善，但它却为我们解决许多复杂问题提供了希望。尽管在遗传算法的研究和应用过程中出现许多难题，同时也会产生许多不同的算法设计观点，然而，目前遗传算法的各种应用实践已经展现出了其优异的性能和巨大的发展潜力，它的发展前景激励着各类专业技术人员把遗传算法的理论和方法运用于自己的工作实践中。我们相信，随着研究工作的进一步深入和发展，遗传算法必将在智能计算领域中起到关键作用。货郎担问题(也称为巡回旅行商问题，是一个较古的问题。最早可以追溯到1759年易描述但是难以处理的时前求解拟退火算法、遗传算法、叉树描述算法。所以，有效解决且化算法的间接比较标准(如遗传算法、神经网络优化、列表寻优(、模拟退火法等)。遗传算法就其本质来说，主要是解决复杂问题的一种鲁棒性强的启发式随机搜索算法。因此遗传算法在于构造合适的遗传算法框架、建立有效的遗传操作以及有效地解决第一章 执安大学)的源于60年代对自然和人工自适应系统的研究。70年代一系列研究工作的基础上80年代成了遗传算的基本框架。主要以一些关键人物所做出的主要贡献见证了遗传算法的发展进程:1 以借鉴生物遗传的机制；70年代初提出了遗传算法的基本定理模式定理(从而奠定了遗传算法的理论基础；80年代实现了第一个基于遗传算法的机器学系统分类器系统(开创了基于遗传算法的机器学习的新概念。2 遗传算法”一词，发展了复制、交叉、变异、显性、倒位等遗传算子，创立了自适应遗传算法的概念。3 立了遗传算法的工作框架，定义了评价遗传算法性能的在线指标和离线指标。4 索、优化和机器学习中的遗传算法(，系统总结了遗传算法的主要研究成果，全面而完整的论述了遗传算法的基本原理及其应用。5 传算法手册(书中包括遗传算法在科学计算、工程技术和社会经济中的大量应用实例。6 出了遗传编程(概念，并成功的将其提出的遗传编程应用于人工智能、机器学习符号处理等方面。主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。它是一种全局化搜索算法，尤其适用于传统搜索算法难于解决的复杂和非线性问题。选择(子、交叉(子和变异(子是遗传算法的3个主要操作算子。遗传算法中包含了如下5个基本要素:(1)对参数进行编码；(2)设定初始种群大小；(3)适应度函数的设计；(4)遗传操作设计；(5)控制参数设定(包括种群大小、最大进化代数、交叉率、变异率等)。)遗传算法对优化问题没有太多的数学要求，而且只要知道目标函数的信息即可；(2)遗传算法采用的是启发性的知识智能搜索算法，在搜索高度空间复杂问题上比以往有更好的效果；(3)遗传算法是对问题参数或者变量编码群进行优化，而不是参数或变量本身；(4)遗传算法使用的选择、交叉、变异算子都是随机的；对不同的问题，很多学者设计了许多不同的编码方法来表示问题的可行解，开发出了许多种不同的遗传算子来模仿不同环境下生物遗传特性。这样，由不同的编码方法和不同的遗传算子就构成了各种不同的遗传算法。但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。基于这个特点，基本遗传算法（称基本遗传算法只使用选择算子、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。8基本遗传算法描述：基本遗传算法只使用选择算子 (交叉算子(变异算子(三种算子。基本遗传算法可以形式化定义为一个八元组：C,E,T)C 个体的编码方法；E 个体适应度评价函数；初始群体；M 群体大小； 选择算子； 交叉算子； 变异算子；T 遗传运算终止条件。遗传算法的应用步骤：第一步：确定决策变量及其各种约束条件，即确定出个体的表现型二步：建立优化模型，即确定出目标函数的类型(是求目标函数的最大值还是求目标函数的最小值？)及其数学描述形式或量化方法。第三步：确定表示可行解的染色体编码方法，也即确定出个体的基因型四步：确定解码方法，即确定出个体基因型五步：确定个体适应度的量化评价方法，即确定出由目标函数值f(X)到个体适应度F(X)的转换规则。第六步：设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法。第七步：确定遗传算法的有关运行参数，即确定出遗传算法的M、T、11 遗传算法的主要构造过程示意图10第二章 码方法在遗传算法中如何描述问题的可行解，即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称为编码。编码是应用遗传算法时要解决的主要问题，也是设计遗传算法的一个关键步骤。编码方法除了决定个体染色体排列形式之外，还决定了个体从搜索空间的基因型变换到解空间的表现型时的解码方法，编码方法也影响到交叉算子、变异算子等遗传算子的运算方法。针对一个具体问题，如何设计一个完美的编码方案一直是遗传算法的应用难点之一，也是遗传算法的一个重要研究方向。目前还没有一套既严密有完整的指导理论及评价准则能够指导我们设计编码方案。码原则一(有意义积木块编码原则):应使用能易于产生与所求问题相关的且具有低阶，短定义长度的编码方案。编码原则二(最小字符集编码原则):应使用能使问题得到自然表示或描述的具有最小字符集的编码方案。迄今为止人们已经提出了许多的编码方法，总的来说，可以分为三类：二进制编码方法，浮点数编码方法，符号编码方法。进制编码二进制编码方法是遗传算法中最常用的一种编码方法，它使用的编码符号集是由二进制符号0和0组成的二值符号集0，1，它所构成的个体基因型是一个二进制编码符号串。它有如下几个优点：(1)编码，解码简单易行。(2)交叉，变异等遗传操作便于实现。(3)符合最小字符集编码原则。(4)便于利用模式定理对算法进行理论分析。二进制编码符号串的长度与问题所要求的精度有关。由于二进制不便于反映所求问题的结构特征，对于一些连续函数的优化问题等，也由于遗传运算的随机特性而使得其局部搜索能力较差，因而人们提出了用格雷码来对个体进行编码。雷码编码格雷码，连续的两个整数所对应的编码值之间只有一个码位不相同。格雷码有这样一个特点：任意两个整数的差是这两个整数所对应的海明距离（这个特点是遗传算法中使用格雷码进行个体编码的主要原因。格雷码编码方法的主要优点是：(1)便于提高遗传算法的局部搜索能力。(2)交叉，变异等遗传操作易于实现。(3)符合最小字符集编码原则。(4)便于用模式定理对算法进行理论分析。假设一个二进制编码为B=对应的格雷码为G=雷码到二进制码的转换公式：格雷码编码方法是二进制编码方法的一种变形，其编码精度与相同长度二进制编码方法的精度相同。由于二进制编码存在着连续函数离散化时的映射误差，而且不便于反映所求问题的特定知识，因而人们提出了用符点数来对个体进行编码。点数编码符点数编码方法:指个体的每个基因值用某一范围内的一个浮点数来表示个体的编码长度等于其决策变量的个数，个体变量的长度等于去决策变量的真实值，所以也叫真值编码方法它有以下几个优点：(1)适合于在遗传算法中表示范围较大的数。(2)适合于精度较高的遗传算法。(3)便于较大空间的遗传搜索。(4)改善了遗传算法的复杂性，提高了运算效率。(5)便于遗传算法与经典优化方法的混合使用。(6)便于设计针对问题的专门知识的知识型遗传算子。(7)便于处理复杂的决策变量约束条件。符号编码方法是指个体染色体编码串中的基因值取自一个无数值含义，而只有代码含义的符号集它的主要优点如下：(1)符合有意义积木块编码原则。12(2)便于在遗传算法中利用所求解问题的专门知识。(3)便于遗传算法与相近似算法之间的混合使用。但对于使用符号编码方法的遗传算法，一般需要认真设计交叉、变异等遗传运算的操作方法，以满足问题的各种约束要求，这样才能提高算法的搜索性能。最后，简要介绍一下参数编码方法。数编码参数编码方法是对含有多个变量的个体进行编码的方法，包含两种编码方法：多参数级联编码方法：将各个参数分别以某种编码方法进行编码，然后再将它们的编码按一定顺序联接在一起就组成了表示全部参数的个体编码。多参数交叉编码方法：将各个参数中起主要作用的码位集中在一起。应度函数在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某个物种对其生存环境的适应程度。对生存环境适应程度较高的物种将有更多的繁殖机会；而对生存环境适应度较低的物种，其繁殖的机会就相对较少，甚至会逐渐灭绝。适应度较高的个体遗传到下一代的概率就相对大一些；而适应度较低的个体遗传到下一代的概率就相对较小一些。度量个体适应度的函数就称为适应度函数。根据个体的适应值，就可决定在此环境下的生存能力。个体适应度大小决定该个体被遗传到下一代群体中的概率。遗传算法仅使用所求问题的目标函数值就可以得到下一步的有关搜索信息。目标函数值的使用是通过评价个体适应度来体现的。由于个体适应度大小决定该个体被遗传到下一代群体中的概率。评价个体适应度的一般过程：(1)对个体编码串进行解码处理后，可得到个体的表现型。(2)由个体的表现型可计算出对应个体的目标函数值。(3)根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应度。但是，在仅用适应度函数来计算个体适应度时,有些遗传算法收敛很快,有些遗传算法收敛很慢，因此在运行到不同的阶段时须对个体的适应度进行适当的扩大或缩小。适应度尺度变换(对个体的适应度进行适当的扩大或缩小变换。个体适应度尺度变换的三种方法：线性尺度变换公式如下：13F=aF+适应度；F尺度变换后的新适应度；数。乘幂尺度变换公式如下：F=F 幂指数数尺度变换公式如下：F=F)系数决定了选择的强制性。择算子遗传算法中使用选择算子（也叫复制算子对群体中的个体进行优胜劣汰操作：适应度较高的个体被遗传到下一代的概率较大；适应度较低的个体被遗传到下一代的概率较小。遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群体中的一种遗传运算。选择操作建立在对个体的适应度进行评价的基础上。选择的主要目的为了避免基因缺失、提高全局收敛性和计算效率。有以下几种常用的选择算子的操作方法：比例选择、最优保存策略、确定式采样选择、无放回随机选择、无放回余数随机选择、排序选择和随机联赛选择等。最常用的几种选择策略有以下几种：(1)轮盘赌选择(体适应度按比例转换为选中概率，将轮盘分成生之间的随机数相当于转动以获得针停放在某一扇区，该扇区代表的个体被选中。概率越大所占转盘面积越大，被选中的机率越大。(2)最优保存策略选择(遗传算法的运行过程中，通过对个体进行交叉、变异等遗传操作而不断产生新的个体，虽然随着群体的进化过程会产生出越来越多的优良个体，但由于遗传操作的随机性，它们14也有可能破坏掉当前群体中适应度最好的个体。我们希望适应度最好的个体要尽可能的保存到下一代群体中，为达到这个目的我们使用最优保存策略进化模型。(3)排序选择方法（要思想是：对群体中的所有个体按其适应度大小进行排序，基于这个排序来分配各个个体被选中的概率。(4)比例选择(体被选中的概率与其适应度大小成正比。由于随机操作的原因，这种选择方法的选择误差较大，有时连适应度高的个体也选不上。(5)确定式采样选择（本思想是按照一种确定的方式进行选择操作。(6)无回放随机选择（据每个个体在下一代群体中的生存期望值来进行随机选择运算。(7)随机联赛选择(次选取几个适应度最高的一个个体遗传到下一代群体中。叉算子在生物的自然进化中，两个同源染色体通过交配而重组，形成新的染色体，从而产生新的个体或物种。模仿这个环节，在遗传算法中也使用交叉算子来产生新个体。交叉运算是指两个相互配对的染色体按某种方式交换其部分基因，从而形成新个体。交叉运算是遗传算法区别于其他进化算法的重要特征，在遗传算法中起关键作用，是产生新个体的主要方法。点交叉算子最常用的交叉算子是单点交叉算子。它是在个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。例如：以下两个个体在第四个基因座之后进行单点交叉运算，得到两个新个体：15单点交叉的重要特点是：若邻接基因座之间的关系能够提供较好的个体性状和较高的个体适应度的话，则单点交叉操作破坏这种个体性状和降低个体适应度的可能性最小。点交叉算子双点交叉(是指在个体编码串中随机设置了两个交叉点，然后进行部分基因交换。双点交叉的具体操作过程是：(1)在相互配对的两个个体编码中随机设置两个交叉点。(2)交换两个个体在所设定的两个交叉点之间的部分染色体。例如：以下两个个体在第二、四个基因座之间进行交叉运算，得到两个新个体：匀交叉算子均匀交叉(是指两个配对个体的每个基因座上的基因都以相同的交叉概率进行交换，从而形成两个新的个体。例如：以下两个个体进行交叉运算，得到两个新个体：分映射交叉(子整个交叉操作由两步来完成:首先对个体编码串进行常规的双点交叉操作。然后根据交叉区域内各个基因值之间的映射关系来修改交叉区域之外的各个基因座的基因值。交叉对象一般是符号编码表示的个体。例如：以下两个个体选取第三、六个基因座之后进行交叉运算，得到两个新个体：序交叉（子16主要思想：先进行常规的双点交叉，然后进行个体巡回顺序的有效顺序修改，修改时要尽量维持个点原有的相对访问顺序。例如:以下两个个体选取第三、六个基因座之后进行交叉运算，得到两个新个体：异算子在生物的遗传和自然进化中，其细胞分裂复制环节有可能会因为某些偶然因素的影响而产生一些复制差错，就会导致生物的某些基因发生某种变异，从而产生新的染色体，表现出新的生物性状。在遗传算法中的变异运算，是指将基因座上的基因值用该基因座的等位基因来替换，从而产生新个体。从遗传运算过程中产生新个体的能力方面来说，交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索能力；而变异运算只是产生新个体的辅助方法，但它也是一个必不可少的运算步骤，因为它决定了遗传算法的局部搜索能力。它们共同完成对搜索空间的全局搜索和局部搜索，使遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。变异算子有以下两个作用：(1)改善遗传算法的局部搜索能力。(2)维持群体多样性，防止早熟现象。较常用的基本位变异、均匀变异、边界变异、非均匀变异和高斯变异等。行参数在遗传算法中需要选择的运行参数主要有个体编码串长度l、群体大小M、交叉概率异概率终止代数T、代沟1) 编码串长度L。使用二进制编码时，编码串长度用浮点数编码时，编码串长度用符号变量来表示个体时。编码串长度外，也可以使用变长度的编码来表示个体。(2) 群体大小提高遗传算法的运算速度，却降低了群体的多样性，有可能会引起遗传算法早熟现象；而当会使得遗传算法的运行效率降低。一般的建议范围是20100。(3) 交叉概率叉操作是产生新个体的主要方法，一般应取较大值，但取值过大的话，它会破坏群体中的优良模式，对进化运算反而产生不利影响；取值过小的话，产生新个体的速度较慢。4)变异概率值较大，虽然能产生较多的新个体，但有可能破坏掉很多的较好模式，使得遗传算法的性能近似于随机搜索算法的性能；取值过大的话，则变异操作产生新个体的能力和抑制早熟的能力就差。5) 终止代数T。表示遗传算法运行到指定的进化代数之后就停止，并将当前群体中的最佳个体作为所求问题的最优解输出。一般为1001000。(6) 代沟G。表示每一代群体中被替换掉的个体中所占的百分率，即每一代中有(M束条件的处理方法主要有搜索空间限定法、可行解变换法、罚函数法。易看出遗传算法的流程可用下图进行描述：图2定一组找一条闭合的旅程，使得每个城市刚好经过一次而且总的旅行距离最短。言之就是寻找一条最短的遍历者说搜索整数子集X=1，2， ，n(一个排列(X)=v1，使T=d( vi，)+d(vi，最小值。式中的d(vi，)表示城市的距离。产生初始种群的方法通常有两种。一种是完全随机的方法产生，它适合与对问题的解无任何先验知识的情况。另一种是某些先验知识可转变为必须满足一组要求，然后在满足这些要求的解中再随机地选取样本。这样选择初始种群可使遗传算法更快地到达最优解。下面给出了 /*y;/*(;x=0;i jjiijjiix=0; p1;p1=p2;p2=i=; p1;p1=p2;p2=i=;i=; xi=(3)对换变异，随机选择串中的两点，交换其码值。 p1,p2;x=%(p1=%p2=%(1; p1;p1=p2;p2=xxxx(4)插入变异，从串中随机选择1个码，将此码插入随机选择的插入点之后。 p1,p2;x=%(p1=%p2=%(2; p1;p1=p2;p2=xi=p2;ip1;xi=x30x= 此外，对于变异操作还有一些变体形式，如9提出的贪心对换变异(其基本思想是从一个染色体中随机的选择两个城市(即两个码值)，然后交换它们，得到新的染色体，以旅程长度为依据比较交换后的染色体与原来的染色体的大小，保留旅程长度值小的染色体。谢胜利7等提出倒位变异算子，该算子是指在个体编码串中随机选择两个城市，是第一个城市的右边城市与第二个城市之间的编码倒序排列，从而产生一个新个体。例如，若有父个体P(145236)，假设随机选择的城市是4，3，那么产生的新个体为43256)。4等采用5方法的思想，提出了异算子。这种方法与贪心对换变异有相同的思想，但是更易扩张更有效率。2实验发现:当城市大小在200之内时，该变异算子可以大大改善程序的运行速度，随着城市数目的增加，尤其是当城市数目达到1000以上时，程序运行速度非常慢。传算法广泛的与其它算法相结合，产生许多混合遗传算法(王俊海8将出了一种基于这种算法应用于局部优化的高效性与遗传算法的鲁棒性很好的结合起了。2等提出一种解决法。8提出启发式算法(取得了很好的效果。第四章 试数据3110个点的,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,74,39,94,11,42,0 ,试结果（1）利用回溯算法对上述数据测试，求出54遗传算法求解4m=径长度 路径5 152 1，2，4，3，56 189 1，2，4，3，5，67 184 1，2，4，7，3，5，68 174 1，2，4，7，8，3，5，610 226 1，6，5，3，8，9，2，10，4，712 251 1，2，11，6，5，3，8，9，10，4，12，713 230 1，2，11，6，13，5，3，8，9，10，4，12，715 230 1，7，12，9，8，3，5，15，14，10，4，2，11，6，1317 222 1，2，16，14，15，5，3，8，9，17，11，6，13，10，4，12，719 203 17,12,4，10，19，3，5，15，14，16，2，11，17，9，8，18，6，1320 212 1,2,16,20,11,17，9，8，14，18，6，13，15，5，3，19，10，4，12，732运行最大代数 50代 100代所用方法 代数 权值 路径 代数 权值1 184 16537