毕业论文-遗传算法研究.doc

遗传算法研究湖南工业大学毕业设计（论文）题目 遗传算法研究学 院湖南工业大学专 业计算机应用技术学 号12535901012401姓 名谭玉婷指导教师二零一四年六月十日摘要遗传算法（GA）是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。作为一种有效的全局优化搜索算法，它具有简单、通用、鲁棒性（Robust）强和适于并行分布处理的特点。基本遗传算法提供了一种通用的算法框架，方便根据具体的问题提供改进策略或者和其它算法混合使用，因此具有广泛的应用潜力。本文中介绍的改良遗传算法改进了基本遗传算法的选择和变异操作，选择操作使用了最优保存策略，保证了当前产生最优个体不会因为交叉、变异而丢失，目的是提高算法的收敛速度；变异操作采用交换、倒序、插入三种变异算子混合的方式，增加种群的多样性，防止算法过早的陷入局部最优解而出现“早熟”现象，目的是提高解的质量。为了验证算法改进策略的有效性，以求解TSP为例，针对不同规模的TSP（eil51、eil76、eil101）做了大量的数据统计。通过对比交换、倒序、插入变异算子以及三种算子混合时解的质量来说明使用多种变异算子混合的优势。同时通过求解相同的问题（att48）与其它智能优化算法（基本遗传算法、模拟退火算法、基本蚁群算法）做了对比，验证算法改进策略的有效性。 关键词： 改良遗传算法 旅行商问题 最优保存策略 混合变异算子AbstractThe genetic algorithm (GA) is a random search algorithm learn from biological natural selection and natural genetic mechanisms. As a kind of effective global parallel optimization search algorithm, It has a simple, universal, robustness strong and suitable for the parallel distributed processing characteristics. The basic genetic algorithm provides a general algorithm framework to facilitate the improvement strategies or mixed with other algorithms, depending on the problem, and therefore has broad application potential. Improved genetic algorithm described in this article to improve the basic genetic algorithm selection and mutation operations, select the operation using the optimal preservation strategy to ensure that the current to produce the best individual will not be lost because of the crossover, and mutation, the purpose is to improve the convergence speed ; mutation operation using exchange, reverse, insert three variation operator mixed methods, increasing the diversity of the population to prevent the algorithm into a local optimal solution to the premature to improve the quality of the solution, in order to verify the effectiveness of the strategy to solve the TSP, for example, for different sizes of TSP (eil51, eil76, eil101) have done a lot of statisti. By contrast, exchange, reverse, insert the quality of the solution when the mutation operator and the mixing of the three operators to use a variety of mutation operator is a mixture of advantages. Compared at the same time by solving the same problem (att48) with the other group of intelligent algorithms (genetic algorithms, simulated annealing algorithm, the basic ant colony algorithm), In order to prove the effectiveness of the improvement strategies of algorithm. Keywords: Improe genetic algorithm , Traveling salesman problem , The optimal preservation strategy , Mixed mutation operator目 录摘要IAbstractII第一章遗传算法概论11.1 遗传算法的产生和国内外研究现状11.2 遗传算法的基本原理21.3遗传算法的特点31.4遗传算法的应用41.5课题的任务6第二章基本遗传算法72.1 基本遗传算法简介72.2 基本遗传算法描述72.3 基本遗传算法的实现10第三章遗传算法求解TSP153.1 旅行商问题概述153.2 使用改进的遗传算法求解TSP16第四章求解TSP的实验结果及分析264.1实验环境264.2算法在求解不同规模下的TSP的实验结果264.3改良的遗传算法和其它智能优化算法的比较274.4使用单一变异算子和混合变异算子的实验结果对比分析28第五章总结30参考文献32附录1改良遗传算法求解TSP Java源程序33附录2英文文献翻译50致谢56- III -第一章 遗传算法概论1.1 遗传算法的产生和国内外研究现状 遗传算法（Genetic Algorithm简称GA）美国的J. Holland教授于1975年在他的专著自然界和人工系统的适应性中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法1 。 遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体（优胜劣汰），利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。最后一代候选解群中的最优解就是所求得的最优解。1991年D.Whitey在他的论文中提出了基于领域交叉的交叉算子（Adjacency based crossover），这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了（旅行商）TSP问题中，通过实验对其进行了验证。D.H.Ackley等提出了随机迭代遗传爬山法（Stochastic Iterated Genetic Hill-climbing，SIGH）采用了一种复杂的概率选举机制，此机制中由m个“投票者”来共同决定新个体的值（m表示群体的大小）。实验结果表明，SIGH与单点交叉、均匀交叉的神经遗传算法相比，所测试的六个函数中有四个表现出更好的性能，而且总体来讲，SIGH比现存的许多算法在求解速度方面更有竞争力2。H.Bersini和G.Seront将遗传算法与单一方法（simplex method）结合起来，形成了一种叫单一操作的多亲交叉算子（simplex crossover），该算子在根据两个母体以及一个额外的个体产生新个体，事实上他的交叉结果与对三个个体用选举交叉产生的结果一致。同时，文献还将三者交叉算子与点交叉、均匀交叉做了比较，结果表明，三者交叉算子比其余两个有更好的性能。国内也有不少的专家和学者对遗传算法的交叉算子进行改进。2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题2004年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现象，提出了一种用基因块编码的并行遗传算法（Building-block Coded Parallel GA，BCPGA）。该方法以粗粒度并行遗传算法为基本框架，在染色体群体中识别出可能的基因块，然后用基因块作为新的基因单位对染色体重新编码，产生长度较短的染色体，在用重新编码的染色体群体作为下一轮以相同方式演化的初始群体。2005年，江雷等针对并行遗传算法求解TSP，探讨了使用弹性策略来维持群体的多样性，使得算法跨过局部收敛的障碍，向全局最优解方向进化。1.2 遗传算法的基本原理1.2.1遗传算法的基本术语由于遗传算法的研究与应用尚在不断发展之中，有关术语的运用尚未完全取得统一。为了在下面的研究中做到准确、清晰、规范的描述，对本文使用到的遗传算法术语解释如下3：个体(individual)：遗传算法中处理的基本对象、数据结构，对应于自然遗传学中的生物个体。种群( population)：个体的集合，对应于自然遗传学中的生物种群。种群大小( population size)：种群中个体数目称为种群大小。位串( bit string)：也叫染色体（chromosome），个体特征的表现形式，对应于自然遗传学中的染色体。基因( gene)：位串中的元素，表示不同的特征，对应于生物学中的遗传物质单位，以DNA序列形式把遗传信息译成编码。基因位( locus)：某一基因在位串（染色体）中的位置适应度(fitness)：某一个体对于环境的适应程度，或者在环境压力下的生存能力，取决于遗传特性。适应度函数（fitness function）：为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数，适应度函数是计算个体在种群中被使用的概率。遗传操作（genetic operator）：遗传算法中有三种关于染色体的运算：选择、交叉和变异，这三种运算被称为遗传操作。选择（selection）操作：选择（selection）操作是模拟生物界优胜劣汰的自然选择法则，从种群中选择适应度较好（较好可能是高于种群的平均适应度也可能是低于种群的平均适应度，取决于要解决的问题和使用什么作为适应度）的个体来生成下一代种群进行交叉变异。交叉(crossover)操作：交叉就是互换两个染色体某些位上的基因以产生新的个体，普通遗传算法中常用的交叉算子有单切点交叉、双切点交叉、循环交叉。变异(mutation)操作：位串中的基因发生变化，发生在同一个个体之内，常见的变异有交换（两个基因交换位置）、倒序（位串上的某一段基因位置反转）、插入（位串上的某一个基因被插入到位串中的其它位置）。交叉率：发生交叉运算的个体个数占全体个体总数的比例，取值范围一般为0.40.99。变异率：发生变异的基因位数所占全体个体的基因总位数的比例，取值范围一般为0.00010.1。1.2.2遗传算法的基本原理遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。在遗传算法中问题的解被表示成“染色体”，在算法中也即是以二进制编码或实数编码的串4。并且，在执行遗传算法之前，随机给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，设定相应的适应度函数，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体” 群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，得到问题的最优解或者近似最优解。1.3遗传算法的特点1、遗传算法的处理对象不是参数（优化问题的参变量）本身，而是对参数集进行了编码的个体。这种编码操作，使得遗传算法可直接对结构对象进行操作（所谓结构对象泛指集合、序列、矩阵、树、图、链和表等各种一维或高维结构形式）。这一特点使得遗传算法具有广泛的应用领域，例如：通过对连接矩阵的操作，遗传算法可用来对神经网络或自动机的结构或参数加以优化。通过对集合的操作，遗传算法可实现对规则集合或知识库的精练而达到高质量的机器学习目的5。通过对树结构的操作，遗传算法可得到用于分类的最佳结构树。通过对任务序列的操作，遗传算法可用于任务规划，而通过对操作序列的处理，遗传算法可自动构造顺序控制系统。 2、遗传算法的基本作用对象是多个可行解的集合，而非单个可行解。它是采用同时处理群体中多个个体的方法，即同时对搜索空间中的多个解进行评估。这一特点使遗传算法具有较好的全局搜索性能，减少了陷于局部优解的可能性。同时这又使得遗传算法本身具有良好的并行性。3、遗传算法仅用适应度函数值来评估个体，而无须搜索空间的知识或其它辅助信息。遗传算法的适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。对适应度函数的唯一要求是，对于输入可计算出能够进行比较的输出。遗传算法的这一特点使它的应用范围极大拓宽，使之可广泛应用于目标函数不可微、不连续、非规划、极其复杂或无解析表达式等类优化问题。4、遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索方向。遗传算法执行选择、交叉、变异等类似生物进化过程的简单随机操作，具有极强的鲁棒性。需要指出，遗传算法采用概率仅仅是作为一种工具来引导其搜索过程朝着搜索空间的更优的解的区域移动。因此尽管看起来它是一种盲目的搜索方法，但实际上有明确的搜索方向。 1.4遗传算法的应用遗传算法由于具有鲁棒性强，实现简单，对问题依赖性小等优点，为求解复杂系统优化问题提供了通用框架，下面是一些主要应用领域：（1）函数优化：是GA的经典应用领域，也是对GA进行性能评价的常用算例，对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，GA却可以得到较好的结果。（2）组合优化6：随问题规模的扩大，搜索空间急剧扩大，对这类复杂问题，实践证明，GA对于组合优化的NP完全问题非常有效。例如求解TSP。（3）生产调度问题：GA已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规模、人物分配等方面都得到了有效的应用。（4）自动控制：GA在自动控制领域中的应用日益增加，并显示了良好的效果。如在参数辨识、人工神经网络的结构优化设计和权值学习，都显示了GA的应用优势。（5）机器人智能控制：GA是源自于对人工自适应系统的研究，已经在移动机器人路径规划、关节机器人运动轨迹规律、机器人逆运动学求解、细胞机器人的结构优化和行动协调等方面得到研究和应用。（6）图像处理和模式识别：在图像处理过程中，如扫描、特征提取、图像分割等不可避免的会产生一些误差。目前，GA已在图像恢复、图像边缘特征提取、几何形状识别等方面得到了应用。（7）人工生命7：基于GA的进化模型是研究人工生命现象的重要理论基础，已在其进化模型、学习模型、行为模型等方面得到应用。（8）遗传程序设计：Koza发展了遗传程序设计，基本思想是：采用树型结构表示计算机程序，运用遗传算法的思想，通过自动生成计算机程序来解决问题。虽然该理论尚未成熟，应用也有些限制，但已成功地应用于人工智能、机器学习等领域。（9）机器学习：基于GA的机器学习、特别分类器系统，在调整人工神经网络的连接权、神经网络结构的优化设计、和多机器人路径规划系统中得到了成功的应用。（10）生物信息学：多重序列比对是生物信息学的重要研究内容，它的目标是通过同时比较多个序列，发现它们之间的相似区域和保守性位点, 进而推断未知生物分子的结构和功能， 或者重构系统发育树，寻找物种之间的进化关系8。遗传算法也是一种启发式算法，它由于能够避免算法陷入局部最优解而受到人们的重视，在生物序列多重比对中也有一定的应用9。1.5课题的任务1.5.1旅行商问题简介旅行商问题（Traveling Saleman Problem，TSP）又译为旅行推销员问题、货郎担问题，简称为TSP，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig（1959）等人提出10。顾名思义，旅行商问题就是有一个推销员，要到n个城市推销商品，最后再回到出发点，为了节约时间和成本，他想找出一个包含所有n个城市并且总路径（包括回到出发点）最短的环路。1.5.2课题任务进行本课题研究是想通过学习遗传算法的理论基础，实现和优化技术来掌握一种实现计算机模拟自然的智能优化算法。研究的内容包括：遗传算法的发展历史、研究现状、基本原理、基本实现技术及应用前景。拟解决的问题主要有：1、 使用基本遗传算法求解旅行商问题（TSP）。2、 在基本遗传算法基础上，对算法加以改进，加快算法的收敛速度和提高解的质量。3、 尝试多种改进方法，分析不同的改进策略对算法的收敛速度和解的质量的影响。第二章基本遗传算法2.1 基本遗传算法简介基于对自然界中生物遗传与进化机理的模仿，针对不同的问题，很多学者设计了许多不同的编码方法来表示问题的可行解，开发出来许多种不同的遗传算子来模仿不同环境下的生物遗传特性。这样，由不同的编码方法和不同的遗传算子就构成了各种不同的遗传算法。但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中的选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。基于这个共同特点，Goldberg总结出了一种统一的最基本的遗传算法基本遗传算法（Simple Genetic Algorithms，简称SGA）。基本遗传算法只使用选择算子、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的（皱）行和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值11。2.2 基本遗传算法描述2.2.1基本遗传算法的形式化定义基本遗传算法可定义为一个8元组：SGA=（C,E,P0,M,O,R,W,T）(2-1)式中：C 个体的编码方法；E个体适应度评价函数；P0初始种群；M种群大小；O选择算子；R交叉算子；W变异算子；T算法终止条件； 2.2.2基本遗传算法的流程图 图 2-1 SGA流程图基本遗传算法(SGA)流程如下：（1） 随机初始化种群（2） 计算种群中各个个体的适应度（3）根据个体的适应度选择优良的个体保留下来，作为下一代种群，并保持种群大小不变（使用优良个体的位串覆盖被淘汰被的个体的位串）。（4）对种群中的个体进行随机两两配对（若种群大小为M，则有M/2对），然后根据交叉概率从配对的个体中选出一部分执行交叉操作。（5）根据变异概率从种群中选出一部分个体执行变异操作（6）若没有达到算法终止条件（比如达到最大迭代次数或者种群的多样性降低到一定程度）则跳转到第2步，继续执行下面操作，否则跳转到第7步（7）输出最优解或者近似最优解2.2.3基本遗传算法的伪代码SGA算法伪代码如下：Procedure SGAbegin/算法开始initialize P(0)/初始化种群t=0;/当前迭代次数小于预设的最大迭代次数时，循环做下面的遗传操作while(t=T)dofor i=1 to M do /计算第t代种群中各个个体的适应度Evaluate fitness of P(t);end forfor i=1 to M do/执行选择算子/选择当前种群中的优良个体并复制到下一代种群，进行下一轮遗传操作Select operation to P(t);end forfor i=1 to M/2 do/执行交叉操作Crossover operation to P(t);end forfor i=1 to M do/执行变异操作Mutation operation to P(t);end fort=t+1;end whileend/算法结束2.3 基本遗传算法的实现2.3.1个体的编码方法在遗传算法的运行过程中，它不对所求解问题的实际决策变量自己进行操作，而是对表示可行解的个体编码施加选择、交叉、变异等遗传运算，通过这种遗传操作来达到优化的目的，这是遗传算法的特点之一。遗传算法通过对这种个体编码的操作，不断搜索出适应度较高的个体，并在群体中逐渐增加其数量，最终寻求出问题的最优解或近似最优解。在遗传算法中如何让描述问题的可行解，即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法就称为编码。对于设计编码方案，De Jong 曾提出了两条操作性较强的实用编码原则：编码原则一（有意义积木块编码原则）： 应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案。编码原则二（最小字符集编码原则）： 应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案。由于遗传算法应用的广泛性，迄今为止人们已经提出了许多种不同的编码方法。总的来说，这些编码方法可以分为三大类：二进制编码方法、浮点数编码方法、符号编码方法。下面介绍旅行商问题（TSP）采用的符号编码方法：假设有n个城市，分别记为C1、C2、Cn，将各个城市的代号按其被访问的顺序连接在一起，就可构成一个表示旅行路线的个体。如：Xt=C1,C2,C3,Cn就表示顺序访问城市C1，C2，C3，.,Cn。若将各个城市按其代号的小标进行编号，则这个个体也可以表示为Xt=1,2,n 这种编码方案问题得到自然表示符合上述两个编码原则，并且便于与相关近似算法（如模拟退火算法）混合使用。2.3.2运行参数设定基本遗传算法有下述四个运行参数需要提前设定：M：群体大小，即群体中所含个体的数量，一般取20-100T：遗传运算的终止进化代数，它表示算法运行到指定的进化代数之后就停止运行。Pc：交叉概率，一般取为0.4-0.99。Pm：变异概率，一般取为0.00001-0.1。需要说明的是，这四个运行参数对遗传算法的求解结果的质量和求解效率都有一定的影响，但目前尚无合理选择它们的理论依据，在遗传算法的实际应用中往往需要经过多次试算后才能确定出这些参数合理的取值大小或取值范围。2.3.3种群初始化基本遗传算法的初始种群一般采用随机生成，假设种群大小为M，则随机生成M个个体（实际上就是随机生成M个位串）组成初始种群。2.3.4个体适应度评价在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某个物种对于其生存环境的适应程度。对生存环境适应程度较好的物种将有更多的繁殖机会；而对生存环境适应度较差的物种，其繁殖机会就相对较少，甚至会逐渐灭绝。与此相类似，遗传算法中也使用适应度这个概念来度量群体中各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概率就较大；而适应度较低的个体遗传到下一代的概率就相对小一些。度量个体适应度的函数称为适应度函数（Fitness Function）。遗传算法的一个特点是它仅使用所求问题的目标函数值就可以得到下一步的有关搜索信息。而对目标函数值得使用是通过评价个体的适应度来体现的。评价个体适应度的一般过程是：（1） 对个体编码串进行解码处理后，可得到个体的表现型。（2） 由个体的表现型可计算出对个体的目标函数值。（3） 根据最优问题的类型，由目标函数值按一定的转换规则求出个体的适应度。例如n个城市旅行商问题（TSP）中，用来表示个体适应度的就可以是按个体的位串表示的巡回这n个城市的顺序的环路总距离。2.3.5选择算子选择（selection）操作是模拟生物界优胜劣汰的自然选择法则的一种染色体运算，就是从种群中选择适应度较高的染色体进行复制，以生成下一代种群。最常用的选择策略是赌轮选择策略。赌轮选择的基本思想：做一个轮盘，然后按照各个染色体的个体适应度比例转化为选中概率(选择概率)，将轮盘分成若干个扇区，随机地产生0, 1 之间的随机数，这样就相当于转动轮盘，获得转盘停止时指针位置，指针停止在某一扇区，该扇区代表的个体即被选中。这里选择概率的计算公式：P(xi)= (2-2)其中f为适应度函数，f(xi)为的适应度注：此公式只适应于选中概率与适应度值大小成正比的情况（也就是适应度值越大表示适应度越优），对于某些适应度值越小表示的适应度越优的情况，需要使用下面公式：P(xi)= (2-3)其中f为适应度函数，f(xi)为的适应度2.3.6交叉算子遗传算法中的交叉操作是先对种群中的个体进行随机两两配对（若种群大小为M，则有M/2对），然后根据交叉概率从配对的个体中选出一部分 （Pc*（M/2）对）执行交叉。交叉就是互换两个染色体某些位上的基因以产生新的个体。基本遗传算法中常用的交叉算子有单切点交叉、双切点交叉12、循环交叉，下面我们来进行依次介绍（1）单切点交叉（single-point crossover）单切点交叉的思想是从种群中选出两个个体P1和P2，随机地选择一个切点（cutting），将切点两侧分别看成一个子串，将右侧的子串分别进行交换，这样就得到了两个新的个体C1和C2。P1和P2其中称为父代染色体，C1和C2称为子代染色体。 切点 切点C1= A1 A2|B3 B4C2 = B1 B2|A3 A4P1=A1 A2A3 A4P2=B1 B2B3 B4 图2-2单切点交叉单切点交叉操作的信息量比较小，交叉位置的选择可能带来较大的偏差，并且染色体末尾的基因总是被交换。（2）双切点交叉（double-point crossover）双切点交叉的思想是从种群中选出两个个体P1和P2，随机地选择两个切点（cutting），交换两个切点之间的子串，从而得到了新一代的染色体。 切点 切点 切点 切点P1=A1B2A3P2=B1A2B3P1=A1A2A3P2=B1B2B3 图2-3双切点交叉（3）循环交叉（cycle crossover）循环交叉的基本思想是子串位置上的值必须与父母相同位置上的值相等。循环交叉操作的具体步骤如下：选P1的第一个元素作为C1的第一个元素；选P2的第一个元素作为C2的第一个元素；在P1中找P2的第一个元素赋给C1的相对位置重复此过程，直到P2上得到P1的第一个元素为止，称为一个循环；对最前的基因按P1、P2基因轮替原则重复以上过程；重复以上过程，直至所有位已完成。 C1=2 _ _3 _ _ 6 _ _C2= 3 _ _6_ _ 2 _ _循环2：9-4P1=2 4 5 3 8 9 6 1 7P1=3 9 8 6 5 4 2 7 1循环1：2-3-6C1=2 9 5 3 8 4 6 _ _C2= 3 4 8 6 5 9 2 _ _循环4：71 C1=2 9 _ 3 _ 4 6 _ _C2= 3 4 _ 6 _ 9 2 _ _循环3：58C1=2 9 5 3 8 4 6 7 1C2=3 4 8 6 5 9 2 1 7 图2-4循环交叉 2.2.7变异算子变异本身是一种局部随机搜索，与选择、交叉算子结合在一起，保证了遗传算法的有效性，使遗传算法具有局部的随机搜索能力；同时使得遗传算法保持种群的多样性，以防止出现非成熟收敛。在变异操作中，变异率不能取得太大，如果变异率大于0.5，遗传算法就退化为随机搜索，而遗传算法的一些重要的数学特性和搜索能力也不复存在了。最常用的变异操作是按位交换变异，它的基本思想：对于同一个个体的基因如果发生变异，则随机与同一个个体的另一个基因交换位置。其它常见的变异操作如：倒序（位串上的某一段基因位置反转）、插入（位串上的某一个基因被插入到位串中的其它位置）。2.2.8终止条件遗传算法最简单的终止条件就是设定终止代数，当算法的迭代次数大于终止代数时就停止迭代，算法结束。除此之外还可以利用某种判定准则，当判定种群已经进化成熟且不再有进化趋势时（即解已经收敛到一个稳定值）就可以终止算法的运行。常有的判定准则有下面两种：1、 连续几代个体平均适应度的差异小于某一极小的阀值；2、 群体中所有个体适应度的方差小于某一个极小的阀值第三章遗传算法求解TSP 本章介绍使用一种求解TSP的改进遗传算法（Improved genetic algorithm 简称IGA），相对与基本遗传算法所做的改良策略主要有下面两个方面：1、选择操作采用了最优保存策略：首先使用最优种群保存了用当前最优个体和前面数次（最优种群群体大小-1次）迭代的种群中的最优个体，然后从最优种群中随机选择部分个体（保证当前最优个体一定被选择）来覆盖当前种群中被淘汰的个体。这样就保证了当前最优个体不会丢失，加快了算法的收敛速度。同时还加大了最优个体的变异率，保持种群多样性，这样有效的防止了算法陷入局部最优解而早熟，提高了解的质量。2、采用多种变异算子混合的策略：变异操作由交换变异、倒序变异和插入变异三种变异算子混合。混合的方法是，每次执行变异操作之前，先生成0-2的随机数，然后根据生成的随机数来选择此次使用哪种变异方式。3.1 旅行商问题概述3.1.1 旅行商问题的描述顾名思义，旅行商问题（Traveling salesman problem简称TSP）就是有一个推销员，要到n个城市推销商品，最后再回到出发点，为了节约时间和成本，他想找出一个包含所有n个城市并且总路径（包括回到出发点）最短的环路。3.1.2旅行商问题的数学模型旅行商问题的数学模型可以描述为：对于n个城市V=v1,v2,vn的一访问次序为T=(t1,t2,tn), tiVi（i=1，2,，n）,tn+1 = t1,则问题即要求min，其中表示城市 i与城市i+1 之间的距离。3.1.3 旅行商问题的复杂度对于TSP这样的一个典型的组合优化问题，最为普通的一种解决办法就是穷举出所有可能的合法序列，然后比较距离函数，得出最优的城市序列。这就是穷举搜索法的思想，理论上它可以解决任何组合优化问题，但是对于n个城市的TSP来说，从任何一个城市出发，经过n-1个城市各一次后在回到出发点，可能的合法回路有(n-1)!条,计算每一条路径需求n个距离之和，因此计算量正比于n!。因此这是一个NP难问题。下面我们就看下使用穷举法解决TSP的难度到底有多大。1、假设现在求解100个城市的TSP，则根据上面的结论，使用穷举法解决这个问题需要做(100)!也就是9.33次加法运算。2、假设使用世界运算速度最快的超级计算机，即拥有每秒钟4700万亿次（即4.7）的运算峰值速度由我国自主研发的“天河一号”超级计算机来穷举搜索（并假设一次运算就可以求两个城市之间的距离和足够大的存储空间）也需要6.30年的时间。也正因为TSP是一个NP难问题，使用穷举法求解城市个数较多（如100个以上）的TSP是不可能的（需要的时间极长）。这就为遗传算法的应用提供了机会，下面我们就来看一求解TSP问题的改进遗传算法。3.2 使用改进的遗传算法求解TSP3.2.1个体的编码和解码前面已经介绍过遗传算法的编码方法可以分为三大类：二进制编码方法、浮点数编码方法、符号编码方法。这里在求解TSP中采用自然数的符号编码，对于n个城市的TSP，采用1-n的自然数编码，分别表示第1到第n个城市。例如n=8时，位串：Xt= 2 3 1 5 4 7 6 8 表示2-3-1-5-4-7-6-8-2的一条旅行路线这种编码是问题能得到自然表示，相当方便。但要注意的是在进行交叉操作的时候可能产生不合法个体，因此需要对编码进行合法性检查，并对不合法的个体进行合法性修复。例如：Px= 2 3 1 5 4 7 6 8 和Py= 8 2 3 4 5 6 7 1 执行单切点交叉：Px= 2 3 1 5 4 7 | 6 8 Cx= 2 3 1 5 4 7 7 1Py= 8 2 3 4 5 6 | 7 1 Cy=8 2 3 4 5 6 6 8交叉直接得到的是两个不合法的个体，需做合法性修复，修复后的结果如下： Cx= 2 3 8 5 4 6 7 1 Cy= 1 2 3 4 5 7 6 8 具体的修复过程，在后面交叉操作中有详细讲解。解码就是求出一条染色体所对应的路径长度的过程。如：一染色体X的顺序实数编码为（2 3 1 5 4 7 6 8），解码就是要把相邻两点的距离进行求和，具体地说就是要把2与3，3与1，1与5，5与4，4与7，7与6，6与8,8与2之间的距离相加，相加的结果就是由解码得到的路径长度。3.2.2个体的数据类型定义个体(individual)是遗传算法中处理的基本对象、数据结构，对应于自然遗传学中的生物个体。在实现算法之前需要定义个体的数据类型Genotyoe类，这个类包含下面几个成员：1、 个体的位串：个体特征的表现形式，在TSP中就是表示访问城市的顺序的编码串。例如： n个城市的TS