基于改進灰狼算法的多任務優(yōu)化算法

史光偉，王啟任

（天津工業(yè)大學電子與信息工程學院，天津 300387）

近年來，多任務優(yōu)化（multi-task optimization，MTO）[1-6]已經成為智能優(yōu)化領域的新興研究方向，MTO 關注如何同時解決多個優(yōu)化問題并提高獨立解決各問題的性能，在圖像處理[7]、路徑規(guī)劃[8]和互聯網[9]等領域MTO 技術已經展現出優(yōu)勢。進化多任務方法[10]和多因素優(yōu)化方法[11]是多任務優(yōu)化的兩類重要分支。由Ong 等[5]提出的感知多任務算法（cognitive multitasking algorithm，CMA）是進化多任務的典型代表，其能夠在統一的基因型空間中進行跨域多任務優(yōu)化。由Gupta 等[4]提出的多因素進化算法（multi-factorial evolutionary algorithm，MFEA）是多因素優(yōu)化的典型代表，該算法利用遺傳算法來實現了不同任務之間的信息交互以及個體的更新。相比于CMA 算法，MFEA 通過發(fā)揮任務之間潛在的互補性來實現知識共享，具有更好的尋優(yōu)性能。

2017 年，深圳大學Chen 等[12]提出了一種基于協同進化模因算法的進化多任務單目標優(yōu)化算法。該算法提出了一種基于準牛頓的局部搜索方法，顯著提高了收斂速度。2018 年，華南理工Chen 等[13]提出了一種基于模因多目標差分進化的多任務優(yōu)化方法。該算法的關鍵思想是使用多個子種群來解決多個任務，每個子種群專注于解決單個任務。2020 年，南方科技大學LYU 等[14]提出了一種基于頭腦風暴的多任務優(yōu)化算法，該算法通過所提出的頭腦風暴操作實現各組成任務的優(yōu)化和不同任務之間的知識轉移。以上所提到的算法都是基于MFEA 進行改進的，大都存在尋優(yōu)精度受限、計算耗時長的問題。

基于上述問題，本文提出一種基于改進灰狼算法的多任務優(yōu)化算法（improved grey wolf algorithm based multi-task optimization algorithm，IGWMTO）。該算法采用灰狼算法（GWO）取代MFEA 中的遺傳算法（GA），并引入抗擾因子和動態(tài)權重參數來對狼群個體進行更新，以期進一步提高多任務優(yōu)化算法的優(yōu)化性能。

1 基本原理

1.1 多任務優(yōu)化

在多任務場景中，通常存在一些有用知識可以用來解決某任務問題，同時也有助于求解其他任務問題[15]。因此，通過將多個任務問題以某種方式進行關聯，將有助于改善尋優(yōu)精度和尋優(yōu)效率。給定一個具有k個任務的MTO 問題，在不失一般性的情況下，假設所有任務都是單目標、無約束的最小化問題。定義第j個任務為Tj，其目標函數為fj：Xj→R。其中Xj為Dj維度的解決空間，R 為實數域。MTO 的目標是為k個任務找到全局最優(yōu)值，即

若在特定任務的解決空間上施加了約束條件，則需將約束函數與任務的目標函數一起考慮優(yōu)化。

1.2 MFEA 算法

MFEA 的核心思想是利用n個個體的種群pop=來同時尋找k個任務的全局最優(yōu)值，其中pi表示種群中的個體。MFEA 算法主要由3 個部分組成：種群初始化、遺傳機制和選擇性評價[16]。對于種群初始化，定義第j個任務的維度為Dj，定義維度等于max{Dj}的統一搜索空間Dmultitask。在初始化過程中，每個個體都被賦予一個由Dmultitask隨機變量組成的向量[17]。同時，MFEA 提出以下定義用于評估每個個體的特征。

（1）因素代價：每個個體在所有任務上的因素代價Ψ 被定義為

式中：λ 為懲罰因子；δ 和f為當前個體在該任務上的約束違反總數和目標函數值。

（2）因素等級：每個個體在所有任務上的因素等級r是利用Ψ 對所有個體進行從小到大的排序的索引。

（3）技能因子：每個個體的技能因子τ 是個體在所有任務中能力最好的任務的索引，即

（4）標量適應度：每個個體的標量適應度φ 被定義為

