基于病毒溯源优化思想的元启发式优化算法

汪 勇，白 雪，艾学轶，蒲秋梅

（1.武汉科技大学管理学院，武汉 430065；2.中央民族大学信息工程学院，北京 100081）

0 引言

元启发式算法（Meta-heuristic Algorithms，MAs）是解决复杂工程问题最有效的方法之一。MAs 性能与其探索和开发能力有关，研究者在探索机制、开发策略等方面进行了大量研究，提出了一些代表性的改进算法。针对布谷鸟搜索算法（CS）存在早熟收敛和开发与探索之间的不平衡问题，Li等（2020）[1]引入历史和群体知识的学习模型，提出一种基于自适应知识学习的布谷鸟搜索算法（I-PKL-CS），在探索和开发之间取得了较好的平衡。Ma等（2019）[2]采用子群体间协作的动态自适应方式，解决CS算法局部搜索能力不强的问题。Muthulakshmi 和Somasundaram（2019）[3]运用交叉操作和扫描策略改进人工蜂群算法（ABC），提高其探索能力。为提高萤火虫算法（FA）的优化精度，避免陷入局部最优值，Li等（2021）[4]在更新公式中加入自适应对数惯性权重，大大提高了FA 的收敛速度，平衡了FA 的全局探索能力和局部开发能力。针对麻雀搜索算法（SSA）的收敛速度和稳定性问题，Chen 等（2021）[5]提出一种基于levy 飞行和对立学习策略的改进SSA 算法（LOSSA），增强了SSA 跳出局部最优的能力。引力搜索算法（GSA）的搜索机制和引力常数指数递减行为易导致粒子多样性迅速丧失而过早收敛，Joshi等（2021）[6]提出一种嵌入邻域档案的改进GSA，以更少的时间复杂度实现多样化的搜索。在求解多目标问题时，Schaffer 等（2020）[7]提出的向量评价遗传算法被看作是求解多目标问题的开创性工作。此后，Kaur 等（2021）[8]提出非支配排序遗传算法（NSGA），Kar等（2021）[9]改进NSGA，提出非常经典的算法NSGA-Ⅱ。不同MAs 的混合应用也是常见的改进手段之一。Muthulakshmi和Somasundaram（2019）[3]将SA的功能集成到ABC 算法中，提出ABC-SA 算法，实现云计算资源的有效分配与调度。Zhou和Chen（2019）[10]引入GA的交叉算子和变异算子，更新PSO 算法种群中的粒子，提出混合PSO-GA算法，提高了求解高维车间调度问题解的质量和收敛速度。鉴于鲸鱼优化算法（WOA）在开发阶段表现不佳，而灰狼优化算法（GWO）在开发阶段表现优异，Hardi和Tarik（2020）[11]将二者杂交，利用GWO在开发阶段具有优异的性能解决WOA局部搜索能力不足的问题。除了对MAs进行改进外，一些更为高效的元启发式方法相继被提出，取得了良好的优化效果。

虽然各种MAs 及其改进算法的研究取得了长足的进步，但算法的优化精度与收敛速度之间的固有矛盾仍然较为突出，全局探索能力和局部开发能力仍需要进一步改善，模拟人类行为特征的MAs尚不多见。鉴于此，本文模拟人类在病毒溯源过程中的优化思想，提出一种新颖的元启发式算法，称为病毒溯源算法（Virus Tracking Algorithm，VTA），旨在进一步提高MAs的优化精度和收敛速度。

1 相关定义

定义1：优化变量是一组反映人体健康状况的生理指标。xij表示感染者xi的第j项生理指标，j=1，2，…，n；yij表示密切接触者yi的第j项生理指标；xij，yij∈[uj，lj]对应优化问题的优化方案，n为生理指标数，uj和lj分别表示指标j的上限和下限。

定义2：感染者的集合称为感染群体，记为X，X={xi|i=1，2，…，N}，xi表示第i个感染者，N为群体规模。所有感染者的第一个密切接触者构成的集合称为密切接触群体，简称密接群体，记为Y，Y={yi|i=1，2，…，N}。

