汪 勇，白 雪，艾學(xué)軼，蒲秋梅

（1.武漢科技大學(xué)管理學(xué)院，武漢 430065；2.中央民族大學(xué)信息工程學(xué)院，北京 100081）

0 引言

元啟發(fā)式算法（Meta-heuristic Algorithms，MAs）是解決復(fù)雜工程問題最有效的方法之一。MAs 性能與其探索和開發(fā)能力有關(guān)，研究者在探索機制、開發(fā)策略等方面進行了大量研究，提出了一些代表性的改進算法。針對布谷鳥搜索算法（CS）存在早熟收斂和開發(fā)與探索之間的不平衡問題，Li等（2020）[1]引入歷史和群體知識的學(xué)習模型，提出一種基于自適應(yīng)知識學(xué)習的布谷鳥搜索算法（I-PKL-CS），在探索和開發(fā)之間取得了較好的平衡。Ma等（2019）[2]采用子群體間協(xié)作的動態(tài)自適應(yīng)方式，解決CS算法局部搜索能力不強的問題。Muthulakshmi 和Somasundaram（2019）[3]運用交叉操作和掃描策略改進人工蜂群算法（ABC），提高其探索能力。為提高螢火蟲算法（FA）的優(yōu)化精度，避免陷入局部最優(yōu)值，Li等（2021）[4]在更新公式中加入自適應(yīng)對數(shù)慣性權(quán)重，大大提高了FA 的收斂速度，平衡了FA 的全局探索能力和局部開發(fā)能力。針對麻雀搜索算法（SSA）的收斂速度和穩(wěn)定性問題，Chen 等（2021）[5]提出一種基于levy 飛行和對立學(xué)習策略的改進SSA 算法（LOSSA），增強了SSA 跳出局部最優(yōu)的能力。引力搜索算法（GSA）的搜索機制和引力常數(shù)指數(shù)遞減行為易導(dǎo)致粒子多樣性迅速喪失而過早收斂，Joshi等（2021）[6]提出一種嵌入鄰域檔案的改進GSA，以更少的時間復(fù)雜度實現(xiàn)多樣化的搜索。在求解多目標問題時，Schaffer 等（2020）[7]提出的向量評價遺傳算法被看作是求解多目標問題的開創(chuàng)性工作。此后，Kaur 等（2021）[8]提出非支配排序遺傳算法（NSGA），Kar等（2021）[9]改進NSGA，提出非常經(jīng)典的算法NSGA-Ⅱ。不同MAs 的混合應(yīng)用也是常見的改進手段之一。Muthulakshmi和Somasundaram（2019）[3]將SA的功能集成到ABC 算法中，提出ABC-SA 算法，實現(xiàn)云計算資源的有效分配與調(diào)度。Zhou和Chen（2019）[10]引入GA的交叉算子和變異算子，更新PSO 算法種群中的粒子，提出混合PSO-GA算法，提高了求解高維車間調(diào)度問題解的質(zhì)量和收斂速度。鑒于鯨魚優(yōu)化算法（WOA）在開發(fā)階段表現(xiàn)不佳，而灰狼優(yōu)化算法（GWO）在開發(fā)階段表現(xiàn)優(yōu)異，Hardi和Tarik（2020）[11]將二者雜交，利用GWO在開發(fā)階段具有優(yōu)異的性能解決WOA局部搜索能力不足的問題。除了對MAs進行改進外，一些更為高效的元啟發(fā)式方法相繼被提出，取得了良好的優(yōu)化效果。

雖然各種MAs 及其改進算法的研究取得了長足的進步，但算法的優(yōu)化精度與收斂速度之間的固有矛盾仍然較為突出，全局探索能力和局部開發(fā)能力仍需要進一步改善，模擬人類行為特征的MAs尚不多見。鑒于此，本文模擬人類在病毒溯源過程中的優(yōu)化思想，提出一種新穎的元啟發(fā)式算法，稱為病毒溯源算法（Virus Tracking Algorithm，VTA），旨在進一步提高MAs的優(yōu)化精度和收斂速度。

