2.2　遗传算法理论

2.2.1　遗传算法的生物学基础

自然选择学说认为适者生存，生物要存活下去，就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物跟环境之间的斗争三个方面。在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也将少得多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的个体。达尔文把这种在生存斗争中适者生存、不适者淘汰的过程叫作自然选择。

达尔文的自然选择学说表明，遗传和变异是决定生物进化的内在因素。遗传是指父代与子代之间，在性状上存在的相似现象；变异是指父代与子代之间，以及子代的个体之间，在性状上存在的差异现象。在生物体内，遗传和变异的关系十分密切。一个生物体的遗传性状往往会发生变异，而变异的性状有的可以遗传。遗传能使生物的性状不断地传送给后代，因此保持了物种的特性；变异能够使生物的性状发生改变，从而适应新的环境而不断地向前发展。

生物的各项生命活动都有它的物质基础，生物的遗传与变异也是这样。根据现代细胞学和遗传学的研究可知：遗传物质的主要载体是染色体，而染色体由基因组成；基因是有遗传效应的片段，它储存着遗传信息，可以被准确地复制，也能够发生突变。生物体自身通过对基因的复制和交叉，使其性状的遗传得到选择和控制。同时，通过基因重组、基因变异和染色体在结构和数目上的变异产生丰富多彩的变异现象。生物的遗传特性，使生物界的物种能够保持相对的稳定；生物的变异特性，使生物个体产生新的性状，以至形成了新的物种，推动了生物的进化和发展。

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

（1）生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状。染色体是由基因及其有规律的排列所构成的。

（2）生物的繁殖过程是由其基因的复制过程来完成的。同源染色体的交叉或变异会产生新的物种，使生物呈现新的性状。

（3）对环境适应能力强的基因或染色体，比适应能力差的基因或染色体有更多的机会遗传到下一代。

2.2.2　遗传算法理论基础

模式定理

模式定义：模式是描述种群中在位串的某些确定位置上具有相似性的位串子集的相似性模板。

不失一般性，考虑二值字符集｛0，1｝，由此可以产生通常的0、1字符串。增加一个符号“*”，称作“通配符”，即“*”既可以当作“0”，也可以当作“1”。这样，二值字符集｛0，1｝就扩展为三值字符集｛0，1，*｝，由此可以产生诸如0110，0 * 1 1 * *，* * 0 1 * 0之类的字符串。

基于三值字符集｛0，1，*｝所产生的能描述具有某些结构相似性的0、1字符串集的字符串，称作模式。这里需要强调的是，“*”只是一个描述符，而并非遗传算法中实际的运算符号，它仅仅是为了描述上的方便而引入的符号。

模式的概念可以简明地描述为具有相似结构特点的个体编码字符串。在引入了模式概念之后，遗传算法的本质是对模式所进行的一系列运算，即通过选择操作将当前群体中的优良模式遗传到下一代群体中，通过交叉操作进行模式的重组，通过变异操作进行模式的突变。通过这些遗传运算，一些较差的模式逐步被淘汰，而一些较好的模式逐步被遗传和进化，最终就可以得到问题的最优解。

多个字符串中隐含着多个不同的模式。确切地说，长度为L的字符串，隐含着2L个不同的模式，而不同的模式所匹配的字符串的个数是不同的。为了反映这种确定性的差异，引入模式阶概念。

模式阶定义：模式H中确定位置的个数称作该模式的模式阶，记作O（H）。

比如，模式011*1*的阶数为4，而模式0*****的阶数为1。显然，一个模式的阶数越高，其样本数就越少，因而其确定性就越高。但是，模式阶并不能反映模式的所有性质；即使具有同阶的模式，在遗传操作下，也会有不同的性质。为此，引入定义距的概念。

定义距定义：在模式H中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距，记作D（H）。

模式定理：在遗传算法选择、交叉和变异算子的作用下，具有低阶、短定义距，并且其平均适应度高于群体平均适应度的模式在子代中将呈指数级增长［8］。

