基本遗传算法

遗传算法

1、 遗传算法生物学基础和基本理论

达尔文自然选择学说认为，生物要生存下去，就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。在生存斗争中，具有有利变异(mutation)的个体容易存活下来，并且有更多的机会将有利变异传给后代;具有不利变异的个体就容易被淘汰，产生后代的机会也少得多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存，不适者淘汰的过程叫做自然选择。达尔文的自然选择学说表明，遗传和变异是决定生物进化的内在因素。遗传是指父代与子代之间，在性状上存在的相似现象。变异是指父代与子代之间，以及子代的个体之间，在性状上或多或少地存在的差异现象。在生物体内，遗传和变异的关系十分密切。一个生物体的遗传性状往往会发生变异，而变异的性状有的可以遗传。遗传能使生物的性状不断地传送给后代，因此保持了物种的特性，变异能够使生物的性状发生改变，从而适应新的环境而不断地向前发展。

生物的各项生命活动都有它的物质基础，生物的遗传与变异也是这样。根据现代细胞学和遗传学的研究得知，遗传物质的主要载体是染色体(chromsome),染色体主要是由DNA(脱氧核糖核酸)和蛋白质组成，其中DNA又是最主要的遗传物质。现代分子水平的遗传学的研究又进一步证明，基因(gene)是有遗传效应的片段，它储存着遗传信息，可以准确地复制，也能够发生突变，并可通过控制蛋白质的合成而控制生物的性状。生物体自身通过对基因的复制(reproduction)和交叉(crossover)，即基因分离、基因自由组合和基因连锁互换)的操作使其性状的遗传得到选择和控制。同时，通过基因重组、基因变异和染色体在结构和数目上的变异产生丰富多采的变异现象。需要指出的是，根据达尔文进化论，多种多样的生物之所以能够适应环境而得以生存进化，是和上述的遗传和变异生命现象分不开的。生物的遗传特性，使生物界的物种能够保持相对的稳定;生物的变异特性，使生物个体产生新的性状，以至于形成了新的物种，推动了生物的进化和发展。

由于生物在繁殖中可能发生基因交叉和变异，引起了生物性状的连续微弱改变，为外界环境的定向选择提供了物质条件和基础，使生物的进化成为可能。人们正是通过对环境的选择、基因的交叉和变异这一生物演化的迭代过程的模仿，从而提出了能够用于求解最优化问题的强鲁棒、自适应的遗传算法。

遗传算法（Genetic Algorithm--GA）起源于对生物系统进行的计算机模拟研究，是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应优化概率搜索算法。它最早由美国Michigan大学的Holland教授提出，起源于20世纪60年代对自然和人工自适应系统的研究。20世纪70年代Holland教授的学生De Jong基于遗传算法在计算机上进行了大量的纯数值函数优化计算实验。最后在20世纪80年代由Goldberg进行归纳总结，形成了遗传算法的基本框架。 遗传算法是基于自然界的生物遗传进化机理而演化出的一种自适应优化算法。针对不同类型的问题，人们设计出了各种不同的编码方法和不同的进化算子，从而构成了不同类型的遗传进化机制，以适应解决各种不同的问题，Goldberg对这些算法加以总结，归纳出这些不同的遗传算法之间的共同特点，即：遗传和

进化过程都是通过选择、交叉和变异的机理来完成对问题最优解的自适应搜素过程，由此提出了一种统一了所有遗传算法本质特征的最基本的遗传算法——基本遗传算法（Simple Genetic Algorithms,SGA）。在基本遗传算法中只使用选择算子、交叉算子、和变异算子这三种基本的遗传算子，从而给其他各类遗传算法提供了基本的算法框架。

2、遗传算法的基本思想

我们以引用生物遗传学上的相关术语来描述遗传算法的基本思想.遗传算法根据待解问题的要求，从代表问题可能潜在解集的一个种群(population)开始,而一个种群是由经过基因(gene)编码(coding)的一定数目的个体(individual)组成.每个个体实际上是带有特征的染色体(chromosome)实体.染色体作为遗传物质的主要载体,其不同的基因组合决定了个体的性能表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的.因此遗传算法中最基础的工作就是实现染色体个体的性能表现，即：实现个体的编码工作。由于仿照基因编码的工作很复杂,针对不同的问题编码都有所不同，在基本遗传算法中为了增强算法的适应性，我们往往简化编码工作,而采用二进制编码。

当完成编码工作，初代种群产生之后，则对种群按照“优胜劣汰，适者生存”的进化原理来逐代(generation)进化，在每一代中,都是根据该代种群个体的适应度值(fitness)的大小来挑选下一代个体群体，并借助于自然遗传学中的遗传算子(genetic operator)来进行组合交叉操作(crossover)、变异操作(mutation)和选择操作（Selection），从而产生出代表新的子代解集的种群。正是这个进化过程使得种群具备了生物界所特有的进化优化机制，使得种群能够像自然界那样让后代种群比父代种群具有更强的适应性，从而更加适应于所处环境。这样进化到最后一代种群中的最优个体经过解码操作(Decoding Operator)，即为所求问题的近似最优解。

2、 遗传算法的基本结构

遗传算法借助生物遗传学的观点，通过对生物遗传和进化过程中的选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程，以实现各个个体的适应性的提高。

遗传算法的流程图如下所示，主要包括：染色体编码、产生初始群体，计算适应度、进化操作等几大部分，下面将分别进行介绍。

基本遗传算法的算法流程图

基本遗传算法是一个迭代过程，它模仿生物在自然环境中的遗传和进化机理，反复将选择算子、交叉算子、变异算子作用于群体，最终可得到问题的最优解或近似最优解。虽然算法的思想比较单纯，结构也比较简单，但它却也具有一定的实用价值，能够解决一些复杂系统的优化计算问题。

