遗传算法防御反向分析

遗传算法是一种具有高度非线性映射、自适应和自组织等功能，在解决局部最优与全局最优问题方面有独特优势的人工智能方法（周明，孙树栋，1999；刑文训，谢金星，1999；玄光南，程润伟，2000）。

一、遗传算法的生物学基础

生物在自然界中的生存繁衍，显示出了其对自然环境的优异自适应能力。受其启发，人们开始致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。遗传算法（Genetic Algorithm，GA）就是这种生物行为的计算机模拟中的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。

1.遗传与变异

生物从其亲代继承特性或性状的生命现象，称为遗传。研究这种生命现象的科学，称为遗传学。

构成生物的基本结构和功能单位是细胞。细胞中含有一种微小的丝状化合物，称为染色体。生物的所有遗传信息都包含在染色体中。遗传信息是由基因组成的，生物的各种性状由其相应的基因所控制，基因是遗传的基本单位。细胞通过分裂具有自我复制的能力，在细胞分裂的过程中，其遗传基因也同时被复制到下一代，从而其性状也被下一代所继承。生物学家的研究表明，控制并决定生物遗传性状的染色体主要由一种叫做脱氧核糖核酸（简称DNA）的物质构成。除此之外，染色体中还含有很多蛋白质。DNA在染色体中有规则地排列，是大分子的有机聚合物，其基本结构单位是核苷酸。每个核苷酸由4种称为碱基的环状有机化合物中的一种、一个分子戊糖和磷酸分子所组成。许多核苷酸通过磷酸二酯键相结合，形成一个长长的链状结构，两个链状结构再通过碱基间的氢键有规律地扭合在一起，相互卷曲，形成一种双螺旋结构。另外，低等生物中还含有一种叫做核糖核酸（简称RNA）的物质，它的作用和结构与DNA类似。基因就是DNA或RNA长链结构中占有一定位置的基本遗传单位。生物的基因数量根据物种的不同而不同，小的病毒只含有几个基因，而高等动植物的基因却以数万计。DNA中，遗传信息在一条长链上按一定的模式排列，亦即进行了遗传编码。一个基因或多个基因决定了组成蛋白质的20种氨基酸的组成比例及其排列顺序。遗传基因在染色体中所占据的位置，称为基因座。同一基因座可能有的全部基因，称为等位基因。某种生物所特有的基因及其构成形式，称为该生物的基因型。而该生物在环境中呈现出的相应的性状，称为该基因的表现型。一个细胞核中所有染色体所携带的遗传信息的全体，称为一个基因组。

细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新细胞就继承了旧细胞的基因。有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉而重组，亦即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合而形成两个新的染色体。另外，在进行细胞复制时，虽然概率很小，但也有可能产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体。这些新的染色体表现出新的性状，于是，遗传基因或染色体在遗传的过程中由于各种各样的原因而发生变化。

2.进化

生物在其延续生存的过程中，逐渐适应其生存环境，使其品质不断得到改良，这种生命现象称为进化。生物的进化是以集团的形式共同进行的，这样的一个团体称为群体，组成群体的单个生物称为个体，每一个个体对其生存环境都有不同的适应能力，这种适应能力称为个体的适应度。达尔文（Darwin）的自然选择学说构成了现代进化论的主体。自然选择学说认为，通过不同生物间的交配以及其他一些原因，生物的基因有可能发生变异而形成一种新的生物基因，这部分变异了的基因也将遗传到下一代。虽然这种变化的概率是可以预测的，但具体哪一个个体发生变化却是偶然的。这种新的基因依据其与环境的适应程度决定其增殖能力，有利于生存环境的基因逐渐增多，而不利于生存环境的基因逐渐减少。通过这种自然的选择，物种将逐渐向适应生存环境的方向进化，从而产生出优良的物种。

3.遗传与进化的系统观

虽然人们还未完全揭开遗传与进化的奥秘，既没有完全掌握其机制，也不完全清楚染色体编码和译码过程的细节，更不完全了解其控制方式，但遗传与进化的以下几个特点却为人们所共识：

（1）生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状。

（2）染色体是由基因及其有规律的排列构成的，遗传和进化过程发生在染色体上。

（3）生物的繁殖过程是由其基因的复制过程来完成的。

（4）通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状。

（5）对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代。

二、遗传算法简介

遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法，最早由美国密执安大学的Holland教授提出，起源于20世纪60年代对自然和人工自适应系统的研究。70年代，De Jong基于遗传算法的思想，在计算机上进行了大量的纯数值函数优化计算实验。在一系列研究工作的基础上，80年代，Goldberg进行归纳总结，形成了遗传算法的基本框架。

一个求函数最小值的优化问题可描述为下述数学规划模型

式中：{X}为决策变量；φ（{X}）为目标函数；U为基本空间；R为U的一个子集。

图1-4-7　最优化问题的可行解及可行解集合

满足约束条件的解{X}称为可行解，集合R表示由所有满足约束条件的解所组成的一个集合，称为可行解集合。它们之间的关系如图1-4-7所示。

对于上述最优化问题，目标函数和约束条件种类繁多，有的是线性的，有的是非线性的；有的是连续的，有的是离散的；有的是单峰值的，有的是多峰值的。在很多复杂情况下，要想完全精确地求出其最优解既不可能，也不现实，因而求出其近似最优解或满意解成为研究者的主要着眼点。一般来说，求最优解或近似最优解的方法主要有：枚举法、启发式算法和搜索算法。

1.枚举法

枚举出可行解集合内的所有可行解，以求出精确最优解。对于连续函数，该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远达不到最优解。另外，当枚举空间比较大时，该方法的求解效率比较低，有时甚至在目前最先进的计算工具上都无法求解。

2.启发式算法

寻求一种能产生可行解的启发式规则，以找到一个最优解或近似最优解。该方法的求解效率虽然比较高，但对每一个需要求解的问题都必须找出其特有的启发式规则，这个启发式规则无通用性，不适合于其他问题。

3.搜索算法

寻求一种搜索算法，该算法可在可行解集合的一个子集内进行搜索操作，以找到问题的最优解或近似最优解。该方法虽然不能保证一定能够得到问题的最优解，但若适当地利用一些启发知识，则可在近似解的质量和求解效率上达到一种较好的平衡。

把每一个X i看作一个遗传基因，它的所有可能取值称为等位基因，这样，X可看作是由n个遗传基因组成的一个染色体。一般情况下，染色体的长度n是固定的，但对一些问题，n也可以是变化的。根据不同的情况，等位基因可以是一组整数，也可以是某一范围内的实数，或者是纯粹的一个记号。最简单的等位基因是由0和1这两个整数组成的，相应的染色体可表示为一个二进制符号串。这种编码所形成的排列形式X是个体的基因型，与它对应的X值是个体的表现型。通常个体的表现型和其基因型是一一对应的关系。染色体X也称为个体X，对于每一个个体X，要按照一定的规则确定其适应度。个体的适应度与其对应的个体表现型X的目标函数值相关联，X越接近目标函数的最优点，其适应度越大；反之，其适应度越小。

遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的，所有的染色体X组成了问题的搜索空间。

生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体。与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代过程，第t代群体记做P（t），经过一代遗传和进化后，得到第t+1代群体，它们也是由多个个体组成的集合，记做P（t+1）。这个群体经过不断的遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现型X将达到或接近于问题的最优解X*。

生物的进化过程主要是通过染色体之间的交叉和染色体的变异来完成的。与此相对应，遗传算法中最优解的搜索过程是模仿生物的进化过程，使用遗传算子作用于群体P（t）中，进行遗传操作，从而得到新一代群体P（t+1）。

三、基本遗传算法的运算过程

基于对自然界中生物遗传与进化机理的模仿，针对不同的问题，学者们设计了许多不同的编码方法来表示问题的可行解，开发了许多不同的遗传算子来模仿不同环境下的生物遗传特性。不同的编码方法和不同的遗传算子构成了各种不同的遗传算法。但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。基于这个共同特点，Goldberg总结了最基本的遗传算法。基本遗传算法只使用选择算子、交叉算子和变异算子这3种基本遗传算子。图1-4-8为基本遗传算法的运算过程示意图。

图1-4-8　基本遗传算法的运算过程

由图1-4-8可以看出，基本遗传算法的主要运算过程为：

（1）初始化。设置进化代数计数器t←0；设置最大进化代数T；随机生成M个个体作为初始群体P（0）。

（2）个体评价。计算群体P（t）中各个个体的适应度。

（3）选择运算。将选择算子作用于群体。

（4）交叉运算。将交叉算子作用于群体。

