求解保障任務分配問題的綜述

朱俊明 何茂森 林沐霖

摘 要 本文首先對保障任務分配問題的基本概念進行了闡述，分析了今年來求解任務分配問題的數學方法及研究現狀，最后總結了現行有效的群智能優化算法并進行了內容闡述。

關鍵詞 任務分配 群智能算法 保障問題

中圖分類號：TN925文獻標識碼：A

1任務分配問題概述

問題描述：N個人分配N項任務，一個人只能分配一項任務，一項任務只能分配給一個人，將一項任務分配給一個人是需要支付報酬的，如何分配任務，保證支付的報酬總數最小？在任務分配問題中，每個人完成每個項目的花費成本是不同的，最終所求是所有人完成所有工作的最花費成本最低。

2任務分配問題的研究現狀

任務分配問題是一個線性規劃問題，數學模型構成簡單，約束條件可根據所構造數學模型的要求進行設置，因此在實際中應用范圍很廣，適合大部分離散分配問題。僅2018年就有眾多學者們用感興趣的群智能優化算法對各類問題進行求解，取得了很好的效果。呂龍等人在求解工作流系統的任務分配問題時，基于蟻群算法通過考慮協作兼容性和每個執行程序的工作量來實現優化，并取得了較好的結果。董海霞等人采用粒子群算法求解無人機的任務分配問題，通過實驗仿真可以實現對多種群的多目標優化方案求解。同樣是面對無人機任務分配問題，魏政磊等人分析了動態任務分配的特點，設計了目標任務序列編碼的方式，提出用改進的灰狼優化算法進行求解，并通過實驗仿真證明，算法收斂且有效。

3任務分配問題的求解方法

從上述研究現狀中可以看出，使用群智能優化算法是求解任務分配問題的一個較好的解決辦法。目前經過大量文獻閱讀可知，此類群智能優化算法有：蟻群算法、粒子群算法、灰狼優化算法等。

3.1蟻群優化算法

意大利學者Colorni等人最早于20世紀90年代提出了蟻群算法（ant colony algorithm），該算法通過模擬自然界中螞蟻群體尋找路徑的行為而提出。螞蟻利用一種被稱為信息素的東西進行交流，所有螞蟻在尋找路徑的過程中會在自己行走過的路徑中不斷釋放信息素，并感知其它螞蟻留下的信息素濃度，經過多輪迭代后確定信息素濃度最強的路徑即為最短路徑。各路徑上的信息素濃度為：

蟻群算法利用信息素進行交流的方式實質上是一種正反饋機制，即可通過正反饋機制的調整，對較優解起到增強的作用，使算法向著最優解演變;同時蟻群算法具有較強的魯棒性，可以應用于很多領域;同時蟻群算法具有并行性，能夠實現全局收斂。但同時蟻群算法也具有前期收斂速度慢等缺點，還需在求解相關實際問題中不斷改進。

3.2粒子群算法

粒子群算法（particle swarm optimization）是一種基于群體的隨機優化算法，最早是由Kennedy等在1995年提出的，它是模擬鳥類覓食過程來尋求最優解的算法。在算法中，每個優化問題的解都是搜索空間中的一只被稱為粒子的鳥，所有粒子都對應一個目標公式的值，依據較優目標公式值會得出每個粒子的飛行方向和距離，這兩個數值由粒子本身個體極值和全局極值來確定，具體進化的速度和位置的求解方式如下：

粒子群算法的特點是既保持了算法結構簡單的特性又可以做到運輸中收斂速度快的較高運算性能，且魯棒性、并行性較好，無論全局還是局部的尋優能力都較強，缺點是容易早熟，但在求解優化問題時依然具有很好的求解能力。

3.3灰狼優化算法

灰狼優化算法（grey optimization algorithm）是S Mirjalili等人于2014年時提出來的一種群智能優化算法，該算法模擬了自然界灰狼種群領到層級和捕食機制提出來的。灰狼種群中由統治階級alpha級狼統治，狼群在其命令下，由beta等級的狼協助其進行決策活動，delta等級的狼執行前兩類狼的決策，具體求解公式如下：

灰狼優化算法在求解多維、多峰的連續函數時，與其它算法相比具有較好的收斂速度和魯棒性，但是在離散應用方面發展較慢，還需更多研究開發相關算法。

參考文獻

[1] Lv Long，Hu Haiyang，Li Zhongjin.Optimizing task allocation in workflow system based on ant colony optimization[J]. Computer Integrated Manufacturing Systems，2018，24（07）：1723-1735.

[2] 董海霞，鄒杰.基于AMPSO算法的無人機任務分配問題研究[J].電光與控制，2018（01）.

[3] 魏政磊，趙輝，黃漢橋等.基于SAGWO算法的UCAVs動態協同任務分配[J].北京航空航天大學學報，2018（01）.

[4] 于連伯.蟻群算法的研究[J].江蘇科技信息，2010（09）.

[5] 鄧偉林，胡桂武.粒子群算法研究與展望[J].現代計算機，2006（11）.

[6] Seyedali，M.&M.M.Seyed&L.Andrew.Grey wolf optimizer[J].Advances in Engineering Software，2014（69）：46-61.