模式定理又称为遗传算法的基本定理。模式定理阐述了遗传算法的理论基础，说明了模式的增加规律，同时也对遗传算法的应用提供了指导。根据模式定理，随着遗传算法的一代一代地进行，那些定义距短的、位数少的、高适应度的模式将越来越多，因而可期望最后得到的位串的性能越来越得到改善，并最终趋向全局的最优点。

模式的思路提供了一种简单而有效的方法，使得能够在有限字符表的基础上讨论有限长位串的严谨定义的相似性；而模式定理从理论上保证了遗传算法是一个可以用来寻求最优可行解的优化过程。

积木块假设

模式定理说明了具有某种结构特征的模式在遗传进化过程中其样本数目将呈指数级增长。这种模式定义为积木块，它在遗传算法中非常重要。

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

之所以称之为积木块，是由于遗传算法的求解过程并不是在搜索空间中逐一地测试各个基因的枚举组合，而是通过一些较好的模式，像搭积木一样，将它们拼接在一起，从而逐渐地构造出适应度越来越高的个体编码串。

模式定理说明了积木块的样本数呈指数级增长，亦即说明了用遗传算法寻求最优样本的可能性，但它并未指明遗传算法一定能够寻求到最优样本；而积木块假设说明了遗传算法的这种能力。

积木块假设：个体的积木块通过选择、交叉、变异等遗传算子的作用，能够相互结合在一起，形成高阶、长距、高平均适应度的个体编码串［9，10］。

积木块假设说明了用遗传算法求解各类问题的基本思想，即通过基因块之间的相互拼接能够产生出问题的更好的解，最终生成全局最优解。

从遗传算法的模式定理得到：具有高适应度、低阶、短定义矩的模式的数量会在种群的进化中呈指数级增长，从而保证了算法获得最优解的一个必要条件。而另一方面，积木块假设则指出：遗传算法有能力使优秀的模式向着更优的方向进化，即遗传算法有能力搜索到全局最优解。

2.2.3　遗传算法的基本概念

简单而言，遗传算法使用群体搜索技术，将种群代表一组问题解，通过对当前种群施加选择、交叉和变异等一系列遗传操作来产生新一代的种群，并逐步使种群进化到包含近似最优解的状态。由于遗传算法是自然遗传学与计算机科学相互渗透而形成的计算方法，所以遗传算法中经常会使用一些有关自然进化的基础术语［11］，其中的术语对应关系如表2.1所示。

群体和个体

群体是生物进化过程中的一个集团，表示可行解集。

个体是组成群体的单个生物体，表示可行解。

染色体和基因

染色体是包含生物体所有遗传信息的化合物，表示可行解的编码。

基因是控制生物体某种性状（即遗传信息）的基本单位，表示可行解编码的分量。

遗传编码

遗传编码将优化变量转化为基因的组合表示形式，优化变量的编码机制有二进制编码、十进制编码（实数编码）等。

二进制编码

这里介绍一下二进制编码的原理和实现。例如，求实数区间［0，4］上函数f（x）的最大值，传统的方法是不断调整自变量x本身的值，直到获得函数最大值；遗传算法则不对参数本身进行调整，而是首先将参数进行编码，形成位串，再对位串进行进化操作。在这里，假设使用二进制编码形式，我们可以由长度为6的位串表示变量x，即从“000000”到“111111”，并将中间的取值映射到实数区间［0，4］内。由于从整数上来看，6位长度的二进制编码位串可以表示0～63，所以对应［0，4］的区间，每个相邻值之间的阶跃值为4/63≈0.0635，这个就是编码精度。一般来说，编码精度越高，所得到的解的质量也越高，意味着解更为优良；但同时，由于遗传操作所需的计算量也更大，因此算法的耗时将更长。因而在解决实际问题时，编码位数需要适当选择。

实数编码

