遗传算法原理及其应用.ppt

《遗传算法原理及其应用.ppt》由会员分享，可在线阅读，更多相关《遗传算法原理及其应用.ppt（71页珍藏版）》请在三一办公上搜索。

1、中山大学智能交通研究中心2010年4月,遗传算法原理及其应用,2,1.遗传算法概述,2.基本遗传算法(SGA),目 录,1.1 遗传算法的产生与发展1.2 遗传算法的生理学基础 1.3 遗传算法的原理与特点1.4 遗传算法的基本操作1.5 遗传算法的应用,2.1 基本遗传算法描述 2.2 基本遗传算法实现 2.3 基本遗传算法流程 2.4 简单函数优化的实例,3,3.遗传算法的改进,4.遗传算法的应用,目 录,3.1 自适应遗传算法 3.2 CHC算法 3.3 基于小生境技术的遗传算法 3.4 退火进化算法,4.1 解决带约束的函数优化问题 4.2 解决多目标优化问题 4.3 解决组合优化问题

2、 4.4 遗传算法在过程建模中的应用 4.5 遗传算法在模式识别中的应用,4,1.1 遗传算法的产生与发展,产生早在50年代，一些生物学家开始研究运用数字计算机模拟生物的自然遗传与自然进化过程；1963年，德国柏林技术大学的I.Rechenberg和H.P.Schwefel，做风洞实验时，产生了进化策略的初步思想；60年代，L.J.Fogel在设计有限态自动机时提出进化规划的思想。1966年Fogel等出版了基于模拟进化的人工智能，系统阐述了进化规划的思想。60年代中期，美国Michigan大学的J.H.Holland教授提出借鉴生物自然遗传的基本原理用于自然 和人工系统的自适应行为研究和串编

3、码技术；1967年，他的学生J.D.Bagley在博士论文中首次提出“遗传算法(Genetic Algorithms)”一词；1975年，Holland出版了著名的“Adaptation in Natural and Artificial Systems”，标志遗传算法的诞生。,5,1.1 遗传算法的产生与发展,发展70年代初，Holland提出了“模式定理”（Schema Theorem），一般认为是“遗传算法的基本定理”，从而奠定了遗传算法研究的理论基础；1985年，在美国召开了第一届遗传算法国际会议，并且成立了国际遗传算法学会(ISGA，International Society of

4、Genetic Algorithms)；1989年，Holland的学生D.J.Goldherg出版了“Genetic Algorithms in Search,Optimization,and Machine Learning”，对遗传算法及其应用作了全面而系统的论述；1991年，L.Davis编辑出版了遗传算法手册，其中包括了遗传算法在工程技术和社会生活中大量的应用实例。,遗传算法进化计算计算智能人工智能,6,1.2 遗传学基本概念与术语,染色体（chromosome）：遗传物质的载体；脱氧核糖核酸（DNA）：大分子有机聚合物，双螺旋结构；RNA遗传因子（gene）：DNA或RNA长链结构

5、中占有一定位置的基本遗传单位；基因型（genotype）：遗传因子组合的模型；表现型（phenotype）：由染色体决定性状的外部表现；个体（individual）：指染色体带有特征的实体；种群（population）：个体的集合，该集合内个体数称为种群的大小；,7,进化（evolution）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化；适应度（fitness）：度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝;选择（selection）：指

6、决定以一定的概率从种群中选择若干个体的操作（实现优胜劣汰）；复制（reproduction）：细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因;,8,交叉（crossover）：在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体。又称基因重组，俗称“杂交”;变异（mutation）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状;编码（coding）：表现型到基因型的映射；解码（decoding）：从基因型到表现型的映射。大象灰颜色皮肤为例,9,1