2.1 编码

遗传算法主要是通过遗传操作对群体中具有某种结构形式的个体施加结构重组处理，从而不断地搜索出群体中个体间的结构相似性，形成并优化积木块以逐渐逼近最优解。由此可见，遗传算法不能直接处理问题空间的参数，必须把参数转换成遗传空间的由基因按一定结构组成的染色体或个体。这一转换操作叫做编码，也可以称作（问题的）表示（representation）。

在遗传算法中如何描述问题的可行解，即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法就称为编码。针对一个具体应用问题，如何设计一种完美的编码方案一直是遗传算法的应用难点之一，也是遗传算法的一个重要研究方向。对实际应用的问题，必须对编码方法、交叉运算方法、变异运算方法、译码方法等统一考虑，以寻求一种对问题的描述最为方便、遗传运算效率最高的编码方案。

2.1.1二进制编码（位串编码）

二进制编码方法是遗传算法种最常用的一种编码方法，它使得编码符号集是由二进制符号0和1所组成的二值符号集{0，1}，它所构成的个体基因型是一个二进制编码符号串。

二进制编码方法有下述一些优点：

（1）编码、译码操作简单易行。

（2）交叉、变异等遗传操作便于实现。

（3）符合最小字符集编码原则。

（4）便于利用模式定理对算法进行理论分析。

2.1.2符号编码

符号编码是指组成个体编码串的码值无数值含义而仅有字符含义。当然，码值本身或者字母表中的各种码值可能以数字形式出现，但其代表的意义则只能是字。许多组合优化问题所采用的编码形式经常是符号编码。最常见的例子是城市旅行商（TSP）问题的编码。TSP问题描述为：

一个商人从某一城市出发，要走遍区域中的所有n 座城市，最终回到出发地，其中每座城市必须经过且只能经过一次。问题是按照何种路线走，整个旅行过程所经过的回路长度最短。如果给每座城市以唯一的符号标识，如英文大写字母表{A,B,Z}，则走过的路线可表示为AGIX„„L（假设城市不超过26 座），如果给定字母表{ c1， c2 ,cn } ,则路线又可表示为C1C2„„Cn ，同理，若给定字母表{1,2,n} ，则路线又可表示为481„„n ，这里，数字同样不代表数值，而代表字符。可见，不同的字母表可以产生出不同的符号编码。在某些应用 问题中，编码甚至可以是矩阵等其它形式。

符号编码的优点在于便于利用专门问题已有的先验知识和信息，同时形式可以变化多样，因而可以处理各种非数值优化问题和组合优化问题，其不足之处在于针对性地设计遗传操作显得复杂一些。

以上简单介绍了位串编码，符号编码。除此之外，还有其他的编码方法，如多数联级编码、实数编码、多参数交叉编码。

2.2初始群体的产生

2.2.1初始群体的设定

一般来讲，初始群体的设定可采取如下策略：

（1）根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。

（2）先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数达到了预先确定的规模。

2.2.2群体多样性

群体规模越大，群体中个体的多样性越高，算法陷入局部解的危险就越小，所以，从考虑群体多样性出发，群体规模应较大。但是，群体规模太大会带来计算量增加的弊病，从而影响算法效能。另外，群体规模太小，会使遗传算法的搜索空间中分布范围有限，因而搜索有可能停止在未成熟阶段，引起早熟（premature convergence）现象。显然，要避免早熟现象，必须保持群体的多样性，即群体规模不能太小。

2.3适应度函数

遗传算法在进化搜索中基本上不用外部信息，仅用适应度函数为依据。遗传算法的目标函数不受连续可微的约束且定义域可以为任意集合。对适应度函数的唯一要求是，针对输入可计算出能加以比较的非负结果。这一特点使得遗传算法应用范围很广。在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。适应度函数评估是选择操作的依据、适应度函数设计直接影响到遗传算法的性能。在选择操作时也可能会出现以下问题：

①在遗传进货的初期，通常会产生一些超常的个体，若按照比例选择法，这些异常个体因竞争力太突出而控制了选择过程，影响算法的全局优化性能。

②在遗传进化后期，即算法接近收敛时，由于种群中个体适应度差异较小时，继续优化的潜能降底可能获得某个局部解。

上述问题我们通常称为遗传算法的骗问题。适应函数设计不当可能造成这种问题的出现。

2.3.1适应度函数设计方法

适应度函数设计主要满足以下条件：

（1） 单值、连续、非负、最大化：这个条件是很容易理解和实现的。

（2） 合理、一致性：要求适应度值反应解的优劣程度，这个条件的达成往往比

较难以衡量。

（3） 计算量小：适应度函数设计应该尽可能简单，这样可以减少计算时间和空

间上的复杂性，降低计算成本。

（4） 通用性强：适应度对某类具体问题，应尽可能通用，最了无需使用者改变

适应度函数中的参数。这个条件应该不是属于强要求。

常见的适应度函数构造方法有：

(1)目标函数映射成适应度函数

在许多问题求解中，其目标是求取费用函数(代价函数)g(x)的最小值，而不是求效能函数或利润函数u(x)的最大值。即使某一问题可自然地表示成求最大值形式，但也不能保证对于所有的x，u(x).都取非负值。由于遗传算法中，适应度函数要比较排序并在此基础上计算选择概率，所以适应度函数的值要取正值。由此可见，在不少场合，将目标函数映射成求最大值形式且函数值非负的适应度函数是必要的。

