基于先天免疫机制的果蝇免疫协同优化算法

张晓茹，王 丹,王 俊,周锦程

(1.黔南民族医学高等专科学校，贵州 都匀 558000； 2.黔南民族师范学院数学与统计学院，贵州 都匀 558000；3.黔南民族师范学院复杂系统与智能优化实验室，贵州 都匀 558000; 4.黔南民族师范学院计算机与信息学院，贵州 都匀 558000)

0 引 言

随着算法研究的深入，基于生物灵感的群智能优化算法犹如雨后春笋般地出现，并得到广泛应用[1-5]。Pan等人[6]着眼果蝇的嗅觉和视觉特征，提出了果蝇优化算法(Fruit-fly Optimization Algorithm, FOA)，因其结构简单、代码短小、运行效率高等优点成为研究的焦点。但该算法在局部挖掘、收敛速度和精度等方面还存在不足，为此涌现了大量的改进型果蝇优化算法[7-13]。而昆虫学理论表明[15-19]，果蝇虽不具有高等动物的后天获得性免疫系统，仅依靠其自身的先天性免疫机制可以有效抵御外来微生物，这为本文算法模块设计提供了新的生物灵感来源。故本文基于果蝇仅有先天性免疫应答的机理，提出果蝇免疫协同优化算法(Co-Fly Immune Optimization Algorithm， CFIOA)。

目前基于果蝇自身先天性免疫机制研究果蝇免疫协同优化算法的工作较为稀少[20]。本文算法不是将人工免疫算法与果蝇算法的组合[21-22]，也不是对果蝇优化算法缺陷的补充与完善[23-24]，本文的创新之处在于着眼果蝇仅有先天性免疫应答的特征，充分利用果蝇自身免疫中的细胞免疫、体液免疫及黑化作用之间彼此独立又相互影响的协同免疫反应，受此启发提出果蝇免疫理论模型，并以此为灵感来源设计果蝇免疫协同优化算法。

1 果蝇免疫理论与算法描述

1.1 果蝇免疫理论模型

果蝇体内没有T和B淋巴细胞，且缺乏抗体和补体，但作为细菌等的传播载体，仅依靠其先天性免疫系统的黑化作用、细胞免疫和体液免疫的共同抵御[14-19]，可以有效确保自身不被感染。黑化作用是抵御病原体感染的最直接免疫反应[14]。细胞免疫主要通过浆细胞、薄层细胞以及晶细胞的识别、吞噬和包裹作用，进一步清除或杀死病原体[14]。体液免疫主要包括Toll和Imd信号通路。当机体被感染，不同信号通路将被相应激活并产生相对应的抗菌肽，达到清除外来微生物的目的[14]。

结合上述理论，获得果蝇免疫理论模型，如图1所示。

图1 果蝇免疫理论模型

1.2 算法描述与设计

考虑如下优化问题(P)：

其中，搜索范围D是有界闭区域；f(x)为D上不同模态的连续函数，x∈D为优化问题候选解，其中x=(x1,x2,…,xn)，n≤1000。由闭区间上连续函数的最值定理可知，上述问题一定存在最优解。

结合以上果蝇免疫理论模型，算法CFIOA的流程如图2所示。CFIOA由1个内循环和1个外循环构成。内循环模块主要模拟免疫机制逐步清除外来病原体的过程；外循环主要用于动态更新获得的最好个体，以逐步获得群体最优。内循环中，首先更新各子群及种群的最优个体信息，并且各子群按一定比例删除较差个体，以此模拟细胞免疫、体液免疫的协同应答过程，目的是获取新的、多样且优质个体。当内循环结束时，更新当前最优个体；当前最优个体与新生的初始个体组成新种群，继续外循环，然后进入内循环，如此重复内、外循环，直到整个搜索过程终止。

图2 算法CFIOA流程图

在抵御外来微生物的免疫反应中，果蝇自身免疫系统的黑化作用、体液免疫和细胞免疫并不是独立作用而是协同免疫的，主要包括：1)体液免疫会影响血细胞功能，而晶细胞又是黑色素沉积过程所需要的；2)在识别病原菌方面，Toll信号路径加强了体液免疫与细胞免疫的促进作用[15]，反过来，这2种免疫反应又共同促进Toll信号通路的激活；3)黑化作用不但可以愈合伤口，而且同细胞的吞噬和包裹免疫作用有关联[17]。