7、.3 遗传算法的原理与特点,原理遗传算法(GA)是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。其采纳了自然进化模型，从代表问题可能潜在解集的一个种群开始，种群由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体；初始种群产生后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的解：在每一代，概据问题域中个体的适应度大小挑选个体；并借助遗传算子进行组合交叉和主客观变异，产生出代表新的解集的种群。这一过程循环执行，直到满足优化准则为止。最后，末代个体经解码，生成近似最优解。基于种群进化机制的遗传算法如同自然界进化一样，后生代种群比前生代更加适

8、应于环境，通过逐代进化，逼近最优解。,10,1.3 遗传算法的原理与特点,遗传算法的基本流程,Fig.2逼近最优解的过程,11,1.3 遗传算法的原理与特点,特点遗传算法的本质并行性。首先，遗传算法并行的方式从问题解的串集开始嫂索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。其次，算法内含并行性，遗传算法采用种群方式组织搜索，因而可同时搜索妥空间的多个区域(n-n3)，并相互交流信息，能以较小的计算获得较大的收益。遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度

9、函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导他的搜索方向。具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，硬度大的个体具有较高的生存概率，并获得更适应环境的基因结构。遗传算法可更直接的应用，对给定的问题，可以产生许多潜在解，最终选择可以由使用者指定，通用性高，应用范围广。,12,1.4 遗传算法的基本操作,遗传基因型(编码)编码方式二进制编码、浮点数编码、格雷码编码、符号编码、复数编码、DNA编码等。以大象灰色皮肤

10、为例：二进制编码：1111111，浮点编码：127.0编码原则完备性（completeness）：问题空间的所有解都能表示为所设计的基因型；健全性（soundness）：任何一个基因型都对应于一个可能解；非冗余性（non-redundancy）：问题空间和表达空间一一对应。二进制编码与浮点数编码的比较在交叉操作时，二进制编码比浮点数编码产生新个体的可能性多，而且产生的新个体不受父个体所构成的超体的限制；在变异操作时，二进制编码的种群稳定性比浮点数编码差。,13,1.4 遗传算法的基本操作,选择适应度计算：按比例的适应度函数（proportional fitness assignment）基于排

11、序的适应度计算（Rank-based fitness assignment）选择算法：轮盘赌选择（roulette wheel selection）随机遍历抽样（stochastic universal selection）局部选择（local selection）截断选择（truncation selection）锦标赛选择（tournament selection）,14,交叉或基因重组二进制交叉（binary valued crossover）：单点交叉（single-point crossover）多点交叉（multiple-point crossover）均匀交叉（uniform c

12、rossover）洗牌交叉（shuffle crossover）缩小代理交叉（crossover with reduced surrogate）实值重组（real valued recombination）：离散重组（discrete recombination）中间重组（intermediate recombination）线性重组（linear recombination）（均匀、非均匀）扩展线性重组（extended linear recombination,15,交叉方式半种群交叉(N/2)对群体中的要交叉的个体进行两两随机配对。若群体大小为M，则最多共有 M/2 对相互配对的个体组参

13、与交叉。(若种群数为奇数，则其中任一个个体多选一次配对)2)全种群交叉(N)对群体中要交叉的个体，从种群中随机挑选一个个体与其完成交叉操作，最多共有M对相互配对的个体参与变异。,16,变异方法 二进制变异单点变异 逆序变异均匀变异实值变异随机变异边界变异非一致变异自适应变异高斯变异,17,变异方式基于个体的变异即对任意一个个体，判断其是否进行变异操作，如果是，则随机生成一变异基因发生变异操作。基于基因座的变异即对种群中的个体，判断每一个个体的每一位基因是否进行变异操作，如果是，则发生变异操作。,18,1.5 遗传算法的应用,函数优化 是遗传算法的经典应用领域;组合优化 实践证明，遗传算法对于组

14、合优化中的NP完全问题非常有效;自动控制 如基于遗传算法的模糊控制器优化设计、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计和权值学习等;机器人智能控制 遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等;组合图像处理和模式识别 目前已在图像恢复、图像边缘持征提取、几何形状识别等方面得到了应用;,19,人工生命 基于遗传算法的进化模型是研究人工生命现象的重要理论基础，遗传算法已在其进化模型、学习模型、行为模型等方面显示了初步的应用能力；遗传程序设计 Koza发展了遗传程序设计的慨念，他使用了以LISP语言所表示的编

