遗传算法综述

遗传算法综述摘要遗传算法(GeneticAlgorithm,GA)是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法，其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。本文从遗传算法的起源谈起，论述了遗传算法的基本思想和基本原理，并对其性能和收敛性进行了分析，最后还介绍了几种改进的遗传算法及其在求解旅行商问题(TSP)方面的应用。关键词：遗传算法；搜索算法；TSP；遗传算法收敛性1引言在自然界中，生物要生存下去，就必须进行生存斗争。在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少得多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存，不适者淘汰的过程叫做自然选择。遗传算法是根据这种生物的自然进化思想而启发得出的一种全局优化算法。遗传算法是由美国的J.Holland教授于1975年在他的专著《自然和人工系统的适应性》中首先提出的，他将遗传算法应用于函数优化中，设计了遗传算法执行策略和性能评价指标。1989年，Goldberg出版了专著《搜索、优化和机器学习中的遗传算法》，系统总结了遗传算法的主要研究成果，全面完整的论述了遗传算法的基本原理和应用，奠定了现代遗传算法的科学基础。遗传算法，在本质上是一种不依赖具体问题的直接搜索方法，是一种求解问题的高效并行全局搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、负载平衡、电磁系统设计、生物科学、社会科学等方面都得到了应用。在人工智能研究中，现在人们认为“遗传算法、自适应系统、细胞自动控制、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”。目前在遗传算法的研究中，尽管还存在一些有争议的问题，甚至还有某些截然不同的学术观点和设计原则，一时尚难统一，整个遗传算法的理论基础还比较薄弱，但是很多实例及应用充分表明，模拟自然进化的搜索过程往往可以产生非常简单、通用和鲁棒性很强的计算方法。如今，无论是对遗传算法的理论研究还是应用研究都分外活跃。2遗传算法的特点2.1遗传算法的基本思想遗传算法抽象于生物体的进化过程，通过全面模拟自然选择和遗传机制，形成一种具有“生成+检验”特征的搜索算法。遗传算法以编码空间代替问题的参数空间，以适应度函数为评价依据，以编码群体为进化基础，以对群体中个体位串的遗传操作实现选择和遗传机制，建立起一个迭代过程。与传统搜索算法不同，遗传算法从一组随机产生的初始解（称为种群）开始搜索过程，群体中的每个个体是问题的一个解（称为染色体），这些染色体在后续迭代中不断进化（称为遗传）。遗传算法是从编码工作开始的，一开始需要实现从表现型到基因型的映射（即编码），初始种群产生后，遗传算法主要通过选择、交叉、变异实现运算。通过运算生成下一代染色体（称为后代）。染色体好坏用适应度来衡量，根据适应度的大小从上一代和后代中选择个体，作为下一代群体，再继续进化。这样经过若干代之后，算法收敛于最好的染色体，它很可能就是问题的最优解或次优解。2.2遗传算法的主要特点根据达尔文的自然选择学说和孟德尔的遗传变异学说建立起来的遗传算法是一种鲁棒的、自适应的、开放性的随机优化算法。遗传算法的优化对象是参数的编码而非参数本身。遗传算法对一些个体进行进化操作，这些个体是基于某种编码方式而获得的位串，因此遗传算法首先有一个有限的字母表。通常遗传算法的编码方式是基于二进制的编码。遗传算法通过适应值函数即目标函数来计算每个个体的适应值大小，而不需要其它有关问题的信息和推导，算法的独立性强，使得遗传算法能够形成一种通用算法框架，在处理完全不同的问题时，仅需要稍加修改就可以移植使用，降低了推广的成本。遗传算法的寻优规则是由概率确定的，而非确定性的。算法的目标函数给出一个进化的方向和目标，但算法以何种路径进行搜索则是概率确定的。因此遗传算法被称为是一种随机优化算法。但这点并不意味着遗传算法是完全地进行随机搜索。遗传算法在解空间中进行高效的启发式搜索，而不是盲目地穷举或者完全随机的搜索。由上所述可知，遗传算法与传统优化方法相比有以下特点：（1）遗传算法的自组织、自适应性（智能性）。应用遗传算法求解问题时，在编码方案、适应度函数及遗传算子确定后，算法将得用进化过程中获得的信息自行组织搜索。由于基于自然的选择策略为“适者生存，不适应者初淘汰”，因而适应度大的个体具有较高的生存概率。通常，产生更适应环境的后代。遗传算法的这种自组织、自适应特征，使它同时具有能根据环境变化来自动发现环境的特性和规律的能力。（2）遗传算法的并行性。它的并行性表现在两个方面：一是遗传算法是内在并行的即遗传算法本身非常适合大规模并行。最简单的并行方式是让数台计算机各自进行独立种群的演化计算，等到运算结束时才通信比较，选取最佳个体。遗传算法适合在目前所有的并行机或分布系统上进行并行处理，而且对并行效率没有太大的影响。二是遗传算法的内含并行性。遗传算法按并行方式搜索一个种群数目的点，而不是单点。由于遗传算法采用种群的方式组织搜索，因而可以同时搜索空间内的多个区域，并相互交流信息。（3）遗传算法的处理对象不是参数本身，而是对参数集进行了编码的个体。此编码操作使得遗传算法可直接对结构对象进行操作。（4）在标准的遗传算法中，基本上不需要其他的辅助信息，而仅用适应度函数值来评估个体，并在此基础上进行遗传操作。它尤其适用于处理传统优化算法难于解决的复杂和非线性问题。3遗传算法的理论基础模式定理与积木块假设构成了遗传算法的基础理论，虽然它们还存在缺陷，但了解模式定理有助于理解遗传算法的优化机理。3.1模式定理模式是指种群个体基因串中的相似样板，它用来描述基因串中某些特征位相同的结构。在二进制编码中，模式是基于三个字符集（0,1,*）的字符串，符号*代表任意字符，即0或者1。例如：模式*001描述了在位置2、3、4具有形式“001”的所有字符串，即｛0001,1001｝。这里，我们先给出模式的两个重要概念：模式阶和定义距。模式中确定位置的个数称为模式的阶，例如（10**1）的阶为3。模式中第一个确定位置和最后一个确定位置之间的距离称为模式的定义距，例如（10**1）的定义距为4。模式定理表述如下：具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。模式定理保证了较优的模式（遗传算法的较优解）的数目呈指数增长，为解释遗传算法机理提供了数学基础。模式定理阐述了遗传算法的理论基础，不仅说明了模式的增加规律，而且也给遗传算法的应用提供了指导作用。但需要指出的是，模式定理是在研究函数优化过程中，基于二进制编码方案得出的，对于其它的编码方式，模式定理不一定适用。此外，还应指出的是，模式定理本身还存在一定缺陷，定理还不够完善。3.2积木块假设模式定理说明了具有某种结构特征的模式在遗传进化过程中其样本数将按指数级增长，这种模式就是具有低阶、短的模式定义长度，且平均适应度高于群体平均适应度的模式。这种类型的模式被称为基因块或积木块（buildingblock）。之所以称之为积木块，是由于遗传算法的求解过程并不是在搜索空间中逐一地测试各个基因的枚举组合，而是通过一些较好的模式，像搭积木一样，将它们拼接在一起，从而逐渐地构造出适应度越来越高的个体编码串。积木块假设：遗传算法通过短定义距、低阶以及高平均适应度的模式，在遗传操作下相互结合，最终接近全局最优解。模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在；而积木块假设则指出遗传算法有能力使优秀的模式向着更优的方向进化，即遗传算法有能力搜索到全局最优解。目前为止，绝大多数的遗传算法的实践和应用都支持积木块假设，如组合优化问题、平滑多峰问题以及带干扰多峰问题等。然而，积木块假设始终没能得到一个数学上的证明。4遗传算法的基本原理4.1遗传算法的基本流程遗传算法在整个进化过程中的遗传操作是随机性的，但它所呈现出的特性并不是完全随机搜索，它能有效地利用历史信息来推测下一代期望性能有所提高的寻优点集。这样一代代地不断进化，最后收敛到一个最适应环境的个体上，求得问题的最优解。概括地讲，遗传算法的操作步骤是：（1）确定个体的字符串的组成及长度。（2）随机建立初始群体。（3）计算各个体的适应度。（4）根据遗传概率，用下述操作产生新群体：（i）复制，将已有的优良个体复制后添入新群体中，删除劣质个体。（ii）交换，将选出的两个个体进行交换，所产生的新个体进人新群体。（iii）突变，随机地改变某个体的某一字符后，将新个体添入新群体。（5）反复执行（3）及（4），直至达到终止条件，选择最佳个体作为遗传算法的结果。简单遗传算法的基本流程如图1所示。