基于二进制编码的个体尽管操作方便，计算简单，但也存在着一些难以克服的困难而无法满足所有问题的要求。例如，对于高维、连续优化问题，由于从一个连续量离散化为一个二进制量本身存在误差，使得算法很难求得精确解。而要提高解的精度又必须加长编码串的长度，造成解空间扩大，算法效率下降。同时，二进制编码也不利于反映所求问题的特定信息，对问题信息和知识利用得不充分也会阻碍算法效率的进一步提高。为了解决二进制编码产生的问题，人们在解决一些数值优化问题（尤其是高维、连续优化问题）时，经常采用实数编码方式。实数编码的优点是计算精确度高，便于和经典连续优化算法结合，适用于数值优化问题；但其缺点是适用范围有限，只能用于连续变量问题。

适应度

适应度即生物群体中个体适应生存环境的能力。在遗传算法中，用来评价个体优劣的数学函数，称为个体的适应度函数。

遗传算法在进化搜索中基本上不用外部信息，仅以适应度函数为依据。它的目标函数不受连续可微的约束，且定义域可以为任意集合。对适应度函数的唯一要求是，针对输入可计算出能进行比较的结果。这一特点使得遗传算法应用范围很广。在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。适应度函数评估是选择操作的依据，适应度函数设计直接影响到遗传算法的性能。常见的适应度函数构造方法主要有：目标函数映射成适应度函数，基于序的适应度函数等。

遗传操作

遗传操作是优选强势个体的“选择”、个体间交换基因产生新个体的“交叉”、个体基因信息突变而产生新个体的“变异”这三种变换的统称。在生物进化过程中，一个群体中生物特性的保持是通过遗传来继承的。生物的遗传主要是通过选择、交叉、变异三个过程把当前父代群体的遗传信息遗传到下一代（子代）成员。与此对应，遗传算法中最优解的搜索过程也模仿生物的这个进化过程，使用所谓的遗传算子来实现，即选择算子、交叉算子、变异算子。

（1）选择算子：根据个体的适应度，按照一定的规则或方法，从第t代群体P（t）中选择出一些优良的个体遗传到下一代群体P（t+1）中。

其中，“轮盘赌”选择法是遗传算法中最早提出的一种选择方法，由Holland提出，因为它简单实用，所以被广泛采用。它是一种基于比例的选择，利用各个个体适应度所占比例的大小来决定其子代保留的可能性。若某个个体i的适应度为fi，种群大小为NP，则它被选取的概率表示为

个体适应度越大，则其被选择的机会也越大；反之亦然。为了选择交叉个体，需要进行多轮选择。每一轮产生一个［0，1］内的均匀随机数，将该随机数作为选择指针来确定被选个体。

（2）交叉算子：将群体P（t）中选中的各个个体随机搭配，对每一对个体，以某一概率（交叉概率Pc）交换它们之间的部分染色体。通过交叉，遗传算法的搜索能力得以飞跃提高。

交叉操作一般分为以下几个步骤：首先，从交配池中随机取出要交配的一对个体；然后，根据位串长度L，对要交配的一对个体，随机选取［1，L-1］中的一个或多个整数k作为交叉位置；最后，根据交叉概率Pc实施交叉操作，配对个体在交叉位置处，相互交换各自的部分基因，从而形成新的一对个体。

（3）变异算子：对群体中的每个个体，以某一概率（变异概率Pm）将某一个或某一些基因座上的基因值改变为其他的等位基因值。根据个体编码方式的不同，变异方式有：实值变异、二进制变异。对于二进制的变异，对相应的基因值取反；对于实值的变异，对相应的基因值用取值范围内的其他随机值替代。

变异操作的一般步骤为：首先，对种群中所有个体按事先设定的变异概率判断是否进行变异；然后，对进行变异的个体随机选择变异位进行变异。

2.2.4　标准遗传算法

