基于解空间定向优化的改进免疫算法研究及应用*

王 波，胡军台，张克勇，李晓航，张逸群，孙世勇

（国网河南省电力公司平顶山供电公司，河南 平顶山 467001）

0 引言

生物免疫系统是由免疫细胞、免疫活性分子和免疫器官等多个子系统组成的复杂系统。免疫系统所属的子系统之间具备着相当复杂的依附关系、竞争关系等，它们具有识别、消除异物的功能［1］，动态控制生物体内的各项指标处于正常状态。人工免疫算法（IA）就是结合生物的免疫系统建立起来的一种有效的优化控制方法，其主要思想是在免疫系统中寻找最佳的抗体来对抗生物体内的异物或病原体。IA 作为现代基本的控制算法已经在系统优化设计［2-3］、系统智能控制［4］、模式识别［5］、故障诊断［6］、网络安全［7］等领域中得到了广泛的应用。但是在实际应用过程中，IA 也存在着搜索效率低、陷入极值等问题，限制了IA 在一些大型信号处理项目中的应用。

如今，对于IA 的改进算法也层出不穷，许多专家学者基于传统IA 的局限性问题，结合现代主流控制算法进行改进，文献［8］中，将人工蜂群算法与IA 相结合，并结合两者优势提出基于蜂群算法与免疫算法的融合控制算法，有效提升了传统单一算法搜索精度不高的问题，提升了算法的收敛速度与全局搜索能力。文献［9］中，将混沌理论引入免疫算法之中，提出了基于混沌理论的新型免疫算法，同样也是提升了IA 的寻优精度以及全局搜索能力，使得新型算法能够有效避免陷入部分极值。

另一些改进思想主要集中在IA 本身，传统的IA 中包含了诸多不定参数，需要进行预先设定，这些参数控制着算法的最终收敛精度、迭代次数、搜索步长等。为提升算法的适用范围，对这些参数的设置提出了相关改进措施。文献［10］中，对免疫算法的变异率进行了详细研究，利用周期变异率替代传统IA 中的固定变异率。文献［11］中，分析了变异率、浓度阈值、记忆库规模的影响程度，利用仿真实验确定了最佳参数设置范围。

本文针对传统IA 在搜索阶段的效率不高问题，提出依靠解空间定向优化的改进IA。相比于其他已有的改进思路，本文从计算量的角度考虑，参考人体免疫系统识别、消灭外来异物、抗原的全部过程，结合药物辅助的手段加快人体免疫系统消灭外来抗原，使得机体能够更快的恢复健康的方法，本文提出一种基于解空间定向优化的改进免疫算法，以获得较高效率的算法搜索过程，以及更高的算法收敛速度。

1 改进免疫算法原理分析

传统免疫算法是根据待测目标函数产生相应的初始解群，记为u0（t）。并且通过对比初始解群获得的算法精度与预设精度进行比较，若此时的候选解群已经满足人为要求，则算法停止对于目标函数的进一步搜索，同时认为此时得到的解即为目标函数最优解；若不满足人为要求，就类似机体免疫系统根据外来病原体逐步形成有效抗体的过程，算法在搜索目标函数区域的同时，逐步形成新的、更优的解群体，不断接近最优解群。因此，定义亲和力参数来衡量解群的优劣，抗体（解群）与抗原（目标函数）之间的亲和度参数可以表示为：

式（1）中，Aappetency表示两者之间的亲和力参数，fit（u）表示抗原与抗体之间的匹配程度，该函数的值越大，说明抗体与抗原之间的匹配度较高，抗体能够有效消灭抗原，因此，更有利于算法的收敛。pra（u）表示奖励函数，调整奖励函数值来增加抗体抗原之间的亲和力。在每一次迭代求解的过程中，利用亲和力与预期阈值之间进行比较，获取最优解群：