图1遗传算法基本流程图遗传算法由五大要素组成：参数编码、初始群体的设定、适应度函数的设计、遗传操作的设计和控制参数的设定。这五个要素构成了遗传算法的核心内容。下面我们分别对它们作比较详细的论述。4.2遗传编码机制编码机制是GA的基础。GA不是对研究对象直接进行讨论，而是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。编码机制实际上是个体在问题空间与GA空间相互映射，图2较好的阐述了这一机理。图2中GA空间的染色体用二进制编码，表现型为问题空间中实际数值。基因型：100101110110101000111编码解码表现型：1240391图2二进制编码与解码评估编码策略常采用以下3个规范：（1）完备性：问题空间中的所有点（候选解）都能作为GA空间中的点（染色体）表现。（2）健全性：GA空间中的染色体能对应所有问题空间中的候选解。（3）非冗余性：染色体和候选解一一对应。上述的3个评估规范是独立于问题领域的普遍准则。因此，对于某个具体的应用领域而言，应该客观地比较和评估该问题领域中所用的编码（加交叉）的方法，由此得到更好的方法或策略。二进制编码是一种最为常用的编码形式，这种编码简单易用，著名的模式定理也是基于二进制编码而提出的。此外，还有灰度编码、实数编码、符号编码等。下面对这几种传统的编码方式分别进行介绍。1）二进制编码首先介绍二进制编码的原理和实现。例如有如下约束条件：xE[-1,2]，求解结果精确到6位小数。这时如要使用二进制编码，则可将自变量定义区间划分为3x106等份。又因为221<3x106<222，所以二进制编码长度至少需要22位。一般来说，编码长度越长，则精度越高，对应得到的解的质量也越高，意味着解更为优良，但同时，由于遗传操作所需要的计算量也更大，因此算法的耗时将更长，效率相应降低。因此在解决实际问题时，编码位数需要适当选择。2）灰度编码在二进制编码中存在一个问题，即在某些情况下空间的拓扑连续性会被打断。如编码串“0111”和“1000”，其基因结构截然相反，但是解码之后所对应的实数却非常接近，分别为7和8。又如编码串“1000”和“0000”，其基因结构非常相似，仅相差一个基因位，但所对应的实数或相差甚远，分别为8和0。这种现象打破了原空间的拓扑连续性。灰度编码就是为了解决这一问题而提出的另一种二进制编码，它实际上是由原二进制编码经过某种变换而产生的。这种由二进制编码到灰度编码的变换可以用公式描述为：:g广ag=a㊉g,i=L一1,L一2,.・・,1lii+1i上述公式中的㊉表示异或运算。根据灰度编码规则，将原二进制编码“0111（7）”和“1000（8）”变换全灰度码我们可以得到其所对应的灰度码分别为“0100（7）”和“1100（8）”。此时我们可以发现，在实数空间中连续的两个值的灰度编码也保持了空间的拓扑连续性。3）实数编码基于二进制编码的个体尽管操作方便，计算简单，但也存在着一些难以克服的困难而无法满足所有问题的要求。如对于高维、连续优化问题，由于从一个连续量离散化为一个二值量本身存在误差，使得算法很难求得精确解。而要提高解的精度又必须加长编码串的长度，从而增加了编码的组合方式，造成解空间扩大，算法效率下降。同时，二进制编码也不利于反映所求问题的特定知识，对问题信息和知识利用得不充分也会阻碍算法效率的进一步提高。为了解决二进制编码产生的问题，人们在解决一些数值优化问题尤其是高维、连续优化问题时，经常采用实数编码方式。实数编码的优点是计算精确度高，便于和经典连续优化算法结合，适用于数值优化问题。但其缺点是适用范围有限，只能对连续变量问题使用。4）符号编码符号编码是指组成个体编码串的码值无数值含义而仅有字符含义。当然，码值本身或者字母表中的各种码值可能以数字形式出现，但其代表的意义则只能是字。许多组合优化问题所采用的编码形式经常是符号编码。符号编码的优点在于便于利用专门问题已有的先验知识和信息，同时形式可以变化多样，因而可以处理各种非数值优化问题和组合优化问题，其不足之处在于针对性地设计遗传操作显得复杂一些。4.3初始群体设定遗传操作是对众多个体同时进行的。这众多的个体组成了群体。在遗传算法处理流程中，继编码设计后的任务是初始群体的设定，并以此为起点一代代进化直到按某种进化停止准则终止进化过程。一般来说，遗传算法中初始群体的个体是随机产生的。初始群体的设定可采取如下的策略：（1）根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。（2）先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数达到了预先确定的规模。群体规模越大，群体中个体的多样性越高，算法陷入局部解的危险就越小。所以，从考虑群体多样性出发，群体规模应较大。但是，群体规模太大会带来若干弊病：一是从计算效率着眼，群体越大，其适应度评估次数增加，所以计算量也增加，从而影响算法效能；二是群体中个体生存下来概率大多采用和适应度成比例的方法，当群体中个体非常多时，少量适应度很高的个体会被选择而生存下来，但大多数个体却被淘汰，这会影响配对库的形成，从而影响交叉操作。另一方面，群体规模太小，会使遗传算法的搜索空间中分布范围有限，因而搜索有可能停止在未成熟阶段，引起未成熟收敛现象。显然，要避免未成熟收敛现象，必须保持群体的多样性，即群体规模不能太小。4.4适应度函数遗传算法在进化搜索中基本上不用外部信息，仅用适应度函数为依据。在GA中，用适应度函数描述每一个体的适宜程度。引进适应度函数的目的在于可根据其适应度对个体进行评估比较,定出优劣程度。适应度函数值越大，解的质量越好。遗传算法的目标函数不受连续可微的约束且定义域可以为任意集合。对适应度函数的唯一要求是，针对输入可计算出能加以比较的非负结果。这一特点使得遗传算法应用范围很广。在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。适应度函数评估是选择操作的依据、适应度函数设计直接影响到遗传算法的性能。适应度函数设计主要满足以下条件：（1）单值、连续、非负、最大化。（2）合理、一致性。（3）计算量小。（4）通用性强。常见的适应度函数构造方法有：（1）目标函数映射成适应度函数。（2）作基于序的适应度函数。可以根据染色体的序进行再分配，而不是根据其实际的目标值。无论何种数学规划都可以作一合理假设，即在染色体中，决策者可以给出一个序的关系，使染色体由好到坏进行排序，由此决定适应度函数。只要保证越好的染色体，适应函数越大。（3）通过适当缩放调整来设计适应度函数（即适应度定标）。遗传算法由于仅靠适应度来评估和引导搜索，所以求解问题所固有的约束条件不能明确地表示出来。我们可以在进化过程中，迭代一次就设法检测新的个体是否违背了约束条件。如果没有违背，则作为有效个体。也可以考虑引入惩罚因子。对于迭代停止条件问题，目前GA的终止条件尚无定论。当适应度函数的最大值已知或者准最优解适应度的下限可以确定时，一般以发现满足最大值或准最优解作为遗传算法迭代停止条件。但是，在许多组合优化问题中，适应度最大值并不清楚，其本身就是搜索的对象，因此适应度下限很难确定。所以，在许多应用事例中，若发现群体个体的进化已趋于稳定状态，换句话说，若发现占群体一定比例的个体已完全是同一个体，则终止算法迭代。除此之外，也可设定适应度函数的最大终止换代数（即迭代次数）作为终止条件。4.5遗传算子遗传操作是模拟生物基因遗传的操作。在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照它们对环境适应的程度（适应度评估）施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度而言，遗传操作可使问题的解，一代又一代地优化，并逼近最优解。遗传算法遗传操作包括以下三个基本遗传算子：（1）选择（2）交叉（3）变异。下面我们在这三个方面分别进行讨论。4.5.1选择算子遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。下面介绍几种传统的选择算子。1）轮盘赌选择法这是遗传算法中最早提出的一种选择方法，由Holland提出，因为简单实用，所以被广泛采用。它是一种基于比例的选择，一种回放式的随机采样方法，可以称为选择的蒙特卡罗法。其选择的概率计算公式为5=鼻J=1其中个体为i,其适应度为f（x）,种群大小为N。由上式可以看出，若个体适应度越大，则其被选择的机会越大。为了选择交配个体，需要进行多轮选择。每一轮产生一个［0,1］均匀随机数，将该随机数作为选择指针来确定被选个体。但由于随机操作的原因，这种选择方法的选择误差也比较大，有时连适应度较高的个体也选择不上。2）随机遍历抽样法此方法与轮盘赌选择法基本相似，是对它的一种改进，特点是只要进行一次轮盘旋转。其采用均匀分布且个数等于种群规模的旋转指针，等距离选择个体，其中第一个指针位置由［0,1/M］区间的均匀随机数决定，提供了零偏差和最小个体扩展。此方法虽然对轮盘赌方法有改进，但是也存在随机操作的误差。3）随机联赛选择在使用遗传算法求解问题的过程中，虽然随着群体的进化过程会产生出越来越多的优良个体，但由于选择、交叉、变异等遗传操作的随机性，当前群体中适应度最好的个体也有可能被破坏掉，从而降低了群体的平均适应度，影响遗传算法的运行效率和收敛速度。为此，我们还经常使用将适应度最好的个体保留到下一代群体中的方法来进行优胜劣汰操作，即当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用它来替换掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体。4.5.2交叉算子所谓交叉运算，是指对两个相互配对的染色体依据交叉概率Pc按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。下面介绍几种常用的交叉算子。1）单点交叉单点交叉，又叫简单交叉。具体操作是：在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新个体。例如：交叉前：P1=00000I0111P2=11100I0000交叉后：P1*=00000I0000P2*=11100I0111其中，交叉点设置在第五和第六基因座之间，然后将截断的部分基因互换。2）两点交叉二点交叉的操作与单点交叉类似，只是随机设定设置2个交叉点。其示例如下：交叉前：000|110|111011|010|000交叉后：000|010|111011|110|0003）多点交叉为了增加交叉的信息量，GA发展了多点交叉的概念。多点交叉的方式与前两种类似，不同之处在于，对于选定的两个个体位串，要随机选择多个交叉点，构成交叉点集合。多点交叉算子的交叉点数和位置的选择有多种方法。对于实参数优化问题采用二进制编码，一般交叉的数量不宜低于实参数的维数。4.5.3变异算子所谓变异算子，是指依据变异概率Pm将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法。一般来说，变异算子操作的基本步骤如下：（1）在群体中所有个体的码串范围内随机地确定基因座。（2）以事先设定的变异概率Pm来对这些基因座的基因值进行变异。最基本的的遗传变异方式如下所示：变异前：110100011变异后：110101011遗传算法导入变异的目的有两个：一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。为了保证个体变异后不会与其父代产生太大的差异，变异概率一般取值较小，以保证种群发展的稳定性。4.6控制参数在GA的实际操作时，需适当确定某些参数的值以提高选优的效果。其基本参数如下所示：（1）M，种群规模，即所包含字符串的个数（2）L，串长，字符串所含字符的个数（3）T，最大终止换代数（4）Pc，交叉概率（5）Pm，变异概率在GA中，控制参数设置的好坏直接关系到遗传算法的全局收敛性。下面我们在几个控制参数对算法性能的影响方面进行简要的分析。（1）种群规模M：群体中个体的数目，直接影响遗传算法的最终结果以及执行效率。种群太小则不能提供足够的采样点，以致算法性能很差；种群太大，尽管可以增加优化信息，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。（2）交叉概率Pc：交叉算子作用于个体对，以产生新的个体，实质上是在解空间中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。变异概率Pm:变异操作是对种群模式的扰动，有利于增加种群的多样性，变异在遗传算法中属于辅助性的搜索操作。变异概率太小则很难产生新模式，容易使算法发生“早熟”，收敛于局部最优解；变异概率太大则会使遗传算法成为随机搜索算法。5遗传算法的改进自从J.Holland系统地提出遗传算法完整结构和理论以来，众多学者一直致力于推动遗传算法的发展，对编码方式、控制参数的确定，选择方式和交叉机理等进行了深入的探究，引入了动态策略和自适应以改善遗传算法的性能，提出了各种改进的遗传算法。下面介绍几种改进的遗传算法。5.1并行遗传算法伴随着遗传算法应用的深入，并行遗传算法及其实现的研究也变得十分重要。一般来说，遗传算法中适应度的计算最费时间，再加上需要不断产生新一代，而每一代又有若干个体，所以如何提高遗传算法的运行速度显得龙为突出。由于遗传算法的内在并行机制，其并行处理是很自然的的解决途径。5.1.1并行遗传算法的分类目前并行遗传算法的实现方案大致可分为三类：全局型一一主从式模型：这种并行系统分为一个主处理器和若干个从处理器。主处理器监控整个染色体种群，并基于全局统计执行选择操作；各个从处理器接受来自主处理器的个本进行重组交叉和变异，产生新一代个体，并计算适应度，再把计算结果传给主处理器。独立型——粗粒度模型：粗粒度模型也称孤岛模型，是目前应用最广泛的一种并行遗传算法。它是将种群分成若干个子群并分配给各自对应的处理器，每个处理器不仅独立计算适应度，而且独立进行选择，重组交叉和变异操作，还要定期地相互传送适应度最好的个体，从而加快满足终止条件的要求。分散型一一细粒度模型：细粒度模型也称邻域模型，这种并行系统为种群中的每一个个体分配一处理器，每个处理器独立的进行适应度计算，而选择、重组交叉和变异的相关操作都在与之相邻的一个处理器之间互相传递的个体中进行。5.1.2迁移策略迁移是并行遗传算法引入的一个新的算子，它是指在进化过程中子群体间交换个体的过程，一般的迁移方法是将子群体中最好的个体发给其它的子群体，通过迁移可以加快较好个体在种群的传播，提高收敛速度和解的精度。与单种群相比只需要较少的个体评价计算工作量。因此即使是采用单一处理器的计算机上以串行方式（伪并行）实现并行算法也能产生较好的结果。因此迁移算子的采用，使并行算法更适应于全局寻优，并且计算量较小。以基于粗粒度模型的并行算法为例，其迁移策略可分为以下两种：（1）一传多：每个处理器对就有若十个相邻处理器，每个处理器产生新一代个体后，都将自己最好的一个个体传送给相邻处理器，并接受来自相邻处理器的最好成绩的个体，将这些个体与自己的个体同时考虑，淘汰适应度差的个体。（2）一传一：考虑到染色体的多样性，每个处理器都将自己最好的个体传给与之相邻的一个处理器，同时增加两个参数：一是处理器之间通讯的频率；二是每次传送给最好个体的数目。5.2CHC算法CHC算法是Eshelman于1991年提出的一种改进的遗传算法的缩称，第一个C代表跨世代精英选择策略，H代表异物种重组，第二个C代表大变异。CHC算法与基本遗传算法SGA不同点于：SGA的遗传操作比较单纯，简单地实现并行处理；而CHC算法牺牲这种单纯性，换取遗传操作的较好效果，并强调优良个体的保留。下面分别介绍其遗传操作的改进之处。选择算子通常，遗传算法是依据个体的适应复制个体完成选择操作的，而在CHC算法中，上世代种群与通过新的交叉方法产生的个体混合起来，从中按一定概率选择较优个体。这一策略称为跨世代精英选择。其明显特征表现在：（1）健壮性：由于这一选择策略，即使当交叉操作产生较劣个体偏多时，由于原种群大多数个体残留，不会引起个体的评价值降低。（2）遗传多样性保持：由于大个体群操作，可以更好地保持进化过程中的遗传多样性。（3）排序方法：克服了比例适应度计算的尺度问题。交叉算子CHC算法使用的重组操作是对均匀交叉的一种改进。均匀交叉对父个体位值的各位位置以相同的概率实行交叉操作，这里改进之处是：当两个父个体位值相异的位数为m时，从中随机选取m/2个位置，实行你个体位值的互换。显然，这样的操作对模式具有很强的破坏性，因此，确定一阀值，当个体间的海明距离（指两个字符串的对应字符取值不同的字符数）低于底值时，不进行交叉操作。

