基于遗传算法对TSP的实现及对四组遗传算子的比较.doc

内蒙古大学本科毕业论文(设计) 第 35 页1 绪论遗传算法是最近几十年来发展起来的新型优化方法，在六十年代末七十年代初主要由美国密歇根大学的John Holland教授与其同事、学生们共同研究形成了较完整的理论和方法，70年代De Jong基于遗传算法的思想在计算机上进行了大量的纯数值函数的优化计算实例，80年代由Goldberg归纳总结了一系列研究工作，形成了遗传算法的基本框架。目前人们已经将遗传算法和其他诸如模拟退火算法、贪婪算法、最速下降法等结合起来形成了混合遗传算法，使得对所求解的问题有更快的收敛速度和更强的鲁棒性。从20世纪90年代开始我国对遗传算法的研究处于升温时期，在最近的几年里也取得了举世瞩目的成绩。遗传算法的主要应用领域有函数优化、组合优化、生产调度、自动控制、机器人智能控制学、图像处理和模式识别、人工生命、遗传编程和机器学习。TSP是组合优化问题中的NP难问题，可能的路径数随着城市的数目的增大呈指数级增长，城市数目越大寻优路径的难度也就越大，到目前为止已经提出了许多种解法。本文基于遗传算法对对称旅行商问题进行求解，并对各种实现方法进行对比讨论。全文包括遗传算法概述、基于遗传算法对TSP的实现及对四组遗传算子的比较、总结等几大部分组成。在遗传算法概述部分简单介绍了遗传算法的机理、各种不同的编码方法、适应度函数和遗传操作，在基于遗传算法对TSP的实现及对四组遗传算子的比较部分首先对TSP作了简要概述，然后介绍了常用的编码方法、适应度函数的确定和针对TSP的遗传算子的设计，接着阐述了实现部分匹配交叉法时需要注意的问题和新设计的交叉算子类贪婪交叉算子，最后对四种实现方法的结果进行对比评价。总结部分对全文的内容进行了总结并指出了文章的不足之处。2 遗传算法概述遗传算法是通过模拟生物在自然环境中遗传和进化的过程而形成的一种自适应的全局优化概率搜索算法，借鉴生物学遗传机制，模仿进化过程中的选择、交叉和变异机理，以群体的方法进行自适应搜索，找到目标空间中的近似最优解或满意解。遗传算法是一个迭代求解的过程，首先初始化当前种群，然后从当前种群中按照某种机制选择适量个体进行遗传操作，在产生新一代种群后找到当前种群中的最佳个体，然后将新产生的种群作为当前种群，继续以上操作，直到满足某种终止条件为止。2.1遗传算法的数学基础首先引入模式（schema）的概念。模式是一个描述字符串集的模板，该字符串集中串的某些位置上存在相似性。一个串中可以隐藏多个模式，一个模式可以隐藏在多个串中，不同的字符串之间通过模式相互联系，所以说遗传算法中串的运算实质上是模式的运算。例如二进制编码中字符集为，*是通配符，可以是0或1，0*10*1*则表示一种模式。模式阶是指模式中确定的位置的个数，定义距指的是模式中第一个确定位置和最后一个确定位置之间的距离。比如编码为0*10*1*表示的模式，它的阶为4，定义距为10。模式定理：在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距和平均适应度高于群体平均适应度的模式在子代中将以指数级增长。我们把低阶、短定义距以及高适应度的模式叫做积木块。由此引出积木块假设。积木块假设：积木块在遗传算子的作用下相互结合能生成高阶、长定义距、高平均适应度的模式，可最终生成全局最优解。模式定理保证了较优模式的样本数呈指数级增长，从而满足了寻找最优解的必要条件，即遗传算法存在找到最优解的可能性，而积木块假设指出了遗传算法具备找到全局最优解的能力。2.2 遗传算法的运算过程遗传算法是通过模仿生物学中遗传和进化的机理完成对问题域中最优解的搜索。首先对目标问题进行编码，编码是表现型到基因型的映射，而遗传算法的实现基础是基因，因此需要将问题域转换成基因空间；其次确定种群大小和适应度函数，种群中的合法个体在解码后其表现型满足目标问题的约束条件，算法在迭代的种群中逐步搜索目标问题的最优解或满意解，因此最优解或满意解经过有限次迭代后一定可以找到，适应度函数是用来评价优良个体的依据，适应度高的个体得以保留，适应度低的个体被淘汰掉；再次随机产生初始种群，产生初始种群时要确保个体的合法性约束，算法从初始种群开始对种群中的每个个体执行遗传操作；基本遗传算子包括选择算子、交叉算子和变异算子，选择算子以个体的适应度为标准来决定哪些个体是否能够保留，交叉和变异算子是产生新一代种群的关键遗传算子，随机确定交叉点和变异点在编码串中的位置，可以产生新个体从而使种群进化逐步逼近最优解或满意解；最后确定中止代数，即达到什么条件终止算法的执行。因为算法是在计算机上执行的，而计算机要求一定的精度，因此目标函数的最优解无法达到理论上的数值，而是一个接近最优解的近似值，所以确定终止代数是必要的，最后逐个解码个体并输出适应度最大的个体的表现型，即为满意解。算法结束。图一是遗传算法的流程图，通过流程图我们可以了解遗传算法的执行过程。 图一 基本遗传算法流程图2.3 遗传算法的手工描述为了对遗传算法的执行过程有一个更清楚的了解，我们通过一个手工演算的例子来说明。以二元函数为例。假设群体中的个体数为4，序号分别为1，2，3，4。编码时对目标函数的两个未知量分别用二位二进制数编码，则整个染色体的长度是4，初始种群P(0)代用随机方法产生，由于问题域以及采用二进制编码，因此随机产生的初始种群不会脱离约束范围，即产生的个体均为合法个体。在产生新种群后计算四个个体的适应度，这里以目标函数值作为适应度值。在执行选择操作时运用轮盘赌选择法，比例度量以个体适应度与总适应度的比值，高适应度的个体遗传到下一代的几率大。选择操作结束后随机确定配对情况，之后我们进行单点交叉，交叉点以交叉概率随机选取，变异操作采用基本位变异，同样以变异概率选择变异点，之后产生的新种群即为下一代种群。算法终止条件是到最大进化代数为止。为方便起见算例中仅进行一次遗传操作，在表一中可以看到在新产生的种群中已出现了目标函数的最优解的基因型，通过解码即可得到目标函数的最优解。个体P(0)代累积适应度选择次数选择结果配对情况112011055/285/28101101-3203001199/281/21001132310111313/2827/28210112-4401000111/28101011交叉点交叉结果变异点变异结果P(1)代1-3：20111111111111331010211101110322-4：3001130001000101101141010101022表一 手工进行的遗传算法示意表2.4 遗传算法的特点相对于其他优化算法，遗传算法有下列一些特点。（1）自组织、自适应、自学习性和概率性。在应用遗传算法时给定了编码方法、适应度函数以及遗传算子后，算法将利用进化过程中获取的信息自行组织搜索。这种搜索方法是一种基于概率的搜索技术，其选择、交叉、变异运算都是以一种概率的方式来进行的，从而增加了搜索过程的灵活性。随着进化过程的进行，新的群体中总会产生出许多优良的个体。 （2）隐并行性。遗传算法同时使用一个群体中多个个体的搜索信息开始最优解的搜索，而不是从一个单一的个体开始搜索，经过对群体的选择、交叉、变异操作后，产生出新的群体，这样群体中包含了更多的群体信息，这是遗传算法的内含并行性。另一种是遗传算法的内在并行性，即遗传算法适合大规模的并行，可以让数千台计算机各自孤立进行运算，运行过程中不需要信息交换，等到运算结束后才进行通信比较，选取最佳个体。（3）遗传算法直接使用由目标函数变换得到的适应度函数作为搜索标准，就可以确定进一步的搜索方向和搜索范围，不需要目标函数的导数等辅助信息，这给很多目标函数无法求导或很难求导的、或导数不存在的函数优化问题，以及组合优化问题带来了方便。（4）遗传算法以决策变量的编码作为运算对象，通过借鉴生物学中染色体和基因等概念来模仿生物的遗传和进化机理，可以方便地进行遗传算子的操作，特别是对无数值或很难有数值概念的优化问题，编码处理更显现出优越性，同时遗传算法靠编码和交叉算子的使用才能保证种群的进化。2.5 遗传算法的实现2.5.1 编码遗传算法的一个重要特点就是在算法的运行过程中不对所求问题的实际决策变量直接进行操作，而是对表示可行解的个体基因型的编码进行遗传操作。编码与交叉操作共同决定了遗传算法的结构。编码是把一个问题的可行解从其解空间转化到遗传算法所能处理的搜索空间的一种转化方法，编码同时决定了解码，好的编码方法直接影响算法的执行效率。目前有许多种编码方法，例如二进制编码、符号编码、浮点数编码、格雷码编码、多参数级联编码、多参数交叉编码、DNA编码等。在对实际问题进行编码时我们应根据问题的不同情况选择不同的编码方法。De Jong提出了两条编码原则：一是有意义积木块编码原则，即应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案，二是最小字符集编码原则，即应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案，比如二进制编码。2.5.1.1 二进制编码法 二进制编码是最基本的编码方法，编码符号集是由0和1组成的二值符号集0，1。个体基因型是一个二进制符号串。问题所要求的精度决定了串的长度。假设某一参数的取值范围是，用表示二进制串即染色体的长度，则它可以产生种不同的编码，用表示问题要求的精度，参数编码对应关系为：，则编码精度。假设某一个个体的编码为，其中，则对应的解码公式为。解码是将编码串的值转化为约束变量的值的过程，利用解码公式可以确定目标函数的值。 2.5.1.2 浮点数编码法二进制编码在将连续函数离散化时存在映射误差，所以提出了浮点数编码法。浮点数编码方法是指个体的基因型用某一范围的一个浮点数表示的方法，个体编码长度等于决策变量的个数。例如基因：3.152.487.328.8914.23 其中每个变量的区间为，那么目标问题有4个决策变量，的表现型为。使用浮点数编码法时要保证基因值在区间范围内，而且在进行交叉和变异等遗传操作时要保证产生的新个体也在问题的约束域内。 2.5.1.3 符号编码法符号编码法是指将个体编码串的基因值用一些无数值含义只有代码含义的符号集表示的方法，符号集的元素可以是字母、数字或者代码等。在旅行商问题中，对个城市的序号进行排列得到的染色体即为一种符号编码串，它表示一条可行路径。假如对4个城市的一条路线为，那么染色体编码串为或者。2.5.2 适应度函数适应度函数是个体空间到正实数空间的映射，即，其中代表个体空间，代表正实数空间。适应度是衡量种群中个体优劣的重要指标，如果该个体在种群中的适应度越高，则它适应环境的能力就越强，那么遗传到下一代的概率也就越大。遗传算法在进化搜索过程中以适应度函数为依据在种群中选择要进行交叉和变异等遗传操作的两个父个体，比如常用的轮盘赌选择法。一般情况下适应度函数由目标函数变换得到。如果直接由目标函数变换得到的适应度值出现负值或者不符合条件的情况时，可以通过适应度函数的线性变换法、幂函数变换法或指数变换法等进行尺度变换，这种变换方法也叫定标。在实际应用中可以根据具体问题灵活定义适应度函数。2.5.3 遗传算子基本的遗传算子包括选择算子、交叉算子和变异算子。现在还有很多新型的遗传算子，如显性操作算子、倒位算子等。2.5.3.1 选择算子选择操作就是在一个种群中选择一个个体的过程，用映射的形式可以表示为 ，其中是种群空间，由个个体组成，是个体空间。选择操作在种群中选择个体时需要以适应度作为选择标准，然后以一定的选择概率进行选择操作。在确定选择概率的分配时，常用的方法有两种：按比例的适应度分配和基于排序的适应度分配。按比例的适应度分配是以各个个体的适应度与总适应度的比例作为选择概率决定个体的生存可能性。若个体的适应度为，则被选中的概率为，其中为种群大小。基于排序的适应度分配是按照适应度进行排序，仅按照个体在群体中的序位进行选择。常用的选择方法有轮盘赌选择法、随机遍历抽样法等。（1）轮盘赌选择法轮盘赌选择法是一种最简单的选择方法。首先需要计算种群的总适应度，然后计算各个体的适应度，那么个体被选中的概率，个体累积概率为。在选择时首先产生一个的随机数，然后与累积概率比较，若，则选中第个个体。从图二中的例子中我们可以清楚地了解轮盘赌选择法的过程。图二 轮盘赌选择法（2）随机遍历抽样法 假设需要选择个个体，随机遍历抽样法是根据累积适应度选择指针等距离地移动来选择个个体，选择指针移动的距离为，初始指针的位置由之间的随机数确定，选择指针从初始指针开始依次选择个个体。图三表示了这一过程。图三 随机遍历抽样法2.5.3.2 交叉算子遗传算法中的交叉操作是指两个相互配对的父个体按照某种方式交换部分基因，从而形成两个子个体的过程，用映射形式表示为父个体空间到子个体空间的映射，表示父个体空间，由一对父个体组成，表示子个体空间。交叉操作是遗传算法的核心操作，是遗传算法区别于其他进化算法的重要特征。遗传算法强调交叉的作用，可行解的进化主要靠选择机制和交叉策略来完成。下面以二进制编码为例，简单介绍几种交叉算子。（1）单点交叉单点交叉是指在两个父染色体上随机选择一个介于之间的交叉点，是染色体的长度，交换两个父染色体位于交叉点之后的基因段。图四是一个二进制编码单点交叉的例子，交叉点选择在第五个基因座之后，两个父染色体交换交叉点之后的基因段。图四 单点交叉（2）双点交叉与多点交叉双点交叉是指随机选择两个介于之间的交叉点，然后交换两个父染色体位于两个交叉点之间的基因段，从而形成两个子染色体。图五以二进制编码说明了双点交叉的过程，交叉点选择在第五个基因座和第十个基因座之后，两个父染色体相互交换两个交叉点之间的基因。图五 双点交叉多点交叉是双点交叉的推广，首先随机选择介于之间的多个不重复的交叉点，间序地交换两个父个体之间的基因。图六以四点交叉为例说明了多点交叉的过程，交叉点选择在第二、五、七和十个基因座之后，然后交换两个父个体位于第一和第二个交叉点之间、第三和第四个交叉点之间的基因。图六 四点交叉（3）均匀交叉均匀交叉是指将每个基因都作为潜在的交叉点，首先随机地产生两个与个体染色体等长的掩码样本，根据掩码样本确定两个子个体。图七以二进制编码下的符号串为例说明了均匀交叉的过程。掩码样本中1代表父个体1提供基因，0代表父个体2提供基因，随机产生两个掩码样本为样本一 1 0 1 1 0 1 0 0 1 1 0 1 0样本二 0 1 1 0 1 0 0 1 0 1 1 0 0则均匀交叉产生的结果为图七 均匀交叉2.5.3.3 变异算子遗传算法中的变异运算是指将个体染色体上的某些基因用与之等位的其他基因代替的过程。变异算子定义为个体空间到个体空间的一种映射，是个体空间。变异为选择、交叉中可能丢失的某些遗传基因进行修复和补充，在全局意义上只是一个背景操作，本身是一种局部随机搜索方法，保证了遗传算法具有局部随机搜索的能力，同时维持了种群的多样性，防止出现未成熟收敛现象。（1）二进制编码下的基本位变异 基本位变异是指染色体上某一个或某几个基因发生变异的过程，即用等位基因替换原始基因。图八所示为两个基因发生变异的情况，分别在第9和12号基因发生变异，用等位基因替换之。图八 基本位变异（2）实值编码下的均匀变异均匀变异是指依次把每一个基因都作为变异点，对每一个变异点以变异概率从基因的取值范围内取一随机数替代原始基因值。假设一个体的染色体为，为变异点，其取值范围为，则变异点变异后的新基因值为，其中为符合均匀分布的介于之间的随机数，得到的新个体为。2.5.4 运行参数遗传算法的运行参数主要包括群体规模、最大进化代数、交叉概率、变异概率，个体染色体长度。通常交叉概率设置在0.20.99之间，变异概率设置在0.0010.1之间。染色体长度随编码方法的不同而不同，二进制编码下的染色体长度需要根据问题变量要求的精度来确定，实值编码下的染色体长度与变量个数相同，符号编码下的长度依编码方式而定，例如旅行商问题中染色体长度与遍访的城市个数相同。群体规模即为种群大小，设置的数值较小时算法运行快，但降低了群体的多样性，而当群体规模太大时会降低运行效率。最大进化代数是终止算法的条件，当达到最大进化代数时停止迭代产生新种群并输出进化过程中找到的最佳个体。3 基于遗传算法对TSP的实现及对四组遗传算子的比较3.1 TSP概述3.1.1 TSP旅行商问题（Traveling Sales Problem，TSP）可描述为已知n个城市以及它们的坐标，现有一个推销员必须遍历所有城市，而且每个城市只能访问一次，最后必须返回到出发城市，问题是如何安排他对这些城市的访问顺序，使得其旅行总路线最短。TSP是NP完全问题，存在的路径条数随着城市数目n的增大呈指数级增长。TSP用图来说明为在图中，每条边上有非负权值，寻找图中存在的哈密顿圈，使得的总权值最小。旅行商问题的实际模型在印刷电路板的钻孔路线方案、连锁店的货物配送、网络布线等优化问题中有着广泛的应用，长期吸引着众多学者的研究，目前归纳起来有多种解法，如近似解法、局部搜索算法、神经网络、遗传算法、克隆算法、模拟退火算法、混合遗传算法等。本文基于遗传算法针对对称旅行商问题给出实现算法。对称旅行商问题是指对于任意两个城市，它们之间的路径，满足。3.1.2 编码方法对于TSP常用的编码方法有两种，一种是基于城市序号的自然编码法，另一种是顺序编码法。（1）基于城市序号的自然编码法自然编码法，即符号编码法，是用城市序号的顺序排列进行编码的方法。比如有5个城市，序号分别为1，2，3，4，5，则编码串为24531的染色体表示路径2-4-5-3-1-2，即从第二个城市出发，沿途经过第4，5，3，1号城市，最后回到第二个城市。（2）顺序编码法Grefenstette等针对TSP于1985年提出了基于顺序表示的编码方法。顺序编码算法为：（一）将所有城市排列构成一个顺序表并记录每一个城市在顺序表中的位置；（二）将染色体设置为空；（三）对于某一条实际路径，从其上的第一个城市开始直到最后一个城市为止重复以下操作：找到该城市在顺序表中的位置，将该城市在顺序表中的位置顺序地加入到染色体中，处理完该城市后在顺序表中删除该城市，重新计算剩余的城市在顺序表中的位置。比如有六个城市，它们的序号为1，2，3，4，5，6，构造顺序表为O=（1，2，3，4，5，6），即第一个城市在顺序表中的位置为1，第二个城市在顺序表中的位置为2，第六个城市在顺序表中的位置为6。对于编码为的染色体表示的路径为,运算过程为。3.1.3 适应度函数在TSP中每一条染色体都代表一条可行路径，路径的总长度为，其中表示这条路径上的第个城市到第个城市的距离，而适应度越高的个体其路径总长度越小，所以通常以定义为个体的适应度。但在实际问题中路径总长度的数值可能很大，计算后得到的适应度数值很小，而且种群中个体的适应度相差不大，为了使种群中较优的个体被选择遗传到下一代的几率增大大，需要对适应度函数做尺度变换。程序中我们定义个体的适应度为基于排序的适应度，具体的做法是首先将种群中的个体按路径长度从小到大排序，然后定义第个个体的适应度为，其中，程序中将设置为，为个体在种群中排序后的序号，是介于的整数，为排序后第个个体的路径长度。通过上述对个体适应度函数的定义可以使路径长度较小的个体的适应度与路径长度较大的个体的适应度相差很大，那么路径长度较小的个体被选择的几率较大，保证了算法收敛到全局最优解或满意解的可能性。3.1.4 选择方法在TSP求解中传统的选择方法是轮盘赌选择法。对各条路径编码后依次计算种群中各个个体的适应度以及累积适应度，然后随机产生一个的随机数，根据累积适应度与的大小选择合适的个体作为下一代的父个体。适应度大的个体被选择到下一代的几率就大。3.1.5 交叉方法针对TSP传统的交叉方法有顺序交叉法、部分匹配交叉法和循环交叉法。（1） 顺序交叉法OX顺序交叉法是Davis于1985年提出的，它是基于自然编码的一种交叉技术。这种交叉操作的主要思想是先随机选择两个交叉点构成交叉区域，将两个父个体的交叉区域分别复制到两个子个体的对应区域处，然后将子个体交叉区域外的基因用通配符表示。对第一个子个体而言，从第二个交叉点后开始顺序排列第二个父个体的基因码，当到达第二个父个体的染色体最后一个基因座时接着从第一个基因座顺序排列基因码，直到第二个交叉点处为止，这样得到一条由基因码的排列构成的路径，然后再将第一个父个体交叉区域内的基因码与这条路径比较，将这条路径中与第一个父个体交叉区域内相同的基因删除，删除完成后将这条路径复制到第一个子个体中，同样从第二个交叉点后开始，顺序排列到染色体最后一个基因，接着从第一个基因开始排列直到第二个交叉点为止，这样就得到了第一个子个体。第二个子个体的产生与第一个子个体的产生相同，只是它的未确定的基因是从第一个父个体的第二个交叉点后开始选取的，然后删除与第二个父个体交叉区域内相同的基因。例如，两个父个体为 ，交叉点分别随机选择在第二和第五个基因座之后，那么两个子个体为，*表示暂时未确定的基因。对于，从父个体中选取位于第五个基因座之后的基因得到路径，然后将与位于交叉区域中的基因比较，删除相同的基因，得到新路径为，将复制到子个体中，仍从第五个基因后开始得到子个体为。对于，从父个体中选取基因得到路径，将与位于交叉区域中的基因比较，删除相同的基因，得到新的路径为，将复制到子个体中，从第五个基因后开始得到子个体为。（2）部分匹配交叉法PMX部分匹配交叉法是Goldberg于1985年提出的基于自然编码的交叉方法。它的基本思想是随机选择两个交叉点，将两个父个体交叉区域中的基因构成一组映射，首先交换两个父个体交叉区域中的基因生成初始的子个体，然后将子个体交叉区域外与交叉区域内相同的基因用映射后的基因替换掉，最终使子染色体上的每一个基因都不同。比如，两个父个体为 ，交叉点分别随机选在第二和第五个基因座之后，两个初始的子个体为。对于交叉区域中的基因有映射关系、，此后将子个体交叉区域外与交叉区域中相同的基因用映射后的基因替换掉得到子个体为。（3）循环交叉法CX循环交叉法是由Oliver等人于1987年提出的。这种交叉法中子个体的基因根据任一父个体产生。比如两个父个体为 ，先将两个子个体、的第一个基因取自父个体、的第一个基因得到子个体为。对于子个体，父个体与子个体第一个基因对应的基因是3，而父个体的第三个基因是3，所以决定的第三个基因为3，即，接着基因3对应的基因6，而父个体的第六个基因是6，决定了的第六个基因为6，即，基因6对应的基因1，而子个体的基因1已经确定，这样构成了一个循环，对于中未确定的基因，用父个体对应位置的基因替换，这样得到子个体为。对于子个体，运用同样的构造过程，基因3对应的基因1，而父个体的第六个基因为1，决定的第六个基因为1，即，基因1对应的基因6，而父个体的第三个基因为6，决定的第三个基因为6，即，基因6对应的基因3，而的第一个基因3已确定，完成了一个循环，中未确定的基因用父个体对应的基因产生，这样得到子个体为。3.1.6 变异方法针对TSP传统的变异方法有位点变异、逆转变异、对换变异和随机插入变异。 （1）位点变异位点变异是指对染色体的某一基因用其对等基因替换的现象，在TSP中位点变异可用于基于顺序编码的染色体。顺序编码下表示的路径是基于顺序表的，每个基因值可以重复出现，所以执行位点变异操作后仍能表示一条合法的路径，只是对等基因的值只能从一定范围中取值。（2）逆转变异逆转变异是指在染色体上随机选择两个变异点，将两个变异点之间的基因按原来相反的次序进行排列从而产生一条新的染色体。比如在选择第二和第六个基因座为变异点后产生的新个体为。（3）对换变异对换变异是指在染色体上随机选择两个变异点，然后将这两个基因进行对换从而产生新个体。比如在选择第二和第六个基因座为变异点后产生的新个体为。（4）随机插入变异随机插入变异是指在染色体上随机选择两个变异点，将其中一个基因插入到另一个基因座后，从而产生新的个体。比如在选择第二和第六个基因座为变异点后将第六个基因插入到第二个基因之后产生的新个体为。3.2 基于遗传算法对TSP实现的方法3.2.1实现算法实现TSP的算法可表述为：第一步：定义基因、染色体、个体、最佳个体群、最差个体群和种群的变量类型，打开城市坐标文件和统计结果输出的磁盘文件；第二步：初始化。包括输入控制参数（种群大小、染色体长度、交叉概率、变异概率、最大进化代数、随机数种子），对各种变量类型分配内存，初始化种群；第三步：统计并输出当前种群中的最佳个体群和最差个体群，即最佳路径和最差路径；第四步：遗传操作，包括从当前种群选择个体，进行交叉和变异操作，产生新一代种群；第五步：用新一代种群替代当前种群，返回第三步，直到达到最大进化代数为止停止搜索。3.2.2 数据结构本文的程序用C语言实现。程序中用自然编码法对路径进行编码，即用城市序号的全排列编码为染色体，染色体上的每一个基因对应于一个城市的信息，包括城市的序号和二维坐标值，染色体的长度即为所求城市的个数。个体的适应度是基于排序的，第个个体的适应度为，设置为0.5，为个体在种群中排序后的序号，是介于的整数，为排序后第个个体的路径长度。选择操作用轮盘赌选择法实现。在程序中基因（gene）是由城市序号和二维实数坐标值构成的结构体，染色体是由基因构成的数组，个体（individual）定义为由染色体、适应度、路径总距离、交叉位置、变异位置和两个父个体构成的结构体，当前种群（old population）和新产生的种群（new population）是由个体构成的数组，数组长度即为种群规模（population size），在程序的统计输出中记录由最佳个体构成的最佳个体群和由最差个体构成的最差个体群，最佳个体和最差个体是由染色体、适应度、路径总距离和当前进化代数构成的结构体，最佳个体群和最差个体群分别是由最佳个体和最差个体构成的数组。它们之间的构成关系为图九 数据结构关系图数据结构定义为struct gene /*基因*/ int cityno; /*城市序号*/ double xcoordinate,ycoordinate; /*城市位置坐标*/;struct individual /*个体*/ struct gene *chrom; /*染色体*/ double fitness; /*个体适应度*/ double totaldistance; /*路径总长度*/ int xcross,ycross; /*交叉位置*/ int xmutation,ymutation; /*变异位置*/ int parent2; /*父个体*/;struct bestever /*最佳个体*/ struct gene *chrom; /*最佳个体染色体*/ double fitness; /*最佳个体适应度*/ double totaldistance; /*最佳个体的路径总长度*/ int generation; /*最佳个体生成代*/;struct worstever /*最差个体*/ struct gene *chrom; /*最差个体染色体*/ double fitness; /*最差个体适应度*/ double totaldistance; /*最差个体的路径总长度*/ int generation; /*最差个体生成代*/;3.2.3 实现方法程序中我们着重设计了不同的交叉算子和变异算子来实现TSP，主要有四组实现方法，分别为部分匹配交叉法+对换变异法（PMX+EM）、部分匹配交叉法+逆转变异法（PMX+RM）、类贪婪交叉法+对换变异法(SGX+EM)和类贪婪交叉法+逆转变异法(SGX+RM)。3.2.3.1实现部分匹配交叉法时需要注意的问题在随机选择两个交叉点后，两条父染色体上在由两个交叉点确定的交叉区域之间基因的映射关系可能存在一对多的情形，即一个基因可能对应多个其他的等位基因。这时在交换两个父染色体的交叉区域之后形成的两个初始子染色体中，在将交叉区域外的基因和交叉区域内的基因进行比较并用映射的基因替换相同基因的过程中，需要多次比较替换。当比较替换一次后，由于是一对多的映射关系，一次替换后在交叉区域外仍然会有重复的基因，因此需要进行第二次比较替换过程，如此下去直到整条染色体中没有重复的基因为止。具体的部分匹配交叉算法C源程序见附录A。我们从下面的两个例子中可以归纳出需要进行比较替换的次数。图十所示为有五个基因的染色体，两条父染色体分别为和，交叉点选在第二个和第四个基因座之后，交叉区域中