1 相關(guān)定義

定義1：優(yōu)化變量是一組反映人體健康狀況的生理指標。xij表示感染者xi的第j項生理指標，j=1，2，…，n；yij表示密切接觸者yi的第j項生理指標；xij，yij∈[uj，lj]對應(yīng)優(yōu)化問題的優(yōu)化方案，n為生理指標數(shù)，uj和lj分別表示指標j的上限和下限。

定義2：感染者的集合稱為感染群體，記為X，X={xi|i=1，2，…，N}，xi表示第i個感染者，N為群體規(guī)模。所有感染者的第一個密切接觸者構(gòu)成的集合稱為密切接觸群體，簡稱密接群體，記為Y，Y={yi|i=1，2，…，N}。

定義3：感染者與密切接觸者的發(fā)病時間、癥狀表現(xiàn)、抵抗力等稱為篩查目標，記為fk(xi)與fk(yi)，分別表示感染者與密切接觸者的第k個篩查目標，k=1，2，…，m，m為篩查目標數(shù)。

定義4：設(shè)xi，xj∈Rn，對于最小化問題，若?k∈[1，m]，式（1）與式（2）均成立，則xi優(yōu)于xj，記為xi?xj；反之，則xj優(yōu)于xi，記為xi?xj。

其中，ek是篩查目標k的誤差精度。式（2）表示xi與xj的所有篩查目標差與該目標誤差比之和為負數(shù)。顯然，由式（2）可知，至少存在一個篩查目標l，l∈[1，m]，使得xi的該項目標優(yōu)于xj，即：

當fk(xi)-fk(xj)＜0 時，優(yōu)劣關(guān)系具有傳遞性。當0 ≤fk(xi)-fk(xj)≤ek時，優(yōu)劣關(guān)系不具有傳遞性。

定義5：根據(jù)定義2與定義4，當xi≥yi時，稱xi為更早感染者；反之，稱yi為更早感染者。設(shè)X(t)為第t輪溯源的感染群體，xi∈X，若?xj∈X，xj≠xi，都有F(xi)＞F(xj)成立，則稱xi為本輪溯源的最早感染者，記為xo。其中，F(xiàn)為感染度函數(shù)。

定義6：截止到當前溯源輪數(shù)為止的最早感染者稱為當前最早感染者，記為x*(t)。x*=arg min{x*(t)，t=1，2，…，T}，x*為誤差最優(yōu)解，簡稱最優(yōu)解，T是總的溯源輪數(shù)。與Pareto最優(yōu)解相比，誤差最優(yōu)解可避免優(yōu)化過程中丟失決策者感興趣的滿意解，更能反映決策者的決策意愿。

定義7：最優(yōu)解目標值與理論最優(yōu)解目標值差值的歸一化指數(shù)稱為優(yōu)化精度（OPI），見式（4）。

其中，Norm 是歸一化函數(shù)，fk(x*)和Ok分別是實際最優(yōu)解和理論最優(yōu)解目標k的值。顯然，OPI∈[0,1]。OPI越大，優(yōu)化精度越高，反之越低。

初始最優(yōu)解與溯源結(jié)束時的最優(yōu)解目標差值的時間比率稱為優(yōu)化速度（CRI），見式（5）。

其中，T是達到誤差范圍內(nèi)最優(yōu)解目標值的溯源輪數(shù)，fk(x*(1))是初始最優(yōu)解目標k的值，fk(x*(T))是第T輪溯源最優(yōu)解目標k的值。

每一輪溯源的最早感染者與當前最早感染者目標離差絕對值的算術(shù)平均值稱為平均絕對值誤差（MAE），見式（6）。

優(yōu)化精度、優(yōu)化速度和平均誤差是評價算法優(yōu)化能力的關(guān)鍵性能指標。

2 病毒溯源算法設(shè)計

算法設(shè)計的基本思路是構(gòu)造追蹤方向、追蹤指令和追蹤范圍控制因子，建立具有目標偏好的感染度函數(shù)，設(shè)計具有定向搜索和多目標優(yōu)化能力的追蹤和篩查兩個階段算子，以提高算法優(yōu)化精度和搜索性能。

