基于双种群的混合免疫动态优化算法

张卫正，张梦华，张伟伟，金保华，吴怀广，王华，李国庆

(郑州轻工业学院 计算机与通信工程学院，河南 郑州 450000)

0 引 言

优化问题在现实世界中广泛存在于金融、工程、学术等各个领域，吸引了大批研究人员。演化机制和群智能算法凭借自适应、自组织、鲁棒性和可并行性等优点，成为求解优化问题的主力军[1]。在实际应用中，优化问题往往具有动态特性，其决策变量、目标函数、约束条件等都有可能随环境的变化而变化。当环境变化时，最直接的做法是将变化后的问题当做一个新的问题进行求解，但是，群智能优化算法中的搜索种群在环境变化前往往已经收敛于局部最优了，当重新进行搜索时，因种群多样性缺失，容易造成早熟收敛和探索性不足等问题，而重新对种群进行多样性分布和再收敛需要消耗很多计算资源。更重要的是，环境变化前后优化问题的适应度地貌(fitness landscape)可能具有一定的相似性，对其相似性的探索可以帮助及时高效地定位最优解，而不必浪费计算资源进行整个搜索域的探索。

近年来，对动态优化问题的研究掀起了一个热潮，取得了大量的研究成果。这些研究主要可以归为5个方面[2]：(1)当发生变化时，增加种群的多样性；(2)在搜索过程中持续保持种群的多样性；(3)基于预测的方法；(4)自适应的方法；(5)多种群的方法。种群多样性缺失的问题是群智能算法在应对环境变化时的一个很大挑战，因此，现有的大多数研究或多或少与多样性控制有关。现有的研究大都不只局限于其中一个方面，而是结合多个方面设计算法，提高性能。

在自然界中，生物免疫系统能够保护机体对抗随时入侵抗原的攻击。为了实现这种功能，生物免疫系统装备了很多优良的特性，比如“自己”或“非己”的识别，自组织，自适应，分布式，记忆，忍耐性和鲁棒性，等等[3]。这些优良特性使生物免疫系统在求解动态优化问题时具有其他启发式算法所不具备的优势，从而引起了国内外学者的关注[4]。A.Simões等[5]提出了一种与免疫系统相结合的遗传算法(ISGA);YANG S X[6]在ISGA基础上进一步提出了ISGAa算法;动态dopt-aiNet[7]利用改进的黄金分割法加强局部搜索，引入了2种新的超变异机制和cell line压缩机制，消除冗余和保持种群的多样性。实验验证了dopt-aiNet在解决动态优化问题时的有效性。F.O.de Franca[8]进一步对dop-aiNet进行适应性改进，并应用在6个具有挑战性的基准测试函数上。K.Trojanowski等[9]测试了5种以免疫机制为基础的算法在解决动态优化问题时的表现，它们分别是：(1)人工免疫迭代算法(AIIA)[10]；(2)B细胞算法(BCA)[11]；(3)克隆选择算法(CLONALG)[12]；(4)opt-aiNet算法[13]；(5)简单人工免疫系统(SAIS)[14]。分别采用7种变异操作算子应用于这些算法,分析它们的性能。V.S.Aragon[15]根据T细胞反应机制提出的动态T细胞模型(DTC)，用来解决动态优化问题。它模拟了T细胞的不同形态,即VC，CD4，CD8和MC。然后分别对不同的种群应用Gray编码和实数编码实现全局和局部搜索。LI Z J等[4]将体细胞高突变和记忆B细胞克隆选择的思想转化为ITDGA的免疫算子，以适应动态环境。针对0～1动态优化问题；LI L L等[16]提出了一种基于双概率的原对偶遗传算法(DPPDGA)，并引入了亚等位基因和优等位基因，以保持较好的多样性，但它们在所有位点上的重复计算带来了较高的计算成本。

在前述研究成果的基础上，本文提出了一种新的基于双种群的混合免疫动态优化算法BPAIS，通过种群多样性保持、平衡全局性搜索和局部性搜索能力，提升算法的性能，最后在测试函数上进行仿真实验,并与其他现有算法进行比较分析。