（5）变异运算。将变异算子作用于群体。群体P（t）经过选择、交叉、变异运算之后得到下一代群体P（t+1）。

（6）终止条件判断。若t＜T，则t←t+1，转到步骤（2）；若t=T，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。

四、遗传算法的特点

单纯形法、梯度法、动态规划法、分枝定界法等，都是为各种优化计算提出的，它们各有长处和适用范围，也各有限制。遗传算法作为一类可用于复杂系统优化计算的鲁棒搜索算法，与其他一些优化算法相比，主要有下述特点：

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

（2）遗传算法直接以目标函数值作为搜索信息。传统的优化算法不仅需要利用目标函数值，而且往往需要目标函数的导数值等其他一些辅助信息才能确定搜索方向。而遗传算法仅使用由目标函数值变换来的适应度，即可确定进一步的搜索方向和搜索范围，无需目标函数的导数值等其他一些辅助信息。这个特性对很多无法求导数的目标函数，或导数不存在的目标函数的优化问题，以及组合优化问题等，显得比较优越。再者，直接利用目标函数或个体适应度，也可使得把搜索范围集中到适应度较高的部分搜索空间中，从而提高了搜索效率。

（3）遗传算法同时使用多个搜索点的搜索信息。传统的优化算法往往是从解空间中的一个初始点开始最优解的迭代搜索过程。单个搜索点所提供的搜索信息毕竟不多，所以搜索效率不高，有时甚至使搜索过程陷于局部最优解而停滞不前。遗传算法从一个由很多个体所组成的初始群体开始最优解的搜索过程。对这个群体所进行的选择、交叉、变异等运算，产生出的是新一代群体，在这之中包括了很多群体信息。这些信息可以避免搜索一些不必搜索的点，所以实际上相当于搜索了更多的点，这是遗传算法特有的一种隐含并行性。

（4）遗传算法使用概率搜索技术。很多传统的优化算法往往使用的是确定性的搜索方法，一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系，这种确定性往往也有可能使得搜索永远达不到最优点，因而也限制了算法的应用范围。而遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等运算都以一种概率的方式来进行，从而增加了其搜索过程的灵活性。虽然这种概率特性也会使群体中产生一些适应度不高的个体，但随着进化过程的进行，新的群体中总会产生出许多优良的个体。理论和实践都已证明了在一定条件下遗传算法总是以概率1收敛于问题的最优解。

五、应用举例——岩体初始应力场反演

式中：σi为岩体自重、地质构造运动等对初始应力场形成有贡献的因子的函数。由于这些因子对初始应力场的影响可通过在有限单元法计算模型上施加荷载及边界条件等效模拟，因此σi也可看作有限单元计算模型上施加荷载及边界条件的函数。

显然，当式（1-4-56）的值足够小，即φ→0时，可以将模拟应力场视为初始应力场，反演完成。

（一）遗传算法设计简析

对式（1-4-56）所描述的优化问题，应用遗传算法进行求解的步骤如下：

（1）根据地形地质勘测试验资料确定有限单元法计算模型，这一步和有限单元法正算法完全一致。

（2）确定遗传算法进化代数T，确定有限单元法计算模型可能的荷载种类、数量及取值范围，在此范围内随机产生一定数目的个体（每组荷载情况对应一个个体），作为初始群体。

（3）应用有限单元法计算初始群体中每个个体对应的实测点处的模拟应力，然后根据实测应力，按式（1-4-56）计算相应的φ值，作为个体的适应度。

（4）根据每个个体的适应度，按一定的方式进行选择操作，将被选中的个体送至配对库中，用以繁殖下一代。

（5）从配对库中任选两个个体进行交叉，产生新的个体。(www.xing528.com)

（6）对每个个体实施一定的变异操作，又产生一定数量的新个体。

（7）再应用有限单元法，计算新一代个体对应的实测点处的模拟应力，计算其适应度。

（8）若代数小于T，则转到步骤（4）；否则，以进化过程中得到的具有最大适应度的个体作为最优解输出，停止计算。

（9）对进化产生的最优解进行人工判断，若达不到精度要求，则以第T代的遗传信息作为第一代，从步骤（3）开始下一个进化过程；否则，终止计算。

图1-4-9　岩体初始应力场反演的遗传算法运算过程

