一种改进的免疫算法研究

刘柏麟，吴湘华

摘要：传统免疫算法是通过仿真免疫系统的多样性机制设计出来的一种算法。传统免疫算法在求解问题时候，算法存在收敛速度慢、容易陷入局部最优等问题。该文通过对传统免疫算法中的变异函数和克隆抑制函数加以改进，以提高算法收敛速度，并使算法具有较好的全局最优性。通过测试函数验证改进后的算法正确有效。

关键词：免疫算法；变异函数；克隆抑制；收敛速度；全局最优

中图分类号：G642      文献标识码：A

文章编号：1009-3044（2022）32-0017-03

1 概述

自古以来，人类通过模拟生物体的结构、功能发明了很多技术和工具，来解决生活中的问题[1]。生物免疫系统作为一种复杂的系统，它能够对外来的入侵物质进行自我识别和清除，同时它还具有自组织、分布式、自适应、动态均衡等性能。当外来的抗原侵入体内时，就会产生对应的抗体，其目的在于最大限度地确保机体的基本生理机能的正常运作，维持人體内部的稳定性。免疫算法基于生物免疫系统的免疫进化机理和信息处理机制，模拟其抗原识别和抗体增殖过程，保持抗体的多样性[2]。传统的免疫算法在局部最优问题上有待解决以及其收敛性也有待改进，为了优化这些问题，本文在传统免疫算法的基础上进行改进。

2 传统免疫算法简介

传统免疫算法的原理是将抗体和抗原结合，进行抗体克隆、变异、选择和记忆等过程，逐步达到抗体优化[3]。传统免疫算法将待优化的问题的目标函数看成免疫系统中的抗原，算法中可行解看成免疫系统中的抗体，可行解的质量看成是抗体和抗原的亲和度，通过进行抗体克隆、变异、选择和记忆等操作，不断优化抗体，利用抗体与抗原的亲和性，确定目标函数和可行解之间的匹配度，确保可行解的差异性和多样性，通过对抗体的期望生存率进行估计，以便促进较优抗体更好地进行遗传和变异。选择最佳的可行解作为记忆细胞，以避免出现相似的可行解，进而达到加快搜索全局最优解的目的。独立的抗体种群进行选择、克隆和变异等免疫操作[4]。在每次单独群体的更新和评估之后，选择不同种群的最优抗体进行多组评价，也就是目前群体中的最佳抗体与上一代的最优抗体相比较，若现有抗体较好，则将其作为本代的最佳抗体，反之，则将上一代的最佳抗体保存为该代的最佳抗体。最佳抗体就会被分配到各自的种群中，从而产生新的抗体。

免疫操作主要包括以下算子：

（1）免疫选择：通过计算种群的抗体亲和度，筛选出高质量的抗体，并进行活化；

（2）克隆：克隆经过选择后的抗体，得到多个新的种群；

（3）变异：对克隆获得的群体进行变异处理，从而产生突变；

（4）克隆抑制：对变异后的群体进行优选操作，保留亲和度较高的抗体。

传统免疫算法描述如下：

步骤1：参数的设定，在算法运行之前确定各个参数的取值。步骤2：初始化种群，根据设定的参数，随机生成初始的抗体种群。步骤3：判定是否已达最大迭代代数，达到最大迭代代数则结束循环，并将执行步骤9；否则继续执行步骤4。步骤4：抗原识别，根据问题构造相应的测试函数，染色体编码代表抗体。步骤5：计算函数目标值，将种群中的抗体引入测试函数，得到相应的函数目标值，将其作为各抗体的亲和度。步骤6：记忆单元的活化，向记忆单元内添加高亲和度的抗体，并执行免疫操作。步骤7：执行免疫操作，主要执行的操作是选择操作、克隆操作、变异操作和克隆抑制操作；选择算子，即在群体中择优，筛选更优的抗体以便于克隆；克隆算子是将选定的抗体复制到新的种群中；变异算子是指在克隆后所形成的种群中进行的突变；克隆抑制是指在变异后群体中重新筛选出具有较高亲和力的抗体。步骤8：种群刷新，根据刷新比例从种群中随机产生剩余个体，和上一步所保留的抗体刷新种群，并返回执行步骤3。步骤9：结束记忆细胞迭代，当达到指定的代数时，停止产生和选择记忆细胞。

免疫算法是模仿生物免疫学和基因进化机理构造的优化搜索算法，是免疫计算的一种最重要形式和对生物免疫过程的一种数学仿真[4]。其主要特性如下：