15、码方法，基于对一种树型结构所进行的遗传操作自动生成计算机程序;机器学习机器学习学习能力是高级自适应系统所应具备的能力之一。基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习模糊控制规则，利用遗传算法来学习隶属度函数，从而更好地改进了模糊系统 的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用于人工神经网络的网络结构优化设计；分类器系统也在学习式多机器人路径规 划系统中得到了成功的应用。,20,2 基本遗传算法,遗传算法在自然与社会现象的模拟、工程计算等方面得到了广泛的应用。在各个不同的应用领域，为了取得更好的结果，人们对GA进行了大量

16、的改进。为不至于混淆，把Holland提出的算法称为基本遗传算法，简称为SGA（Simple Genetic Algorithm)，也有称其为(GA、CGA)。以SGA为例，阐述遗传算法的设计与实现方法。,21,2.1 基本遗传算法描述,2.1.1 SGA的构成要素(1)染色体编码方法 基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因由二值符号集0，1组成。初始群体中各个个体的基因值用均匀分布的随机数来生成。如：x：就可表示一个个体，该个体的染色体长度是 l18。(2)个体适应度评价 基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少

17、。为正确计算这个概率，这里要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数 值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。,22,(3)遗传算子 基本遗传算法使用下述三种遗传算子：选择运算：使用比例选择算子；交叉运算：使用单点交叉算子；变异运算：使用基本位变异算子。(4)基本遗传算法的运行参数 基本遗传算法有下述4个运行参数需要提前设定：M：群体大小，即群体中所含个体的数量，一般取为20 100。T：遗传运算的终止进化代数，一般取为100 500 pc：交叉概率，一般取为0.4 0.99 pm：变异概率，一般取为 0.00

18、01 0.1*这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前 尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次试 算后才能确定出这些参数合理的取值大小或取值范围。,23,2.1.2 基本遗传算法的描述 基本遗传算法可定义为一个7元组：GA(M,F,s,c,m,pc,pm)M群体大小；F个体适应度评价函数；s选择操作算于；c交叉操作算子：m变异操作算于；pc交叉概率；pm变异概率；,24,2.2 基本遗传算法的实现,2.2.1 编码与解码(1)编码 假设某一参数的取值范围是umin,umax，我们用长度为l的二进制编码符号串来表示该参数，则它总共能够产生

19、2l种不同的编码，参数编码时的对应关系如下：00000000000000000 umin 00000000000000011 umin+1111111111111111=2l1 umax,其中，为二进制编码的编码精度，其公式为：,25,(2)解码 假设某一个体的编码是：x：bl bl-1 bl-2b2b1 则对应的解码公式为：,26,例 设-3.0 x 12.1,精度要求=1/10000，由公式：,即：217 151001 218 x需要18位 0/1 符号表示。如：解码：,得：,27,2.2.2 个体适应度评价 如前所述，要求所有个体的适应度必须为正数或零，不能是负数。(1)当优化目标是求函