直到达到预设阈值。在传统的免疫算法中，会产生较多的冗余计算，导致算法的收敛速度不高，且算法效率不高，这是由于传统的免疫算法为了追求目标函数搜索的完备性，对目标函数的整体进行搜索，因此，浪费了较多不必要的搜索时间。为了降低算法在目标函数搜索过程中的冗余过程，本文增加了定向搜索判定，在算法迭代的过程中，朝着目标函数的优化方向进行搜索，排除掉较多的无效的搜索区域。能够有效降低算法的搜索耗时，同时也会使得免疫算法不再因陷入极小值而停止搜索，提高了算法的收敛效率。并可针对新的目标函数区域对候选解群进行相应的变异和克隆步骤。

对于目标函数的处理过程与机体对抗外来抗原类似，在进行多次判定后，集体会选取最优抗体用于对抗抗原。体现在算法上，根据不断迭代求解解群，结合亲和力判断，将亲和力更高的解群进行克隆。迭代算法保证逐步提升候选解群与目标函数的亲和力，解群的克隆规模应根据人为要求进行设置。

变异是为了保证候选解群的多样性，防止陷入局部最优值。变异操作一直是免疫算法中十分重要的部分，对于变异率的设置对算法的影响明显。根据文献［16］作出的研究表明：变异率的取值既不能太大又不能太小，太小的话，变异操作的效果不明显，群体多样性不能保证；变异率也不能太大，会导致群体的稳定性很差。为此，将变异率设置成为变化的参数，保证候选解群稳定性的同时，也使候选解群具有一定的多样性。为增加算法的收敛速度，每一次克隆过程中进行亲和力判定，同时进一步更新候选解群。更新算法参数，重复步骤2 至步骤5，直至满足人为要求，最终得到最优解群uopt（t）。改进的免疫算法实施的具体流程图如下页图1 所示。

如图1 所示，利用变异率Pm与阈值T 共同约束，每一次迭代求解候选解群的变异程度与算法的全局搜索能力，即决定了算法的收敛速度，提升变异率后，可以增加求解最优解群的机会，但同时也会使整个算法的收敛速度降低，因此，定义算法的终止判据：

图1 改进的免疫算法流程图

f（uopt）∈（min f（x）-△δ，min f（x）+△δ） （3）式（3）中，△δ 表示目标函数的搜索区域。当搜索出的解群uopt满足人为要求，则停止搜索，即认为此时得到的候选解群为最优解群。如图1 所示，算法步骤2～步骤5 是一个马尔科夫过程，因此，任意初始状态分布均有［17］：

式（4）中，s*表示满足最大亲和力式（1）的搜索空间集合，An表示初始状态。根据马尔科夫链的相关性质：

2 仿真实验及结果分析

为验证基于解空间定向优化的改进免疫算法的可行性和优越性，利用一系列一元测试函数对算法进行仿真实验。仿真过程中的目标函数设置如表1 所示，仿真主要考察算法的收敛效率，实验结果利用响应耗时来表征。测试函数分为5 个，包括了单峰函数与多峰函数。

表1 目标函数设置

表2 传统免疫算法与本文算法测试结果比较

对比传统的免疫算法与本文算法对于目标函数的求解最优解群的最终结果，可以看出：本文算法能够在保证标准差的同时，缩短整体算法的运算时间；在单峰函数搜索过程中，本文算法约为传统免疫算法的1/3，其余的目标函数搜索过程也可缩短传统响应耗时的一半左右，体现出了本文算法在响应时间上的优势。

3 结论

本文提出基于解空间定向优化的改进免疫算法，从算法响应耗时的角度出发，增加了定向搜索判别过程，在保证解群精度的条件下，算法响应耗时最大降低至传统免疫算法的1/3，体现出了改进算法的优越性。改进的免疫算法针对多极值的函数寻优时，耗时会逐步增加，因此，需要针对多极值函数的解空间优化方向进行改进，可以在亲和力与变异、克隆参数上进一步优化。