定义3：感染者与密切接触者的发病时间、症状表现、抵抗力等称为筛查目标，记为fk(xi)与fk(yi)，分别表示感染者与密切接触者的第k个筛查目标，k=1，2，…，m，m为筛查目标数。

定义4：设xi，xj∈Rn，对于最小化问题，若∀k∈[1，m]，式（1）与式（2）均成立，则xi优于xj，记为xi≻xj；反之，则xj优于xi，记为xi≺xj。

其中，ek是筛查目标k的误差精度。式（2）表示xi与xj的所有筛查目标差与该目标误差比之和为负数。显然，由式（2）可知，至少存在一个筛查目标l，l∈[1，m]，使得xi的该项目标优于xj，即：

当fk(xi)-fk(xj)＜0 时，优劣关系具有传递性。当0 ≤fk(xi)-fk(xj)≤ek时，优劣关系不具有传递性。

定义5：根据定义2与定义4，当xi≥yi时，称xi为更早感染者；反之，称yi为更早感染者。设X(t)为第t轮溯源的感染群体，xi∈X，若∀xj∈X，xj≠xi，都有F(xi)＞F(xj)成立，则称xi为本轮溯源的最早感染者，记为xo。其中，F为感染度函数。

定义6：截止到当前溯源轮数为止的最早感染者称为当前最早感染者，记为x*(t)。x*=arg min{x*(t)，t=1，2，…，T}，x*为误差最优解，简称最优解，T是总的溯源轮数。与Pareto最优解相比，误差最优解可避免优化过程中丢失决策者感兴趣的满意解，更能反映决策者的决策意愿。

定义7：最优解目标值与理论最优解目标值差值的归一化指数称为优化精度（OPI），见式（4）。

其中，Norm 是归一化函数，fk(x*)和Ok分别是实际最优解和理论最优解目标k的值。显然，OPI∈[0,1]。OPI越大，优化精度越高，反之越低。

初始最优解与溯源结束时的最优解目标差值的时间比率称为优化速度（CRI），见式（5）。

其中，T是达到误差范围内最优解目标值的溯源轮数，fk(x*(1))是初始最优解目标k的值，fk(x*(T))是第T轮溯源最优解目标k的值。

每一轮溯源的最早感染者与当前最早感染者目标离差绝对值的算术平均值称为平均绝对值误差（MAE），见式（6）。

优化精度、优化速度和平均误差是评价算法优化能力的关键性能指标。

2 病毒溯源算法设计

算法设计的基本思路是构造追踪方向、追踪指令和追踪范围控制因子，建立具有目标偏好的感染度函数，设计具有定向搜索和多目标优化能力的追踪和筛查两个阶段算子，以提高算法优化精度和搜索性能。

2.1 追踪阶段

VTA追踪阶段模拟病毒溯源的追踪过程，从当前感染群体出发，通过感染者生理指标的启发式计算，获得感染群体中所有感染者的密切接触者，产生密切接触群体。

设xij(t)表示第t轮溯源感染者xi的第j项生理指标，yij(t)表示其第一个密切接触者相应的生理指标，i=1，2，…，N；j=1，2，…，n。根据病毒传播特征可知，yij(t)位于xij(t)的δ范围内，二者的差分关系可表示为：

为提高追踪的准确性，考虑追踪方向Dij(t)、追踪指令Iij(t)和追踪范围Sij(t)因素，搜索最有可能感染病毒的密切接触者。令δ=Dij(t)Iij(t)Sij(t)，则密切接触者yij(t)与感染者xij(t)的启发式计算见式（8）。

式（8）中，Dij(t)是感染者生理指标xij的追踪方向，更新方法见式（9）。