标准遗传算法（Standard Genetic Algorithm，SGA）是由美国J.H.Holland教授与他的同事和学生于1975年研究出的遗传算法理论和方法［1］。20世纪60年代中期，Holland提出了位串编码技术。这种编码既适用于变异操作，又适用于交叉操作，并强调将交叉作为主要的遗传操作。随后，他将该算法应用到自然和人工系统的自适应行为的研究中。Holland早期有关遗传算法的许多概念一直沿用至今，遗传算法通用的编码技术和简单有效的遗传操作为其后来的成功应用和广泛应用奠定了基础。

标准遗传算法又称为经典遗传算法，它的优化变量由二进制编码来描述，多个优化变量的二进制编码串接在一起组成染色体，这种编码既适用于交叉操作，又适用于变异操作。在创建初始群体时，代表个体的二进制串是在一定字长的限制下随机产生的。交叉算子作用在按交叉概率选中的两个染色体上，随机选中交叉位置，将两个染色体上对应于这些位置上的二进制数值进行交换，生成两个新的个体；而变异算子作用在按变异概率随机选中的个体上，一般是随机选定变异位，将该位的二进制值取反，生成一个新的个体。

2.2.5　遗传算法的特点

遗传算法是模拟生物在自然环境中的遗传和进化的过程而形成的一种并行、高效、全局搜索的方法，它主要有以下特点：

（1）遗传算法以决策变量的编码作为运算对象。这种对决策变量的编码处理方式，使得在优化计算过程中可以借鉴生物学中染色体和基因等概念，模仿自然界中生物的遗传和进化等的机理，方便地应用遗传操作算子。特别是对一些只有代码概念而无数值概念或很难有数值概念的优化问题，编码处理方式更显示出了其独特的优越性。

（2）遗传算法直接以目标函数值作为搜索信息。它仅使用由目标函数值变换来的适应度函数值，就可确定进一步的搜索方向和搜索范围，而不需要目标函数的导数值等其他一些辅助信息。实际应用中很多函数无法或很难求导，甚至根本不存在导数，对于这类目标函数的优化和组合优化问题，遗传算法就显示了其高度的优越性，因为它避开了函数求导这个障碍。

（3）遗传算法同时使用多个搜索点的搜索信息。遗传算法对最优解的搜索过程，是从一个由很多个体所组成的初始群体开始的，而不是从单一的个体开始的。对这个群体所进行的选择、交叉、变异等运算，产生出新一代的群体，其中包括了很多群体信息。这些信息可以避免搜索一些不必搜索的点，相当于搜索了更多的点，这是遗传算法所特有的一种隐含并行性。

（4）遗传算法是一种基于概率的搜索技术。遗传算法属于自适应概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。虽然这种概率特性也会使群体中产生一些适应度不高的个体，但随着进化过程的进行，新的群体中总会更多地产生出优良的个体。与其他一些算法相比，遗传算法的鲁棒性使得参数对其搜索效果的影响尽可能小。

（5）遗传算法具有自组织、自适应和自学习等特性。当遗传算法利用进化过程获得信息自行组织搜索时，适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构。同时，遗传算法具有可扩展性，易于同别的算法相结合，生成综合双方优势的混合算法。

2.2.6　遗传算法的改进方向

标准遗传算法的主要本质特征，在于群体搜索策略和简单的遗传算子，这使得遗传算法获得了强大的全局最优解搜索能力、问题域的独立性、信息处理的并行性、应用的鲁棒性和操作的简明性，从而成为一种具有良好适应性和可规模化的求解方法。但大量的实践和研究表明，标准遗传算法存在局部搜索能力差和“早熟”等缺陷，不能保证算法收敛。

在现有的许多文献中出现了针对标准遗传算法的各种改进算法，并取得了一定的成效［12-15］。它们主要集中在对遗传算法的性能有重大影响的6个方面：编码机制、选择策略、交叉算子、变异算子、特殊算子和参数设计（包括群体规模、交叉概率、变异概率）等。

此外，遗传算法与差分进化算法、免疫算法、蚁群算法、粒子群算法、模拟退火算法、禁忌搜索算法、神经网络算法和量子计算等结合起来所构成的各种混合遗传算法，可以综合遗传算法和其他算法的优点，提高运行效率和求解质量。