运算过程如图1-4-9所示。有限单元法计算作为一个独立的模块嵌在遗传算法中，该遗传算法所能解决问题的复杂程度，完全取决于有限单元法计算模块。由于有限单元法已能很好地解决弹性、弹塑性、弹粘塑性等复杂问题，因此，基于遗传算法的岩体初始应力场反演已经彻底摆脱了线性回归反演中的弹性假定。

（二）编码

在遗传算法的运行过程中，不对所求解问题的实际决策变量进行直接操作，而是对表示可行解的个体编码施加选择、交叉、变异等遗传操作，通过这种遗传操作来达到优化的目的。把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法，称为编码。

迄今已经提出的编码方法可以分为三大类。

（1）二进制编码方法。以二进制符号0和1所组成的编码符号串作为个体编码。

（2）浮点数编码方法。以决策变量的真实值作为个体编码。

（3）符号编码方法。以无数值含义、只有代码含义的符号集作为个体编码。

由于二进制编码方法具有编码、解码操作简单易行，交叉、变异等遗传操作便于实现，符合最小字符集编码原则（能使问题得到自然表示或描述的具有最小编码字符集）等优点，在遗传算法中获得广泛使用。

在岩体初始地应力场反演问题中，由若干组荷载构成问题空间。根据工程经验，先确定荷载的取值范围，再采用二进制编码方法进行编码。这样，每一组中的每个荷载都可以用一个二进制子串来表示。将同组中的全部荷载二进制子串串联起来，可以得到一个完整的子串，即可构成遗传算法空间中的染色体。具体操作如下：

x表示一个荷载，其取值范围为[a，b]，假设本问题二进制编码与实际变量的最大误差为e，则x子串的长度n的取值为

子串与[a，b]的对应关系为：当子串全为0时，对应a；当子串全为1时，对应b；其他情况下，子串a 1a 2…a n将对应[a，b]中的一个数，其值为

（三）适应度函数

在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某个物种对于其生存环境的适应程度。对生存环境适应度较高的物种将会有更多的繁殖机会；而对生存环境适应程度较低的物种，其繁殖机会相对较少，甚至会逐渐灭绝。与此类似，遗传算法中也使用适应度这个概念来度量群体中各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概率较大；适应度较低的个体遗传到下一代的概率相对较小。度量适应度的函数称为适应度函数。

在地应力反演中，取如式（1-4-56）所示的实测应力值与模拟应力值之差的平方和来描述解的偏差程度。φ值越小，越接近最优解，个体适应度越高。将φ乘以-1后再作为个体的适应度，于是，适应度函数可定义为

（四）遗传算子

完成遗传操作功能的遗传算子是遗传算法的核心，包括选择、交叉和变异三个基本算子。

1.选择算子

在生物的遗传和自然进化过程中，适应程度较高的物种将会有更多的机会遗传到下一代。模仿这一过程，遗传算法使用选择算子对群体中的个体进行优胜劣汰操作。其基本思想是：根据各个个体的适应度，按照一定的规则或方法，从群体中选择出一些优良的个体遗传到下一代。

基本遗传算法中使用的选择算子是比例选择算子。其基本思想是：各个个体被选中的概率与其适应度大小成正比。由于选择操作的随机性，有可能破坏当前群体中适应度最好的个体，从而对遗传算法的运行效率、收敛性产生不利影响。因此，希望适应度最好的个体要尽可能地保留到下一代群体中。为达到这一目的，遗传算法在选择操作中可采用最优保存策略。

最优保存策略基本思想是：当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用它来替换本代群体中经过交叉、变异等遗传操作后产生的适应度最低的个体。具体操作过程如下：

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

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

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

最优保护策略还可加以推广，即在每一代的进化过程中保留多个最优个体不参加交叉、变异等遗传运算，而直接将它们复制到下一代中。这种选择方法也称为稳态复制。

最优保护策略的实施保证了迄今为止所得到的最优个体不被遗传操作破坏，是遗传算法收敛性的重要保证。但是，它也容易使得某个局部最优个体不易被淘汰，反而快速扩散，从而使得算法的全局搜索能力不强。为了克服这个缺点，可在应用最优保护策略的同时，配合使用具有随机性的选择算子。笔者采用最优保护策略配合以随机联赛选择作为选择算子。

