遗传算法中的误导问题

模式定理说明低阶、短距及平均适应度高于群体平均适应度的模式，在子代中将以指数级增长。这个定理只说明了寻找全局最优解的必要条件，即寻找全局最优解的可能性，而没有证明上述模式在遗传算子作用下能生成高阶、长距、高平均适应度的模式，即最终能生成全局最优解。

虽然大量的遗传算法应用实例都表明，遗传算法在寻求全局最优解方面均已获得成功，但实例不等于理论证明。长期以来，人们做了大量的工作，希望找到上述假设的理论证明，或者更精确地说，希望找到可以保证遗传算法能达到或接近全局最优解的条件，如Bagley和Rosenberg早年的工作，Bethke和Holland等人近年来的工作。但遗憾的是至今仍未有完整的令人满意的结果。

由于证明全局最优解问题较难，于是人们又改变了一个角度来探讨这一问题，即给定一些带有误导性的初始条件，“迷惑”遗传算法，使其偏离全局最优解。通过这样的研究，看一看遗传算法会不会偏离全局最优解？如果会偏离，那么误导的初始条件是怎样的条件？我们称这样的遗传算法问题为误导问题（deceptive problem）。以下以实例来介绍这种研究方法的主要思想和研究结果。

假设有一个由4个阶数为2（即有2个确定位置）的模式构成的集合，各模式具有如下的适应度：

其中：f（00），f（01），f（10），f（11）分别是各对应模式的平均适应度，并假定为常值，其中有一个是全局最优值，不妨假定f（11）是全局最优值，即有

现在，设法引入“误导”遗传算法的条件。考虑4个一阶模式的适应度，即f（*0），f（*1），f（0*）以及f（1*）。一阶模式的适应度等于其包含的所有二阶模式适应度的平均值，即有

所谓“误导”条件，即那些导致原来假定的全局最优解f（11）不是全局最优解的条件，亦即包含全局最优解f（11）的一阶模式的适应度小于不包含最优解的一阶模式的适应度的条件，也就是

由式（9.3.14）～式（9.3.17）有

式（9.3.20）、式（9.3.21）给出了“误导”条件。以下我们来讨论“误导”条件会不会迷惑遗传算法，使其偏离全局最优解f（11）。

可以看出，式（9.3.20）和式（9.3.21）并不能同时成立，否则就有f（00）＞f（11）（根据两个不等式同边相加，不等式仍保持成立，即可证），从而违背了f（11）是全局最优解的假定。不失一般性，不妨假定式（9.3.20）成立，由此，通过一个全局条件（f（11）为全局最优值）和一个“误导”条件（f（0*）＞f（1*）），就确定了一个“误导”问题。

将上述各适应度值按f（00）进行规一化处理：

则全局条件式（9.3.13）可以表示为

则“误导”条件式（9.3.20）可以表示为

由式（9.3.23）和式（9.3.24），可以推出

由式（9.3.25）可以看出，存在着如下两类“误导”问题。(www.xing528.com)

类型Ⅰ：f（01）＞f（00）（c＞1）。

类型Ⅱ：f（00）≥f（01）（c≤1）。

显然，一阶问题（仅有一个确定位）中是不可能存在“误导”问题的，因为无法找到与全局条件相适应的“误导”条件，因此上述2阶“误导”问题是可能存在的最小（阶）“误导”问题。

为了达到“误导”的目的（使遗传算法偏离全局最优解），应使得具有全局最优值的模式在遗传算子作用下减少，则由模式定理可得

这里假设p m=0。

我们已经知道，模式定理所得到的生存概率ps只是一个下界。因为在交换算子作用下，即使交换点落在定义距内，模式也不一定会遭到破坏，这取决于配偶的情况。在上述“误导”问题中，00与01交换产生01和00，父模式并未发生丢失，只有当一个模式确定位置与其配偶互为补数时（二进制串），才会发生丢失。比如00和11交换产生01和10；同理，01与10交换产生11和00。该问题中各模式相互交换的结果由表9.3.1表示，其中S表示子代与父代完全相同。

表9.3.1　2阶问题各模式相互交换的结果

由表9.3.1可以看到，互补的模式（确定位互补）在交换算子作用下遭到破坏，然而另一对互补的模式通过交换，又会重新产生遭到破坏的模式。通过表9.3.1，可以列出在简单选择（按适应度比例选择）、简单交换（单点交换）以及等概率配对的情况下，4个竞争模式在子代中的期望样本数为

其中：是模式在第j代中样本的比例；变量是当前代中群体的平均适应度，用式（9.3.30）表示为

参数p＇c是交换发生在模式定义距内的概率，计算式为

其中：pc为发生交换的概率。

式（9.3.26）～式（9.3.29）描述了模式H在子代中的样本比例的逐代变化情况，显然，遗传算法收敛于全局最优解的一个必要条件是：全局最优模式的样本比例在足够多代后趋近于1，即

通过许多实例，按式（9.3.26）～式（9.3.29）计算后可以得到如下结论。

（1）对于类型Ⅰ最小“误导”问题，在一般初始条件下，（4个模式的初始样本数非0），任何类型Ⅰ“误导”问题都能收敛到全局最优解，即条件式（9.3.32）能够达到。

（2）对于类型Ⅱ最小“误导”问题，在大多数初始条件下，类型Ⅱ都收敛到了全局最优解，但在模式00有很大初始样本数时，模式11可能被丢弃，而不能收敛到最优解（模式11的某个样本），只能达到次最优解（模式00的某个样本）。

以上的分析只是基于固定编码方式（二进制编码）和简单的遗传操作（选择、交换、变异）。采用其他编码方式和复杂的遗传操作研究对全局最优解的影响，可能还会有新的发现，但至今这方面的研究还不多。