（5）多因素最優(yōu)：如果個體pi是k個任務的全局最優(yōu)，則稱其為多因素最優(yōu)。

對于遺傳機制，MFEA 采用選擇性交配和選擇性模仿2 種方法實現信息在不同任務之間的轉移，并通過隨機交配概率來平衡搜索空間的開發(fā)和探索。在選擇性評估過程中，MFEA 采用一種垂直文化傳播方法來對種群個體進行評估，該方法允許后代模仿上一代的技能因子，進而減少了計算成本[18]。

1.3 灰狼算法

灰狼算法[19]對狼的社會等級進行數學建模，將最優(yōu)個體定義為α 狼，第二優(yōu)和第三優(yōu)的個體分別定義為β 狼和γ 狼，其余剩下個體為ω 狼。灰狼算法利用α 狼、β 狼和γ 狼的位置信息對狼群個體進行更新迭代，從而完成最優(yōu)解的尋找，即針對獵物的包圍過程。上述思想可建模為

式中：t為當前迭代次數；A和C為系數向量；Xp為獵物位置向量；X為灰狼位置向量；D為當前位置與獵物之間的距離。系數向量A和C可表示為：

在迭代過程中，向量a由2 線性下降到0，而r1和r2為[0,1]中的隨機向量。Dα、Dβ和Dγ分別表示當前候選灰狼與最優(yōu)3 頭狼之間的距離，且有

式中：Xα、Xβ和Xγ分別為α、β 和γ 狼的位置向量；X為灰狼的位置向量。進一步，狩獵過程可建模為

其中

2 基于改進灰狼算法的多任務優(yōu)化算法

本文所提IGWMTO 算法的工作流程如圖1 所示。

圖1 IGEMTO 算法流程圖Fig.1 Flow diagram of IGWMTO

相比于MFEA 算法，本文IGWMTO 算法的優(yōu)勢主要體現在以下方面：

（1）采用灰狼算法代替MFEA 算法的遺傳算法，利用個體在所有任務上的技能因子和因素等級來對狼群進行分類，并利用適應度值動態(tài)更新個體隸屬任務。

（2）引入獅群優(yōu)化算法中的抗擾因子[20]，增大了灰狼隨機游走初期的范圍，加強了全局勘探能力，使α 狼、β 狼和γ 狼的位置更新具有一定的隨機性，進而提高種群的多樣性，并且有效避免了陷入局部最優(yōu)的問題，從而得到最優(yōu)解。

（3）基本GWO 算法通過計算3 個最佳灰狼位置的平均值來更新灰狼位置，這種策略并沒有考慮3 頭狼在群體狩獵活動中的貢獻度問題。由于GWO 算法的α 狼并不一定是全局最優(yōu)解，這時在不斷迭代中，隨著其余ω 狼向這3 頭狼逼近，容易陷入局部最優(yōu)。本文算法引入動態(tài)權重參數來平衡全局搜索和局部搜索的相互影響，可進一步提高算法收斂速度和精度。

IGWMTO 算法的具體步驟主要包括以下部分。

步驟1：隨機生成N個個體，并對所有個體進行初始化處理。

步驟2：計算每個個體在所有任務上的適應度值并構建矩陣，其可以表示為

式中：k為任務數量，矩陣元素為每個個體針對某個任務的適應度值。

步驟3：將矩陣中每一行的元素進行排序，并提取每個個體在任務上的排序索引值構建因素等級向量，其向量n=（n1，n2，…，nk）內部元素為該個體在所有任務上的因素等級，其中最小元素所對應的任務為該個體的技能因子η（η∈[1，2，…，k]）。

步驟4：根據該技能因子對狼群進行分類，將排序前三的索引對應的個體分別記作該任務上的α、β 和γ 狼，可以獲得其位置向量Xα、Xβ和Xγ。

步驟5：在對狼群個體進行更新迭代時，考慮到α狼具有很強的局部搜索能力，但容易使得種群陷入局部最優(yōu)。因此，引入獅群優(yōu)化算法的擾動因子，使得狼群個體更新保持一定隨機性，擴大搜索范圍并避免算法過早收斂。進而將式（11）修正為：

式中：ω1為成年獅子比例因子且是（0，1）中的一個隨機數，為使算法收斂更快，值一般小于0.5。ω2為母獅擾動因子，其定義為