1 相关基础理论

1.1 动态优化问题

不失一般性，动态环境下的优化问题可以描述为

最优化f(X，t)=f(x1，x2，…，xq，t),

(1)

最优化问题可以是最小化问题，也可以是最大化问题。

1.2 生物免疫系统

生物免疫系统主要功能是保护机体不受外来病原体等“非己”入侵，为了描述方便，这些“非己”在本文中一律被称为“抗原”(antigen)。为了免受抗原入侵，免疫系统进化出了多层保护机制，如图1所示。

图1 生物免疫系统的多层防御机制Fig.1 Multi-layer defense mechanism of biological immune system

首先是物理层的阻隔，包括皮肤、黏膜等；其次是生化层，机体的分泌物，如唾液、胃酸等可以消灭大部分的抗原；最后是免疫系统的主要部分，分为固有免疫系统和适应性免疫系统。固有免疫系统又叫做非特异性免疫系统，由补体、噬菌细胞等固有免疫细胞组成，是机体先天性就具备的识别和消灭抗原的能力。固有免疫细胞遍布全身，随血流移动，当遭遇抗原，一方面固有免疫细胞可以通过固有免疫反应消灭一部分抗原，另一方面它会激活T淋巴细胞，促使适应性免疫反应。适应性免疫系统是特异性免疫反应系统，主要由T淋巴细胞和B淋巴细胞组成。B淋巴细胞表面存在特异抗原的识别受体，称为抗体(antibody)。每一种B淋巴细胞只能分泌一种抗体。抗体能够与抗原相结合，其结合强度取决于抗体和抗原的模式匹配程度，又称为亲和度(affinity)。特定的抗体对不同的抗原具有不同的亲和度，当亲和度足够高时，抗体可以绑定抗原，并通过调动免疫机制将其消灭。适应性免疫系统对抗原的识别具有专一性，可以识别并消灭固有免疫系统不能消灭的抗原。克隆选择学说[3]是Burnet根据B淋巴细胞适应性免疫反应的机制而提出的最具有代表性的免疫学说之一。其基本思想是只有含有与抗原亲和度高的抗体(B淋巴细胞)得到增殖，而不能识别抗原的则不被选择。抗体数量的增加通过B淋巴细胞自身的克隆。克隆的细胞再通过超变异产生新的抗体，通过不断选择，克隆，超变异最终产生与抗原最佳配体，将抗原消除。这些最佳配体还将被保存为记忆细胞，当再次遭遇相同或者相似抗原时，可以及时高效地消灭抗原。

1.3 人工免疫系统

人工免疫系统(artificial immune system)通过提取生物免疫隐喻，根据免疫细胞的行为和免疫反应的机制构造算法，寻找问题的最优解。在求解优化问题时，最具有代表性的人工免疫算法是基于克隆选择学说的克隆选择算法(clonal selection algorithm，CSA)。L.N.De Castro等[6]最早提出了克隆选择算法CLONALG，并应用于字母识别、多模函数优化、组合优化和TSP问题等。随后，研究学者根据不同的需求，陆续提出了不同的克隆选择算法。

在克隆选择算法中，需要解决的问题被映射为抗原，问题的解被映射为抗体。克隆选择算法主要涉及的免疫机制为选择、克隆和变异。免疫克隆选择算法的主要流程如算法1所示。

算法1 克隆选择算法

Step1：初始化，产生初始抗体种群，k=1

Step2：评价，计算抗体-抗原亲合力，即抗体的适应度值

Step3：选择m个与抗原亲和度高的抗体

Step4：循环条件判断。如果循环条件满足则算法继续，否则结束，输出最优抗体及其适应度值

Step5：对所选择的抗体进行克隆操作

Step6：对克隆个体实施变异操作

Step7：计算新产生个体的适应度值

Step8：选择适应度值高的个体

Step9：k=k+1，返回Step4

2 双种群混合免疫动态优化算法

2.1 种群初始化和种群划分

初始种群由在可行域中随机产生的,呈均匀分布的个体所组成，其产生方式为

Xi，j=LBj+α×(UBj-LBj)，