（1）该算法模拟了免疫反应过程，是一种具有全局搜索功能的优化算法。其对高质量抗体局部搜索时通过变异算子和种群刷新来生成新的个体，并在一定范围内寻找新的可能解区间，并保证了算法的全局收敛性。

（2）该算法采用了生物免疫系统中的多样性维持机制，并根据抗体浓度的大小来判断抗体的优劣。这种方法既能有效地抑制高浓度抗体，又能保证个体的多样性，从而保证全局收敛。

（3）生物免疫系统可以随时对抗原进行良好的识别[6]。该算法利用了启发式的智能搜索机制，能够在不受问题和初始值约束的情况下，从较差的解群体中寻找最优解，具有很好的鲁棒性。

（4）该算法无需集中控制，能够进行并行运算。此外，免疫算法的优化过程是一个多进程并行的过程。它能在寻找问题的最优解的过程中，获得多个次最优解，即在寻找最优解的情况下，获得了更好的选择，特别适用于多模式优化问题。

（5）该算法在保持解的多样性的同时，既采用了选择、变异算子，又加入了随机初始化群体，从而提高了解抗体的选择能力，使算法能在全局最优条件下收敛。然而，与其他的智能算法相比，该算法在解决函数问题时，不能很好地收敛于全局最优，而且随着时间的推移，其收敛速度和精确度也会逐步下降。

（6）该算法在优化多峰函数方面有较慢的收敛速度和精度较差的问题，通过简单的提高抗体种群规模可以扩大免疫算法的搜索范围，但是仍然会出现抗体退化、收敛速度慢的问题。

3 传统免疫算法的改进

从免疫系统的角度出发，数值函数优化是在一定范围内找到最佳值，相当于抗体种群进化来鉴别单个抗原。抗原与待解决的问题对应，最佳抗体与待解问题的最佳值对应，而函数值则与抗体与抗原的亲和程度对应。本文对免疫变异算子克隆抑制算子进行改进。

3.1 免疫变异算子改进

在传统的免疫算法中，大多数使用单点变异或者随机取反来实现算法。本文定义变异点数量n，将算子从单点变异设置为多点变异，可以直观地分析收敛速度随着变异点数量n的改变有何变动，避免产生局部最优的问题，同时种群中的多样性也得到提高。免疫变异算子im_mutation描述如下：

算子1：免疫变异算子im_mutation

功能：对克隆得到的种群进行n点随机变异

输入：克隆后形成的种群pop，变异点数量n

输出：进行变异操作后形成的种群mupop

具体执行过程：

（1）设置变异点数量n；

（2）输入克隆后得到的种群pop，令i = 1，j = 1；

（3）i <= px时执行（4），否则执行（7）；

（4）返回行向量index，包含从1到px没有重复元素的整数随机排列；

（5）j <= n时执行（6）且j值增1，否则i值增1返回（3）；

（6）将（4）中返回的元素作为序列，对每一个序列指定的变异点值进行取反运算；

（7）输出进行变异后的形成的种群mupop。

3.2 克隆抑制算子改进

通常，克隆抑制算子是对变异后的种群进行则最优个体，进行种群刷新迭代。传统免疫算法抑制后截取的个体数一般为常数，没有充分研究该值对算法的影响，改进后的算法定义抑制后截取的个体数k，筛选出具有较高的亲和度的k个抗体，亲和度较低的抗体达到抑制效果。k取值过小不利于寻找全局最优解和收敛代数可能较大，k取值过大，每代运算时间会增加，影响收敛速度，克隆抑制算子k值的选取对收敛效果起到极其关键的作用，通过研究k值对算法效率的影响，以指导在实际问题中如何更好地进行克隆抑制操作。克隆抑制算子inhibit_clone描述如下：

算子2：克隆抑制算子inhibit_clone

功能：在经过变异后的种群中取出k个最优个体

输入：变异后形成的种群pop，求解区间bounds，抑制后截取个体数k

输出：个体进行克隆抑制操作后形成的种群newpop

具体执行过程：

（1）输入变异后的二进制种群pop，求解区间bounds，抑制后截取个体数k；

（2）计算出群体中每条染色体个体的目标值objvalue；

（3）根据亲和度大小排序，逆序；

（4）截取第1行到第k行作为新的二进制种群；

（5）输出个体进行克隆抑制操作后的形成的種群newpop。

4 实验仿真

4.1 算法的最优解截止代数判定

