遗传算法的数学机理及其在混合动力系统优化中的应用

时间：2023-10-14 理论教育版权反馈

【摘要】：图2-1 内含并行性遗传算法对信息的利用必须考查选择、交叉和变异对模式的作用效果。模式定理是遗传算法的基本理论，保证了较优的模式的数目呈指数级增长，为解释遗传算法机理提供了一种数学工具。

1.模式定理

（1）模式遗传算法的执行过程中包含了大量的随机性操作，因此有必要对其数学机理进行分析，为此首先引入“模式”（schema）这一概念。

我们将种群中的个体即基因串中的相似样板称为“模式”。模式表示基因中某些特征位相同的结构，因此模式也可解释为相同的构形，它描述的是一个串的子集。在二进制编码的串中，模式是基于三个字符集（0，1，*）的字符串，符号*代表任意字符，即0或1。例如模式*1*描述了一个四个元的子集{010，011，110，111}。

对于二进制编码串，当串长为l时，共有3^l个不同的模式，遗传算法中串的运算实际上是模式的运算。如果各个串的每一位按等概率生成0或1，则规模为n种群模式总数的期望值为

种群最多可以同时处理n×2^l个模式。从图2-1可以看出其内含并行性（implicit parallelism）。如果独立地考虑种群中的各个串，则仅能得到n条信息。然而，当把适应值与各个串结合起来考虑，发掘串群体的相似点，我们就得到大量的信息来帮助指导搜索，相似点的大量信息包含在规模不大的种群中。

图2-1 内含并行性

遗传算法对信息的利用必须考查选择、交叉和变异对模式的作用效果。模式定理给出了这一问题的答案。

（2）模式阶和定义距所有的模式并不是以同等机会产生的。有些模式比起其他模式更确定，如与模式0*****相比，模式011**1在相似性方面有更明确的表示。有些模式的跨度要比其他的长，如与模式1*1***相比，1****1要跨越整个串长更大的部分。为了定量地描述模式，我们介绍模式中包含的两个重要参数：模式阶（schema order）和定义距（defining length）。

定义2-1 模式H中确定位置的个数称为模式H的模式阶，记做0（H）。例如，0（011*1*）=4。

定义2-2 模式H中第一个确定位置和最后一个确定位置之间的距离称为模式的定义距，记做δ（H）。例如，δ（011*1**）=4。

在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距反映了这种性质的差异。

（3）模式定理假定在给定时间步t，一个特定的模式H有m个代表串包含在种群A（t）中，记为m=m（H，t）。在再生阶段，每个串根据它的适应值进行复制，一个串A_i的再生概率为

当采用非重叠的n个串的种群代替种群A（t），可以得到下式：

式中，f（H）是在时间步t表示模式H的串平均适应度。整个种群的平均适应度可记成

故在基本遗传算法的结构条件下，若遗传操作只选择转移到下一代的话，则下式成立：

这表明，一个特定的模式按照其平均适应度值与种群的平均适应度值之间的比率生长。换言之，那些适应值高于种群平均适应值的模式在下一代中将会有更多的代表串，而对于适应度值低于种群平均适应值的模式，它们在下一代中的代表串将会减少。假设从t=0开始，某一特定模式适应度值保持在种群平均适应度值以上一个（c为一常数），则模式的选择生长方程变为

式（2-29）表明，在种群平均值以上（或以下）的模式将按指数增长（或衰减）的方式被复制。在一定程度上这种复制算子在种群中并行地采样，许多不同的模式按照相同的规则增长或衰减。仅仅靠复制过程无助于检测搜索空间中新的区域，因为复制并没有搜索新的相似点。因而需要采取交叉操作，交叉是两个串之间随机地进行信息交换。这里仅考虑单点交叉的场合。

为了搞清楚模式受交叉影响的方式和程序，我们以一个串长为7的特定串和包含在其中的两个具有代表性的模式为例：

设串A被选择来进行交叉，假设随机地选择一个交叉位置（在串长为7时仅有6个可选位置），如果选定位置在3和4之间，考查交叉对模式H₁和H₂的作用。其中交叉位置用“|”标记。

显然，如果A的交叉对象在模式H₁的确定位置上与A不同，模式H₁将被破坏。而对于相同的交叉位置，模式H₂将保留到下一子代串中。虽然这里取的交叉位置比较特别，但是很明显，在交叉过程中模式H₁比模式H₂更不易生存，这是因为交叉点一般更易落在距离最远的确定位置之间。一般地，模式H被破坏的概率为δ（H）/（l-1），模式H生存概率为1-δ（H）/（l-1）。模式H₁被破坏的概率为5/6（生存概率为1/6）；模式H₂被破坏的概率为1/6（生存概率为5/6）。考虑到交叉本身是以随机方式进行的，即以概率P_c进行的交叉，因此对于模式H的生存概率可以计算如下：