(2)

式中：i=1，…，Np，Np为种群的大小；j=1，…，D，D为决策变量的维数；UB和LB分别为可行域的上下边界；α为在[0，1]中均匀分布的随机数。

对产生的初始种群根据目标函数评估适应度值，并根据适应度值的高低进行排序，选择p%的较优的个体作为自适应免疫种群AB={ab1，…，abNb}，剩余的被当作固有免疫种群IAB={Iab1，…，IabNa}，Na+Nb=Np。这样，根据适应度值，种群被划分为固有种群和自适应种群。

2.2 固有免疫反应

在生物学上，固有免疫反应是一个非特异性反应过程。固有免疫反应的搜索方式被定义为

(3)

其中，i=1，…，Na，j=1，…，D，N(0，1)为均值0，方差1的高斯随机数，randIab为在可行域内随机产生的随机数。

固有免疫种群负责全局检测抗原，并保持种群的多样性。因此，采用高斯随机数增加扰动，并通过引入随机数使其保持多样性分布。

2.3 适应性免疫优化反应

与固有免疫反应不同，适应性免疫反应是特异性免疫反应。基于克隆选择学说，抗体要经历克隆、超变异和选择的过程产生新的个体。在本文中，算法混合使用了差分进化算子，具体实施过程包括克隆、变异、交叉和选择。

克隆(clone)：对每一个适应性免疫种群中的个体，产生Ncl个克隆，其中Ncl为克隆的个数。

变异(mutation)：对每一个克隆，引入结合差分进化策略中的DE/best/2[17]算子，进行如下变异过程：

Vi=abbest+F×(abr1-abr2)+

F×(abr3-abr4)，

(4)

其中，abbest为当前种群中适应度值最优的个体，r1，r2，r3，r4为随机产生的在[1，Nb]内的整数，而且r1≠r2≠r3≠r4≠i，F为一个正的参数，控制着差分向量。

交叉(crossover)：

(5)

式中：j=1，…，D，D为维数；rand为(0，1)区间的随机数；CR∈[0，1]，为交叉率；jrand∈[1，D]，为确保至少有一维发生变化而随机选择的维数。

选择(selection)：

(6)

对新产生的试验向量(trial vector)Ui进行适应度评估。如果它的适应度值优于父代，则Ui被选择，否则被丢弃。适应性免疫种群负责局部定位最优值，利用差分进化算子加强算法的局部搜索能力。因为差分进化算子局部搜索能力较优，种群在其作用下会很快收敛到局部最优。这里，采用欧式距离计算种群中的个体与种群中最优个体的距离，取平均值作为种群的半径。如果种群的半径小于预先给定的阈值δ，则认为适应性种群已经收敛，将最优个体保存在记忆集合中，删除其他的个体，然后种群重新进行初始化。另外，在每一次迭代中，如果适应性免疫种群中的最优个体与免疫集合中任意个体的距离小于δ，则适应性免疫种群将被删除。

2.4 环境变化检测

在每一次迭代时，种群中全局最优的个体适应度值都要被重新评估，检测是否与之前的一致。若不一致，则表明环境发生变化。如果环境发生变化被检测到，合并固有种群和适应性种群，进行重新评估，并按照适应度值进行排序，再重新按照比例划分为固有种群和适应性种群。另外，在变化时，记忆跟踪机制将被启动。

2.5 记忆跟踪机制

记忆集合中存放的是变化前环境中已收敛的适应性种群的最优个体。一般情况下，这些个体位于或接近适应度景观的局部最优点。环境变化会使优化问题适应度景观发生改变，进一步导致原本的最优解发生改变。但变化后的环境往往与变化前的环境存在一定程度的相似相关性。变化前环境中的局部最优解有可能是变化后环境的全局最优解。对变化前环境的局部最优的跟踪被证明可以有效地提升求解的效率[2]。因此，本文提出了一种记忆跟踪机制跟踪局部最优，提高寻优的效率。当环境变化被检测到，记忆集合中的个体的适应度将被重新评估，然后利用局部搜索算法对每一个记忆集合中的个体进行局部寻优。局部搜索算法有很多，如爬山法，模拟退火法[18]等。本文借鉴单纯直接搜索算法[19]进行局部搜索，跟踪局部最优。