在通常搜索方法下，为了把一个最小化问题转化为最大化问题，只需要简单的把费用函数乘以-1即可，但对遗传算法而言，这种方法还不足以保证在各种情况下的非负值。对此，可采用以下的方法进行转换:

.当g(x)

显然存在多种方式来选择系数Cmax. Cmax可以是一个合适的输入值，也可采用迄今为止进化过程中g(x)的最大值或当前群体中g(x)的最大值。当然Cmax也可以是前K代中g(x)的最大值。Cmax最好与群体无关。

当求解间题的目标函数采用利润函数形式时，为了保证其非负性，可用如下变换式: 当U(x)+Cmin>0⎧U(x)+Cmin..........f(x)=⎨ ................其它情况⎩0..........

式中系数Cmin可以是合适的输入值，或是当前一代或前K代中的g(x)的最小值，也可以是群体方差的函数。

（2）通过对知度的适当缩放调整（称为适应度定标Fitness Scaling）来设计评价函数。例如，Goldberg提出了一种线性适应度定标方案：Gen,liu和Ida提出了一种基于指数适应度的评论函数，它介于基于序的评价函数和线性适应度定标方案之间。

2.3.2适应度函数的设计对遗传算法的影响

适应度函数影响遗传算法的迭代停止条件。

严格地讲，遗传算法的迭代停止条件目前尚无定论。当适应度函数的最大值已知或者准最优解适应度的下限可以确定时，一般以发现满足最大值或准最优解作为遗传算法迭代停止条件。但是，在许多组合优化问题中，适应度最大值并不清楚，其本身就是搜索的对象，因此适应度下限很难确定口所以，在许多应用事例中，若发现群体个体的进化已趋于稳定状态，换句话说，若发现占群体一定比例的个体已完全是同一个体，则终止算法迭代。

适应度函数与问题约束条件

遗传算法由于仅靠适应度来评估和引导搜索，所以求解问题所固有的约束条件不能明确地表示出来。在实际应用中，许多间题都是带约束条件的，像货郎担问题就是一个典型的约束组合优化间题。用遗传算法求解此类问题需要考虑一些对策。

按理说，我们可以采用一种十分自然的方法来考虑约束条件，即在进化过程中，迭代一次就设法检测.新的个体是否违背了约束条件。如果没有违背，则作为有效个体，反之，作为无效个体被除去。这种方法对于弱约束同题求解还是有效的，但对于强约束间题求解效果不佳。这是因为在这种场合，寻找一个有效个体的难度不亚于寻找最优个体。

作为对策，可采取一种惩罚方法(penalty method)。该方法的基本思想是设法对个体违背约束条件的情况给予惩罚，并将此惩罚体现在适应度函数设计中。这样，一个约束优化问题就转换为一个附带考虑代价(cost)或惩罚(penalty)的非约束优化问题.

3 基本遗传算子

遗传操作是模拟生物基因遗传的操作。在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照它们对环境适应的程度(适应度评估)施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度而言，遗传操作可使问题的解，一代又一代地优化，并逼近最优解。遗传算法遗传操作包括以下三个基本遗传算子(genetic operator)：1)选择(selection) ;2)交叉(crossover); 3)变异(mutation)。这三个遗传算子有如下特点：

(1)这三个遗传算子的操作都是在随机扰动情况下进行的。换句话说，遗传

操作是随机化操作，因此，群体中个体向最优解迁移的规则是随机的。需要再次强调的是，这种随机化操作和传统的随机搜索方法是有区别的。遗传操作进行的是高效有向的搜索而不是如一般随机搜索方法所进行的无向搜索。

(2)遗传操作的效果和上述三个遗传算子所取的操作概率，编码方法，群体大小，初始群体以及适应度函数的设定密切相关。

(3)三个基本遗传算子的操作方法或操作策略随具体求解间题的不同而异。更具体地讲，是和个体的编码方式直接有关。

3.1 选择算子

选择又称为繁殖或复制（Reproduction），是一个从旧种群（old population）中选择生命力强的个体位串产生新种群的过程。这个操作是模仿自然选择现象，将达尔文的适者生存理论运用于位串的过程。

遗传算法中的选择算子（Selection Operator）就是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群体中的一种遗传算子。选择操作是建立在对个体的适应度进行评价的基础之上的，其主要目的是为了避免基因缺失、提高全局收敛性和计算效率,其作用是从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。

下面是几种常用的选择算子的操作方法。

3.1.1比例选择

最常用和最基本的选择算子是比例选择算子。所谓比例选择（Proportional Model)是指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。

设群体大小为M，个体i的适应度为Fi，则个体i被选种的概率Pis为： Pis=FiM∑F

i=1(i=1,2, ,M) i

比例选择实际上也叫做赌轮盘选择（Roulette Wheel Selection），即赌轮

[11]策略 由霍兰德提出，由于简单实用，被广泛使用。这种选择策略在遗传算法中使用的最多，它也是先计算个体的相对适应值fi

f记为pi，然后根据选择概

i

率{pi,i=1,2,„,N}把一个圆盘分成N份。在进行选择时，可以转动圆盘，若某点落到第i个扇形内，则选择个体i。转盘式选择策略的特点是每个群体成员在转盘选择策略下都有被选择的机会。

3.1.2最优保存策略

使用最优保存策略进化模型（Elitist Model)来进行优胜劣汰操作，即当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用它来替换掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体。最早是由Rudolhp C[12]提出采用最优选择策略来保持群体中最好的个体不丢失，以保证算法的收敛性。

最优保存策略进化模型的具体操作过程是：

（1）找出当前群体中适应度最高的个体和适应度最低的个体。

