基于病毒溯源優化思想的元啟發式優化算法

汪 勇，白 雪，艾學軼，蒲秋梅

（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 的三個目標優化結果保持最優?？傮w來看，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 的良好性能，在算法應用方面值得進一步研究。