毕业论文普通遗传算法与佳点集遗传算法的研究

PAGE1PAGE3目录摘要 1关键词 1引言 11遗传算法概论 11．1遗传算法的历史和研究现状 11．2遗传算法的基本原理 31．2．1遗传算法基本概念 31．2．2遗传算法基本原理 31．2．3遗传算法的特点 32普通遗传算法 42．1普通遗传遗传算法思想 42．2普通遗传算法的遗传操作 42．2．1选择（selection）操作 42．2．2交叉(crossover)操作 42．2．3变异(mutation)操作 54遗传算法在TSP问题上的应用 84．1TSP问题概述 84．2遗传算法求解TSP问题 84．2．1编码与解码 84．2．2初始化种群 94．2．3适应度函数 94．2．4选择算子 104．2．5交叉算子 104．2．6变异算子 154．2．7停止准则 155TSP问题的实验结果及分析 155．1普通遗传算法与佳点集遗传算法的比较与分析 155．1．1最优解分析 155．1．2算法收敛速度分析 175．1．3算法运行时间分析 18总结 18致谢 18参考文献 19Abstract 19Keywords 19遗传算法在TSP问题上的应用摘要：遗传算法(GA)模拟自然进化机制，在搜索优化问题全局或全局附近的最优解上具有较好的鲁棒性、内在的并行性和较优越的稳定性，因而在诸如组合优化、图像处理等方面有着广泛的应用。但是传统的遗传算法性能很大程度上依赖于相关参数的取值与算子的作用方式，佳点集遗传算法利用数论中的佳点集理论和方法，来改进普通遗传算法中的各相关算子，以期克服普通遗传算法收敛速度慢，易陷入局部最优的弱点。本文在分析普通遗传算法和佳点集遗传算法机理上，利用JAVA语言实现了佳点集算法演示系统，通过选取不同的遗传算子来对标准TSP的数据集中的大量数据进行了对比分析和验证。我们的实验结果表明对于较大规模的TSP组合问题佳点集的优势是非常明显的。关键词：Tsp问题；普通遗传算法；佳点集遗传算法；单切点交叉算子；双切点交叉算子；循环交叉算子；佳点集交叉算子；引言遗传算法GeneticAlgorithm（GA）是由美国密歇根大学的JohnH.Holland教授及其学生于20世纪60年代末到70年代初提出的。它是以达尔文的自然进化论“适者生存、优胜劣汰”和孟德尔遗传变异理论为基础，模拟生物进化过程。它具有大范围快速全局搜索能力，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求的最优解。正是遗传算法的诸多特点，使得它在求解组合优化、机器学习、并行处理等问题上得到了广泛的应用。普通遗传算法是通过模拟染色体群的选择、交叉和变异等操作，不断迭代，最终收敛到高适应度值的染色体，从而求得问题的最优解。但是随着问题规模的扩大，组合优化问题的搜索空间急剧扩大，普通遗传算法的收敛速度慢、易陷入局部最优的缺点就暴露了。而佳点集遗传算法正是通过佳点集的方法改进交叉算子，加快算法收敛到全局最优解的速度，降低发生早熟的概率，提高整个算法的计算效率。1遗传算法概论1．1遗传算法的历史和研究现状早在1967年Bagley和Rosenberg就提出了生物遗传算法(GA)的初步思想，1975年由美国Michigan大学的JohnHolland的出色工作奠定了遗传学算法的理论基础，遗传变异和优胜劣汰现象的优化搜索算法付诸了实际应用，这也标志着遗传算法的诞生。到了80年代初期，Holland的一些学生的毕业论文中对遗传算法的应用以及在应用中遇到的问题进行了研究，其中有Delong(1975)对GA的各种策略的性能和机理进行了大量的细致分析与实验。与此同时Holland还给出了一个自适应的规则学习系统，并于1980年成功地实现了这一学习系统，Holland及其学生的研究成果使得人们开始看到了GA的应用价值。1981年Betake的博士论文中提出了用Walsh函数来研究遗传算法的方法，Alberta大学的Brindle在其博士论文中开始对选择策略进行了研究，这一时期的研究回答了GA算法的到底有何意义，有何价值。也正是他们的研究使得更多的人把目光投向了遗传算法，1985年召开了第一届GA国际会议，至此以后每两年召开一次。80年代中期，遗传算法广泛的应用于许多的应用领域，如TSP问题、调度问题、机器学习、模式分类问题，囚徒困境问题以及多关节机械手轨迹规划问题。1989年D.J.Goldberg总结了遗传算法的主要成果，全面论述了遗传学的基本原理极其应用，奠定了现代GA的科学基础。进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不仅它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。1991年D.Whitey在他的论文中提出了基于领域交叉的交叉算子（Adjacencybasedcrossover），这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了TSP问题中，通过实验对其进行了验证。D.H.Ackley等提出了随机迭代遗传爬山法（StochasticIteratedGeneticHill-climbing，SIGH）采用了一种复杂的概率选举机制，此机制中由m个“投票者”来共同决定新个体的值（m表示群体的大小）。实验结果表明，SIGH与单点交叉、均匀交叉的神经遗传算法相比，所测试的六个函数中有四个表现出更好的性能，而且总体来讲，SIGH比现存的许多算法在求解速度方面更有竞争力。H.Bersini和G.Seront将遗传算法与单一方法（simplexmethod）结合起来，形成了一种叫单一操作的多亲交叉算子（simplexcrossover），该算子在根据两个母体以及一个额外的个体产生新个体，事实上他的交叉结果与对三个个体用选举交叉产生的结果一致。同时，文献还将三者交叉算子与点交叉、均匀交叉做了比较，结果表明，三者交叉算子比其余两个有更好的性能。近年来，国内也有不少的专家和学者对遗传算法的交叉算子进行改进。2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优解问题2004年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现象，提出了一种用基因块编码的并行遗传算法（Building-blockCodedParallelGA，BCPGA）。该方法以粗粒度并行遗传算法为基本框架，在染色体群体中识别出可能的基因块，然后用基因块作为新的基因单位对染色体重新编码，产生长度较短的染色体，在用重新编码的染色体群体作为下一轮以相同方式演化的初始群体。2005年，江雷等针对并行遗传算法求解TSP问题,探讨了使用弹性策略来维持群体的多样性,使得算法跨过局部收敛的障碍,向全局最优解方向进化。总之人们对遗传算法的研究主要可以概括为以下三个方面：遗传算法搜索在进化到一定的程度就往往会使得种群的适应度趋向于相同，这样似的种群间的概率变的非常接近，这时的选择和复制策略接近于纯随机的抽样过程，使得搜索的收敛速度比较慢，针对这一问题，人们提出了不同的选择和复制策略。遗传算法的收敛性研究。主要结果是典型的GA不会收敛到全局最优，对于保留精英(elitismselection)的选择策略，GA能收敛到全局最优。尽管这一结论说明了改进的GA最终能收敛到全局最优解，但收敛到最优解的时间可能很长。遗传算法收敛性能的研究，普通的遗传算法搜索的局部性而往往不能全局最优，针对这一问题人们采用设计合适的交叉算子和变异算子来解决。而本文要实现的基于佳点集的遗传算法就是通过设计合适的交叉算子来解决收敛速度和收敛性能的问题的。关于遗传算法收敛性能的研究，到目前为止还没有肯定的结论哪一种方法的遗传算法性能绝对最优，对于遗传算法的性能往往是问题不同，得到的结论也不同。1．2遗传算法的基本原理1．2．1遗传算法基本概念种群(population)：染色体带有特征的个体的集合称为种群。该集合内个体数称为群体的大小。个体(individual)：指染色体带有特征的实体。种群大小(populationsize):种群中个体数目称为群体大小。适应度(fitness)：各个个体对环境的适应程度叫做适应度(fitness)。适应度函数（fitnessfunction）：为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数，适应度函数是计算个体在群体中被使用的概率。遗传操作（geneticoperator）：遗传算法中有三种关于染色体的运算：选择、交叉和变异，这三种运算被称为遗传操作。交叉率：交叉运算的染色体个数占全体染色体总数的比例，取值范围一般为0.4~0.99。变异率：参加发生变异的基因位数所占全体染色体的基因总位数的比例，取值范围一般为0.0001~0.1,这里主要是参考了计算机毕业设计网上的文章。1．2．2遗传算法基本原理遗传算法[10]GA把问题的解表示成“染色体”，在算法中也即是以二进制编码或实数编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，设定相应的适应度函数，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，得到问题的最优解。1．2．3遗传算法的特点遗传算法GA利用了生物进化和遗传的思想，所以它有许多与传统的优化方法不同的特点(1)GA遗传算法是对问题参数集的编码(染色体群)作为运算对象。使得我们可以借鉴生物学中的染色体和基因的概念，模仿自然界生物的遗传和进化机理对问题参数集的编码(染色体群)进行进化，而不是象传统优化方法对参数本身进行优化。(2)GA是从问题的集合开始进行群体搜索，而不是从某个解开始进行单点搜索。形象地说，GA是并行地爬多个峰，这一特点使GA具有较好的全局搜索性能，大大减少了陷入局部最优解的可能性。(3)GA的适应性强，仅用适应度函数值来引导搜索，而不需要问题领域的先验知识或其它辅助信息，从而对问题的依赖性较小。(4)GA使的选择、交叉、变异三个算子都是随机操作，具有不确定性。采用概率的变迁规则来指导搜索方向，引导搜索过程朝着搜索空间的更优化的解区域移动。因此它是一种启发式搜索。2普通遗传算法初始化群体2．1普通遗传遗传算法思想初始化群体(1)初始化群体;计算适应度(2)计算群体上每个个体的适应度值;计算适应度(3)按由个体适应度值所决定的某个选择操作规则选择将进入下一代的个体;选择操作(4)按概率Pc进行交叉操作;交叉操作(5)按概率Pm进行变异操作;交叉操作(6)没有满足某种停止条件，则转第(2)步，否则进入（7）。变异操作(7)输出种群中适应度值最优的染色体作变异操作为问题的满意解或最优解。条件终止条件终止算法简单流程图如右图所示：适合度最优群体适合度最优群体结束结束图1遗传算法简单流程图2．2普通遗传算法的遗传操作2．2．1选择（selection）操作选择（selection）操作是模拟生物界优胜劣汰的自然选择法则的一种染色体运算，就是从种群中选择适应度较高的染色体进行复制，以生成下一代种群。最常用的选择策略是赌轮选择策略。赌轮选择的基本思想：做一个轮盘，然后按照各个染色体的个体适应度比例转化为选中概率(选择概率)，将轮盘分成若干个扇区，随机地产生「0,1]之间的随机数，这样就相当于转动轮盘，获得转盘停止时指针位置，指针停止在某一扇区，该扇区代表的个体即被选中。这里选择概率的计算公式：P(xi)=其中f为适应度函数，f(xi)为的适应度。2．2．2交叉(crossover)操作交叉就是互换两个染色体某些位上的基因以产生新的个体，普通遗传算法中常用的交叉算子有单切点交叉、双切点交叉、循环交叉，下面我们来进行依次介绍（1）单切点交叉（single-pointcrossover）单切点交叉的思想是从种群中选出两个个体P=1\*Arabic1和P2，随机地选择一个切点（cutting），将切点两侧分别看成一个子串，将右侧的子串分别进行交换，这样就得到了两个新的个体C1和C2。P1和P2其中称为父代染色体，C1和C2称为子代染色体。切点切点P1=A1P1=A1∣A2P2=B1∣B2C1=A1|B2C2=B1|A2图2单切点交叉示意图单切点交叉操作的信息量比较小，交叉位置的选择可能带来较大的偏差，并且染色体末尾的基因总是被交换。（2）双切点交叉（double-pointcrossover）双切点交叉的思想是从种群中选出两个个体P=1\*Arabic1和P2，随机地选择两个切点（cutting），交换两个切点之间的子串，从而得到了新一代的染色体。切点切点切点切点P1=A1P1=A1∣B2∣A3P2=B1∣A2∣B3P1=A1∣A2∣A3P2=B1∣B2∣B3图3双切点交叉示意图（3）循环交叉（cyclecrossover）循环交叉[12]的基本思想是子串位置上的值必须与父母相同位置上的值相等。循环交叉操作的具体步骤如下：选P1的第一个元素作为C1的第一个元素；选P2的第一个元素作为C2的第一个元素；在P1中找P2的第一个元素赋给C1的相对位置……重复此过程，直到P2上得到P1的第一个元素为止，称为一个循环；对最前的基因按P1、P2基因轮替原则重复以上过程；重复以上过程，直至所有位已完成。P1=２４５３８９６１７P1=３９８６５４２７１P1=２４５３８９６１７P1=３９８６５４２７１循环１：２－３－６C1=２＿＿３＿＿６＿＿C2=3＿＿６＿＿２＿＿循环２：９－４C1=２95３84６＿＿C2=348６59２＿＿C1=２95３84６＿＿C2=348６59２＿＿循环4：7－1C1=２9＿３＿4６＿＿C2=34＿６＿9２＿＿循环3：5－8C1=295384671C1=295384671C2=348659217图4循环交叉示意图2．2．3变异(mutation)操作变异本身是一种局部随机搜索，与选择/交叉算子结合在一起，保证了遗传算法的有效性，使遗传算法具有局部的随机搜索能力;同时使得遗传算法保持种群的多样性，以防止出现非成熟收敛。在变异操作中，变异率不能取得太大，如果变异率大于0.5，遗传算法就退化为随机搜索，而遗传算法的一些重要的数学特性和搜索能力也不复存在了。最常用的变异操作是按位交换变异，它的基本思想：对于同一个个体的基因如果发生变异，则随机与同一个个体的另一个基因交换位置。4遗传算法在TSP问题上的应用4．1TSP问题概述TSP问题就是已知个城市各城市间的距离，一旅行商从某一城市出发访问每个城市一次且仅一次，最后回到出发城市，如何安排才能使其所走路程最短？问题的数学模型可以描述为：对于n个城市V={v1,v2,…,vn}的一访问次序为T=(t1,t2,…,tn),tiVi（i=1，2,…，n）,tn+1=t1,则问题即要求min，其中表示城市i与城市i+1之间的距离。对于TSP这样的一个典型的组合优化问题，最为普通的一种解决办法就是穷举出所有可能的合法序列，然后比较距离函数，得出最优的城市序列。这就是穷举搜索法的思想，理论上它可以解决任何组合优化问题，但是对于n个城市的TSP问题来说，可能的合法回路有条,计算每一条路径需求n个距离之和，因此计算量正比于。即使使用运算速度为105亿次每秒的巨型计算机按穷举搜索法计算100个城市的TSP问题也需要1.4810136年的时间，在这里还没有考虑算法所需的巨大的存储空间，由此可见TSP问题的时空复杂度之高，这就为遗传算法的应用提供了机会，下面我们就来看一求解TSP问题的遗传算法。4．2遗传算法求解TSP问题4．2．1编码与解码在遗传算法中每一个个体表示成一个染色体，每一个染色体又是由一个个基因位所构成的。这样每一个个体对象相当于生物体的表现型，而染色体就相当于生物体的基因型，从表现型到基因型的映射称为编码。在遗传算法中最初使用的编码方法是二进制编码：每个染色体使用固定长度的0，1字符串表示，如：X=（0110010）表示一个染色体，该个体的染色体长度为7，二进制编码具有易于位值计算、包括的实数范围大的优点。适合于背包问题、实优化问题和指派问题，但是在另外的一些实际问题如TSP问题，二进制编码编码长，不易计算同时不易进行变异交叉操作，易产生大量非可行解，所以针对特殊的问题，可以采用不同的编码方法。本文在TSP求解中，采用基于城市序号的顺序实数编码，它是用１～ｎ的自然数来编码，这种编码不允许重复，即xi1,2,3,…,n,且当ij时，xixj如：X=（2315476）表示一个染色体长度为7的顺序实数编码，对于7个城市的旅行商问题，上述编码表示2-3-1-5-4-7-6-2的一条行走路线。这种编码虽然方便，但是要注意编码的合法性检查，并对不合法的个体进行合法性修复。解码就是求出一条染色体所对应的路径长度的过程。如：一染色体X的顺序实数编码为（2315476），解码就是要把相邻两点的距离进行求和，具体地说就是要把2与3，3与1，1与5，5与4，4与7，7与6，6与2之间的距离相加，相加的结果就是由解码得到的路径长度d。4．2．2初始化种群遗传算法是一种既有群体寻优的方法算法运行时是一个群体在搜索空间进行搜索，一般采用随机方法产生一个初始种群。本文就是采用是一种经典的洗牌随机生成的方法生成初始种群，设表示编码的一维数组为P1[n]和P2[n],先把P1[n]和P2[n]按城市序号初始化为{0，1，…，n-1}，令i=0，产生一个（n-1）-i范围内的整数r，然后将P1[n-1-i]赋值于P2[i],P1[n-1-i]赋值给P1[r]。i增加1后，进入下一轮循环。如此循环直至达到所需的群体规模为止。P2[n]即为洗牌随机生成后的序列。其算法JAVA实现如下：publicvoidinit(List<City>list,intpopSize,intcityNum,StringfileName){ initDistance(list,fileName,cityNum); for(inti=0;i<popSize;i++){ this.citys.add(i,newGenoType(this.copy(list),0,0,0,0));//初始化种群数组 int[]num=newint[cityNum]; for(intj=0;j<cityNum;j++){ num[j]=j; } inttemp=cityNum; //随机地初始化城市序列 for(intj=0;j<cityNum;j++){ intr=(int)(Math.random()*temp); this.citys.get(i).get(j).setSequece(num[r]); num[r]=num[temp-1]; temp--; } this.citys.get(i).setFitness(0); this.citys.get(i).setSelectP(0); this.citys.get(i).setExceptp(0); this.citys.get(i).setIsSelected(0); } }4．2．3适应度函数适应度函数一般根据目标函数来进行设计。目标函数一般表示为f(x),适应度函数一般表示为F（x）。对优化问题，适应度函数就是目标函数。TSP的目标是路径总长度为最短，路径总长度可作为TSP问题的适应度函数F（x）=f(x)=（其中xn+1=x1）计算种群适应度的函数JAVA实现：privatevoidCalFitness(intpopSize,intcityNum){ for(inti=0;i<popSize;i++){ doublelen2=this.citys.get(i).getFitness(); for(intj=0;j<cityNum-1;j++){ len2+= this.distance[this.citys.get(i).get(j).getSequece()][this.citys .get(i).get(j+1).getSequece()]; } len2+=this.distance[this.citys.get(i).get(0).getSequece()][this.citys .get(i).get(cityNum-1).getSequece()]; this.citys.get(i).setFitness(len2); } }4．2．4选择算子在每一代的运算过程中，个体被选中的概率与其在群体中的相对适应度成正比，即采用赌轮选择机制。计算选择算子的JAVA实现：privatevoidCalSelectP(intpopSize){ doublesum=0; for(inti=0;i<popSize;i++) //计算所有种群的适应度之和 sum+=this.citys.get(i).getFitness(); for(inti=0;i<popSize;i++) //计算每一个种群的选择概率 this.citys.get(i).setSelectP( (double)this.citys.get(i).getFitness()/sum); }4．2．5交叉算子1、普通单切点、双切点交叉算子由单切点交叉算子的思想，随机选取个体A1、A2，然后随机地选取一基因位交换两个体中该基因位之后的基因，而双切点交叉算子是在随机选取的两个个体中随机的选取两个基因位，然后把两基因位之间的基因位相互交换位置，由于我们TSP问题采用的是顺序实数编码，产生的后代也必须是合法的编码，然而单切点和双切点交叉都不能保证交叉后个体的合法性，因此我们要对非法个体进行合法性修复，如：切点非法个体P1=2167︱P1=2167︱4563P2=4316︱5762P1=21675762P2=43164563P1=21675762P2=53164563P1=21675762P2=53164563映射关系：4-55-76-63-2图5单切点交叉算子合法性修复示意图单切点交叉算子的JAVA实现：publicvoidSiglePointPTcrossover(intpopSize,intcityNum,doublepxover){ intx; inty; intpop=(int)(popSize*pxover/2); while(pop>0){ x=(int)(Math.random()*popSize); y=(int)(Math.random()*popSize); intlocation=(int)(Math.random()*cityNum); SiglePointPTexecuteCrossover(x,y,location,cityNum);//xy两个体执行普通遗传算法的单切点交叉 pop--; } }publicvoidSiglePointPTexecuteCrossover(intx,inty,intlocation, intcityNum){ for(inti=location;i<cityNum;i++){//交换两个体的序列 inttemp=this.citys.get(x).get(i).getSequece(); this.citys.get(x).get(i).setSequece( this.citys.get(y).get(i).getSequece()); this.citys.get(y).get(i).setSequece(temp); intj=0; //个体修复 while(j<cityNum){ if((j!=i) &&this.citys.get(x).get(j).getSequece()==this.citys .get(x).get(i).getSequece()) this.citys.get(x).get(j).setSequece( this.citys.get(y).get(i).getSequece()); j++; } intk=0; while(k<cityNum){ if((k!=i) &&this.citys.get(y).get(k).getSequece()==this.citys .get(y).get(i).getSequece()) this.citys.get(y).get(k).setSequece( this.citys.get(x).get(i).getSequece()); k++; } } }双切点交叉算子的JAVA实现类似于单切点交叉算子，在此不做详细介绍。2、普通循环交叉算子为克服单切点、双切点交叉带来的子代个体解的不合法性，我们采用循环交叉的方法，该交叉算子的思想在上文中已做详细介绍，这里不做赘述。循环交叉算子较好的保留了父代的位值特征，较好的避免了不合法个体的产生，但是由于算法的复杂性，使得运算速度大为降低。普通循环交叉算子的JAVA实现：publicvoidCyclePTcrossover(intpopSize,intcityNum,doublepxover){ intx; inty; intpop=(int)(popSize*pxover/2); while(pop>0){ x=(int)(Math.random()*popSize); y=(int)(Math.random()*popSize); CyclePTexecuteCrossover(x,y,cityNum);//xy两个体执行交叉 pop--; } }publicvoidCyclePTexecuteCrossover(intx,inty,intcityNum){ intarr1[]=newint[cityNum]; intarr2[]=newint[cityNum]; for(inti=0;i<cityNum;i++){ arr1[i]=this.citys.get(x).get(i).getSequece(); arr2[i]=this.citys.get(y).get(i).getSequece(); } Crossutil=newCross(arr1,arr2);//实现循环交叉的主体类对象 int[]result1=util.getResult1(); int[]result2=util.getResult2(); for(inti=0;i<cityNum;i++){ this.citys.get(x).get(i).setSequece(result1[i]); this.citys.get(y).get(i).setSequece(result2[i]); } }3、佳点集交叉算子根据佳点集的理论，结合TSP问题的实际意义我们给出TSP问题的佳点集交叉算子：随机选取个体A1、A2的前t位不同，后L-t位相同，取t维单位立方体。在t维单位立方体中任取一点P（p1,p2,…,pt），将个体A1、A2中相同的基因位去掉，设余下的基因编码位S（s1,s2,…,st）其中s1<s2<…<st,将P进行从小到大排序得到T（t1,t2,…,tt）,则T相对于S，得到一个新的S排列，这个新的S排列于A1和A2个体中的相同部分合在一起就得到了佳点集交叉后的新个体。例如：A1=（7，2，0，1，8，5，9，4，3，6）A2=（1，2，4，0，5，6，9，3，7，6）相同部分：（*，2，*,*，*,*,9,*,*，6）不同部分：S（0，1，3，4，5，7，8）取佳点P（0.2，0.12，0.81，0.73，0.5，0.4，0.83）从小到大排序得到T(0.12，0.2，0.4，0.5，0.73，0.81，0.83)T相对于S，得到一个新的S排列S（1，0，7，5，4，3，8）与A1和A2相同部分合并得交叉后的新个体：（1，2，0，7，5，4，9，3，8，6）佳点集交叉操作有效的避免了普通交叉算子因交叉产生的非法个体，又避免了因问题规模的扩大，使算法性能的下降。佳点集交叉算子的JAVA实现：privatevoidexecuteCrossover(intx,inty,intcityNum){ intdimension=0; for(inti=0;i<cityNum;i++) if(this.citys.get(x).get(i).getSequece()!=this.citys.get(y).get(i).getSequece())//个体x和个体y中对应位基因不同 dimension++; intdiffItem=0; double[]diff=newdouble[dimension];//用于存储不同的基因片段 for(inti=0;i<cityNum;i++){ if(this.citys.get(x).get(i).getSequece()!=this.citys.get(y).get(i).getSequece()){ diff[diffItem]=this.citys.get(x).get(i).getSequece(); this.citys.get(x).get(i).setSequece(-1); this.citys.get(y).get(i).setSequece(-1); diffItem++; } } Arrays.sort(diff);//将不同的基因片段进行排序 double[]temp=newdouble[dimension]; temp=gp(x,dimension);//用于交叉函数的交叉点，运用佳点集交叉 for(intk=0;k<dimension;k++) //通过temp[]交换数组temp中的值 for(intj=0;j<dimension;j++) if(temp[j]==k){ doubleitem=temp[k]; temp[k]=temp[j]; temp[j]=item; item=diff[k]; diff[k]=diff[j]; diff[j]=item; } inttempDimension=dimension; inttempi=0; while(tempDimension>0){ if(this.citys.get(x).get(tempi).getSequece()==-1)//当为不同的基因片段时{ this.citys.get(x).get(tempi).setSequece((int)diff[dimension-tempDimension]); tempDimension--; } tempi++; } Arrays.sort(diff); temp=gp(y,dimension); for(intk=0;k<dimension;k++) for(intj=0;j<dimension;j++) if(temp[j]==k){ doubleitem=temp[k]; temp[k]=temp[j]; temp[j]=item; item=diff[k]; diff[k]=diff[j]; diff[j]=item; } tempDimension=dimension; tempi=0; while(tempDimension>0){ if(this.citys.get(y).get(tempi).getSequece()==-1){ this.citys.get(y).get(tempi).setSequece((int)diff[dimension-tempDimension]); tempDimension--; } tempi++; } }privatedouble[]gp(intindividual,intdimension){ double[]temp=newdouble[dimension]; double[]temp1=newdouble[dimension]; intp=2*dimension+3; while(!isSushu(p)) p++; for(inti=0;i<dimension;i++){ temp[i]=2*Math.cos(2*Math.PI*(i+1)/p)*(individual+1); temp[i]=temp[i]-(int)temp[i]; if(temp[i]<0) temp[i]=1+temp[i]; } for(inti=0;i<dimension;i++) temp1[i]=temp[i]; Arrays.sort(temp1);//排序 for(inti=0;i<dimension;i++) for(intj=0;j<dimension;j++) if(temp[j]==temp1[i]) temp[j]=i; returntemp; }4．2．6变异算子变异是在种群中按照变异概率任选若干个基因位改变其位值，对于二进制编码来说，就是反转位值。而对于顺序实数编码，就是在同一个个体的基因中，随机选取另一个基因交换位置，如：变异算子的JAVA实现：publicvoidmutate(intpopSize,intcityNum,doublepmultation){ doublerandom; inttemp; inttemp1; inttemp2; for(inti=0;i<popSize;i++){ random=Math.random(); if(random<=pmultation){ temp1=(int)(Math.random()*cityNum); temp2=(int)(Math.random()*cityNum); temp=this.citys.get(i).get(temp1).getSequece(); this.citys.get(i).get(temp1).setSequece( this.citys.get(i).get(temp2).getSequece()); this.citys.get(i).get(temp2).setSequece(temp); } } }4．2．7停止准则遗传算法中的停止准则一般是设定最大代数的方式，最大代数常设为popsize，本文采用，最大代数与收敛情况相结合的方式来设计停止准则，判断停止准则的JAVA代码：if(tsp.isSame(result))//判断2000代内的最优解是否相同，相同则结束，不同则看下一代 break;index++;if(index==range)//重新计数index=0;5TSP问题的实验结果及分析5．1普通遗传算法与佳点集遗传算法的比较与分析5．1．1最优解分析我们分别用佳点集遗传算法和普通遗传算法（单切点、双切点、循环交叉）对Bayg29个城市进行求解，取交叉概率为0.9，变异概率为0.04，群体规模为50，最大迭代代数8000将算法各执行30次，实验结果如下：图6遗传算法各交叉算子比较1对各最优解数据作统计学处理得到下表：图7遗传算法各交叉算子比较2由实验结果可以看出普通单切点和双切点交叉操作的交叉位置的选择随机性比较大，因此每次执行的最优解的偏差也比较大，相比较而言，佳点集交叉和循环交叉的随机性较小，因此算法每次执行得到的