本文中免疫算法优化的评估标准是综合考虑最优目标值、方差、熵值，体现实际免疫系统的多样性[7]。方差表示种群在某个空间的分布情况，信息熵表示种群中个体的混乱程度。方差定义为：[D（X）=k=1，2，3...[X-E（X）]2pk]，其中[X]表示种群，[E（X）]表示种群均值，[pk]表示分布概率。熵值定义为：[H（X）=-k=1，2，3...p（xi）log2p（xi）]其中[p（xi）]表示个体在种群中的占比。当方差和熵值都比较大的时候，说明搜索空间大而且种群多样性强，适合初始种群情况。如果种群的方差小、熵值大，说明搜索空间较小且种群的多样性比较强。如果种群的方差大、熵值小，说明搜索空间较大且种群的多样性较为弱。当熵值和方差都趋于一定的极小值时，群体中的最优个体占比最大，此时免疫算法无法找到更优解，即可判定收敛。

3.1 仿真参数设定

为了验证算子改进后，免疫算法在求解函数中各种优化问题时的改进效果及优越性，选择几个常用测试函数进行仿真，下面以测试函数f（x） = x + 10× sin（5×x） + 7×cos（4×x），x∈[-10，10]，进行详细的数据分析。种群大小设置为100，精度设置染色体长度为18，单次克隆个体数为10，种群刷新比例为0.3，进化代数设置为100代，变异点n取1～4，抑制操作后截取的个体数取1～4，本文设置了两个变量对算法进行改进，变异点数量n和抑制后截取个体数k。对两者进行单一变量分析，判断算法收敛性能是否提升。

4.2 仿真结果分析

使用单一变量原则固定一个种群，变异点数量n和抑制后截取个体数k两者选取一个作为变量，进行免疫算法操作，通过观察最优目标值与最优值占比关系、方差和熵值关系，得出收敛代数。通过以上方法，对比多个不同种群的收敛代数，观察变异点数量n和抑制后截取个体数k这两个变量对算法收敛速度的影响。以下对初始种群pop1进行具体举例。

（1）当初始种群pop1和抑制后截取个体数k =1固定不变时，单一变量变异点数量n=1时，在进化代数G的变化下，最优目标值与其占比关系见图1，方差和熵值关系见图2。

由此可知，当抑制后截取个体数k=1，变异点数量n=1时，种群在44代时收敛。

同理，由此可知，当抑制后截取个体数k=1，变异点数量n=2时，种群在11代时收敛；当抑制后截取个体数k=1，变异点数量n=3时，种群在23代时收敛；当抑制后截取个体数k=1，变异点数量n=4时，种群在20代时收敛；当变异点数量n=3， 抑制后截取个体数k=2时，种群在12代时收敛；当变异点数量n=3， 抑制后截取个体数k=3时，种群在13代时收敛；当变异点数量n=3， 抑制后截取个体数k=4时，种群在8代时收敛。

以此类推，通过以上方法测试六组不同的种群，运用单一变量原则，观察变异点数量n和克隆抑制后截取个体数k的改变对算法收敛性能的影响。

当k=1时，收敛代数如表1：

当n=3时，收敛代数如表2：

通过以上的仿真数据可知，固定始种群和变异点数量，抑制后截取个体数设置为变量；亦或固定初始种群和抑制后截取个体数，变异点数量设置为变量，可以明显地观察到算法收敛速度变化。当n值和k值过小时，都会使收敛性能下降。由此判断，想要提高算法的收敛性能，可以在变量上选择采用多点变异n和适当选取抑制后截取个体数k。

5 结论

免疫算法是一种以人工免疫系统为基础的学习算法，它具有较强的自主性和应答性，同时还具备了一定的搜索和优化的能力。其基本思想是将抗体与抗原结合，经过抗体选择、克隆、变异、记忆等步骤，使抗体得到最优。本文通过设置变异点数量与克隆抑制后截取个体数，对算法进行了改进和创新。

参考文献：

[1] Mohammadi M，Raahemi B，Akbari A，et al.Improving linear discriminant analysis with artificial immune system-based evolutionary algorithms[J].Information Sciences，2012，189：219-232.

[2] 张晓.人工免疫算法改进及其应用研究[D].西安：陕西师范大学，2017.

[3] 马春连.基于人工免疫系统的多目标进化算法的研究[D].淮南：安徽理工大学，2014.

[4] 汪桂金，胡剑锋.多种群人工免疫算法在多峰函数上的优化[J].南昌大学学报（工科版），2018，40（3）：299-302，306.

[5] 蔡自兴，龚涛.免疫算法研究的进展[J].控制与决策，2004，19（8）：841-846.

[6] 石刚.改进免疫克隆选择算法的研究与应用[D].沈阳：东北大学，2011.

[7] 孙宁.人工免疫优化算法及其应用研究[D].哈尔滨：哈尔滨工业大学，2006.

【通联编辑：朱宝贵】