免疫进化算法的收敛性优化

1.问题的描述与假设

函数值f*＝f（x*）＜+∞称为一个整体极大值，当且仅当

成立时，x*∈S成为一个整体极大值点，将所有整体极大值点的集合记为argf*。

进一步，假定f满足以下条件：

（1）argf*非空。

（2）f是定义在S上的随机变量。

（3）对∀ε＞0，集合Mε＝{x∈S|f（x）≥f*-ε}满足m（Mε）＞0，m为Lebesgue测度。

2.免疫进化算法的马尔可夫链模型及其收敛性[54]

定义 设X＝{Xt|t＝0.1，…}是离散参数的随机过程，在一定的精度条件下，其状态空间S为有限集，记为Ω。如果对于任意非负整数t及任意的状态i0，i1，…，it+1∈Ω，只要P（X0＝i0，X1＝i1，…，Xt＝it）＞0，总有

成立（X满足马尔可夫链无后效性），则称X为离散参数的有限马尔可夫链。

设连续参数优化问题式（5-23）对应的最优解为x*，可定义算法的收敛性如下：

成立，则称算法以概率1收敛到全局最优解。

定理 免疫进化算法是以概率1收敛到全局最优解。

设Pij为从状态Ei到Ej的转移概率，从保留最优个体（状态）的角度来考虑：

如果将个体（状态）按适应度从大到小进行排列，则免疫进化算法有限状态马尔可夫链一步转移概率矩阵为

记此马尔可夫链的n步转移概率矩阵为H（n），由无后效性，得

故得

所以，从马尔可夫链的极限分布可知，免疫进化算法以概率1收敛到全局最优解。这说明，不论从何状态出发，免疫进化算法都是全局收敛的，免疫进化算法是以概率1收敛到全局的最优解。另外，值得一提的是免疫进化算法不仅对初始群体的分布，而且对初始群体的规模的影响有很好的免疫性，这无疑对算法的稳定性具有很大的意义。

3.免疫进化算法的全局收敛性条件[157]

定义 对一个定义在概率空间（Ω，A，P）上的非负随机变量序列{xn，n＝0，1，…}：(www.xing528.com)

在这三种形式的收敛中，完全收敛最强，它蕴涵了其他两种形式的收敛，以概率收敛最弱。

根据式（5-22），免疫进化算法采用正态分布作为生殖方式产生下一代群体，生殖所对应的随机向量记为y，其各个分量是独立同分布的随机变量[σt×N（0，1）]。记y的密度函数为Pt（y），第t代群体中的某一个体x进入Mε的概率为P（t），即

从而有

在第t代群体中的N个个体中无一进入Mε的概率为

由有关无穷级数和无穷乘积的结论可知

又因免疫进化算法在迭代中实施最优个体保留，故得出下面关于免疫进化算法是完全收敛到全局最优解的条件。

该定理不仅给出了免疫进化算法完全收敛的条件，而且对于算法在实际应用中的参数选取有非常重要的指导意义。

4.免疫进化算法和遗传算法计算效率的对比分析[158]

免疫进化算法也是在现有进化算法的基础上，借鉴生物免疫机制形成的一种优化算法。因此，对比分析免疫进化算法和遗传算法的计算效率对深刻认识两种算法的本身是十分必要的。设群体的规模为N，则免疫进化算法、标准遗传算法、保留最优个体的标准遗传算法所对应的状态空间的大小分别为|Ω|、|Ω|N、|Ω|N+1。由此可见，遗传算法的马尔可夫链状态空间的维数要远大于免疫进化算法对应的维数，这必定会在一定程度上加大了遗传算法求解问题时的复杂性，从而降低了其计算效率。另外，免疫进化算法每一次迭代将产生N个个体，它们对应N个新的状态，这相当于该算法在一次迭代中对同一过程进行了N次并行计算。而遗传算法一次迭代产生N个个体只构成一个状态。这从一个侧面揭示了免疫进化算法有着较高的计算效率。从运行的机理来看，免疫进化算法在产生新个体时，新抗体的产生多集中于上一代最优个体的附近，但也顾及了上一代最优个体附近以外的区域。这说明免疫进化算法在加强对问题局部搜索能力的同时，也兼顾了全局搜索。这种搜索方式充分利用了求解问题的特征信息，即免疫进化算法子代群体的产生是以父代最优个体为指导的，这是免疫进化算法核心思想的集中体现。与遗传算法相比，它能有效地克服不成熟收敛，使得最优抗体很快趋于全局最优。对于遗传算法而言，它实际上是一种“生成+检测”的迭代方法，检测是通过选择算子来实现的，生成则是通过交叉算子和变异算子共同作用来完成的。基于这样的一种思想，一旦在群体中产生一个较优的个体（局部最优解），一方面，由于交叉算子和变异算子均是随机的、无指导的产生后代个体，通过这种方式很难（小概率）搜索到适应度更高的个体；另一方面，在选择算子的作用下，群体中其他个体会很快向较优个体趋同，对于这样的群体，选择算子和交叉算子基本已失去作用，小概率的变异算子无疑使得群体进化几乎陷入停顿。在这种情况下，既使增加了迭代次数，遗传算法也常常陷入局部最优解不能自拔，可以这样说，早熟现象是遗传算法自身无法克服的问题。运算机理的分析也从另一个侧面揭示了免疫进化算法有着更快的收敛速度。

综合上述分析不难看出，免疫进化算法是一种结合问题特征信息的算法，它是有指导的、并行的搜索。虽然理论分析二者在迭代趋于无穷时都是全局收敛的，但免疫进化算法无疑显示出比遗传算法更高的计算效率，有着更快的收敛速度。从这个意义上讲，免疫进化算法是更为接近确定性优化的一种全新迭代优化算法。