2.1 追蹤階段

VTA追蹤階段模擬病毒溯源的追蹤過程，從當前感染群體出發(fā)，通過感染者生理指標的啟發(fā)式計算，獲得感染群體中所有感染者的密切接觸者，產(chǎn)生密切接觸群體。

設(shè)xij(t)表示第t輪溯源感染者xi的第j項生理指標，yij(t)表示其第一個密切接觸者相應(yīng)的生理指標，i=1，2，…，N；j=1，2，…，n。根據(jù)病毒傳播特征可知，yij(t)位于xij(t)的δ范圍內(nèi)，二者的差分關(guān)系可表示為：

為提高追蹤的準確性，考慮追蹤方向Dij(t)、追蹤指令I(lǐng)ij(t)和追蹤范圍Sij(t)因素，搜索最有可能感染病毒的密切接觸者。令δ=Dij(t)Iij(t)Sij(t)，則密切接觸者yij(t)與感染者xij(t)的啟發(fā)式計算見式（8）。

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

根據(jù)密切接觸者與感染者的篩查目標及生理指標變化趨勢，確定下一輪溯源的追蹤方向。當篩查目標與生理指標變化趨勢一致時，Dij(t)=1，表示沿著生理指標值增加方向追蹤；反之，Dij(t)= -1，表示沿著生理指標值減小方向追蹤。當生理指標保持不變或感染者與密切接觸者感染時間不具有先后關(guān)系時，追蹤方向保持不變。追蹤方向引導(dǎo)算法朝著最優(yōu)解方向定向搜索，降低了VTA 搜索的隨機性。

Iij(t)是感染者生理指標xij的追蹤指令。設(shè)感染者xi按感染度升序排列，xi在該排列中的位置記為L(xi)。Lr表示一個隨機位置，，r0是區(qū)間[0,1]內(nèi)的隨機數(shù)。當L(xi)≥Lr時，xi的所有指標均隨機改變，xi被追蹤的概率為1-0.5n；當L(xi)＜Lr時，xi的所有指標均同步改變或保持不變，xi被追蹤的概率為0.5。故Iij(t)的取值見式（10）。

其中，r1是在區(qū)間[0,1]內(nèi)的隨機數(shù)。Iij(t)=0 表示停止追蹤，Iij(t)=1表示進行追蹤。

啟發(fā)式因子Sij(t)表示感染者生理指標xij的追蹤范圍。本輪溯源的追蹤范圍與上一輪溯源的追蹤范圍相關(guān)，其遞推關(guān)系見式（11）。

Sij(1)=(uj-lj)r2，uj和lj分別是第j個指標的上界和下界。r2是區(qū)間[0,1]內(nèi)的隨機數(shù)。密切接觸者與感染者目標乘積比作為Sij(t)與Sij(t-1)的相關(guān)系數(shù)。當yi?xi時，追蹤范圍減?。环粗?，追蹤范圍擴大。當優(yōu)化變量值接近最優(yōu)值時，式（11）使優(yōu)化變量值的變化范圍減小，避免算法錯過最優(yōu)解，防止發(fā)生振蕩現(xiàn)象，加快了算法的收斂速度。

2.2 篩查階段

2.2.1 更早感染者篩查

VTA篩查階段模擬病毒溯源的篩查過程，在小規(guī)模范圍內(nèi)搜索可能的最優(yōu)解。包括更早感染者篩查和最早感染者篩查兩個子階段。更早感染者篩查是在感染群體和密接群體之間進行排查，逐一對兩個群體中的感染者及其密切接觸者進行目標比對，確定更早感染者。所有更早感染者構(gòu)成新一輪溯源的感染群體。根據(jù)定義4 和定義5，第t+1輪溯源感染者xi(t+1)可以表示為：