2.6 算法框架

本文提出了一种基于双种群的免疫动态优化算法，初始种群根据适应度被划分为固有免疫种群和适应度免疫种群，固有免疫种群负责全局探索，保持种群多样性，而适应性免疫种群则负责局部定位最优解，该算法步骤描述如下。

算法2 BPAIS算法

Step1：初始化,随机生成规模大小为Np的初始种群

Step2： 评价每一个个体的适应度值

Step3：种群划分，根据适应度值将初始种群划分为固有免疫种群和适应性免疫种群

Step4：环境变化检测

Step5：If环境变化发生

重新初始化种群

种群划分

重新评估记忆集合中个体的适应度值

关于气氛感，现象学抛弃了一比一比对的传统理性二分法，认为在客观对象、内意识、时间，乃至身体后面，总牵扯、勾连与垫衬着一个晕圈一样的背景场域，所以诸多物事背景中的淡晕、氤氲的气氛，自然得到呈现与关注。沿着这种思路，当今德国美学家吉尔诺特·伯梅(1937～)，提出了“气氛美学”观念，言明气氛是审美中感知者与感知对象互相对话融合的场域氛围，且依赖身体性在场的方式，感受到这种气氛。现象学美学家茵伽登论述文学作品在语音、意义、图式与意象四个复合层次之上，有统摄四者的“形而上质”，此“质”即是一种弥漫一切照亮一切的氛围;恰如本雅明所谓环绕艺术作品的“灵韵”。

对记忆集合中的个体进行局部搜索

End If

Step6：适应性免疫优化反应

Step7：If 免疫集合不为空

If适应性免疫种群中最优值与免疫集合中任一个体的距离都小于δ

删除适应性免疫种群

End If

End If

Step8：If 适应性免疫种群收敛

将最优个体放入记忆集合

删除适应性免疫种群

End If

Step9：If 适应性免疫种群为空

固有免疫反应

固有免疫种群和新产生的随机个体一起构成初始种群

对初始种群进行适应度评估

种群划分

Step10：循环条件判断。如果终止条件满足，则结束，否则，返回Step 4

3 仿真实验

3.1 测试函数

3.1.1 STCG函数

STCG[9]测试函数定义了一个动态变化的适应度景观f:X×t→R，其中，X=X1×X2,为可行解集，t为离散的时间。

将可行解集X分解成一系列不相交的子集Aij，即X=∪i∪jAij，对于每个子集Aij，定义了一个抛物面形状的单峰函数fij，

fij(x1，x2)=

(8)

其中,Pij∈[0，pmax]，它控制适应度景观中第ij个峰的高度，本文中pmax=100。如果pij(t)随迭代而变化，将会获得动态景观：其峰值的高度可以周期性地或非周期性地改变。当模拟这些环境时，只有位于主对角线上(图1)或棋盘上2条对角线上(图2)的峰值高度才会发生变化。所有剩余峰的高度保持不变，而且它们的高度都小于变化峰的高度。

图2 STCG主对角线上的峰发生变化

图3 STCG 2条对角线上的峰发生变化

3.1.2 移动峰测试函数

移动峰测试函数是由Branke[20]提出的，针对动态最优化问题的一个通用模型，是至今最为广泛采用的测试函数集。它的适应性景观由一系列峰组成，每一个峰由位置、高度、宽度和峰的形状确定。一个D维的移动峰函数定义为

(9)

式中：Hi(t)和Wi(t)分别为t时刻第i个峰的高度和宽度；Xij(t)为第i个峰的第j维在t时刻的位置，一共有N个彼此相互独立的峰通过最大化函数max结合，构造成移动峰函数。每一次发生变化，每一个峰的位置、高度和宽度的变化为

Hi(t)=Hi(t-1)+height_severityσh，

(10)

Wi(t)=Wi(t-1)+wight_severityσw，

(11)

Xi(t)=Xi(t-1)+vi(t)，

(12)

λvi(t-1))，