同时考虑选择、交叉操作对模式的影响，由于选择与交叉操作是不相关的，可以得到子代模式的估计：

式（2-31）表明，模式增长或衰减依赖于两个因素：一个因素是模式的适应值是在平均适应值以上还是在平均适应值以下；另一个因素是模式具有相对长还是相对短的定义距。那些既在种群平均适应度值以上同时又具有短定义距的模式将按指数增长率被采样。

下面再考虑变异操作对模式的影响。变异操作是以概率P_m随机地改变一个位上的值，为了使得模式H可以生存下来，所有特定的位必须存活。因为单个等位基因存活的概率为1-P_m，并且由于每次变异都是统计独立的，因此，当模式H中0（H）个确定位都存活时，这时模式H才被保留下来，存活概率为

（1-P_m）^0（H）≈1-0（H）P_m，P_m＜＜1 （2-32）

因此，在考虑选择、交叉和变异操作的作用下，一个特定模式在下一代中期望出现的数目可以近似地表示为

式中，m（H，t+1）表示在t+1代种群中存在模式H的个体数目；m（H，t）表示在t代种群中存在模式H的个体数目；f（H）表示在t代种群中包含模式H的个体平均适应度；表示在t代种群中所有个体的平均适应度；l表示个体的长度；P_c表示交叉概率；P_m表示变异概率。

对于k点交叉的场合，上式可以作如下改变（证明从略）：

综上所述，我们可得到遗传算法的一个重要的结论——模式定理（schema the-orem）。

定理2-1 在遗传算子选择、交叉、变异的作用下，具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长^{[24，25，41]}。

模式定理是遗传算法的基本理论，保证了较优的模式（遗传算法的较优解）的数目呈指数级增长，为解释遗传算法机理提供了一种数学工具。

2.积木块假设

在模式定理中所指的具有低阶、短定义距以及平均适应度高于种群平均适应度的模式被定义为积木块（building block）^[41]。它们在遗传算法中很重要，在子代中呈指数增长，在遗传操作下相互结合，产生适应度更高的个体，从而找到更优的可行解。

积木块假设：遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），在遗传操作作用下相互结合，最终接近全局最优解。

满足这个假设的条件比较简单，包括两个方面：

1）表现型相近的个体，其基因型类似；

2）遗传因子间相关性低。(www.xing528.com)

下面考虑一个整数解的最优化问题，采用4位二进制基因码。表现型7对应基因型0111；8对应1000。假定7是问题的最优解，种群中有8对应的个体1000，用一般的遗传算子不易生成最优解7对应的个体0111，但采用逆位（inversion）操作，则1000很容易变为0111。图2-2表示了种群中的积木块。

图2-2 适于逆位操作的积木块

目前大量的实践支持积木块假设，它在许多领域内都取得成功，例如平滑多峰问题、带干扰多峰问题以及组合优化问题等。模式定理保证了较优模式（遗传算法的较优解）的样本呈指数增长，从而满足了求最优解的必要条件，即遗传算法存在找到全局最优解的可能性；而积木块假设指出，遗传算法具备寻找全局最优解的能力，即积木块在遗传算子的作用下，能生成低阶、短距、高平均适应度的模式，最终生成全局最优解。

3.模式定理成立的必要条件

Holland的模式定理揭示了种群中优良个体（优良模式）样本数呈指数增长的规律，从而从理论上保证了遗传算法是一类模拟自然进化的最优化算法，为遗传算法应用于最优化问题提供了理论基础。但模式定理并未深入考虑定理成立应满足的条件，认为只要交叉概率P_c和变异概率P_m参数满足P_c≤1，P_m≤1时定理成立，后继者在研究遗传算法的理论问题时，也没有对其给出模式定理成立时的约束条件，没有解决算法设计中控制参数选取等问题，只是建议在应用遗传算法时变异概率参数取较小值（一般取0.01）。本节研究模式定理的必要条件，推导定理成立时交叉概率、变异概率参数应满足的约束关系。