式中：s表示獅子在活動范圍內移動的最大步長；l和h分別表示獅子運動范圍空間各維度的最小均值和最大均值；T為最大迭代次數；t為當前迭代次數；ω3為幼獅干擾因子，其可以表示為：

式中：T為最大迭代次數；t為當前迭代次數。在上述公式中，ω2和ω3的步長均設為1。

步驟6：計算當前迭代次數下的狼群個體適應度值。由式（10）可知，典型灰狼算法ω 狼受當前迭代次數占主導地位的灰狼（α、β 和γ 狼）影響。但是，考慮到α、β 和γ 狼的能力存在差異，并且隨著迭代次數的增加，ω 狼會受到α、β 和γ 狼的動態(tài)影響。因此，為了平衡全局搜索和局部搜索之間的相互影響，本文引入動態(tài)權重參數C[21]來更新種群的個體值，其計算公式為

式中：C為一個隨機向量，其范圍為[0，1]。

步驟7：根據式（17）計算當前迭代次數下個體在所有任務上的適應度值并進行對比。若相較于原始任務，該個體在另一任務上的適應度值更好，則需動態(tài)更新該個體所屬任務，并圍繞該任務的頭狼繼續(xù)更新。

步驟8：對所有任務中的頭狼進行更新，重復上述步驟，直到最大迭代次數。

3 實驗及結果分析

本文將種群規(guī)模與迭代次數都設為100，在Benchmark 測試函數上對所提算法進行測試，表1 為測試函數設置情況，且令各維度的搜索空間相同。選取MFEA 作為參照進行對比，令2 種算法分別在多個不同的優(yōu)化問題上進行尋優(yōu)迭代，并將統計結果記錄于表2 中，針對所有的優(yōu)化問題，給出了MFEA 和本文算法運行100 次的最佳適應度值、均值和方差。將每個問題所對應的收斂曲線繪制于圖2—圖5。

表1 Benchmark 測試函數Tab.1 Benchmark test functions

表2 MFEA 和IGWMTO 在不同問題中的結果Tab.2 Results of MFEA and IGWMTO on different problems

圖2 MFEA 和IGWMTO 在問題1 上的收斂趨勢Fig.2 Convergence trends for MFEA and IGWMTO on problem 1

圖3 MFEA 和IGWMTO 在問題2 上的收斂趨勢Fig.3 Convergence trends for MFEA and IGWMTO on problem 2

圖4 MFEA 和IGWMTO 在問題3上的收斂趨勢Fig.4 Convergence trends for MFEA and IGWMTO on problem 3

圖5 MFEA 和IGWMTO 在問題4 上的收斂趨勢Fig.5 Convergence trend of MFEA and IGWMTO on problem 4

由表2 可以看出，IGWMTO 在4 個不同的優(yōu)化問題中的結果均優(yōu)于MFEA 的尋優(yōu)結果。上述結果表明，IGWMTO 具有良好的快速尋優(yōu)能力和深度尋優(yōu)能力。

算法運行時間如表3 所示。

表3 IGWMTO 與MFEA 的運行時間Tab.3 Running time of IGWMTO and MFEA s

由圖2—圖5 可知，相比于MFEA，IGWMTO 在所有任務中的曲線下降速度更快，收斂速度和效果更好。由表3 可知，IGWMTO 在運算速度上也存在優(yōu)勢，相較于MFEA 算法，其在4 個不同優(yōu)化問題中的運行時間分別降低了約80.1%、76.8%、74.8%和76.5%。

4 結束語

本文提出了一種新穎且易于實現的基于改進灰狼算法的多任務優(yōu)化算法，其通過計算個體的因素等級和技能因子來對狼群進行分類并根據適應度值動態(tài)更新個體隸屬任務，引入獅群優(yōu)化算法的抗擾因子和動態(tài)權重參數來對原始灰狼算法進行改進。該方法不僅提高了種群的多樣性，而且平衡了全局搜索和局部搜索之間的相互影響，大大提高了算法收斂的精度和速度。與MFEA 算法相比，本文IGWMTA 算法在4個不同優(yōu)化問題中的運行時間分別降低了約80.1%、76.8%、74.8%和76.5%。