（2）若当前群体中最佳个体的适应度比总的迄今为止的最好个体的适应度还要高，则以当前群体中的最佳个体作为新的迄今为止的最好个体。

（3）用迄今为止的最好个体替换掉当前群体中的最差个体。

最优保存策略的实施可保证迄今为止所得到的最优个体不会被交叉、变异等遗传运算所破坏，它是遗传算法收敛性的一个重要保证条件。但另一方面，它使得算法的全局搜索能力不强。所以该方法一般要与其它一些选择操作方法配合起来使用，方可以有良好的效果。另外最优保存策略还可以加以推广，即在每一代的进化过程中保留多个最优个体不参加交叉、变异等遗传运算，而直接将它们复制到下一代群体中。这种选择方法也称为稳态复制。

除了上述选择算子外，还有确定式采样选择（Deterministic Sampling）、期望值选择（Expected Value Model）、无回放余数随机选择（Remainder Stochastic Sampling with Replacement）、排序选择（Rank-based Model）、随机联赛选择（Stochastic Tournament Model）等[1,5]各种算子。

3.2交叉算子

在生物的自然进化过程中，两个同源染色体通过交配而重组，形成新的染色体，从而产生出新的个体或物种。交配重组是生物遗传和进化过程中的一个主要环节，模仿这个环节，在遗传算法中也使用交叉算子来产生新的个体。

遗传算法中的所谓交叉运算，是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别其它进化算法的重要特征，它在遗传算法中起着关键的作用，是产生新个体的主要方法。交叉算子的设计和实现与所研究的问题密切相关，一般要求它既不要太多地破坏个体编码串中表示优良性状的优良模式，又要能够有效地产生出一些较好的新个体模式。另外，交叉操作数的设计要和编码设计统一考虑。

遗传算法中，在交叉运算之前还必须先对群体中的个体进行配对。对于占主流地位的二值编码而言，各种交叉算子都包括两个基本内容[5]：

（1）从由选择操作形成的配对库（mating pool）中，对个体随机配对并按预先设定的交叉概率来决定每对是否需要进行交叉操作；

（2）设定配对个体的交叉点（cross site），并对这些点前后的配对个体的部分结构（或基因）进行相互交换。

下面介绍几种适合于二进制编码个体或实数编码个体的交叉运算。

3.2.1单点交叉

单点交叉（One-point Crossover）[1,3]又称为简单交叉，它是指在个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。

如： 个体A 1001 | 111------>1001000新个体A'