根据上一节的叙述可知，模式（schema）表示一些具有相似性的模板或超平面。一个模式描述在某些基因位置具有相似结构的个体编码串的子集。以二进制编码为例，个体a∈{0，1}^l是长度为l位的二进制字符串，而模式H∈{0，1，*}^l却是由字符集{0，1，*}中的元素组成的字符串，其中，“*”表示通配符，它既可表示二进制字符“1”，也可表示字符“0”。当模式H中的通配符被确定的字符所替代时，该字符串就称为H的一个实例，模式H的所有实例的集合记为ψ（H）。例如，ψ（H=*1*）={010，011，110，111}。模式H中确定位的数量称为模式的阶，记为0（H），例如，0（H=1*00**）=3，0（H=01*1**0*）=4。模式H中第一个确定位的位置和最后一个确定位的位置之间的距离称为该模式的定义距，记为δ（H），例如，δ（H=1****1）=5，δ（H=*0*01*）=3，δ（H=**1***）=0。

设第t代种群X（t）中与模式H匹配的样本数为M（H，t），模式H的一个样本串以概率被选择，其中f_i是个体X_i（t）的适应值。再假设群体规模为N且初始个体互异，交叉概率为P_c，变异概率为P_m，模式长度为L。在选择、交叉与变异作用下，模式H在第t+1代的样本数为M（H，t+1），满足

式中，；f（H）是模式H的平均适应值；0（H）是模式H的样本平均模式阶。Holland通过式（2-35）给出模式定理，描述如下：

遗传算法中，在选择、交叉和变异算子的作用下，具有低阶、短的定义距，并且平均适应值高于种群平均适应值的模式将按指数规律增长。

本节的后部分，应用概率统计学研究模式定理成立的参数条件，为提高遗传算法的搜索效率提供参数设置的理论依据^[42]。

4.定义与适应值赋值方法

假设全局最优解为某个模式的一个实例，简称为最优模式实例，给出以下符号定义：

0（H_i）：种群中模式H的样本i与最优模式实例相匹配的确定位数目，即模式阶。

δ（H_i）：种群中模式H的样本i与理论上存在的实例相匹配的第一个确定位置与最后一个确定位置之间的距离，即定义距。

例如，某一问题全局最优解对应的最优模式实例为1011001100，则0（H=**1*01010*）=3（即第3、5、9位与最优模式实例相匹配），0（H=1**11011*1）=5（即第1、4、6、7、8位与最优模式实例相匹配）；δ（H=**1*01010*）=6，δ（H=1**11011*1）=7。

N：种群规模，种群初始化时个体互异。

L：模式串的长度。

在生物界的生存竞争中，某个体或物种要生存下去，它必须具备适应环境的能力。环境根据生物个体的适应能力决定其在生存竞争中的胜败。遗传算法中，个体的适应值是决定个体是否被选择进入下一代种群的主要依据。在某一轮的进化中，低阶模式在进化时，被破坏的可能性小，朝着全局最优解方向进化的概率大；对于某一具体的模式而言，由该模式进化而得的实例，高阶模式实例与最优模式实例相匹配的位数多，与最优模式实例的差距小。固不妨将个体适应值f_i定义如下：

按照该方法给个体赋适应值，避免了个体因表面适应而导致其适应值比较大的情况出现，真正抓住了个体基因的内在品质，充分体现了遗传算法选择策略的本质，使真正优良的个体有较大的适应值。假设模式H有低阶、短定义距以及平均适应值高于种群适应值的性质，根据f_i的定义，种群的平均适应值为

模式H在第t代的平均适应值为

推证过程如下：

根据Holland的模式定理，模式H在遗传算子的作用下按指数规律增长，即式（2-35）成立。依照Holland的假设，模式H的平均适应值一直高于种群平均适应值，高出部分为。从t=0开始，由式（2-35）可知，模式H在第t代样本数为

由于种群规模的确定性，对式（2-39）取极限有。式（2-35）可转换为

由于M（H，t）＞M（H，0），f（H）＞0，上式可进一步转换为

因为t→∞时，f=f（H），所以有

由于种群初始化时个体的互异性，因而M（H，0）=1，将f（H）、代入式（2-42）可得

遗传算法是一个寻找全局最优解的优化过程，它具有全局收敛性^[7]，能够搜索到全局最优解，所以模式H在t→∞的过程中，最终主宰种群，种群中存在样本i使得0（H_i）=L成立，且δ（H_i）=L成立。对于某一确定问题，从理论上而言，只存在一种串组合实例是真正的全局最优解，当算法搜索到由模式H进化而得的全局最优解样本后，其他模式样本的适应值都小于模式H的全局最优解样本的适应值，最终其他模式样本被淘汰，模式H的样本（即全局最优解样本）控制整个种群，固有