灰狼優化算法求解任務分配問題

朱 凡 謝亮亮

（[1]江西機電職業技術學院 江西·南昌 330000；[2]江西銀行股份有限公司 江西·南昌 330000）

0 引言

任務分配問題是一類典型的組合優化問題，它的優化目標是確定合理的子任務分配方案使所有任務的總完成時間最短。在問題規模較大和規定時間范圍內尋找到問題的滿意解。

很多啟發式算法都是是對自然現象的模擬，其中灰狼優化算法（GWO）就是2012年Mirjalili S提出的一種通過模擬自然界中灰狼種群捕食過程的新型元啟發式算法。GWO是通過設定合適的適應度函數就能使目標函數達到最優解。目前，GWO應用范圍廣泛，但還沒有將其應用于求解任務分配問題。因GWO原理簡單、需調整的參數少、易于實現、全局搜索能力強等特點，本文嘗試將其應用于解決任務分配問題。

1 任務分配問題的數學描述

式中，（1）表示每個工人要執行一項任務；（2）表示每項任務被執行且被執行一次；（3）表示分配方案的元素值只能取0或者1。

2 灰狼優化算法（GWO）

GWO是一種隨機全局優化方法，靈感來自于自然界中的灰狼種群的領導等級和狩獵機制。具體原理如下：

2.1 灰狼的等級劃分

在GWO中，灰狼群有社會等級層次這樣一個特殊點和群體狩獵的另一個特定社會行為。一般被分為四層，是狼群中適應度最佳的狼稱為領導者，是狼群中適應度次最佳的狼稱作下屬狼負責幫助做決策或一些其他的活動，是狼群中適應度第三優的狼，它服從于是狼群中等級最低的狼且被比它等級高的狼所控制。

2.2 灰狼圍住獵物模型

灰狼群在狩獵的時候，首先要對獵物進行跟蹤，之后追逐獵物，接著趕上獵物進而團團圍住獵物。此時的數學模型公式為如下所示：

2.3 狩獵數學模型

在GWO中狩獵行為就是數學中的優化操作，這時主要由灰狼群中前三個等級引導，而灰狼跟隨著前三個等級的狼。當灰狼群團團圍住獵物，進而騷擾獵物，直到獵物停下，最后開始攻擊獵物，執行狩獵行為。這個行為通常是領導者帶領一同參與。

2.4 確定位置攻擊獵物

狼群會根據獵物所停住的位置進行鎖定，進而開始發動攻擊來完成狩獵活動。為了靠近獵物，在模型中設定的值并減小，因此的值會因為而減小了。也就是說，在解決具體問題的時候，的值會從2減小到0，則是范圍內的隨機一個值。如果的值在[-1，1]內，獵物和灰狼的當前的位置之間的任意位置就是灰狼的下一個位置?；依菍ΛC物發起攻擊時是小于1的。

2.5 搜尋獵物

GWO是從狼群的隨機創建到四個等級的狼群劃分并預測獵物的位置，進而實現狼群中所有狼與獵物的新距離。從公式（6）中a的值的改變來判定GWO的全局搜索能力，從的取值來確定狼群與獵物距離的遠近，最后達到結束條件，得到GWO優化后的最優解。

3 用GWO算法求解任務分配問題

簡單的任務分配問題是給出兩列元素及任意兩列元素配對時的代價，找到1組一對一的配對使其代價和最小。設一列，表示工人編號，另一列，表示任務編號；一對一的分配表示每個工人被分配到1項任務，且不同的工人與不同的任務相配，，表示給工人分配任務時的代價。狼群的狩獵過程包括：跟蹤，追逐，接近獵物；追趕包圍，騷擾獵物直到它們停下；攻擊。設有只狼，用狼群捕食來表示任務分配，每只灰狼代表決策變量的1個可能取值，每只灰狼的位置初始隨機生成，記錄下灰狼的初始位置；之后捕食獵物時，再記錄下每只灰狼到達自己能最好攻擊獵物位置。把任務分配問題與灰狼優化算法聯系起來，是要每只灰狼快速到達自己該達到的位置以攻擊獵物，最終在最短時間內捕食到獵物，正如每個工人在最快時間內完成自己的任務，以至于最后的總代價最小。

由于任務無先后之分，工人無主次之分，為使算法更具一般性，每只狼的位置由不同工人、不同任務得到，不妨令灰狼離獵物的最佳攻擊位置為某個工人做某項任務的代價。由此可得任務分配問題的灰狼優化算法描述如下：

（2）適應度計算：適應度函數用于評價個體的優劣程度，適應度越大個體越好，反之適應度越小則個體越差；適應度函數是由目標函數來設定的，在GWO中也是區分狼群中個體層次的標準。在GWO中，需要計算每只灰狼的適應度，適應度函數用公式（12）表示：

則取適應值前三的灰狼為：

4 實驗仿真與分析

本文仿真實驗采用的實驗環境有軟硬件兩個部分。軟件部分采用的工具為 Matlab-R2009a，硬件部分 PC機型號是ACER 4752G，Intel Core 2 i3-2350M處理器，4G內存。用多維矩陣進行了大量的仿真驗證，并把GWO與傳統的匈牙利算法進行比較，結果如表1所示。

表1：算法的求解時聞與優化結果比較

從表格中的數據可以看出：5×5的矩陣，匈牙利算法的速度為0.039273/s，本文GWO算法為0.004065/s，提速9.6613倍。50×50的矩陣，匈牙利算法的速度為0.182077/s，本文GWO算法為0.035542/s，提速5.1229倍。100×100的矩陣，匈牙利算法的速度為0.371586/s，本文GWO算法為0.075491/s，提速4.9223倍。分析仿真結果，得出結論：本文算法GWO的計算速度明顯高于匈牙利算法。但隨著矩陣維數的增加，兩者計算速度的倍數也在減小，從而說明GWO的穩定性有待加強。

5 結束語

雖然灰狼優化算法出現的時間沒有其他智能算法長，但它已顯示出求解優化問題的優勢。本文綜合任務分配的理論與實際意義，針對任務分配問題首次運用了GWO，仿真結果證明效果良好。