在算法模块设计中，果蝇的协同免疫机理主要表现在：下面算法步骤Step6.2通过对比种群A中个体的适应度值、边界函数值以及Bbest来确定新一代个体的更新方向，此模块设计灵感来源于细胞免疫中吞噬、包裹的应答过程，同时也体现了Toll信号通路对细胞免疫的促进作用；Step6.3、Step6.4分别借助Abest、Bbest、Cbest和xbest共同更新种群个体信息，主要模拟体液免疫中Toll和Imd这2种不同信号通路被细胞免疫和体液免疫协同促进激活的免疫应答机理。

结合果蝇免疫理论模型(见图1)和算法CFIOA流程图(见图2)，具体的果蝇免疫协同优化算法步骤可描述为：

Step1参数初始化：群体规模为N，外循环的最大迭代数为Gout，内循环最大迭代数Gin，选择率ω、α、β、δ；置t←1。

Step2随机产生N个个体构成初始群体P，计算个体间的距离，并对距离作归一化处理；记P(t)(P(t)表示第t代的个体种群)中适应度最高的个体为xbest。

Step3置m←1。

Step4执行黑化作用：按距离阈值α剔除P中较差的个体，保留的个体组成群体P*。

Step5种群分割：在P*中随机选取w(1-α)N个个体构成群体A；种群P*-A中距离大于阈值β的个体构成稀疏种群B，其余个体构成稠密种群C。

Step6执行细胞免疫和体液体免疫：

Step6.1种群A、B、C中适应度最高的个体依次记作Abest、Bbest、Cbest，并更新xbest；各子群分别删除δ%的较差个体。

Step6.2细胞免疫：种群A中个体xj执行如下变异：

以获得新种群A*。其中，a、b分别是搜索范围左、右端点的向量；s=min{x-a,b-x}，xdist是个体x与种群A的距离。

Step6.3体液免疫Toll信号通路：种群B中个体xj按如下方式更新：

x′j=xbest+r(Cbest-xj)

获新种群B*，其中，r是0～1的随机数。

Step6.4体液免疫Imd信号通路：种群C中个体xj执行如下变异策略：

x′j=η(Bbest+Abest)+(1-η)(Cbest-xj)

获新种群C*，其中：

Step6.5P(t)←A*∪B*∪C*，若第t代的种群P(t)中适应度最优的个体优于xbest，则更新xbest。

Step6.6若m

Step7若t

否则输出xbest。

2 数值比较实验

数值比较实验均在Window 10/CPU 3.60 GHz /RAM 16.0 GB /VC++环境下展开。参与比较的算法包括FFO[6]、IFFO[6]、MFOA[25]及MDFOA[26]。测试包括7个单模态函数(f1～f7)和3个多模态函数(f8～f10)的最小化问题，分别对应文献[28]的函数(f1、f3、f5、f10、f9、f12、f13、f19、f16、f14)。各算法分别求解各测试问题50次，种群规模均取60，最大迭代数均为225。各算法其他参数设置均与其文献相同。算法CFIOA包含5个参数，经多次数值实验结果分析，选取：

为充分测试CFIOA的行为特性，以上算法均在维数n=100和n=200这2种情形展开数值实验比较与分析，借助搜索效果、执行效率、显著性检验分析，检测它们求解不同类型函数的共同特征与差异性；并单独对算法CFIOA展开维度为n=500、n=600、n=700的高维求解实验，以验证该算法的高维优化能力。

2.1 实验比较分析

2.1.1 100维性能测试与比较分析

当n=100时，上述5种算法分别独立求解每个测试问题50次，获得的平均优化均值统计结果如表1所示。其中，f*表示不同函数在该维度下的目标理论值。以f1、f4、f7、f10为例，各算法获得的平均搜索曲线如图3所示。其中，t表示算法的迭代次数，ft表示各算法在50次独立运行中第t代群体获得的平均目标值。

图3 100维函数f1、f4、f7、f10的平均搜索曲线

表1 100维的统计结果