根据密切接触者与感染者的筛查目标及生理指标变化趋势，确定下一轮溯源的追踪方向。当筛查目标与生理指标变化趋势一致时，Dij(t)=1，表示沿着生理指标值增加方向追踪；反之，Dij(t)= -1，表示沿着生理指标值减小方向追踪。当生理指标保持不变或感染者与密切接触者感染时间不具有先后关系时，追踪方向保持不变。追踪方向引导算法朝着最优解方向定向搜索，降低了VTA 搜索的随机性。

Iij(t)是感染者生理指标xij的追踪指令。设感染者xi按感染度升序排列，xi在该排列中的位置记为L(xi)。Lr表示一个随机位置，，r0是区间[0,1]内的随机数。当L(xi)≥Lr时，xi的所有指标均随机改变，xi被追踪的概率为1-0.5n；当L(xi)＜Lr时，xi的所有指标均同步改变或保持不变，xi被追踪的概率为0.5。故Iij(t)的取值见式（10）。

其中，r1是在区间[0,1]内的随机数。Iij(t)=0 表示停止追踪，Iij(t)=1表示进行追踪。

启发式因子Sij(t)表示感染者生理指标xij的追踪范围。本轮溯源的追踪范围与上一轮溯源的追踪范围相关，其递推关系见式（11）。

Sij(1)=(uj-lj)r2，uj和lj分别是第j个指标的上界和下界。r2是区间[0,1]内的随机数。密切接触者与感染者目标乘积比作为Sij(t)与Sij(t-1)的相关系数。当yi≻xi时，追踪范围减小；反之，追踪范围扩大。当优化变量值接近最优值时，式（11）使优化变量值的变化范围减小，避免算法错过最优解，防止发生振荡现象，加快了算法的收敛速度。

2.2 筛查阶段

2.2.1 更早感染者筛查

VTA筛查阶段模拟病毒溯源的筛查过程，在小规模范围内搜索可能的最优解。包括更早感染者筛查和最早感染者筛查两个子阶段。更早感染者筛查是在感染群体和密接群体之间进行排查，逐一对两个群体中的感染者及其密切接触者进行目标比对，确定更早感染者。所有更早感染者构成新一轮溯源的感染群体。根据定义4 和定义5，第t+1轮溯源感染者xi(t+1)可以表示为：

其中，当感染者xi(t)的筛查目标值优于密切接触者yi(t)时，xi(t)为更早感染者，选择xi(t)作为第t+1 轮溯源的感染者；反之，选择yi(t)作为第t+1 轮溯源的感染者。当xi(t)=yi(t)时，保留xi(t)作为第t+1轮溯源的感染者。

2.2.2 最早感染者筛查

计算感染者的感染度值，选择感染度值最大的感染者作为本轮溯源的最早感染者。感染度定义为感染优先关系得分的统计值，根据定义5，感染者xi的感染度值F(xi)的计算公式如下：

φ(k，xi，xj)表示xi与xj关于目标k的感染优先关系得分，φ(k，xi，xj)的计算公式如下：

其中，ρ(k，pf)为目标偏好函数，见式（15）。当追踪者指定偏好目标pf时，其他目标不参与得分计算，pf∈[1，m]。

根据定义4，由式（14）知，φ(k，xi，xj)= -φ(k，xj，xi)，即两个感染者的感染优先关系得分之和为0，故∑F(X)=0。第t轮溯源最早感染者的感染度见式（16）。

2.2.3 当前最早感染者筛查

根据定义5 与定义6，比较第t-1 轮溯源的当前最早感染者x*(t-1)与第t轮溯源的最早感染者xo(t)的优劣关系，确定第t轮溯源的当前最早感染者x*(t)，见式（17）。

2.3 算法描述

对当前感染群体进行感染度筛查，以获得感染群体的最早感染者。对最早感染者与上一轮溯源的当前最早感染者进行筛查，确定本轮溯源的当前最早感染者。与此同时，通过追踪产生密接群体，并对感染者及其密切接触者进行两两筛查，确定更早感染者，由更早感染者组成新一轮溯源的感染群体。优化过程见图1。

图1 VTA优化过程

图1 展示的是第t轮追踪产生密接群体并筛查产生第t+1轮感染群体的过程。算法描述如下：