其中，當感染者xi(t)的篩查目標值優(yōu)于密切接觸者yi(t)時，xi(t)為更早感染者，選擇xi(t)作為第t+1 輪溯源的感染者；反之，選擇yi(t)作為第t+1 輪溯源的感染者。當xi(t)=yi(t)時，保留xi(t)作為第t+1輪溯源的感染者。

2.2.2 最早感染者篩查

計算感染者的感染度值，選擇感染度值最大的感染者作為本輪溯源的最早感染者。感染度定義為感染優(yōu)先關(guān)系得分的統(tǒng)計值，根據(jù)定義5，感染者xi的感染度值F(xi)的計算公式如下：

φ(k，xi，xj)表示xi與xj關(guān)于目標k的感染優(yōu)先關(guān)系得分，φ(k，xi，xj)的計算公式如下：

其中，ρ(k，pf)為目標偏好函數(shù)，見式（15）。當追蹤者指定偏好目標pf時，其他目標不參與得分計算，pf∈[1，m]。

根據(jù)定義4，由式（14）知，φ(k，xi，xj)= -φ(k，xj，xi)，即兩個感染者的感染優(yōu)先關(guān)系得分之和為0，故∑F(X)=0。第t輪溯源最早感染者的感染度見式（16）。

2.2.3 當前最早感染者篩查

根據(jù)定義5 與定義6，比較第t-1 輪溯源的當前最早感染者x*(t-1)與第t輪溯源的最早感染者xo(t)的優(yōu)劣關(guān)系，確定第t輪溯源的當前最早感染者x*(t)，見式（17）。

2.3 算法描述

對當前感染群體進行感染度篩查，以獲得感染群體的最早感染者。對最早感染者與上一輪溯源的當前最早感染者進行篩查，確定本輪溯源的當前最早感染者。與此同時，通過追蹤產(chǎn)生密接群體，并對感染者及其密切接觸者進行兩兩篩查，確定更早感染者，由更早感染者組成新一輪溯源的感染群體。優(yōu)化過程見圖1。

圖1 VTA優(yōu)化過程

圖1 展示的是第t輪追蹤產(chǎn)生密接群體并篩查產(chǎn)生第t+1輪感染群體的過程。算法描述如下：

（1）參數(shù)設(shè)置

設(shè)置生理指標n，群體規(guī)模N，追蹤方向D，追蹤范圍S，溯源輪數(shù)T，偏好目標pf，誤差精度e，初始感染群體X。

（2）計算感染群體篩查目標

根據(jù)定義3構(gòu)建優(yōu)化問題的篩查目標函數(shù)，計算初始感染群體X的感染者篩查目標值fk(x)，k=1，2，…，m。

（3）計算感染度

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

（4）篩查最早感染者和當前最早感染者

根據(jù)感染度，篩查第t輪感染群體最早感染者xo(t)及目標值fx，按式（17）確定當前最早感染者x*(t)，并保存其篩查目標值。

（5）終止溯源

若達到最大溯源輪數(shù)，則終止溯源計算，轉(zhuǎn)至步驟（10）；否則，轉(zhuǎn)至下一步。

（6）追蹤密切接觸者

按式（7）至式（11）追蹤所有感染者的密切接觸者，構(gòu)造密接群體Y。

（7）計算密接群體篩查目標

計算密接群體Y中密切接觸者的篩查目標值fy。

（8）篩查更早感染者

按式（12）逐一篩查感染者及其密切接觸者，確定更早感染者，產(chǎn)生新一輪溯源的感染群體X。

（9）調(diào)整追蹤方向和追蹤范圍

根據(jù)感染者和密切接觸者的優(yōu)劣關(guān)系，按式（9）更新追蹤方向X，按式（11）調(diào)整追蹤范圍S，轉(zhuǎn)至步驟（3）。

（10）確定當前最早感染者

按式（17）確定當前最早感染者x*(T)，輸出x*(T)、篩查目標值fk(x*(T))、每一輪溯源的最早感染者xo(t)及篩查目標值fk(xo(t))。

2.4 算法時間復(fù)雜度分析

