求解保障任務(wù)分配問題的綜述

朱俊明 何茂森 林沐霖

摘 要 本文首先對保障任務(wù)分配問題的基本概念進(jìn)行了闡述，分析了今年來求解任務(wù)分配問題的數(shù)學(xué)方法及研究現(xiàn)狀，最后總結(jié)了現(xiàn)行有效的群智能優(yōu)化算法并進(jìn)行了內(nèi)容闡述。

關(guān)鍵詞 任務(wù)分配 群智能算法 保障問題

中圖分類號：TN925文獻(xiàn)標(biāo)識碼：A

1任務(wù)分配問題概述

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

2任務(wù)分配問題的研究現(xiàn)狀

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

3任務(wù)分配問題的求解方法

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

3.1蟻群優(yōu)化算法

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

蟻群算法利用信息素進(jìn)行交流的方式實(shí)質(zhì)上是一種正反饋機(jī)制，即可通過正反饋機(jī)制的調(diào)整，對較優(yōu)解起到增強(qiáng)的作用，使算法向著最優(yōu)解演變;同時蟻群算法具有較強(qiáng)的魯棒性，可以應(yīng)用于很多領(lǐng)域;同時蟻群算法具有并行性，能夠?qū)崿F(xiàn)全局收斂。但同時蟻群算法也具有前期收斂速度慢等缺點(diǎn)，還需在求解相關(guān)實(shí)際問題中不斷改進(jìn)。

3.2粒子群算法

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

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

3.3灰狼優(yōu)化算法

灰狼優(yōu)化算法（grey optimization algorithm）是S Mirjalili等人于2014年時提出來的一種群智能優(yōu)化算法，該算法模擬了自然界灰狼種群領(lǐng)到層級和捕食機(jī)制提出來的?；依欠N群中由統(tǒng)治階級alpha級狼統(tǒng)治，狼群在其命令下，由beta等級的狼協(xié)助其進(jìn)行決策活動，delta等級的狼執(zhí)行前兩類狼的決策，具體求解公式如下：

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

參考文獻(xiàn)

[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ī)任務(wù)分配問題研究[J].電光與控制，2018（01）.

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

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

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

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