并且，与种群进化收敛的同时，逐渐地减小该阀值。5.2.3变异算子CHC算法在进化前期不采取变异操作，当种群进化到一定的收敛时期，从优秀个体中选择一部分个体进行初始化。初始化的方法是选择一定比例的基因座，随机地决定它们的位值。这个比例值称为扩散率，一般取0.35。6遗传算法的应用遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面以旅行商问题（TSP）为例，介绍一下遗传算法的实际应用。6.1TSP问题的数学模型旅行商问题的经典提法：有一货物推销员要去若十个城市推销货物，从城市1出发，经其余各城市至少一次，然后回到城市1，问选择怎样的行走路线，才能使总行程最短（各城市间距离为已知）。其严格的数学定义如下：记G=（V，E）为赋权图，V={1,2,3,…,n}为顶点集，E为边集，各个顶点间的距离为C.jOC..>0且4=+8，/引并设[1,边（i,j）在最优路线上%~[0，其它则旅行商问题的数学模型可表示如下：y-iz-gs-w£5L1I—‘扬g{0,1},£"=1,2,5z-gs-w£5L1I—‘这里IS|表示图G的顶点个数。对于约束条件，前两个约束意味着对每个顶点而言，仅有一条边进一条边出，后一条约束则保证了没有任何子回路解的产生。满足上述约束条件的解构成了一条遍历所有点的哈密尔顿回路。6.2确定适应度函数为了将TSP从问题空间转到GA空间中，我们首先要确定适应度函数，我们将一个合法的城市序列s=（C1,C2,…，Cn,Cn+1）（Cn+1就是C1）作为一个个体。这个序列中相邻两城之间的距离之和的倒数就可作为相应个体s的适应度，从而适应度函数就是f(s)=__z"d(c,c)ii+1i=1其中d(Ci,Ci+1)为两城市间的距离。6.3编码方式用遗传算法求解旅行商问题，编码的方式很重要。本章采用路经编码，即直接采用城市在路径中的位置进行表示，例如回路：2-4-5-6-1-3-2直接表示成（245613）。与求解TSP的其他编码方式相比，如二进制表示、近邻表示、次序表示、矩阵表示和边的表示等，路径表示更自然和直观一些，而且路径表示易于加入启发式信息，便于遗传交叉操作。下面设计的遗传交叉算子就是基于路径编码。6.4交叉策略对于传统的求解TSP的遗传交叉算子，如部分匹配交叉、顺序交叉、循环交叉、基于位置的交叉、基于顺序的交叉等，他们都存在以下缺点：或者没有充分考虑TSP的特点，忽视了父代中边的邻接状况；或者交叉后的子代个体不能很好地保留父代的优秀基因，而且有时需要对子代做些改动才可以。以下给出的边重组交叉算子，可以使交叉后产生的个体尽可能地保留父代的优秀基因，并能产生可行后代。设两个个体：P1=123456P2=126354如下所示（两点间的数值为距离）Pl.TOC\o"1-5"\h\z*1234561524743P2：0一P0一^P―O~~0~峪1263541根据每个顶点在两条给出路径中的位置，计算每个顶点在这两条路径中与之相邻的顶点数，重复的相邻顶点在计算时只计一次，然后按每个顶点的度数从大

到小对顶点进行排序，对于度数相同的顶点按序号顺序从小到大排列，可生成下列表格。城市与之相邻的城市32456612351246213641355346算法的具体步骤如下：令V二①；从表格中的第一个顶点开始，在与之相邻的点中找出所有度数大于2的顶点，放入V中，若V#①，则转3；若V=①，转4；在V中寻找与顶点距离最大的点（若出现多个顶点到顶点的距离相等且为最大值，则在这些顶点中选择度数最大的点，若这些顶点的度数亦相等，则任意选择其中的一个顶点），去掉两点间的路径，然后重新计算每个顶点在路径中的度数，并按上述生成表格的方法重新生成表格，转1;此时表格中所有顶点的度数均为2,按照表中各顶点之间的邻接关系进行连接，形成一条闭合的回路。通过以上步骤可得下表。城市与之相邻的城市1242133624115546635根据相邻位置重新连接后，得到P1和P2的子代