VTA 的計算量主要由篩查目標計算、感染度計算、追蹤方向和追蹤范圍更新、更早感染者篩查和當前最早感染者篩查過程組成。因感染群體規(guī)模為N，篩查目標數(shù)為m，篩查目標的計算時間復(fù)雜度為O(N)。由式（13）知，對于多個篩查目標，感染度計算的時間復(fù)雜度為O(m×N2)，但當考慮偏好目標時，時間復(fù)雜度下降為O(N)。追蹤方向和追蹤范圍矩陣包含n×N個數(shù)值，每完成一個感染者追蹤方向和追蹤范圍的更新需進行n次生理指標值和m個目標的比較，故追蹤方向更新的時間復(fù)雜度為O(m×n×N)。由式（12）知，感染者與密切接觸者進行m次篩查目標比較以確定更早感染者，故N個感染者的計算時間復(fù)雜度為O(m×N)。每一輪溯源需要比較上一輪最早感染者與本輪最早感染者的篩查目標，以確定當前最早感染者。由式（17）知，時間復(fù)雜度為O(m)。故無目標偏好的VTA最大計算時間復(fù)雜度為O(m×n×N2)，具有目標偏好的VTA最大計算時間復(fù)雜度為O(m×n×N)。

3 算法性能測試

3.1 測試準備

（1）測試函數(shù)

選擇17 個測試函數(shù)，其中CEC 2013 測試函數(shù)5 個、F系列測試函數(shù)3個、ZDT和DTLZ測試函數(shù)5個[12]，自建4個工程類測試函數(shù)W1至W4。其中，CEC和W1為單目標測試函數(shù)，其他為多目標測試函數(shù)。

（2）參數(shù)設(shè)置

為驗證VTA的性能，同時與差分進化（DE）、引力搜索（GSA）、灰狼優(yōu)化（GWO）、非支配排序遺傳算法（NSGA-Ⅲ）、粒子群優(yōu)化（PSO）和鯨魚優(yōu)化（WOA）進行對比測試。所有算法的初始群體均相同，群體規(guī)模N=20，最大迭代次數(shù)T=5000。為提高各算法對特殊初始群體的適應(yīng)性以及保持計算的有效性，除VTA外，其他算法均采用其改進算法。各算法具體參數(shù)見表1。

表1 參數(shù)設(shè)置

3.2 最優(yōu)解分析

為減小算法隨機性對目標值的影響，所有算法均計算50 次，取其平均值作為最優(yōu)解目標值。各算法求解的最優(yōu)解目標值見表2。由表2 可知，對于6 個單目標測試函數(shù)，除GWO、PSO和WOA在CEC f8上目標值接近VTA外，VTA 在其他單目標函數(shù)上的目標值明顯低于其他算法。對于5 個雙目標測試函數(shù)，除ZDT1 的一個目標略低于WOA 外，VTA 在其他函數(shù)上的兩個目標值均低于其他算法。對于4個三目標測試函數(shù)，VTA在DTLZ1上的測試結(jié)果明顯優(yōu)于其他算法，在其他函數(shù)上均有目標值具有明顯的優(yōu)勢，其他目標值接近于最優(yōu)。對于2個四目標測試函數(shù)，VTA求解的DTLZ1的前三個目標接近WOA最低，第四個目標值則明顯低于其他算法。W4 的三個目標優(yōu)化結(jié)果保持最優(yōu)。總體來看，VTA 表現(xiàn)最優(yōu)，GWO 和WOA 的優(yōu)化能力較好，其他算法優(yōu)化能力一般。

表2 最優(yōu)解目標值

為便于觀察最優(yōu)解目標值的變化趨勢，考慮目標值的差異程度，選擇4個測試函數(shù)進行對比分析。各函數(shù)最優(yōu)解目標曲線見圖2至圖4。

圖2 CEC f8、W1目標優(yōu)化曲線

圖2 （a）和圖2（b）分別是單目標函數(shù)CEC f8 和W1 的目標優(yōu)化曲線。VTA和DE收斂速度最快，但DE優(yōu)化精度較低，VTA曲線始終保持最優(yōu)。其他算法無論是優(yōu)化速度還是優(yōu)化精度，都不及VTA效果優(yōu)越。