（1）参数设置

设置生理指标n，群体规模N，追踪方向D，追踪范围S，溯源轮数T，偏好目标pf，误差精度e，初始感染群体X。

（2）计算感染群体筛查目标

根据定义3构建优化问题的筛查目标函数，计算初始感染群体X的感染者筛查目标值fk(x)，k=1，2，…，m。

（3）计算感染度

按式（13）至式（15）计算感染群体X的感染者感染度值F。

（4）筛查最早感染者和当前最早感染者

根据感染度，筛查第t轮感染群体最早感染者xo(t)及目标值fx，按式（17）确定当前最早感染者x*(t)，并保存其筛查目标值。

（5）终止溯源

若达到最大溯源轮数，则终止溯源计算，转至步骤（10）；否则，转至下一步。

（6）追踪密切接触者

按式（7）至式（11）追踪所有感染者的密切接触者，构造密接群体Y。

（7）计算密接群体筛查目标

计算密接群体Y中密切接触者的筛查目标值fy。

（8）筛查更早感染者

按式（12）逐一筛查感染者及其密切接触者，确定更早感染者，产生新一轮溯源的感染群体X。

（9）调整追踪方向和追踪范围

根据感染者和密切接触者的优劣关系，按式（9）更新追踪方向X，按式（11）调整追踪范围S，转至步骤（3）。

（10）确定当前最早感染者

按式（17）确定当前最早感染者x*(T)，输出x*(T)、筛查目标值fk(x*(T))、每一轮溯源的最早感染者xo(t)及筛查目标值fk(xo(t))。

2.4 算法时间复杂度分析

VTA 的计算量主要由筛查目标计算、感染度计算、追踪方向和追踪范围更新、更早感染者筛查和当前最早感染者筛查过程组成。因感染群体规模为N，筛查目标数为m，筛查目标的计算时间复杂度为O(N)。由式（13）知，对于多个筛查目标，感染度计算的时间复杂度为O(m×N2)，但当考虑偏好目标时，时间复杂度下降为O(N)。追踪方向和追踪范围矩阵包含n×N个数值，每完成一个感染者追踪方向和追踪范围的更新需进行n次生理指标值和m个目标的比较，故追踪方向更新的时间复杂度为O(m×n×N)。由式（12）知，感染者与密切接触者进行m次筛查目标比较以确定更早感染者，故N个感染者的计算时间复杂度为O(m×N)。每一轮溯源需要比较上一轮最早感染者与本轮最早感染者的筛查目标，以确定当前最早感染者。由式（17）知，时间复杂度为O(m)。故无目标偏好的VTA最大计算时间复杂度为O(m×n×N2)，具有目标偏好的VTA最大计算时间复杂度为O(m×n×N)。

3 算法性能测试

3.1 测试准备

（1）测试函数

选择17 个测试函数，其中CEC 2013 测试函数5 个、F系列测试函数3个、ZDT和DTLZ测试函数5个[12]，自建4个工程类测试函数W1至W4。其中，CEC和W1为单目标测试函数，其他为多目标测试函数。

（2）参数设置

为验证VTA的性能，同时与差分进化（DE）、引力搜索（GSA）、灰狼优化（GWO）、非支配排序遗传算法（NSGA-Ⅲ）、粒子群优化（PSO）和鲸鱼优化（WOA）进行对比测试。所有算法的初始群体均相同，群体规模N=20，最大迭代次数T=5000。为提高各算法对特殊初始群体的适应性以及保持计算的有效性，除VTA外，其他算法均采用其改进算法。各算法具体参数见表1。

表1 参数设置

3.2 最优解分析