20、数最大值，并且目标函数总取正值时，可以直接设定个体 的适应度F(X)就等于相应的目标函数值f(X)，即：F(X)f(X)(2)对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就 可将其转化为求目标函数最大值的优化问题，即：min f(X)max(-f(X)但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有 求函数最小值，显然上面两式保证不了所有情况下个体的适应度都是非负数这个 要求，需要进行适应度函数尺度转换，将目标函数值 f(x)变换为个体的适应度F(x)。,28,(3)SGA适应度函数变换常用方法：方法一：对于求目标函数最大值的优化问题，变换方法为：其中，

21、Cmin为一个适当地相对比较小的数，它可用下面方法之一来选取：预先指定的一个较小的数。进化到当前代为止的最小目标函数值。当前代或最近几代群体中的最小目标函数值。方法二：对于求目标函数最小值的优化问题，变换方法为：其中，Cmax是一个适当地相对比较大的数，它可用下面几种方法求得：预先指定的一个较大的数。进化到当前代为止的最大目标函数值。当前代或最近几代群体中的最大目标函数值。,29,2.2.3 比例选择算子指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。pi=fi/fi(i=1,2,M)式中 pi个体i被选中的概率；fi个体i的适应度；fi群体的累加适应度。显然，个体适应度愈高

22、，被选中的概率愈大。但是，适应度小的个体也有可 能被选中，以便增加下一代群体的多样性。执行比例选择的手段是轮盘选择。个体被选中的概率取决于个体的相对适应度：从统计意义讲，适应度大的个体，其刻度长，被选中的可能性大；反之，适应度小的个体被选中的可能性小，但有时也会被“破格”选中。,30,2.2.4 单点交叉算子.对群体中的个体进行两两随机配对。若群体大小为M，则共有 M/2 对相互 配对的个体组。.每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。若染色体的长度为l，则共有(l-1)个可能的交叉点位置。.对每一对相互配对的个体，依设定的交叉概率pc在其交叉点处相互交换两个个 体的部分染

23、色体，从而产生出两个新的个体。单点交叉运算的示例如下所示:,交叉概率,式中 M群体中个体的数目；Mc群体中被交换个体的数目。,31,2.2.5 基本位变异算子对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作 的某一基因座上的原有基因值为0，则变异操作将该基因值变为1，反之，若原有 基因值为1，则变异操作将其变为0。基本位变异因子的具体执行过程是：.对个体的每一个基因座，依变异概率pm指定其为变异点。.对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替，从而产生出一个新的个体。基本位变异运算的示例如下所示：A：1010 1 01010 A：1010 0 010

24、10,变异点,32,变异是针对个体的某一个或某一些基因座上的基因值执行的，因此变异概率pm 也是针对基因而言，即：,式中 B每代中变异的基因数目；M每代中群体拥有的个体数目 l个体中基因串长度。,变异概率,33,2.3 GA算法流程图,34,问题的提出 一元函数求最大值：,2.4 简单函数优化实例,35,编码 表现型：x 基因型：二进制编码（串长取决于求解精度）按编码原理：假设要求求解精度到6位小数，区间长度为2-(-1)3，即需将区间分为3/0.000001=3106等份。所以编码的二进制串长应为22位。,36,产生初始种群 产生的方式：随机 产生的结果：长度为22的二进制串 产生的数量：种

25、群的大小（规模），如30，50，,37,计算适应度直接用目标函数作为适应度函数 解码：将个体s转化为-1,2区间的实数：s x=0.637197 计算x的函数值（适应度）：f(x)=xsin(10 x)+2.0=2.586345,38,遗传操作 选择：比例选择法；交叉：单点交叉；变异：小概率变异,39,模拟结果 设置的参数：种群大小50；交叉概率0.75；变异概率0.05；最大代数200。得到的最佳个体：smax xmax=1.8506;f(xmax)=3.8503;,40,模拟结果 进化的过程：,41,3 遗传算法的改进,传统的GA在解决时就存在如下问题：首先，模型复杂，参数太多难以达到优化

26、目的，优化速度慢且达不到最优解。其次，约束条件复杂、繁多，算法收敛的时候很难满足约束条件。因此，在处理交通控制问题上扬长避短，需要改进遗传算法，使其达到智能控制的效果。改进措施改变遗传算法的组成成分；采用混合遗传算法；采用动态自适应技术；采用非标准的遗传操作算子；采用并行遗传算法等。,42,参数分析交叉概率Pc和变异概率Pm的选择是影响遗传算法行为和性能的关键，直接影响算法的收敛性；Pc越大，新个体产生的速度就越快，但过大会使优秀个体的结构很快被破坏；Pc过小，搜索过程缓慢，以至停止不前；Pm过小，不易产生新个体结构，Pm过大，变成纯粹的随机搜索；,43,自适应策略Srinvivas等提出一种

27、自适应遗传算法，Pc和Pm能够随适应度自动改变：当种群各个体适应度趋于一致或趋于局部最优时，使Pc和Pm增加；而当群体适应度比较分散时，使Pc和Pm减少；对于适应度较高的个体，对应于较低的Pc和Pm；而较低适应度的个体，对应于较高的Pc和Pm。,44,自适应方法 fmax群体中最大的适应度值；favg每代群体的平均适应度值；f要交叉的两个个体中较大的适应度值；f要交叉或变异的个体适应度值；,k1、k2、k3、k4取(0,1)的值,45,自适应方法进一步改进适用于进化后期，不适于进化前期，因为前期的优秀个体有可能是局部最优点；使最大适应度个体的交叉概率和变异概率由0提高到Pc2和Pm2；采用精英

28、选择策略；,46,自适应方法进一步改进,47,改进思路1991年Eshelman提出的一种改进遗传算法；C：跨世代精英选择（Cross generational elitist selection）策略；H：异物种重组（Heterogeneous recombination）；C：大变异（Cataclysmic mutation）。,4.3.1 CHC算法,48,选择上一代种群与通过新的交叉方法产生的个体群混合起来，从中按一定概率选择较优的个体；即使交叉操作产生较劣个体偏多，由于原种群大多数个体残留，不会引起个体的评价值降低；可以更好地保持遗传多样性；排序方法，克服比例适应度计算的尺度问题。,

29、49,交叉均匀交叉的改进：当两个父个体位值相异的位数为m时，从中随机选取m/2个位置，实行父个体位值的交换；确定一阈值，当个体间距离低于该阈值时，不进行交叉操作。进化收敛的同时，逐渐地减小该阈值。,50,变异在进化前期不采取变异操作，当种群进化到一定收敛时期，从最优个体中选择一部分个体进行初始化；初始化：选择一定比例（扩散率，一般0.35）的基因座，随机地决定它们的位值。,4.3.1 CHC算法,51,小生境概念小生境（niche）：生物学中，特定环境中的一种组织功能；在SGA中，容易“近亲繁殖”；NGA（Niche Generic Algorithm），将每一代个体划分为若干类，每类选出优秀

30、个体组成一个种群；优势：保持解的多样性，提高全局搜索能力，适合复杂多峰函数的优化。,4.3.3 基于小生境技术的遗传算法,52,选择策略预选择机制、排挤机制、分享机制；预选择（preselection,1970）机制当子个体的适应度超过其父个体适应度时，子个体才可以替代父个体，否则父个体仍保留；有效维持种群多样性，造就小生境进化环境。,4.3.3 基于小生境技术的遗传算法,53,排挤（crowding,1975）机制设置排挤因子CF（CF=2或3），随机选取1/CF个个体组成排挤成员，排挤与其相似（用距离来度量）的个体；个体之间的相似性可用个体编码串之间的海明距离来度量。,4.3.3 基于小生

31、境技术的遗传算法,54,共享（sharing,1987）机制通过个体之间的相似性程度的共享函数来调整各个体的适应度；共享函数的目的：将搜索空间的多个峰值在地理上区分开来，每一个峰值处接受一定比例数目的个体，比例数目与峰值高度有关；,4.3.3 基于小生境技术的遗传算法,55,共享（sharing,1987）机制共享函数的值越大，表明个体之间越相似，记为Sh(dij)，dij为两个个体i和j之间的距离；share是niche的半径，由使用者给定。,4.3.3 基于小生境技术的遗传算法,56,共享（sharing,1987）机制共享法将个体的适应度降低，即适应度值fi除以一个niche计数mi：在

32、距离为share的范围内的个体彼此削减适应度，这些个体将收敛在一个niche内，避免了整个种群的收敛。,4.3.3 基于小生境技术的遗传算法,57,退火进化算法,退火进化算法(annealing evolution algorithm,AEA）遗传算法（GA)模拟退火算法（SA）是人工智能中用于解决组合优化问题的经典但是，SA 在全局搜索能力方面不足，GA 在局部搜索能力方面不足。而退火进化算法（annealing evolution algorithm,AEA)综合了SA和GA算法，优势互补，发挥SA 局部搜索能力和GA 全局搜索能力,克服SA 全局搜索能力差及效率不高的问题和GA 局部搜索