随机联赛选择是一种基于个体适应度之间大小关系的选择方法。其基本思想是：每次随机选取几个个体之中适应度最高的一个个体遗传到下一代中。在联赛选择中，只有个体适应度之间的大小比较运算。每次进行适应度大小比较的个体数目N称为联赛规模。一般情况下，N取值为2。具体操作过程如下：

（1）从群体中随机选取N个个体进行适应度大小比较，将高的个体遗传到下一代。

（2）将上述过程重复M次，即可得到下一代群体中的M个个体。

2.交叉算子

在生物的自然进化过程中，两个同源染色体通过交配而重组，形成新的染色体，从而产生新的个体或物种。交配重组是生物遗传和进化过程中的一个重要环节。模仿这个环节，在遗传算法中使用交叉算子来产生新的个体。其基本思想是：对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算在遗传算法中起着关键作用，是遗传算法的重要特征。

遗传算法中，在交叉运算之前还必须先对群体中的个体进行配对。本遗传算法采用的配对策略是随机配对，即将群体中的M个个体以随机的方式组成配对个体组，交叉操作在这些配对个体组中的两个个体之间进行。

交叉算子的设计和实现一般与所求解的具体问题相关，要求既不要太多地破坏个体编码串中表示优良性状的优良模式，又要能够有效地产生出一些较好的新个体模式。笔者采用适合二进制编码个体的均匀交叉作为交叉算子。

均匀交叉是指两个配对个体的每一个基因座上的基因都以相同的交叉概率Pc进行交换，从而形成两个新的个体。具体操作过程如下：

（1）随机产生一个与个体编码串长度等长的屏蔽字W=w 1 w 2…w i…w l，其中l为个体编码串长度。

（2）按下述规则从A、B两个父代个体中产生出两个新的子代个体A′、B′。

1）若w i=0，则A′在第i个基因座上的基因值继承A的对应基因值，B′在第i个基因座上的基因值继承B的对应基因值。

2）若w i=1，则A′在第i个基因座上的基因值继承B的对应基因值，B′在第i个基因座上的基因值继承A的对应基因值。

均匀交叉操作如图1-4-10所示。

图1-4-10　均匀交叉操作

3.变异算子

在生物的自然进化过程中，细胞分裂复制环节有可能会因为某些偶然因素的影响而产生一些复制差错，导致生物某些基因发生变异。虽然发生此类变异的概率很小，但仍是产生新物种的一个不可忽视的原因。模仿这一环节，遗传算法引入变异算子来产生新个体。

（1）基本位变异。以变异概率Pb随机指定个体编码串中某一位或几位基因座，对其基因值作变异操作。对于二进制编码个体，变异操作为对其基因值作反运算，如图1-4-11所示。

（2）非均匀变异。以概率P u随机指定个体，对其原有基因值作一随机扰动，以扰动后的结果作为变异后的新基因值。相当于整个解向量在解空间进行了一个轻微的变动。

图1-4-11　基本位变异

（五）算例结果

采用与本章第五节相同的算例，依据实测点的应力值，通过遗传算法进行初始应力场反演（图1-4-2，图1-4-3）。

首先假定Δ和U、V的取值范围均为[-10，10]，以式（1-4-59）作为适应度函数。遗传算法各运行参数为：每代群体规模M=5；个体由Δ和U、V组成，故每个个体所含变量个数nparam=3；编码与实际变量的最大误差取e=0.001时，按式（1-4-57）可得单个变量子串长度n=18，故个体编码串长度l=nparam×n=3×18=54；交叉概率取P c=0.5，基本位变异概率取Pb=0.02，非均匀变异概率取P u=0.04；进化代数取T=60。

第一个进化过程T=60结束时，整个进化过程中所产生个体的最大适应度f 60=-0.671992，最佳个体对应的Δ′=-0.019722MN/m3、U′=3.107080MPa，V′=4.103829MPa。反演结果如表1-4-5所示。

表1-4-5　初始应力测值与反演值对比（第一个进化过程T=60结束时）

总体平均相对误差为12%。由于误差较大，考虑再进行一个T=60的进化过程。第二个进化过程结束时（即总的进化代数为2T=120代），所产生个体的最大适应度f 120=-0.239801，最佳个体所对应的Δ″=-0.029335MN/m3，U″=3.012480MPa，V″=4.068657MPa。反演结果如表1-4-6所示，总体平均相对误差为3%，反演结果明显改善。

表1-4-6　初始应力测值与反演值对比（第二个进化过程T=60结束时）