为减小算法随机性对目标值的影响，所有算法均计算50 次，取其平均值作为最优解目标值。各算法求解的最优解目标值见表2。由表2 可知，对于6 个单目标测试函数，除GWO、PSO和WOA在CEC f8上目标值接近VTA外，VTA 在其他单目标函数上的目标值明显低于其他算法。对于5 个双目标测试函数，除ZDT1 的一个目标略低于WOA 外，VTA 在其他函数上的两个目标值均低于其他算法。对于4个三目标测试函数，VTA在DTLZ1上的测试结果明显优于其他算法，在其他函数上均有目标值具有明显的优势，其他目标值接近于最优。对于2个四目标测试函数，VTA求解的DTLZ1的前三个目标接近WOA最低，第四个目标值则明显低于其他算法。W4 的三个目标优化结果保持最优。总体来看，VTA 表现最优，GWO 和WOA 的优化能力较好，其他算法优化能力一般。

表2 最优解目标值

为便于观察最优解目标值的变化趋势，考虑目标值的差异程度，选择4个测试函数进行对比分析。各函数最优解目标曲线见图2至图4。

图2 CEC f8、W1目标优化曲线

图2 （a）和图2（b）分别是单目标函数CEC f8 和W1 的目标优化曲线。VTA和DE收敛速度最快，但DE优化精度较低，VTA曲线始终保持最优。其他算法无论是优化速度还是优化精度，都不及VTA效果优越。

图3 是双目标函数W2 的目标优化曲线。可以看出，VTA 优化的两个目标曲线下降速度最快，且始终保持最低，表明VTA对于W2的优化效果最优。其他算法在两个目标上的优化性能基本一致，优化速度较慢且精度较低。

图3 W2目标优化曲线

图4是四目标函数W4的目标优化曲线。VTA在目标1、目标2和目标4上的下降趋势最为明显，优化速度最快，优化精度最高。除DE 在目标2 上的优化速度较快外，其他算法在这三个目标上的优化速度基本一致。VTA 在目标3 上的优化速度和优化精度仅优于GSA。整体来看，VTA优于参与比较的其他算法。

图4 W4目标优化曲线

3.3 考虑目标偏好的VTA优化能力分析

选择两个双目标函数ZDT1 和W2 以及三目标函数DTLZ3，分别采用无目标偏好和有目标偏好进行优化，最优解目标值见表3。

表3 目标偏好

表3是VTA的优化结果，三个测试函数的考虑目标偏好的最优解目标值均优于无偏好目标值，非偏好目标值略有增大，大于无偏好相应目标值，但与其他算法相比，非偏好目标值仍保持较小。可见，考虑目标偏好的VTA 仍具有较高的优化精度，满足决策者对于多目标决策问题的目标偏好需求。以ZDT1为例，考虑目标偏好的目标值变化趋势见图5。

图5 考虑目标偏好的VTA优化曲线

图5 （a）和图5（b）分别是ZDT1 的两个目标最优解优化曲线，可以看出，偏好目标的优化曲线比无偏好情形下降趋势更明显，具有更快的优化速度。

3.4 关键性能指标分析

为观察各算法的优化能力，选择4 个测试函数，根据定义7计算关键性能指标，结果见表4。

表4 关键性能指标

由表4知，除函数W2外，VTA在其他函数上的优化精度接近于1，明显高于其他算法，所测试函数的优化精度均最高。表4 的CRI 表示各算法的优化速度，除CEC f8外，VTA的在其他3个函数上的优化速度明显高于其他算法，观察表4的平均误差可以发现，除VTA在W2的目标2上的平均误差较DE 略高外，VTA 在其他函数各目标上的平均误差远低于其他算法，其优化精度高，优化速度快且平均误差较小。

4 结束语

本文的实验结果表明，病毒溯源优化思想的算法模拟是有效的，且易于实现。VTA启发式追踪算子降低了算法搜索的随机性，能够快速定向搜索最优解。与同类算法相比，优化精度、优化速度和平均误差均具有明显优势。筛查算子使得VTA 具有多目标优化能力，考虑目标偏好的VTA 仍能保持良好的多目标优化性能。给出的误差最优解定义扩展了Pareto最优解范围，更能体现决策者的决策意愿，实验证明是可行的。测试函数验证了VTA 的良好性能，在算法应用方面值得进一步研究。