个体B(0011 | 000---—>0011111新个体B'

（交叉点）

3.2.2双点交叉和多点交叉

双点交叉（Two-point Crossover）是指在个体编码串中随机设置了二个交叉点，然后再进行部分基因交换。它的具体操作过程是：在相互配对的两个个体编码串中随机设置两个交叉点；再交换两个个体在所设定的两个交叉点之间的部分染色体。

如： 个体 A 10 | 110 | 11 -------->1001011 新个体A' 个体 B 00 | 010 | 00 -------->0011000 新个体B'

（交叉点1） （交叉点2）

多点交叉（Multi－point Crossover）有时又被称为广义交叉（Generalized Crossover），是指在个体编码串中随机设置了多个交叉点，然后进行基因交换。一般不太使用多点交叉算子，因为它有可能破坏一些好的模式。随着交叉点数的增多，个体的结构被破坏的可能性也逐渐增大，这样就很难有效地保存较好的模式，从而影响遗传算法的性能。

另外，还有均匀交叉（Uniform Crossover）、算术交叉（Arithmetic Crossover）

[1]等交叉算子。

3.3 变异算子

在生物的遗传和自然进化过程中，其细胞分裂复制环节有可能会因为某些偶然因素的影响而产生一些复制差错，这样就会导致生物的某些基因发生某种变异，从而产生出新的染色体，表现出新的生物性状。虽然发生这种变异的可能性较小，但它也是产生新物种的一个不可忽视的原因。模仿生物遗传和进化过程中的这个环节，在遗传算法中也引入了变异算子来产生出新的个体。

遗传算法中的所谓变异算子，是指将个体染色体编码传中的某些基因座上的基因值用该基因座的其它等位基因来替换，从而形成一个新的个体。

一般来说，变异算子操作的基本步骤如下：

（1）在群体中所有个体的码串范围内随机地确定基因座；

（2）以事先设定的变异概率pm来对这些基因座的基因值进行变异。

遗传算法导入变异的目的有两个：一是使遗传算法具有局部随机搜索能力；二是使遗传算法可维持群体多样性，以防止出现早熟现象。

3.3.1基本位变异

基本位变异(Simple Mutation)操作是指对个体编码串以变异概率pm随机指定的某一位或几位基因座上的基因值作变异运算。

3.3.2均匀变异

均匀变异(Uniform Mutation)操作是指分别用符合某一范围均匀分布的随机数,以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。

均匀变异的具体操作过程是：依次指定个体编码串中的每个基因座为变异点；对每一个变异点，以变异概率pm从对应基因的取值范围内取一个随机数来

替代原有基因值。

均匀变异操作特别适合应用于遗传算法的初期运行阶段，它使得搜索点可以在整个搜索空间内自由地移动，从而可以增加群体的多样性，使算法处理更多的模式。

3.3.3逆转变异

所谓逆转算子（Inversion Operator）也称倒位算子，是指颠倒个体编码串中随机指定的两个基因座之间的基因排列顺序，从而形成一个新的染色体。逆转操作的目的主要是为了能够使遗传算法更有利于生成较好的模式。

3.3.4自适应变异算子

自适应变异算子（Adapitive Mutation Operator）与基本变异算子的操作内容类似，唯一不同的是交叉概率pm不是固定不变而是随群体中个体的多样性程度而自适应调整。

在简单遗传算法中，变异就是某个字符串某一位的值偶然的（概率很小的）随机的改变。变异操作可以起到恢复位串字符多样性的作用，并能适当地提高遗传算法的搜索效率。当它有节制地和交叉一起使用时，它就是一种防止过度成熟而丢失重要概念的保险策略。

4 遗传算法的数学基础

4.1模式定理

通过前面的介绍、我们已初步知道遗传算法是一个以适应度函数(或目标函数)为依据，通过对群体个体施加遗传操作实现群体内个体结构重组的迭代处理过程。在这一过程中，群体个体(问题的解)一代一代地得以优化并逐渐逼近最优解。遗传算法模拟的是自然界生物优胜劣汰进化过程。但是，作为一种智能搜索算法，它的木质内涵是什么?更具体地讲，遗传算法所依赖的基于遗传操作，即选择、交叉和变异算子何以能使遗传算法体现出其它算法所没有的鲁棒性、自适应性和全局优化性等特点?下面我们将讨论遗传算法的理论基础。GA 在应用上确已取得显著成功, 但其基础研究相对来说却比较薄弱。就目前情况看,能称得上为理论成果的只有所谓的模式定理 (Sehema Theorem )。模式( schema) 是在某些确定位置上取相同字符的字符串集合。

模式( schema)是一个描述字符串集的模板，该字符串集中的串的某些位置上存在相似性。不失一般性，我们考虑二值字符集{0,1}，由此可以产生通常的0, 1字符串。现在我们增加一个符号“*”，称作”无关符”（don't care)或通配符，即“*”既可以被当作“0”，也可以被当作“1”。这样，二值字符集{0,1}就扩展为三值字符集{0,1,*}由此可以产生诸如0110,0 * 1 1 * *,* * 0 1 * 0等字符串。

基于三值字符集{0,1,*}所产生的能描述具有某些结构相似性的0,1字符串集的字符串称作模式。

以长度为5的串为例，模式*0001描述了在位置2,3,4,5具有形式“0001”的所有字符串，即(00001, 10001};又比如模式，*1**0描述了所有在位置2为" 1"及位置5为“0”的字符串，即

{01010,01000,01100,01110,11000,11010,11100,11110}而模式01010描述了只

有一个串的集合，即{01010}。由此可以看出，模式的概念为我们提供了一种简

洁的用于描述在某些位置上具有结构相似性的。0,1字符串集合的方法。这里需

要强调的是，“*”只是一个描述符，而并非遗传算法中实际的运算符号，它仅仅

是为了描述上的方便而引入的符号而已。

然而，模式概念的引入并不是仅仅为了描述上的方便。在引入模式概念前，

我们所看到的遗传算法是:在某一代中，r个互不相同的串在选择、交叉、变异

等遗传算子作用下产生下一代的N个新的互不相同的串。那么，在两代之间究竟

保留了什么性质，破坏了什么性质，我们无从得知，因为我们所看到的串都是相

互独立的，互不联系的。而引入模式概念后，我们看到一个串实际上隐含着多个

模式(长度为n的串隐含着2n个模式)，一个模式可以隐含在多个串中，不同的

串之间通过模式而相互联系。遗传算法中串的运算实质上是模式的运算。因此，

通过分析模式在遗传操作下的变化，就可以了解什么性质被延续，什么性质被丢

弃，从而把握遗传算法的实质，这正是模式定理所要揭示的内容。

首先，我们给出模式的两个重要概念:模式阶(schema order)和定义距

(defining length)。

我们知道多个串中隐含着多个不同的模式。确切地说，长度为L的串，隐含

着2^L个不同的模式，而不同的模式所匹配的串(称作模式的样本)的个数是不同

的。比如模式011*1*与模式0*****相比，前者所匹配的串〔样本)的个数比后者

少，即前者的确定性高。

为了反映这种确定性的差异，我们引入模式阶概念:模式H中确定位置的个

数称作该模式的模式阶，记作O(H)。

比如模式011*1*的阶数为4，而模式0*****为1 。显然，一个模式的阶数

越高，其样本数就越少，因而确定性越高。但是，模式阶并不能反映模式的所有

性质。即使具有同阶的模式，在遗传操作下，也会有差不同的性质。为此，我们

再引入定义距概念：

在模式H中第一个确定位置和最后一个确定位置之间的距离称作该模式的

定义距，记作D(H).

比如模式011*1*，的定义距为4，而模式0****为0。

模式阶和定义距描述了模式的基本性质。

【定义】：模式（schema）是描述种群中在位串的某些确定位置上具有相似性

的位串子集的相似性模板（similarity template）[13]。

模式的概念使得我们可以简明地描述具有相似结构特点的个体编码字符串。

在引入了模式概念之后，遗传算法的本质是对模式所进行的一系列运算，即通过

选择操作数将当前群体中的优良模式遗传到下一代群体中，通过交叉操作数进行

模式的重组，通过变异操作数进行模式的突变。通过这些遗传运算，一些较差的

模式逐步被淘汰，而一些较好的模式逐步被遗传和进化，最终就可以得到问题的

最优解。

【模式定理】在遗传算法选择、交叉和变异算子的作用下，具有低阶、短的

定义长度，并且平均适应度高于群体平均适应度的模式在子代中将按指数级数

增长[5]。

模式定理（schema theory），又称为遗传算法的基本定理（the fundamental

theorem of genetic algorithms）。模式定理阐述了遗传算法的理论基础，说明

了模式的增加规律，同时也给遗传算法的应用提供了指导作用。 根据模式理论，