33、能力差及其早熟现象。AEA把SA算法与GA结合在一起，通过变异与选择不断改善解群体，并行搜索解空间，从而有可能更迅速地找到全局最优解。由于在选择中采用Metropolis准则，因而保留了SA算法易跳出某局部极值“陷阱”的优点，易于向全局极小值快速收敛。算法求解过程如下：(1)初始化进化代数计数器k0，随机给出种群P(k)初值，给定初试退火温度T0。(2)评价当前群体P(k)的适应度。(3)个体交叉操作（附带保优操作）：P(k)CrossoverP(k)。(4)个体变异操作（附带保优操作）：P(k)”MutationP(k)。(5)由SA状态函数产生新个体。(6)个体模拟退火操作(Metropo

34、lis准则接受新个体)：P(k)”SAP(k)”。(7)判断SA抽样是否稳定，若不稳定，则返回(5)；若稳定，则往下执行退温操作TT(8)个体复制操作，由择优选择模型保留最佳种群：P(k+1)ReproductionP(k)P(k)”。(9)终止条件判断，若不满足终止条件，则kk+1,转到(2)；若满足终止条件，则输出当前最优个体，结束算法。,58,4 遗传算法的应用,遗传算法在交通中的应用解决带约束的函数优化问题 交通规划解决多目标优化问题 交通信号控制解决组合优化问题(TSP问题)TSP问题遗传算法在过程建模中的应用BP、模糊等参数优化在模式识别中的应用 图像处理,59,1 解决带约束的函