由表1可知，CFIOA在求解单模态函数(除f3)和多模态函数(除f8)时均有100%的成功率达到理论极值(方差为0)，进一步验证了该算法的求解效果和稳定性。对于函数f4，FFO、IFFO均获得较差的优化均值，且均方差小，说明该算法陷入局部极值后难以跳出，因此种群多样性还有待提高；而MFOA、MDFOA虽然获得的优化均值较大，但因算法采取动态、多种变异协同进化的更新策略，一定程度上维持群体的多样性，提高了搜索到最优解的可能性。从图3各算法的平均搜索曲线可见，算法CFIOA在进化中增加了对区间信息的考虑，同时采用各子群独立又相互影响的协同进化方式，从而保证了求解效果与搜索效率，所以获得优化均值的速度最快且效果最好。

2.1.2 200维性能测试与比较分析

当n=200时，5种比较算法分别求解f1～f10各50次，统计结果见表2。绘制各算法关于函数f1、f4、f7、f10的平均搜索曲线见图4。

表2 200维的比较统计结果

图4 200维函数f1、f4、f7、f10的平均搜索曲线

由表2与表1比较可知，随着问题维数的增加，算法FFO、IFFO、MFOA及MDFOA都有一定的退化，而算法CFIOA的求解效果相对稳定，但对于函数f8只达到理论极值的30%左右。随着求解问题维度的增加，MDFOA求解f8效果最好，但求解f1、f4、f6、f7时效果均较差，而4个函数的搜索区域为非对称区间，最优解的位置也不相同，这说明求解函数的区间对该算法有一定的影响，且随着维数增加，影响更明显。图4与图3中关于各算法的平均搜索曲线的分析结果相似。

2.2 算法效率与显著性差异分析

为明确各算法的搜索效率，5种算法独立求解10个测试函数50次的平均运行时间，见表3。

表3 各算法的平均运行时间分析 单位：s

由表3可知，随着问题维数的增加，各算法运行所需时间也呈倍数增加；而相同维度下，CFIOA所需的平均运行时间最短，主要因为其内循环的特殊设计在很大程度上降低了计算量，缩短了算法搜索时间；FFO、IFFO和MDFOA的优化效率相差不大，而MFOA所需时间略长。

表4 各算法显著性结果分析

从表4的统计数据可知，相同维数下，算法CFIOA获得的F值和FA值较其他算法均较小，且统计值(Statistic)均大于5.99，这说明算法CFIOA在解的质量方面较其他4种算法存在显著性差异[28]。算法FFO、IFFO对应的的F值、FA值均相差较小，表示它们解质量的差异不显著。较FFO、IFFO，MFOA获得的F值和FA值较小，说明MFOA较FFO和IFFO在解的质量方面有一定优势，同理，MDFOA优于FFO、IFFO、MFOA获得的解质量。

2.3 CFIOA的高维优化性能测试与分析

取维数n=500、600、700，算法CFIOA独立求解f1～f10各50次，获得的优化均值统计结果如表5所示。

表5 CFIOA关于500、600、700维函数的统计结果

由表5可知，算法CFIOA求解500、600、700维的函数f2、f7、f9、f10时均能达到理论极值且均方差为0，说明CFIOA在求解此类问题时几乎不受问题维数的影响；求解问题f1时，除700维外，其他均达到了理论极值，而求解700维的该问题时均方差较大，说明求解此问题获得的最优解相差较大，也说明了该算法种群多样性得到了维持；求解500、600维的函数f4、f6时可以达到理论极值，且均方差值为0；求解f8及f4(n=700)时获得的优化均值与其对应的理论目标值还有差距，但均方差较大，说明该算法的种群多样性得到了较好的保持，但其进化模块还需要进一步完善。

3 结束语

本文受果蝇仅有简单且有效的先天性免疫应答机制的启发，并以此为设计来源，提出了果蝇免疫协同优化算法。算法设计中，模拟黑化作用、细胞免疫、体液免疫之间的协同免疫应答机理，为算法的种群多样性和求解效果提供了保障。大量实验表明，算法CFIOA在求解稳定性、算法收敛性以及收敛速度和精度方面较比较算法均有明显优势，并且问题维数对该算法的影响较小。因此，下一步将挑战更高维函数的优化情况以及含有约束条件的优化问题，以提高算法应用的广泛性。