随着遗传算法的一代一代地进行，那些定义长度短的、位数少的、高适值的模式

将越来越多，因而可期望最后得到的位串（即这些模式的组合）的性能越来越得

到改善，并最终趋向全局的最优点。

模式的思路为我们提供了一种简单而有效的方法，使能够在有限字母表的基

础上讨论有限长位串的严谨定义的相似性；而模式定理从理论上保证了遗传算法

是一个可以用来寻求最优可行解的优化过程[14]。

4.2 积木块假设

模式定理说明了具有某种结构特征的模式在遗传进化过程中其样本数目将

按照指数级数增长，这种模式在遗传算法中非常重要，我们给它起了个特别的名

字——积木块。

【定义】：具有低阶、短定义距以及高平均适应度的模式称作积木块（Building

Block）。

之所以称之为积木块，是由于遗传算法的求解过程并不是在搜索空间中逐一

地测试各个基因的枚举组合，而是通过一些较好的模式，像搭积木一样，将它们

拼接在一起，从而逐渐地构造出适应度越来越高的个体编码串。

模式定理说明了积木块的样本数呈指数级数增长亦即说明了用遗传算法寻

求最优样本的可能性，但它并未指明遗传算法一定能够寻求到最优样本。而积木

块假设却说明了遗传算法的这种能力。

【积木块假设】个体的积木块通过选择、交叉、变异等遗传算子的作用，能

够相互结合在一起，形成高阶、长距、高平均适应度的个体编码串。

积木块假设（building block hypothesis）说明了用遗传算法求解各类问题的

基本思想，即通过基因块之间的相互拼接能够产生出问题的更好的解，最终生成

全局最优解。

基于模式定理和积木块假设，就使得我们能够在很多应用问题中广泛地使用

遗传算法的思想。

5 遗传算法的优缺点与应用

根据达尔文的自然选择学说和孟德尔的遗传变异学说建立起来的遗传算法

是一种鲁棒的、自适应的、开放性的随机优化算法。它将生物进化的原理和机制

引入实际问题的解群体中，解群体也叫种群(population)。种群中的每个个体

(individual)是由位串编码构成的个体解，不同的个体（也叫位串）对应于具体

问题的一个适应值(fitness)，即个体解的优良程度，按照适应值的不同而保留

较优个体。由于基因复制，选择操作形成的子代(offspring)中保留了大量的父

代遗传信息。同时，引入交叉和变异操作，使得子代种群中可能出现与父代个体

基因不相同的新个体，这种新个体将新的遗传基因带入种群中，为种群的进化提

供了物质基础。然后在新进化的种群中再按照适应值选择出足够数量的子代个体

以组成子代种群，如此周而复始，使得由代表问题解决方案的个体组成的种群不

断向前进化，直到满足某一结束条件则退出算法。此时，当前种群中适应值最高

的个体即代表了所获得的问题解决方案。

由于遗传算法独到的工作原理和机制，使它能够在复杂地形和空间中进行全

局优化搜索，并且具有较强的鲁棒性。它对进化过程中的适应值函数没有限制性

的要求或假设，即不要求适应值函数连续或者可微等，甚至不需要有显式的函数

形式，因此目标函数也可以是映射矩阵或者神经网络等隐函数。以往常规的优化

方法往往需要目标函数连续可微，并且只能得到局部最优而非全局最优，穷举法

虽然理论上能够获得全局最优，但其计算时间却面临指数爆炸的危险。著名的动

态规划法也仅仅适用于中、小规模的问题。

遗传算法的优化对象是参数的编码而非参数本身。遗传算法对一些个体进行

进化操作，这些个体是基于某种编码方式而获得的位串，因此遗传算法首先有一

个有限的字母表。而对应于实际问题解方案的个体则是这个字母表的闭包子集。

应当注意的是，一般遗传算法中的个体编码串的长度都是统一的，所以这些组合

方式构成了字母表闭包的一个子集。通常遗传算法的编码方式是基于二进制的编

码。

遗传算法具有很强的并行性，这种并行性主要表现在两个方面。其一是内含

并行性(implicit parallelism)，即遗传算法的遗传操作是从许多个体开始的，

一个种群中的多个个体同时进行进化，这使得算法具有并行特征。理论研究证明，

遗传算法每处理数量为n 的个体计算，实际处理的模式数量却为n3 。其二是内

在并行性(inherent parallelism)，即遗传算法本身能够实现并行计算。最简单

的并行方式是让许多台计算机稳中有各自进行独立种群的进化计算，计算的过程

中甚至可以不进行任何形式的通信，直到每个种群进化收敛得到结果后再通信比

较，选出最终最优个体。多种群并行进化和岛模型的提出都为遗传算法实现宏观

并行提供了条件。

遗传算法通过适应值函数即目标函数来计算每个个体的适应值大小，而不需

要其它有关问题的信息和推导，算法的独立性强，使得遗传算法能够形成一种通

用算法框架，在处理完全不同的问题时，仅需要稍加修改就可以移植使用，降低

了推广的成本。这点使遗传算法被迅速推广应用，也是各个领域的学者对它普通

感兴趣的原因之一。

遗传算法的寻优规则是由概率确定的，而非确定性的。算法的目标函数给出

一个进化的方向和目标，但算法以何种路径进行搜索则是概率确定的。因此遗传

算法被称为是一种随机优化算法。但这点并不意味着遗传算法是完全地进行随机

搜索。遗传算法在解空间中进行高效的启发式搜索，而不是盲目地穷举或者完全

随机的搜索。

由上文的讨论可以看出，遗传算法与传统的搜索方法相比较而言，具有以下