(13)

式中：σh和σw分别为均值0，方差1 的高斯随机数；s为控制着峰变化的强度；r为在每一维选择一个随机数归一化到s的向量；λ∈[0.0，1.0]，为控制着当前峰的位置与上一次环境中峰的位置的相关性。

通过调整对应参数的值，可以生成各种不同的移动峰测试函数。

3.2 实验环境设置

3.2.1 测试方案

为了与其他算法进行公平比较，本文采用了以下2种环境测试方案。

测试方案1：如表1所示，采用STCG和MPB 2种测试函数。对于STCG问题，维度设定为2，“10×10”表示将搜索区划分为100个方格，每一个格中有一个独立的峰。c代表周期变化，nc代表非周期变化。

表1 STCG和MPB 2种测试函数的参数Tab.1 Parameters of STCG and MPB test functions

对于MPB问题，维数设定为5，维度设定了2种场景，分别有5个峰和50个峰，每一维的搜索区间为[0，100]，对于环境类型为1的情况，峰的高度变化区间为[30，70]，宽度为[0.0001，0.2]，变化强度为1。而对于环境类型为2的情况，其峰的高度变化区间为[30，70]，宽度为[1，12]，变化强度为1。

测试方案2：采用移动峰测试函数，峰的个数有6种情况，为{5，10，20，30，50，100}，变化强度s有4种情况，为{1，2，3，5}，环境关联系数λ为0，即不相关。高度的变化强度设定为7，宽度的变化强度设定为1。

表2 移动峰测试函数的参数Tab.2 Parameters of moving peak test function

环境变化的间隔为5 000次适应度函数评估，一共变化100次，共计500 000次适应度值评估。每次实验，算法都采用不同的随机种子点开始，一共运行30次，取离线误差的方差和均值。

3.2.2 评价标准

在对算法进行评价时，标准采用离线误差oe，表示自上次环境变化以后评估的最佳个体与最优值之间的平均偏差,定义为

(14)

简而言之，每次评估解的适应度时，辅助变量值通过偏离实际评估的解最优值更新，如果它比上次变化后的任何其他值都要好，或者因为上次变化而偏离了最佳解的最优值，那么每次当景观改变时，应该重置自上次变化以来最优解的值。当实验结束时，变量中的总和除以评估总数。

3.3 实验设置

实验分为2个部分。

(1)测试方案1与基于人工免疫的算法进行比较，参与比较的算法有：人工免疫迭代算法(AIIA)[10]；B细胞算法(BCA)[11]；克隆选择算法(CLONALG)[12]；opt-aiNet算法[13]；简单人工免疫系统(SAIS)[14]；动态T细胞模型(DTC)[15]。

(2)测试方案2与其他进化算法进行比较，参与比较的算法有：多量子群优化算法mQSO(5，5q)[21]； 适应性多量子群优化算法AmQSO[22]；带电粒子群优化算法的多重优化mCPSO[21]；基于种群的萤火虫算法SFA[23]；基于物种的粒子群优化算法SPSO[24]；通过记忆增强动态优化的基于物种的粒子群优化算法MSPSO[25]。

种群个体数目Np设置为50，种群划分比例p设置为10，克隆个数设置为1，距离阈值δ设置为1，F设置为0.7，CR设置为0.9。为公平比较，其余实验参数均与其他相比较的算法保持一致。

3.3 结果和讨论

3.3.1 BPAIS与基于免疫的算法实验比较

实验对比结果如表3所示，独立运行50次测试方案1，选择获得的最优值进行比较，其中参与比较的免疫算法的结果来自于文献[9]中各种免疫算法与不同变异策略相结合的最好值。

表3 BPAIS与其他免疫算法在测试方案1中的 离线误差最好值Tab.3 Best values of offline error obtained by BPAIS and other immune algorithms in test case 1