35、数优化问题,约束最优化问题（Constrained Optimization Problems）的表述,60,多目标优化问题,61,遗传算法在过程建模中的应用,优化神经网络的权值 神经网络建模：,62,用遗传算法进行特征提取 目的：从可能的m个特征中依据某个评价标准选出d个特征（md）；,遗传算法在模式识别中的应用,63,TSP Benchmark 问题 41 94;37 84;54 67;25 62;7 64;2 99;68 58;71 44;54 62;83 69;64 60;18 54;22 60;83 46;91 38;25 38;24 42;58 69;71 71;74 78;87

36、76;18 40;13 40;82 7;62 32;58 35;45 21;41 26;44 35;4 50,解决组合优化问题,64,TSP Benchmark 问题 编码：直接采用解的表示形式，30位（30个城市）长，每位代表所经过的城市序号（无重复）；适应度函数：个体所代表的路径距离的倒数；选择：轮盘赌方法,65,TSP Benchmark 问题 交叉：有序交叉法 1）随机选取两个交叉点；2）两个父个体交换中间部分；3）替换交换后重复的城市序号。,X1:9 8|4 5 6 7 1|3 2 0X2:8 7|1 4 0 3 2|9 6 5,X1:9 8|1 4 0 3 2|3 2 0X2:8 7|4 5 6 7 1|9 6 5,X1:9 8|1 4 0 3 2|7 5 6X2:8 3|4 5 6 7 1|9 0 2,66,TSP Benchmark 问题 变异：随机选择同一个个体的两个点进行交换；初始参数：种群规模 100 交叉概率 0.8 变异概率 0.8 终止代数 2000,67,TSP Benchmark 问题运行结果,68,TSP Benchmark 问题 运行结果：,69,TSP Benchmark 问题 运行结果：,70,TSP Benchmark 运行结果：,The End,