圖3 是雙目標函數(shù)W2 的目標優(yōu)化曲線?？梢钥闯?，VTA 優(yōu)化的兩個目標曲線下降速度最快，且始終保持最低，表明VTA對于W2的優(yōu)化效果最優(yōu)。其他算法在兩個目標上的優(yōu)化性能基本一致，優(yōu)化速度較慢且精度較低。

圖3 W2目標優(yōu)化曲線

圖4是四目標函數(shù)W4的目標優(yōu)化曲線。VTA在目標1、目標2和目標4上的下降趨勢最為明顯，優(yōu)化速度最快，優(yōu)化精度最高。除DE 在目標2 上的優(yōu)化速度較快外，其他算法在這三個目標上的優(yōu)化速度基本一致。VTA 在目標3 上的優(yōu)化速度和優(yōu)化精度僅優(yōu)于GSA。整體來看，VTA優(yōu)于參與比較的其他算法。

圖4 W4目標優(yōu)化曲線

3.3 考慮目標偏好的VTA優(yōu)化能力分析

選擇兩個雙目標函數(shù)ZDT1 和W2 以及三目標函數(shù)DTLZ3，分別采用無目標偏好和有目標偏好進行優(yōu)化，最優(yōu)解目標值見表3。

表3 目標偏好

表3是VTA的優(yōu)化結(jié)果，三個測試函數(shù)的考慮目標偏好的最優(yōu)解目標值均優(yōu)于無偏好目標值，非偏好目標值略有增大，大于無偏好相應(yīng)目標值，但與其他算法相比，非偏好目標值仍保持較小。可見，考慮目標偏好的VTA 仍具有較高的優(yōu)化精度，滿足決策者對于多目標決策問題的目標偏好需求。以ZDT1為例，考慮目標偏好的目標值變化趨勢見圖5。

圖5 考慮目標偏好的VTA優(yōu)化曲線

圖5 （a）和圖5（b）分別是ZDT1 的兩個目標最優(yōu)解優(yōu)化曲線，可以看出，偏好目標的優(yōu)化曲線比無偏好情形下降趨勢更明顯，具有更快的優(yōu)化速度。

3.4 關(guān)鍵性能指標分析

為觀察各算法的優(yōu)化能力，選擇4 個測試函數(shù)，根據(jù)定義7計算關(guān)鍵性能指標，結(jié)果見表4。

表4 關(guān)鍵性能指標

由表4知，除函數(shù)W2外，VTA在其他函數(shù)上的優(yōu)化精度接近于1，明顯高于其他算法，所測試函數(shù)的優(yōu)化精度均最高。表4 的CRI 表示各算法的優(yōu)化速度，除CEC f8外，VTA的在其他3個函數(shù)上的優(yōu)化速度明顯高于其他算法，觀察表4的平均誤差可以發(fā)現(xiàn)，除VTA在W2的目標2上的平均誤差較DE 略高外，VTA 在其他函數(shù)各目標上的平均誤差遠低于其他算法，其優(yōu)化精度高，優(yōu)化速度快且平均誤差較小。

4 結(jié)束語

本文的實驗結(jié)果表明，病毒溯源優(yōu)化思想的算法模擬是有效的，且易于實現(xiàn)。VTA啟發(fā)式追蹤算子降低了算法搜索的隨機性，能夠快速定向搜索最優(yōu)解。與同類算法相比，優(yōu)化精度、優(yōu)化速度和平均誤差均具有明顯優(yōu)勢。篩查算子使得VTA 具有多目標優(yōu)化能力，考慮目標偏好的VTA 仍能保持良好的多目標優(yōu)化性能。給出的誤差最優(yōu)解定義擴展了Pareto最優(yōu)解范圍，更能體現(xiàn)決策者的決策意愿，實驗證明是可行的。測試函數(shù)驗證了VTA 的良好性能，在算法應(yīng)用方面值得進一步研究。