遗传算法
第一章绪论
遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法，由美国J.Holland教授提出，其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可光泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域，是21世纪有关智能计算中的关键技术之一。本章先从生物进化讲起，接着示例介绍简单遗传算法的具体设计方法和步骤，然后归纳出遗传算法的一般特点，最后简要介绍遗传算法的研究历史和现状以及今后将研究的主要有关课题
1.1引言
生命科学--与工程科学的相互交叉、相互渗透和相互促进是近代科学技术发展的一个显著特点，而遗传算法的蓬勃发展正体现了科学发展的这一特征和趋势。
遗传算法(Genetic Algorithm-GA)，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1 975年首先提出的[1]。J.Holland教授和他的研究小组围绕遗传算法进行研究的宗旨有两个，一是抽取和解释自然系统的自适应过程，二是设计具有自然系统机理的人工系统。毫无疑问，Holland教授的研究，无论对白然系统还是对人工系统都是十分有意义的。
众所周知，在人工智能领域中，有不少间题需要在夏杂而庞大的搜索空间中寻找最优解或准最优解。像货郎担间题和规划问题等组合优化问题就是典型的例子。在求解此类问题时，若不能利用问题的固有知识来缩小搜索空间则会产生搜索的组合爆炸。因此，研究能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程，从而得到最优解或准最优解的通用搜索算法一直是令人瞩目的课题。遗传算法就是这种特别有效的算法。它的主要特点是简单、通用，鲁棒性强，适用于并行分布处理，应用范围广。尽管遗传算法本身在理论和应用方法上仍有许多待进一步研究的问题，但它在组合优化问题求解、自适应控制、规划设计、机器学习和人工生命等领域的应用中已展现了其特色和魅力。
1.2生物进化
生命自从在地球上诞生以来，就开始了漫长的生物进化历程，低级、简单的生物类型逐渐发展为高级、复杂的生物类型。这一过程已经由古生物学、胚胎学和比较解剖学等方面的研究工作所证实。生物进化的原因自古至今有着各种不同的解释，其中被人们广泛接受的是达尔文的自然选择学说。
自然选择学说认为，生物要生存下去，就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物跟无机环
境之间的斗争三个方面。在生存斗争中，具有有利变异(mutation)的个体容易存活下来，并且有更多的机会将有利变异传给后代;具有不利变异的个体就容易被淘汰，产生后代的机会也少得多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存，不适者淘汰的过程叫做自然选择。达尔文的自然选择学说表明，遗传和变异是决定生物进化的内在因素。遗传是指父代与子代之间，在性状上存在的相似现象。变异是指父代与子代之间，以及子代的个体之间，在性状上或多或少地存在的差异现象。在生物体内，遗传和变异的.关系十分密切。一个生物体的遗传性状往往会发生变异，而变异的性状有的可以遗传。遗传能使生物的性状不断地传送给后代，因此保持了物种的特性，变异能够使生物的性状发生改变，从而适应新的环境而不断地向前发展。
生物的各项生命活动都有它的物质基础，生物的遗传与变异也是这样。根据现代细胞学和遗传学的研究得知，遗传物质的主要载体是染色体(chromsome)，染色体主要是由DNA(脱氧核糖核酸)和蛋白质组成，其中DNA又是最主要的遗传物质。现代分子水平的遗传学的研究又进一步证明，基因(gene)是有遗传效应的片段，它储存着遗传信息，可以准确地复制，也能够发生突变，并可通过控制蛋白质的合成而控制生物的性状。生物体自身通过对基因的复制(reproduction)和交叉(crossover)，即基因分离、基因自由组合和基因连锁互换的操作使其性状的遗传得到选择和控制。同时，通过基因重组、基因变异和染色体在结构和数目上的变异产生丰富多采的变异现象。需要指出的是，根据达尔文进化论，多种多样的生物之所以能够适应环境而得以生存进化，是和上述的遗传和变异生命现象分不开的。生物的遗传特性，使生物界的物种能够保持相对的稳定;生物的变异特性，使生物个体产生新的性状，以至于形成了新的物种，推动了生物的进化和发展。
1.3遗传算法
遗传算法是模拟前述生物进化过程的计算模型。遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理以及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位。
1.3.1基拙用语
由于遗传算法是自然遗传学和计算机科学相互结合渗透而成的新的计算方法，所以遗传算法中经常使用有关自然进化中的一些基础用语。了解这些用语对于学习和应用遗传算法是十分必要的。
如前所述，生物的遗传物质的主要载体是染色体，DNA是其中最主要的遗传物质，而基因又是控制生
物性状的遗传物质的功能单位和结构。复数个基因组成染色体，染色体中基因的位置称作基因座(locus)，而基因所取的值又叫做等位基因(alleles)。基因和基因座决定了染色体的特征，也就决定了生物个体的性状。此外，染色体有两种相应的表示模式，即基因型(genetype)和表现型(phenotype)。所谓表现型是指生物个体所表现出来的性状，而基因型指与表现型密切相关的基因组成。同一种基因型的生物个体在不同的环境条件下可以有不同的表现型，因此表现型是基因型与环境条件相互作用的结果。在遗传算法中，染色体对应的是数据或数组，在标准的遗传算法中，这通常是由一维的串结构数据来表现的。串上各个位置对应上述的基因座，而各位置上所取的值对应上述的等位基因。遗传算法处理的是染色体，或者叫基因型个体(individuals)。一定数量的个体组成了群体(population)，也叫集团。群体中个体的数日称为群体的大小(population size)，也叫群体规模。而各个体对环境的适应程度叫做适应度(fitness)。
此外，执行遗传算法时包含两个必需的数据转换操作，一个是表现型到基因型的转换，另一个是基因型到表现型的转换。前者是把搜索空间中的参数或解转换成遗传空问中的染色体或个体，此过程又叫做编码(coding)操作;后者是前者的一个相反操作，叫做译码(decoding)操作口关于编码和译码操作的详细介绍将在第二章中进行。
为便于读者在以后各章节学习遗传算法时查阅方便，将自然遗传学和人工遗传算法中所使用的基础用语的对应关系列于表1.1中。
1.3.2标准遗传算法
遗传算法是具有“生成+检测”(generate and test)的迭代过程的搜索算法。它的基本处理流程如下所示。
1. 编码和初始集团形成
2. 集团中个体适应度的检测评估
3. 选择 -> 交叉 -> 变异
4. 跳转至2
由此可见，遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。选择(selection)、交叉(crossover)和变异(mutation)是遗传算法的3个主要操作算子，它们构成了所谓的遗传操作(genetic operation)，使遗传算法具有了其它传统方法所没有的特性。遗传算法中包含了5个基本要素:1)参数编码;2)初始群体的设定;3)适应度函数的设计;4)遗传操作设计;5)控制参数设定(主要是指群体大小和使用遗传操作的概立等。这5个要素构成了遗传算法的核心内容。我们将在第二章中对它们作详细深入的论述。这里，我们仅以一个简单的函数极值求解为例，来概述遗传算法的基本概念及处理过程。
假定用遗传算法求f(x)=x^2 函数的最大值，x 属于[0，31]。表1.2给出了用遗传算法求解此间题的
计算过程和结果。
下面我们对表1.2中的各计算量作详细介绍。
l.编码
由于遗传算法不能直接处理解空间的解数据，因此我们必须通过编码将它们表示成遗传空间的基因型串结构数据。在表1。2中，我们把变量X编码为5位长的二进制无符号整数表示形式。比如X=13可表示为01101的形式。
2.初始群体的生成
由于遗传算法的群体型操作需要，所以我们必须为遗传操作准备一个由若干初始解组成的初始群体。为了简化说明，在表1.2中我们取群体大小为4，即群体由4个个体组成。在表1.2左端给出了这一初始群体的成员。需要说明的是，初始群体的每个个体都是通过随机方法产生的。初始群体也称作为进化的初始代，即第一代(first generation)。
3.适应度评估检检测
遗传算法在搜索进化过程中一般不需要其它外部信息，仅用评估函数值来评估个体或解的优劣，并作为以后遗传操作的依据。评估函数值又称作适应度。这里，我们根据f(x)=x^2来评估群体中各个体。显然，为了利用了f=x^2这一评估函数即适应度函数，要把基因型个体译码成表现型个体，即搜索空间中的解，比如11000要译码为24。
4.选择(selection)
选择或复制操作的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。判断个体优良与否的准则就是各自的适应度值。显然这一操作是借用了达尔文适者生存的进化原则，即个体适应度越高，其被选择的机会就越多。选择操作实现方式很多。这里，我们采用和适应度值成比例的概率方法来进行选择的方法。具体地说，就是首先计算群休中所有个体适应度的总和 Count(f)。，再计算每个个体的适应度所占的比例(f / Count(f))，并以此作为相应的选择概率P。表l-2给出了选择4个个体的概率，由此概率可计算出每个个体被选择的次数。我们也可以采用图1.2所示的赌轮方式来决定各个体的选择份数。赌轮上按前述的各个体适应按比例进行了分配。转动赌轮4次，我们就可以决定各自的选择份数:表1.2给出了相应的结果:个体1和个体4各复制1份，个体2复制2份，个体3不复制而被淘汰。这是我们所期待的结果，即最优秀的个体(个体2，适应度为576获得了最多的生存繁殖机会(2份复制)，最差的个体(个体3，适应度为64)被淘汰。由此得到的4份复制送到配对库(mating pool)，以备配对繁殖。
5.交叉操作
简单的交叉(即一点交叉)可分两步进行:首先对配对库中的个体进行随机配对;其次，在配对个体中随机设定交叉处(表l.2中的配对库中的竖线表示交叉处)，配对个体彼此交换部分信息。由表1.2可见，配对库中的个体2与个
体1配对，交叉处为4，通过交叉得到了两个新的个体:
0110|1 -> 01100
1100|0 -> 11001
表1.2
编号 |1 |2 |3 |4
初始群体 n=4|01101 |11000 |01000 |10011
X值 |13 |24 |8 |19
适应度 x^2|169 |576 |64 |361
选择概率 P |0.14 |0.49 |0.06 |0.31
适应度期望 |0.58 |1.97 |0.22 |1.23
计数来自赌轮|1 |2 |0 |1
复制后交配率|0110:1|1100:0|11:000|10:011
配对随机选择|2 |1 |4 |3
交叉位置随机|4 |4 |2 |2
新一代群体 |01100 |11001 |11011 |10000
X值 |12 |25 |27 |16
f(x)=x^2 |144 |625 |729 |256
同样，配对库中的个体3和个体4的配对交叉(交叉处为2)得到另外两个新个体11011和10000这4个新个体形成了新的群体，即新一代。需要指出的是，交叉操作是遗传算法中最主要的遗传操作。由于交义操作我们得到了新一代个体。仔细观察比较表1.2中新旧群体，不难发现新群体中个体适应度的平均值和最大值都有了明显提高。由于这个例子的适应度函数也就是函数f(x)=x^2本身，所以函数值也变大了。由此可见，新群体中的个体(即解)的确是朝着我们所期望的方向进化了。当然，这个例子所用的是单变量函数，这也许不足以说明遗传算法的优点，但在本书第三章中我们将会看到，对于由几十到几百个变量组成的函数，遗传算法照样能不依靠任何搜索空间的外部知识而仅用适应度函数来指导和优化搜索的方
向。
6.变异
变异操作是按位〔bit)进行的，即把某一位的内容进行变异。对于二进制编码的个体来说，若某位原为O，则通过变异操作就变成了1，反之亦然。变异操作同样也是随机进行的。一般而言，变异概率Pm都取得很小。在这个例子中，我们取Pm=0.001，由于群体中共有 20*0.001 = 0.02位可以变异，这意味群体中没有一位可变异。变异操作是十分微妙的遗传操作，它需要和交叉操作妥善配合使用，目的是挖掘群体中个体的多样性，克服有可能限于局部解的弊病。关于这一点我们将在第二章中进行充分的讨论。
在本例的模拟计算中，我们仅通过一代进化就使间题的解得到了优化，如果按图1.1所示的那样进行多次迭代处理，或者说群体继续不断地一代代进化下去，那么，最终一定可以得到最优解或近似最优解。
上述的遗传算法操作过程构成了标准的遗传算法，有时也叫简单遗传算法，简称SGA(Simple GA)。SGA的特点是:
1)采用赌轮选择方法;
2)随机配对;
3)采用一点交叉并生成两个子个体;
4)群体内允许有相同的个体存在;
通过上述简单例子的讨论，我们不难发现，遗传算法所依赖的两个必不可少而又最重要的操作(
即选择和交叉)是出乎意料的简单可行。除了随机数产生、串结构数据复制以及部分串结构数据互换外，似乎没有更多更复杂行为。读者一定会问，在这种简单而似乎有些盲目的结构数据复制和重组的操作中，遗传算法究竟干了些什么?其中是否存在某种规律或带有指导性的结论?本书的第二章将对这些问题进行深入的讨论并给予回答。
1.4遗传算法的特点
遗传算法的特点，可以从它和传统的搜索方法的对比以及分析它和若干搜索方法与自律分布系统的亲近关系充分体现出来。
1.4.1遗传算法和其它传统搜索方法的对比
首先让我们把它和几个主要的传统搜索方法作一简要对比，以此来看看遗传算法的鲁棒性到底强在哪里?作为一个搜索方法，它的优越性到底体现在何处?
解析方法是常用的搜索方法之一。它通常是通过求解使目标函数梯度为零的一组非线性方程来进行搜索的。一般而言，若目标函数连续可微，解的空间方程比较简单，解析法还是可以用的。但是，若方程的变量有几十或几百个时，它就无能为力了。爬山法也是常用的搜索方法，它和解析法一样都是属于寻找局部优解的方法。对于爬山法而言，只有在更好的解位于当前解附近的前提下，才能继续向优解搜索。显然这种方法对于具有单峰分布性质的解空间才能进行行之有效的搜索，并得到最优解，而对于如图1.3所示的多峰空间，爬山法(包括解析法)连局部最优解都很难得到。
另一种典型的搜索方法是穷举法。该方法简单易行，即在一个连续有限搜索空间或离散无限搜索空间中，计算空间中每个点的目标函数值，且每次计算一个。显然，这种方法效率太低而鲁棒性不强口许多实际问题所对应的搜索空间都很大，不允许一点一点地慢慢求解。
随机搜索方法比起上述的搜索方法有所改进，是一种常用的方法，但它的搜索效率依然不高。一般而言，只有解在搜索空间中形成紧致分布时，它的搜索才有效。但这一条件在实际应用中难于满足。需要指出的是，我们必须把随机搜索(random search)方法和随机化技术(randomized technique)区分开来。遗传算法就是一个利用随机化技术来指导对一个被编码的参数空间进行高效搜索的方法。而另一个搜索方法—模拟退火(simulated annealing)方法也是利用随机化处理技术来指导对于最小能量状态的搜索。因此，随机化搜索技术并不意味着是无方向搜索，这一点是与随机搜索有所不同的。
当然，前述的几种传统的搜索方法虽然鲁棒性不强，但这些方法在一定的条件下，尤其是将它们混合使用也是有效的。不过，当面临更为复杂的问题
时，必须采用像遗传算法这样更好的方法。
遗传算法具有十分顽强的鲁棒性，这是因为比起普通的优化搜索方法，它采用了许多独特的方法和技术，归纳起来，主要有以下几
个方面:
(l)遗传算法的处理对象不是参数本身，而是对参数集进行了编码的个体。此编码操作，使得遗传算法可直接对结构对象进行操作。所谓结构对象泛指集合、序列、矩阵、树、图、链和表等各种一维或二维甚至一三维结构形式的对象。这一特点，使得遗传算法具有广泛的应用领域。比如:
l)通过对连接矩阵的操作，遗传算法可用来对神经网络或自动机的结构或参数加以优化;
2)通过对集合的操作，遗传算法可实现对规则集合或知识库的精炼而达到高质量的机器学习目的;
3)通过对树结构的操作，用遗传算法可得到用于分类的最佳决策树;
4)通过对任务序列的操作，遗传算法可用于任务规划，而通过对操作序列的处理，遗传算法可自动构造顺序控制系统。
(2)如前所述，许多传统搜索方法都是单点搜索算法，即通过一些变动规则，问题的解从搜索空间中的当前解(点)移到另一解(点)。这种点对点的搜索方法，对于多峰分布的搜索空间常常会陷于局部的某个单峰的优解:相反，遗传算法是采用同时处理群体中多个个体的方法，即同时对搜索空间中的多个解进行评估。更形象地说，遗传算法是并行地爬多个峰。这一特点使遗传算法具有较好的全局搜索性能，减少了陷于局部优解的风险。同时，这使遗传算法本身也比较易于并行化。
(3)在标准的遗传算法中，基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，并在此基础上进行遗传操作。需要着重提出的是，遗传算法的适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定C对适应度函数的唯一要求是，对于输人可计算出加以比较的正的输出。遗传算法的这一特点使它的应用范围大大扩展。
(4)遗传算法不是采用确定性规则，而是采用概率的变迁规.则来指导它的搜索方向。在以后的章节中我们将会看到，遗传算法采用概率仅仅是作为一种工具来引导其搜索过程朝着搜索空间的更优化的解区域移动。冈此虽然看起来它是一种盲目搜索方法，但实际上有明确的搜索方向。
上述这些具有特色的技术和方法使得遗传算法使用简单，鲁棒性强，易于并行化，从而应用范围甚广。
1.4.2遗传算法和若干搜索方法的亲近关系
如果从更高的层次来观察遗传算法，我们不难发现它和若干搜索方法有着明显的亲近关系。分析这些关系可使我们从另一个侧面更深入地
了解遗传算法的特点。
1.遗传算法和射束搜索(beam search)方法
射束搜索方法是为了抑制搜索空间计算量的组合爆炸而提出的一种最优搜索方法。该方法预先把射束幅度定义为一个长度为N的开放表，在搜索的进程中仅维持N个最优节点，其它节点一律舍去。通过搜索，若发现有新的更好的节点，则用它把开放表中最差的节点替换掉。该搜索过程和遗传算法有一定的相似性。遗传算法中的“群体大小”相当于射束搜索中的“射束幅度”。
2.遗传算法和单纯方法(simplex mdhod)
单纯方法是一种直接搜索方法。它把日标函数值排序加以利用。这样，由多个端点形成的单路就可对应山的形状，然后进行爬山搜索。单纯方法的基本操作是反射(reflectin)操作，且反复进行。这十分类似于遗传算法中的“交叉”操作。同时单纯方法中形成单路的端点数相当于遗传算法中的群体大小。显然，单纯方法和遗传算法在利用多点信息的全局处理上是有共同点的。
3.遗传算法和模拟退火法
模拟退.火法的最大特点是搜索中可以摆脱局部解，这是传统约爬山法所不具备的。遗传算法中的“选择”操作是以和各个体的适应