几个优点：

①自组织、自适应和自学习性（智能性）。应用遗传算法求解问题时，在编

码方案、适应度函数及遗传算子确定后，算法将得用进化过程中获得的信息自行

组织搜索。由于基于自然的选择策略为“适者生存，不适应者初淘汰”，因而适

应度大的个体具有较高的生存概率。通常，产生更适应环境的后代。遗传算法的

这种自组织、自适应特征，使它同时具有能根据环境变化来自动发现环境的特性

和规律的能力。自然选择消除了算法设计过程中的一个最大障碍，即需要事先描

述问题的全部特点，并要说明针对问题的不同特点算法应采取的措施。因此，利

用遗传算法的方法我们可以解决那些复杂的非结构问题。

②遗传算法的本质并行性。遗传算法按并行方式搜索一个种群数目的点，而

不是单点。它的并行性表现在两个方面，一是遗传算法是内在并行的（inherent

parallelism），即遗传算法本身非常适合大规模并行。最简单的并行方式是让几

甚至数千台计算机各自进行独立种群的演化计算，运行过程中甚至不进行任何通

信（独产种群之间若有少量的通信一般会带来更好的结果），等到运算结束时才

通信比较，选取最佳个体。这种并行处理方式对并行系统结构没有什么限制和要

求可以说，遗传算法适合在目前所有的并行机或分布系统上进行并行处理，而且

对并行效率没有太大的影响。二是遗传算法的内含并行性（inplicit

paralelism）。由于遗传算法采用种群的方式组织搜索，因而可以同时搜索空间

内的多个区域，并相互交流信息。使用这种搜索方式，虽然每次只执行与种群规

模n成比例的计算，但实质上已进行了大约O(n3)次有效搜索，这就使遗传算法

能以较少的计算获得较大的收益。

③遗传算法的处理对象不是参数本身，而是对参数集进行了编码的个体。

此编码操作使得遗传算法可直接对结构对象进行操作。

④许多传统搜索方法都是采用单点搜索算法，这种点对点的搜索方法对于多

峰分布的搜索空间经常会陷入局部的某个单峰的局部最优解。而遗传算法采用的

是同时对搜索空间的多个解进行评估。所以使得遗传算法具有较好的全局搜索能

力。

⑤在标准的遗传算法中，基本上不需要其他的辅助信息，而仅用适应度函数

值来评估个体，并在此基础上进行遗传操作。它尤其适用于处理传统优化算法难

于解决的复杂和非线性问题。正是基于以上的几个优点，遗传算法在很多领域都

有着广泛的应用。

遗传算法是对字符串进行操作，逐步实现进化遗传，可以解决许多复杂的问

题。但是，由于遗传算法常用定长的字符串表达问题，限制了它的应用范围。

遗传算法的主要缺点是：

①不能描述层次化的问题。

②不能描述计算机程序。在人工智能领域 中，计算机自动编程一直是个热

门课题。遗传算法通过进化和遗传，只能改变字符串的形式，不能形成层次结构

的计算机程序。为此，需要改变问题的表达方法，以便实现计算机自动编程 。

③缺乏动态可变性。遗传算法的定长字符串，不具备动态可变性。字符串长

度一旦确定，就很难动态地表达状态或行为的变化，限制了问题的表述。由此可

见，遗传算法这种字符串表达形式 ，限制了对问题的结构和大小的灵活处理。

因此，迫使人们寻求新的表达方法。

遗传算法为一个自底向上的过分程，它把各参数码的建筑块组合起来进行寻

优。

遗传算法提供了一种求解复杂系统优化问题的通用框架, 它不依赖于问题

的具体领域,对问题的种类有很强的鲁棒性,所以广泛应用于很多学科。下面是遗

传算法的一些主要应用领域。

1)天然气管道的最优控制

伊得诺斯大学的GoldGerg采用遗传算法研究一个复杂结构输气管道系统的

运行控制问题.该系统模拟了从西南向东北输送天然气的输气管道系统.输气管

道由许多支线组成,每条支线上的送气量各不相同,公有的控制手段就是用压缩

机来改变特定支线中的压力以及用阀门来调节储气罐进出气流的流量,而且管道

气压的实际变化极大地滞后于操纵或压缩机的动作.Goldberg采用拟人的控制

器经过遗传算法学习,建立了一套完备的规则知识层次体系,能够有效地实施管

道运行的控制,以及对管道被戳穿事故作出恰当的反映.

2)喷气式飞机涡机的设计

通用电器公司和Rensselaer综合技术学院的一组研究人员成功地将遗传算法用到一种商业客机等使用的高函道比喷气发动机的涡轮的设计之中.这种涡轮由好几级静止的和旋转的叶扇组成,安装在近似圆筒的函道内,是发动机开发计划的核心部分.涡轮的设计涉及到至少100变量,每个变量的取值范围各不相同,由此形成了具有10^387以上的搜索空间.涡轮设计方案的”适应度”取决于它满足一组限制的程度如何,这组限制有50个左右,如内壁和外壁的形状,函道内各点处燃气气流的压力,速度和扰动情况等.在一般情况下,一个工程师独立工作并获得一个满意设计要用大约几周时间.运行基于GA的发动机模拟软件和专家系统有助于引导设计人找出有意义的修改,工程师用这样的专家系统,在不到一天的时间里就能完成一种设计.

3) 函数优化