表3 描述了 BPAIS与其他免疫算法在测试方案1中的STCG和MPB 2种测试函数的比较结果。在STCG函数上，测试了周期性变化的10个峰，20个峰和非周期变化的12个峰，20个峰的情况，在MPB函数上，测试了5个峰和50个峰的情况。结果表明，在所有测试情况下，BPAIS的离线误差最小，性能最好。这是因为参与比较的除DTC以外的基于免疫的算法并没有针对动态变化的处理机制，只是在原本处理静态问题的基础上调整了算子(特别是超变异算子)的构造。当环境变化时，虽然超变异能在一定程度上增加种群的多样性，但从另一方面又削弱了种群的收敛性。因此，这些基于免疫算法的求解效果很差。DTC算法从T淋巴细胞的免疫机制出发，将种群分为4个子种群，包括原始细胞，效用细胞，CD4的效用细胞，CD8的效用细胞和记忆细胞，通过激活机制转换种群中细胞的不同状态处理动态优化问题。DTC算法的机制比较复杂，涉及的参数也比较多，各个种群搜索机制和激活机制也各不相同，导致算法中有很多低效搜索，而且算法留存的记忆并没有得到高效再利用。虽然比之前的基于免疫的算法效果好，但结果还是不尽如人意。而本文提出的BPAIS通过种群的划分，对不同的种群侧重于不同的搜索机制，再加上记忆跟踪机制的配合，得到搜索效果比其他免疫算法更好。

3.3.2 BPAIS与其他进化算法的实验比较

为了进一步检验BPAIS算法的性能，采用移动峰函数进一步对算法进行了仿真和实验，分析并与其他进化算法进行比较。实验结果如表4～5所示，离线误差以均值和标准差的形式展示，其中最好的值以下划线显示。

表4展示了测试方案2中移动峰函数峰的个数不同时算法的表现，可以看出，随着峰个数的增加，大多数算法的离线误差是先增后减的。这是因为当峰的数目较少时，峰个数的增加会加大种群陷入局部最优的风险，从而增加算法寻优的难度。而当峰个数较多时，算法虽然也容易陷入局部最优，但是因为峰的密度较大，即使陷入后也很容易从峰值较低的峰跳到峰值较高的峰上，搜索结果反而会变好。从算法的对比分析可以看出，所提BPAIS算法要优于mQSO(5，5q)，AmQSO，MSPSO，SFA，SPSO。而和MSPSO算法相比时，除了在峰个数为5和10时效果稍差，其余情况下，所提出的BPAIS算法寻优结果都优于算法MSPSO。

表5展示了测试方案2中移动峰函数的变化强度s不同时算法的结果。从结果可以看出，随着变化强度s的增加，所有算法的性能都会变差。这是因为变化强度越大，环境变化的越剧烈，变化后的环境与变化前的环境差异也越大，算法搜索的难度也会不断增加。从对比情况看，所提出的BPAIS算法优于除MSPSO算法外的其他进化算法，而与MSPSO算法的结果在变化剧烈程度s为1，2，5时，所提BPAIS算法的搜索结果稍逊于MSPSO算法，而当s为3时，所提算法的精度略好于MSPSO算法。总体而言，BPAIS算法具有很强的竞争力。

表4 BPAIS和其他进化算法在测试方案2(移动峰函数峰的数目变化)中的离线误差(均值和标准差)Tab.4 Offline errors(mean & std)of BPAIS and other evolutionary algorithms in test case 2 (MPB with number of peaks varying)

表5 BPAIS和其他进化算法在测试方案2(移动峰函数变化强度s改变)上的离线误差(均值和标准差)Tab.5 Offline errors(mean & std)of BPAIS and other evolutionary algorithms in test case 2 (MPB with change severity s varying)

4 结 论

在传统克隆选择算法的基础上，结合固有免疫反应、自适应免疫反应过程和记忆跟踪机制，提出了一种基于双种群的免疫动态优化算法BPAIS。固有免疫反应用来保持种群的多样性，适应性免疫反应用来提高算法的局部搜索能力，记忆跟踪机制用来跟踪局部最优解。通过在移动峰测试函数和STCG测试函数中的仿真实验，结果表明，BPAIS算法具有很好的动态优化能力，能够有效地跟踪和定位全局最优解，与其他算法相比，可以较好地解决早熟收敛和多样性缺失的问题，显示出很强的竞争力。