函数优化是遗传算法的经典应用领域,也是对遗传算法进行性能评价的常用算例。很多人构造出了各种各样的复杂形式的测试函数,有连续函数也有离散函数,有凸函数也有凹函数,有低维函数也有高维函数,有确定函数也有随机函数,有单峰值函数也有多峰值函数等,用这些几何特性各具特色的函数来评价遗传算法的性能,更能反映算法的本质效果。而对于一些非线性、多模型、多目标的函数优化问题,用其他优化方法较难求解,而遗传算法却可以方便地得到较好的结果。

4 )组合优化

随着问题规模的增大,组合优化问题的搜索空间也急剧扩大,有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题,人们已意识到应把主要精力放在寻求其满意解上,而遗传算法是寻求这种满意解的最佳工具之一。实践证明,遗传算法已经在求解旅行商问题、背包问题、装箱问题、布局优化、图形划分问题等各种具有NP 难度的问题得到成功的应用.

5) 作业调度问题

作业调度问题是一种资源分配问题。这里的资源主要是指设备资源，问题的求解目标是要找到一个将一组工件安排到设备上去，以使作业可为“最优”完成的方案。每个作业由一些任务组成，而每个任务必须由特定的设备处理。一个高度是按先后顺序条件将所有任务安排到设备上的一种方案。通常，约束的数目很大，使JSP成为一个非常难解的组合问题（NP完全问题）。物流调度问题（Flow shop Scheduling problem,ESP）则是具有更严格条件的JSP特例，并可约化为TSP问题。目前在现实生产中主要是靠一些经验来进行调度。现在遗传算法已成为解决复杂调度问题的有效工具,在单件生产车间调度、流水线生产间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。

6) 智能控制

许多控制领域问题，当考虑到系统优化、自适应、自组织和自学习等方面析要求时，一般存在着许多常规方法难以奏效的困难，例如，当有非连续评价函数、

缺初始信息、模型参数和结构或控制过程中的随机性、不确定性等复杂因素出现时，现有的控制理论和方法往往因需要求导信息、对初始条件的敏感性、对高品质的领域知识依赖性而难以得到很好的应用。

遗传算法借助搜索机制的随机性，能够搜索问题域的全局最优解，并且对噪声和变化表现出很好的健壮性和自适应能力。遗传算法在控制领域的应用大致分为两类：一类是离线设计和分析；另一类是在线自适应调整。前者遗传算法作为优化器，对于已知的控制对象寻求合适的控制规则以满足品质方面要求，或者或者对特定控制器结构搜索最优的参数。后者遗传算法作为一种学习机制来确定求知的或非稳系统的特征，或者对控制器进行自适应调整。

在智能控制领域中有很多与优化相关的问题需要求解,遗传算法已在其中得到了初步的应用,并显示出良好的效果。例如用遗传算法进行航空控制系统的优化、使用遗传算法设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等,都显示出了遗传算法在这些领域中应用的可能性

7) 机器人学

机器人是一类复杂的难以精确建模的人工系统,而遗传算法的起源就来自于人工自适应系统的研究,所以,机器人学理所当然地成为遗传算法的一个重要应用领域。例如,遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面得到研究和应用.

8 )图像处理

图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中,如扫描、特征提取、图像分割等不可避免地会存在一些误差,从而影响图像的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在这些图像处理中的优化计算方面找到了用武之地,目前已在模式识别(包括汉字识别) 、图像恢复、图像边缘特征提取等方面得到了应用

9)人工生命

人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大主要特征。人工生命与遗传算法有着密切的关系。基于遗传算法的进化模型是研究人工生命现象的重要基础理论,虽然人工生命的研究尚处于启蒙阶段,但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力,并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成,遗传算法为人工生命的研究提供一个有效的工具,人工生命的研究也必将促进遗传算法的进一步发展。

10)遗传编程

1989 年,美国Standford 大学的Koza 教授发展了遗传编程的概念,其基本思想是:采用树型结构表示计算机程序,运用遗传算法的思想,通过自动生成计算机程序来解决问题。虽然遗传编程的理论尚未成熟,应用也有一些限制,但它已成

功地应用于人工智能、机器学习等领域,目前公开的遗传编程实验系统有十多个,例如, Koza 开发的ADF 系统,White 开发的GPELST 系统等

11) 机器学习

迄今，自然界只有人类才真正具有完善的学习能力，机器学习实际上是对人的学习机制的一种抽象和模拟，是一种理想的学习模型。基于符号学习的机器学习系统、条件反射型学习系统、类比式学习系统、推理学习系统等，只具备一些较初级的学习能力。近年来，由于遗传算法的发展，基于进化机制的遗传学习成为一种新机器学习方法，它将知识表达为另一种符号形式——遗传基因型，通过模拟生物的进化过程，实现专门领域知识的合理增长型学习，所以有的学者将之称为次符号学习方法。机器学习成为遗传算法经典应用领域这一，归功于密歇根大学Holland等早期工作。他们将基于遗传的机器学习（Genetic-based machine learning,GBML）方法发展成为CS1的分类系统（classifed system）学习方式，奠定了遗传算法重要思想基础，后来初归纳为“密歇要方法”，1991年，De Jong等提出了“匹茨堡方法”。1994年，日本名屋大学的市桥等结合两种方法的优点提出“名古屋方法这些方法都分别在复杂机器学习系统中获得了成功的应用。

遗传算法应用于机器学习，与最优问题的应用存在着根本的不同，最优化问题强调调搜索收敛到一个近似最优解，而GBML不仅要获得代表一条规则的好的个体，而且更加强调最佳协调规则组合。一般而言，GBML应该具备以下几方面的机能：

①新规则生成，遵循优胜劣汰的机制；

②学习过程中不破坏已经获得的优良规则；

③规则数目不预先给定；

④相似的或者相互包含的规则，进行适当的取舍，规则集合不过分冗余。