魏得路，張雪松，胡 明

(1.電子科技大學(xué)，四川 成都 611731； 2.中國(guó)電子科學(xué)研究院，北京 100041)

0 引 言

艦載航空兵作為航母編隊(duì)攻防作戰(zhàn)的核心力量，預(yù)警機(jī)、戰(zhàn)斗機(jī)、電子戰(zhàn)飛機(jī)、反潛機(jī)、無(wú)人機(jī)、勤務(wù)機(jī)等多機(jī)種聯(lián)合執(zhí)行作戰(zhàn)任務(wù)是航母編隊(duì)的基本作戰(zhàn)樣式。要使得聯(lián)合作戰(zhàn)發(fā)揮最大效能，必須合理的分配任務(wù)，使得各作戰(zhàn)平臺(tái)在合適的地點(diǎn)和時(shí)間去執(zhí)行合適的任務(wù)。任務(wù)分配問(wèn)題的模型主要有車輛路徑問(wèn)題模型、動(dòng)態(tài)網(wǎng)絡(luò)流優(yōu)化模型、多旅行商問(wèn)題模型等，它是一個(gè)NP完全問(wèn)題。對(duì)于此類問(wèn)題，精確算法大多難以求解，因此多采用近似算法，如貪心法和啟發(fā)式算法等。其中貪心算法主要有動(dòng)態(tài)列表規(guī)劃(Dynamic List Scheduling，DLS)算法[1-2]，以及基于DLS改進(jìn)的MPDLS算法等。文獻(xiàn)[3]將布谷鳥搜索算法與MPDLS算法結(jié)合，以任務(wù)完成時(shí)間以及資源利用率為優(yōu)化目標(biāo)求解了任務(wù)的分配。啟發(fā)式算法有禁忌搜索、模擬退火等搜索算法[4]，以及遺傳算法、蟻群算法、粒子群算法等群體智能算法。文獻(xiàn)[5]將導(dǎo)彈群對(duì)多目標(biāo)的問(wèn)題建模，采用遺傳算法求解。文獻(xiàn)[6]將多無(wú)人機(jī)任務(wù)分配問(wèn)題建模為多旅行商問(wèn)題模型，并采用蟻群算法求解。

然而，當(dāng)前對(duì)于任務(wù)分配的研究，還存在幾個(gè)問(wèn)題。首先，大多數(shù)研究忽略了作戰(zhàn)半徑的影響。在作戰(zhàn)半徑與戰(zhàn)場(chǎng)尺度相比較小情況下，作戰(zhàn)半徑對(duì)距離的影響不大，但對(duì)于預(yù)警機(jī)及某些無(wú)人偵察機(jī)來(lái)說(shuō)，其作戰(zhàn)半徑較大，不可忽略。第二個(gè)問(wèn)題是大多數(shù)研究沒有考慮多機(jī)種聯(lián)合任務(wù)的分配，對(duì)聯(lián)合任務(wù)分配沒有提出有效的解決方案[7]。針對(duì)以上兩點(diǎn)，本文將分配問(wèn)題建模為復(fù)雜的多旅行商問(wèn)題，以圖中邊的組合作為分配問(wèn)題的解，改進(jìn)蟻群算法為多信息素蟻群算法，通過(guò)蟻群的學(xué)習(xí)對(duì)圖進(jìn)行剪枝搜索，為任務(wù)分配問(wèn)題提供了一個(gè)有效的解決方案。

1 聯(lián)合任務(wù)分配問(wèn)題模型

1.1 基本描述

飛行平臺(tái)與聯(lián)合任務(wù)的描述為：

(1)聯(lián)合任務(wù)是作戰(zhàn)的目標(biāo)，其相應(yīng)的屬性有：任務(wù)Ti,i=1,2,3…N的位置坐標(biāo)Positioni=(xi,yi)；任務(wù)Ti需要的執(zhí)行時(shí)間tdi；任務(wù)Ti需要的平臺(tái)的類型和數(shù)量矢量bi=(bi1,bi2,bi3,…bim)，其中bim表示任務(wù)Ti需要的類型為m的平臺(tái)的數(shù)量。

(2)飛行平臺(tái)是任務(wù)的執(zhí)行者，它的屬性有：平臺(tái)Pi,i=1,2,3…M的類型tpi；平臺(tái)Pi的位置Positioni=(xi,yi)；平臺(tái)Pi的移動(dòng)速度vi；平臺(tái)的作戰(zhàn)半徑Ri。

任務(wù)的執(zhí)行矩陣代表著平臺(tái)與任務(wù)的匹配關(guān)系。對(duì)于m個(gè)平臺(tái)，n個(gè)任務(wù)的任務(wù)分配問(wèn)題，執(zhí)行矩陣是一個(gè)mn的矩陣。如式(1)中矩陣E表示一個(gè)執(zhí)行矩陣，其中xij=1代表平臺(tái)Pi參與執(zhí)行任務(wù)Tj，否則代表平臺(tái)Pi不參與執(zhí)行任務(wù)Tj。根據(jù)該矩陣的第i行可得到平臺(tái)Pi參與的所有任務(wù)；相應(yīng)的，根據(jù)矩陣第j行，可得到參與Tj的所有平臺(tái)。

(1)

1.2 平臺(tái)的路線模型

聯(lián)合任務(wù)分配中，存在平臺(tái)參與多個(gè)任務(wù)的情況，這就要求計(jì)算出平臺(tái)抵達(dá)每個(gè)任務(wù)的時(shí)間。各類型艦載機(jī)作戰(zhàn)半徑各不相同，轟炸機(jī)、戰(zhàn)斗機(jī)等需要在任務(wù)點(diǎn)幾公里內(nèi)進(jìn)行作戰(zhàn)，而預(yù)警機(jī)偵察機(jī)等甚至可以在一百甚至幾百公里外參戰(zhàn)。在估算平臺(tái)執(zhí)行任務(wù)的航程時(shí)，需要考慮到平臺(tái)的作戰(zhàn)半徑。目前大多數(shù)對(duì)于任務(wù)分配的研究都忽略了作戰(zhàn)半徑的影響，直接使用平臺(tái)和任務(wù)之間的距離當(dāng)作平臺(tái)參與任務(wù)需要飛行的距離，導(dǎo)致估算時(shí)與實(shí)際情況相差較多。

考慮到作戰(zhàn)半徑對(duì)平臺(tái)執(zhí)行任務(wù)的影響，以及以下兩個(gè)因素：(1)平臺(tái)最快到達(dá)可執(zhí)行任務(wù)點(diǎn)；(2)充分利用平臺(tái)在任務(wù)區(qū)內(nèi)等待其他協(xié)作平臺(tái)到位的空閑時(shí)間。本文提出了一種新的平臺(tái)移動(dòng)方式，如圖1，平臺(tái)當(dāng)前將要執(zhí)行的任務(wù)為任務(wù)1，平臺(tái)的接下來(lái)一個(gè)任務(wù)為任務(wù)2，并且定義平臺(tái)飛行中兩個(gè)關(guān)鍵位置：(1)任務(wù)進(jìn)入點(diǎn)，即平臺(tái)進(jìn)入任務(wù)區(qū)的位置；(2)任務(wù)執(zhí)行點(diǎn)即平臺(tái)執(zhí)行任務(wù)的位置。則平臺(tái)的移動(dòng)方式為：

(1)對(duì)于任務(wù)1，平臺(tái)的移動(dòng)方式為從當(dāng)前位置到任務(wù)位置直線移動(dòng)，保證最快的時(shí)間到達(dá)任務(wù)區(qū)，直到平臺(tái)與任務(wù)之間距離小于或等于平臺(tái)作戰(zhàn)半徑，這時(shí)平臺(tái)所處位置為任務(wù)進(jìn)入點(diǎn)(圖1(a)中a點(diǎn))；

(2)此時(shí)平臺(tái)已經(jīng)可以開始執(zhí)行任務(wù)，但可能處于等待其他平臺(tái)就位狀態(tài)中，此時(shí)平臺(tái)移動(dòng)目標(biāo)為當(dāng)前任務(wù)區(qū)中離任務(wù)2最近點(diǎn)(圖1(b)中b點(diǎn))；

(3)移動(dòng)過(guò)程中，若其他參與平臺(tái)已就位，則任務(wù)1開始執(zhí)行，這時(shí)的位置為平臺(tái)的任務(wù)1執(zhí)行點(diǎn)(圖1(c)中c點(diǎn))；

(4)任務(wù)1執(zhí)行完畢后，平臺(tái)開始向下一個(gè)任務(wù)移動(dòng)，目標(biāo)為任務(wù)2的任務(wù)區(qū)進(jìn)入點(diǎn)(圖1(c)中d點(diǎn))，移動(dòng)方式與任務(wù)1移動(dòng)方式相同。

圖1 平臺(tái)移動(dòng)方式

通過(guò)這種方式，充分利用了平臺(tái)等待的時(shí)間，將平臺(tái)參與的所有任務(wù)的路線以迭代的方式計(jì)算出來(lái)，所有平臺(tái)共同迭代可以求得所有任務(wù)的開始執(zhí)行時(shí)間以及完成所有任務(wù)的時(shí)間，為后續(xù)航線規(guī)劃提供更精確的支持。

下面分析這種航程估算方式與傳統(tǒng)方式的差別。如圖2所示，兩種估算方式的對(duì)應(yīng)的航程分別為a-c-d和a-O1-e，其中c的位置為線段ab上一點(diǎn)。若平臺(tái)進(jìn)入任務(wù)1的路線與任務(wù)2的夾角為θ，平臺(tái)作戰(zhàn)半徑為R，任務(wù)之間距離為d，當(dāng)c點(diǎn)位于a和b時(shí)，兩段航程之間的距離差的最大值和最小值分別如公式(2)和(3)所示。

(2)

(3)

隨著夾角θ在(0-180)之間不斷增加，航程距離差逐漸減少。θ為180時(shí)，航程差為0，而θ為0時(shí)，航程差為最大值2R。

隨著作戰(zhàn)半徑的增加，航程差逐漸增加。公式(2)和(3)證明，隨著作戰(zhàn)半徑的增加，傳統(tǒng)的忽略作戰(zhàn)半徑的航程估算誤差值越來(lái)越大。

圖2 航程比較示意圖

1.3 任務(wù)分配問(wèn)題數(shù)學(xué)模型

聯(lián)合任務(wù)分配的問(wèn)題可以描述為：對(duì)于若干平臺(tái)和任務(wù)的場(chǎng)景，找到或調(diào)整任務(wù)的分配順序和任務(wù)的執(zhí)行矩陣，在滿足平臺(tái)的參數(shù)、任務(wù)的要求等約束條件下，達(dá)到最優(yōu)化目標(biāo)。本文重點(diǎn)研究平臺(tái)在空間上的移動(dòng)與協(xié)作，以最小化任務(wù)完成時(shí)間為目標(biāo)，將聯(lián)合任務(wù)分配問(wèn)題的約束條件和目標(biāo)函數(shù)定義為：

約束條件：

(1)任務(wù)完成約束。對(duì)于每一個(gè)任務(wù)，根據(jù)任務(wù)需求的平臺(tái)類型和相應(yīng)的數(shù)量，選擇參與該任務(wù)的平臺(tái)，選中的數(shù)量不少于任務(wù)需求。

(2)平臺(tái)可達(dá)性約束。平臺(tái)在執(zhí)行任務(wù)時(shí)，要在任務(wù)執(zhí)行時(shí)間之前抵達(dá)任務(wù)區(qū)。

目標(biāo)函數(shù)：完成所有任務(wù)花費(fèi)的時(shí)間最短。

本文以MTSP模型為基礎(chǔ)，將平臺(tái)和任務(wù)看作旅行商和城市，將任務(wù)之間的遷移代價(jià)看作城市之間的距離，將任務(wù)的分配看作城市的訪問(wèn)，將聯(lián)合任務(wù)預(yù)分配問(wèn)題描述為協(xié)作多旅行商問(wèn)題(Collaborative Multiple Salesman Problem，CMTSP)模型：存在若干旅行商和一定個(gè)數(shù)的城市，其中旅行商分為幾個(gè)類型，每個(gè)城市需要一定個(gè)數(shù)的各種類型的旅行商一起表演一段時(shí)間，尋找旅行商在所有城市表演完成的最短時(shí)間以及訪問(wèn)方案。將該問(wèn)題表示成圖問(wèn)題，旅行商對(duì)應(yīng)圖中的節(jié)點(diǎn)，城市之間的路線對(duì)應(yīng)圖中的邊，問(wèn)題的解為圖中某些邊的組合，這樣就把聯(lián)合任務(wù)分配問(wèn)題表示成了一個(gè)圖問(wèn)題。

其數(shù)學(xué)描述如公式(4)所示。其中(t1,t2,…tn)代表各個(gè)任務(wù)的完成時(shí)間，bij和numij分別代表第i個(gè)任務(wù)需要的第j類飛機(jī)數(shù)量和參與該任務(wù)的數(shù)量，公式約束條件中第一部分表示對(duì)于每個(gè)任務(wù)，參與執(zhí)行任務(wù)的平臺(tái)數(shù)量不少于任務(wù)需求的數(shù)量。公式中frt(i,j)表示平臺(tái)Pi到達(dá)j任務(wù)的時(shí)間，由任務(wù)之間的航程與平臺(tái)速度相除得到，其中航程按照本章第四小節(jié)的方法來(lái)進(jìn)行計(jì)算。task(m,k)表示平臺(tái)Pm任務(wù)列表中執(zhí)行的第k個(gè)任務(wù)的編號(hào)，tdj為編號(hào)j的任務(wù)需要的執(zhí)行時(shí)間，則tj-tdj為該任務(wù)的開始執(zhí)行時(shí)間。約束條件第二部分表示，對(duì)于每個(gè)平臺(tái)，平臺(tái)抵達(dá)須執(zhí)行任務(wù)的時(shí)間不晚于任務(wù)開始時(shí)間。

min max(t1,t2,…tn)

(4)

2 多信息素蟻群算法

聯(lián)合任務(wù)分配問(wèn)題是NP問(wèn)題，在規(guī)模較大時(shí)難以用精確算法求解。某些貪心算法如合同網(wǎng)算法中并不能找到完美的任務(wù)排序與平臺(tái)選擇策略，且沒有對(duì)結(jié)果的反饋以學(xué)習(xí)更優(yōu)的選擇策略。啟發(fā)式算法中，遺傳算法并不能很好的利用一些現(xiàn)有規(guī)則，而蟻群算法天然的帶有啟發(fā)函數(shù)這個(gè)概念，可以更好地利用經(jīng)驗(yàn)知識(shí)，同時(shí)使用信息素修補(bǔ)經(jīng)驗(yàn)知識(shí)的不足。因此，本文以合同網(wǎng)的思路改進(jìn)蟻群算法，對(duì)聯(lián)合任務(wù)分配問(wèn)題進(jìn)行求解，如圖3所示。其中任務(wù)排序策略和平臺(tái)選擇策略都使用啟發(fā)函數(shù)和信息素結(jié)合的方式，終止條件定義為到達(dá)最大迭代次數(shù)或者算法已經(jīng)收斂，反饋通過(guò)對(duì)信息素進(jìn)行調(diào)整來(lái)實(shí)現(xiàn)。

圖3 問(wèn)題求解思路圖

2.1 基本蟻群算法

M.Dorigo根據(jù)螞蟻在尋找食物中的行為，發(fā)現(xiàn)螞蟻可以在協(xié)作的情況下發(fā)現(xiàn)覓食的較短路線。經(jīng)過(guò)研究發(fā)現(xiàn)，螞蟻在移動(dòng)的過(guò)程中會(huì)釋放一種稱為信息素(pheromone)的物質(zhì)。蟻群之間通過(guò)信息素進(jìn)行溝通，信息素越多的地方螞蟻也會(huì)傾向于向那個(gè)方向移動(dòng)。若在螞蟻與食物之間有幾條路線可以選擇，剛開始的時(shí)候，所有路上都沒有信息素，螞蟻會(huì)隨機(jī)移動(dòng)。而隨著螞蟻的不斷移動(dòng)，較短路線上走過(guò)的螞蟻數(shù)量較多，也會(huì)留下更多的信息素吸引其他螞蟻過(guò)去，使得最短路線上的螞蟻數(shù)量越來(lái)越多。

圖4 蟻群尋路示意圖

如圖4所示，在螞蟻搜尋食物過(guò)程中，沒有信息素的時(shí)候螞蟻隨機(jī)選擇路線，當(dāng)某條路徑較短，螞蟻在此條路徑上來(lái)回移動(dòng)的次數(shù)較多，因此該條路徑上留下的信息素會(huì)逐漸增加，而信息素的積累也會(huì)誘使螞蟻選擇該條路徑，這樣就形成了一個(gè)正反饋。最終，大多數(shù)螞蟻選擇的哪條路線很可能就是覓食的最短路線。當(dāng)然，信息素不是一成不變的，它還有揮發(fā)性。螞蟻并不完全根據(jù)信息素的含量來(lái)選擇路線。大多數(shù)的螞蟻傾向于選擇信息素含量高的路線，也有少數(shù)螞蟻會(huì)隨機(jī)選擇路線，若有螞蟻找到了更短的路線，則更短路線上信息素會(huì)逐漸增加，原路線上的信息素逐漸揮發(fā)，新的更短路線會(huì)成為大多數(shù)螞蟻的選擇。

(5)

某些無(wú)效路徑上的信息素需要進(jìn)行調(diào)整，以防止其吸引其他螞蟻。若在t+n時(shí)刻所有螞蟻移動(dòng)完成，則t+n時(shí)刻對(duì)路徑Lij上的信息量按公式(6)進(jìn)行調(diào)整。

(6)

公式(6)中p表示信息素的揮發(fā)因子，表示信息素在該次更新中先衰減為原來(lái)的1-p倍。在算法中，p的值很重要，會(huì)影響到算法的收斂速度。若p的值過(guò)大，則信息素難以積累，算法隨機(jī)性過(guò)大，算法容易波動(dòng)，難以收斂；若p的值過(guò)小，則算法收斂速度太快，容易收斂到局部最優(yōu)解，難以進(jìn)行大范圍的搜索。公式(6)中的δij(k,t)表示編號(hào)k的螞蟻在i城市與j城市之間移動(dòng)增加的信息素。

算法中螞蟻不斷地移動(dòng)，最終信息素收斂到目標(biāo)路線上，也就對(duì)原問(wèn)題做出了求解。

2.2 算法改進(jìn)策略

2.2.1多信息素

多信息素蟻群算法采用城市被訪問(wèn)的時(shí)間作為基礎(chǔ)構(gòu)造啟發(fā)函數(shù)，算法中的螞蟻移動(dòng)由蟻群算法中的單個(gè)螞蟻移動(dòng)變?yōu)橐唤M的多個(gè)螞蟻的共同移動(dòng)，算法中的信息素更新則是各螞蟻更新對(duì)應(yīng)的那一種信息素。

一個(gè)經(jīng)典案例為：飛行平臺(tái)的數(shù)量為m，任務(wù)數(shù)量為n，平臺(tái)類別數(shù)為t，每一個(gè)種類的平臺(tái)個(gè)數(shù)分別為(a1,a2,…at)，Pik表示類別為i的第k個(gè)平臺(tái)，任務(wù)Tj需要的各類型平臺(tái)數(shù)量分別為(bj1,bj2,…bjt)。下面依次案例介紹算法中的啟發(fā)函數(shù)、螞蟻的移動(dòng)以及信息素的更新等。

2.2.2啟發(fā)函數(shù)

啟發(fā)函數(shù)是多信息素蟻群算法中重要的一部分，它作為一種“經(jīng)驗(yàn)知識(shí)”，引導(dǎo)算法進(jìn)化的方向，影響算法的效果。好的啟發(fā)函數(shù)引導(dǎo)算法搜索適當(dāng)?shù)膮^(qū)域，讓算法在更短的時(shí)間內(nèi)獲得較好的效果。蟻群算法求解TSP中，大多使用城市間距離的倒數(shù)作為啟發(fā)函數(shù)，即離當(dāng)前訪問(wèn)城市更近的城市，其啟發(fā)函數(shù)的值越大，在信息素相同的情況下，被訪問(wèn)的概率也越大。在CMTSP中，城市和旅行商之間存在雙向選擇，選擇下一個(gè)城市時(shí)要多個(gè)旅行商共同選擇，選擇去往該城市的旅行商時(shí)也需要一起選擇。也就是說(shuō)，求解CMTSP的多信息素蟻群算法需要有兩個(gè)啟發(fā)函數(shù)，一個(gè)選擇城市，一個(gè)選擇去往該城市的旅行商。

在這里，本文以飛行平臺(tái)可以抵達(dá)任務(wù)區(qū)的時(shí)間為基礎(chǔ)構(gòu)造啟發(fā)函數(shù)。公式(7)中frt(ik,j)表示平臺(tái)Pik到達(dá)任務(wù)Tj任務(wù)區(qū)的時(shí)間，x和y代表相應(yīng)的平臺(tái)或任務(wù)的位置坐標(biāo)，Rik代表平臺(tái)的作戰(zhàn)半徑。公式8中RTij表示類別為i的飛機(jī)可抵達(dá)任務(wù)j的任務(wù)區(qū)的最小時(shí)間，fnmax(k,l)表示序列l(wèi)中第k大的值，bji為任務(wù)Tj需要的類別為i的平臺(tái)的數(shù)量。公式(9)表示任務(wù)Tj可被執(zhí)行的最早時(shí)間的倒數(shù)作為啟發(fā)函數(shù)Q(j)，其中Δ為修正因子，防止時(shí)間為0使得啟發(fā)函數(shù)無(wú)窮大。

(7)

RTij=fnmax(bji,(frt(i1,j),frt(i2,j),…frt(iai,j))

(8)

(9)

因此，任務(wù)選取的啟發(fā)函數(shù)可以描述為：該任務(wù)在當(dāng)前狀態(tài)下可最早被執(zhí)行時(shí)間的倒數(shù)。若任務(wù)可在較短的時(shí)間內(nèi)完成，即平臺(tái)參與該任務(wù)的代價(jià)較低，則該任務(wù)的啟發(fā)值較大，會(huì)更優(yōu)先的被選擇執(zhí)行。

任務(wù)選取平臺(tái)的啟發(fā)函數(shù)也是根據(jù)平臺(tái)抵達(dá)當(dāng)前任務(wù)的時(shí)間得到。若當(dāng)前選中任務(wù)為Tj，則平臺(tái)Pik參與Tj的啟發(fā)函數(shù)Q1(i,k,j)如公式(10)所示，其值為平臺(tái)到達(dá)該任務(wù)區(qū)的時(shí)間的倒數(shù)，Δ為修正因子。

(10)

2.2.3螞蟻移動(dòng)

螞蟻的移動(dòng)是蟻群算法核心的一環(huán)，螞蟻根據(jù)信息素和經(jīng)驗(yàn)知識(shí)的引導(dǎo)移動(dòng)的過(guò)程也是一個(gè)解的組合構(gòu)造過(guò)程，因此這一步驟與問(wèn)題本身性質(zhì)有著緊密的結(jié)合?；鞠伻核惴ㄇ蠼釺SP時(shí)螞蟻的移動(dòng)指單個(gè)螞蟻根據(jù)禁忌表在城市之間移動(dòng)，直到走完所有的城市，構(gòu)造出TSP的一個(gè)解。多信息素蟻群算法中螞蟻的移動(dòng)代表的是一組螞蟻的共同移動(dòng)。對(duì)于m個(gè)旅行商和n個(gè)城市的CMTSP，算法使用m只螞蟻代表m個(gè)旅行商，用螞蟻的移動(dòng)代表旅行商訪問(wèn)城市。螞蟻移動(dòng)的過(guò)程主要步驟為：

Step1：初始化已訪問(wèn)城市列表；

Step2：從未訪問(wèn)的城市選擇一個(gè)作為下一個(gè)將要訪問(wèn)的目標(biāo)；

Step3：根據(jù)城市的需要，選擇幾個(gè)螞蟻訪問(wèn)該選中的城市。若找不到滿足條件的螞蟻，則螞蟻移動(dòng)結(jié)束，且沒有獲得一個(gè)可行解；

Step4：確定這幾只螞蟻共同的訪問(wèn)時(shí)間，更新這幾只螞蟻的狀態(tài)；

Step5：更新城市狀態(tài)為已訪問(wèn)；

Step6：若所有城市訪問(wèn)已完成，則螞蟻的移動(dòng)結(jié)束，獲得一個(gè)移動(dòng)方式，否則轉(zhuǎn)Step2；

(11)

(12)

式(11)中綜合m種信息素，依據(jù)信息素對(duì)應(yīng)的平臺(tái)的類別，對(duì)信息素分類處理。式(12)中α、β分別為信息素和啟發(fā)函數(shù)重要性因子，α的值越大則信息素的影響越大，算法的搜索空間更大；β值越大，表示啟發(fā)函數(shù)的影響越大，算法的搜索更精細(xì)致。

若編號(hào)k的城市被選中，接下來(lái)要選擇去往k的螞蟻。Step3根據(jù)城市k需要的旅行商的種類，同樣采取賭輪盤的方式，從每個(gè)種類的螞蟻中抽取該種類所需數(shù)量的螞蟻去往該城市。以第i類為例，該種類共有ai個(gè)螞蟻，當(dāng)前城市k需要第i類螞蟻數(shù)量為bki，則賭輪盤目的為從ai個(gè)螞蟻中抽取bki個(gè)，已經(jīng)被選中的螞蟻會(huì)從allowed表中移除，保證不會(huì)重復(fù)抽取。抽取的依據(jù)也是信息素含量和啟發(fā)函數(shù)，第i類編號(hào)x的螞蟻每輪被選中的概率如公式(13)所示。

(13)

抽取完成后，綜合所有螞蟻的抵達(dá)時(shí)間，確定所有選中螞蟻訪問(wèn)的最終時(shí)間，更新選中螞蟻的狀態(tài)，繼續(xù)選擇下一個(gè)城市直到所有城市訪問(wèn)完畢。

2.2.4信息素更新

信息素是蟻群算法中螞蟻對(duì)問(wèn)題信息不停的試探中學(xué)習(xí)到的知識(shí)，同時(shí)指引著蟻群的動(dòng)作，影響著算法的搜索方向和收斂結(jié)果。為了防止信息素殘留在無(wú)效路徑，對(duì)當(dāng)前的信息素進(jìn)行揮發(fā)操作，即當(dāng)前所有信息素按一定比例減少。之后，根據(jù)各組螞蟻解得質(zhì)量情況，計(jì)算各組螞蟻的適應(yīng)度，進(jìn)行信息素的增加。

在多信息素蟻群算法中，為了精確的描述問(wèn)題，增加了多種信息素，信息素組合的種類更多，算法更容易進(jìn)入局部最優(yōu)解，因此采用少數(shù)精英更新和更新次數(shù)控制兩種策略，其中將當(dāng)前全局最優(yōu)解作為精英的一個(gè)。

少數(shù)精英更新策略指只有種群中適應(yīng)度較高的一部分參與信息素的更新，精英不僅包含最優(yōu)解，還包含次優(yōu)解。這種策略與上述的最優(yōu)解更新類似，與最優(yōu)解更新相比，既保留了較好個(gè)體的信息，又淘汰了較差的個(gè)體，兼顧了搜索速度與效果。

更新次數(shù)控制策略指每段信息素在每次迭代中可以更新的次數(shù)不超過(guò)某個(gè)值。這個(gè)策略旨在減緩算法收斂速度，增加算法的搜索空間。同時(shí)可更新次數(shù)采取變化的數(shù)值，算法初期為了全局搜索并避免過(guò)早收斂，將該值設(shè)置的較小；算法后期增加該值進(jìn)行局部空間的搜索。

每組螞蟻更新信息素增加量根據(jù)該組螞蟻的適應(yīng)度來(lái)計(jì)算。本文中使用種群中所有組螞蟻游歷完所有城市后的時(shí)間計(jì)算各組螞蟻應(yīng)更新的信息素含量，若各組螞蟻游歷時(shí)間最大值為tmax，最小值為tmin，若某組螞蟻遍歷的時(shí)間為t，則該組增加的信息素如公式(14)所示。

(14)

式(14)中μ為每次更新最多的信息量，w為權(quán)重參數(shù)，值越大則該組螞蟻更新的信息素與最大值差距越大，該組螞蟻的路線越容易被淘汰。每組螞蟻增加信息素時(shí)，只增加本組內(nèi)螞蟻經(jīng)過(guò)的路線的信息素。

信息素更新的步驟主要有：

Step1：初始化所有種類信息素每段上的已更新次數(shù)；

Step2：計(jì)算各組螞蟻的適應(yīng)度和信息素更新量；

Step3：場(chǎng)上信息素按照信息素?fù)]發(fā)速率進(jìn)行衰減；

Step4：將所有組螞蟻的信息素更新量進(jìn)行排序，選取前v組作為精英；

Step5：選中的v組螞蟻按照更新量依次增加信息素，若某種信息素在某段更新次數(shù)達(dá)到最大更新次數(shù)則跳過(guò)這段的信息素的更新。

2.3 算法步驟

算法流程圖如圖5所示，算法的整體步驟為：

圖5 多信息素蟻群算法流程圖

Step1：算法參數(shù)初始化，包括蟻群組數(shù)量、最大迭代次數(shù)、信息素?fù)]發(fā)比例、信息素最大更新次數(shù)等；

Step2：初始化信息素分布，初始狀態(tài)時(shí)設(shè)置所有信息素為同一固定值。

Step3：進(jìn)行各組螞蟻的移動(dòng)；

Step4：進(jìn)行信息素的更新，包括信息素的衰減和增加；

Step5：若滿足停止條件如達(dá)到最大迭代次數(shù)則算法停止輸出算法結(jié)果；否則轉(zhuǎn)Step3。

2.4 算法分析

多信息素蟻群算法中的螞蟻和旅行商的互相選擇的思路來(lái)自于合同網(wǎng)協(xié)議的合同簽約流程，其選擇的策略是在啟發(fā)函數(shù)的基礎(chǔ)上通過(guò)信息素含量進(jìn)行調(diào)整，同時(shí)信息素的含量在不斷學(xué)習(xí)中進(jìn)行修正。由于問(wèn)題中飛行平臺(tái)在任務(wù)之間遷移時(shí)有一定的馬爾科夫性質(zhì)，即平臺(tái)在任務(wù)之間的遷移代價(jià)與前置任務(wù)的關(guān)系較小，因此只保存任務(wù)之間遷移的信息素，減少了需要保存的信息。

原問(wèn)題為NP問(wèn)題，其復(fù)雜度為指數(shù)級(jí)。多信息素蟻群算法中，若旅行商個(gè)數(shù)為n，種群個(gè)體組數(shù)2n，每組螞蟻個(gè)數(shù)m，迭代次數(shù)為c，螞蟻移動(dòng)中單次旅行商的選擇復(fù)雜度為O(mn)，平臺(tái)的選擇為O(m)，所以螞蟻移動(dòng)完成的總復(fù)雜度為 O((mn+m)n)；信息素更新的復(fù)雜度為O(mn^2)。因此算法的總復(fù)雜度為O(cmn^3)，為多項(xiàng)式復(fù)雜度。在平臺(tái)數(shù)量固定的情況下，隨著任務(wù)數(shù)量的增加，算法單次迭代時(shí)間與任務(wù)數(shù)量的三次方呈線性關(guān)系。算法中的各組螞蟻可以并行移動(dòng)，信息素的更新也可以并行計(jì)算，因此算法可以通過(guò)并行計(jì)算，使得執(zhí)行時(shí)間縮短。

3 仿真結(jié)果及分析

3.1 算法仿真結(jié)果

本文的仿真環(huán)境為i7+Windows下的Matlab，蟻群算法參數(shù)設(shè)置為：信息素?fù)]發(fā)率0.2，種群個(gè)數(shù)為任務(wù)總數(shù)的兩倍，迭代次數(shù)為100，啟發(fā)因子為0.5。首先對(duì)一個(gè)簡(jiǎn)單實(shí)例進(jìn)行仿真驗(yàn)證。該案例中，戰(zhàn)場(chǎng)為1000 km×1000 km的矩形空間，共有8架飛行平臺(tái)，分為三種類型，各類型的的數(shù)量分別為2，2，4，各平臺(tái)的作戰(zhàn)半徑、移動(dòng)速度、初始位置如表1所示；須執(zhí)行任務(wù)共有8個(gè)，各任務(wù)的位置以及需求如表2所示。平臺(tái)與任務(wù)的初始分布如圖6所示。

表1 平臺(tái)參數(shù)表

表2 任務(wù)參數(shù)表

圖6 平臺(tái)任務(wù)初始分布圖

算法求解的結(jié)果如下：表3代表每個(gè)任務(wù)開始執(zhí)行的時(shí)間；表4代表每個(gè)平臺(tái)執(zhí)行的任務(wù)列表，包括執(zhí)行的任務(wù)編號(hào)和執(zhí)行位置；圖7中以平臺(tái)為起點(diǎn)的曲線是根據(jù)平臺(tái)路線模型得到的各個(gè)平臺(tái)的飛行路線，這里的路線與表4的任務(wù)列表一一對(duì)應(yīng)。對(duì)比表1和表2的參數(shù)，可以看到這個(gè)方案可以滿足所有任務(wù)完成這個(gè)條件，且所有平臺(tái)的執(zhí)行任務(wù)點(diǎn)都在任務(wù)區(qū)內(nèi)。

表3 任務(wù)執(zhí)行時(shí)間表

表4 各平臺(tái)執(zhí)行任務(wù)順序

續(xù)表4

圖7 平臺(tái)估算航程圖

算法收斂曲線如圖8所示。對(duì)于此簡(jiǎn)單案例，算法最優(yōu)值在迭代12次達(dá)到最低點(diǎn)，算法平均值也在迭代60次左右到達(dá)最低點(diǎn)且趨于平穩(wěn)，算法收斂的最優(yōu)解為3.04 h，是最后一個(gè)任務(wù)完成的時(shí)間。圖中可以看到，算法具有隨機(jī)尋優(yōu)的特性，在算法初期算法最優(yōu)值和平均值都有很大波動(dòng)，代表算法在大范圍的搜索；算法后期算法最優(yōu)值和平均值波動(dòng)較小，算法在進(jìn)行局部的搜索，在小范圍繼續(xù)尋找更優(yōu)解。

圖8 算法結(jié)果收斂圖

圖9展示了算法迭代結(jié)束后，平臺(tái)1對(duì)應(yīng)的信息素的分布圖。圖中的九個(gè)端點(diǎn)中有八個(gè)代表著任務(wù)的位置，最后一個(gè)端點(diǎn)代表平臺(tái)1的初始位置。圖中線的粗細(xì)代表信息素的含量大小，線越粗代表這兩個(gè)端點(diǎn)之間的信息素越多，也就代表平臺(tái)更傾向于連續(xù)執(zhí)行這兩個(gè)端點(diǎn)代表的任務(wù)。由于任務(wù)2和任務(wù)3不需要類型1的平臺(tái)參與，因此圖中連接這兩個(gè)任務(wù)的路線上的信息素很少。由圖可知，信息素已經(jīng)積累到了幾條主要的線路上，幾條線路可以組成由平臺(tái)位置為起點(diǎn)的一條路徑，該圖中路徑為起始位置-1-5-8-7-6，與平臺(tái)1的任務(wù)列表1587相對(duì)應(yīng)。方案中平臺(tái)1并沒有參與執(zhí)行任務(wù)6，是因?yàn)槠脚_(tái)2也可執(zhí)行任務(wù)6，且兩者執(zhí)行效果相近，因而相持不下，并沒有完全的淘汰掉其中一種，保留了兩種可能性。

圖9 平臺(tái)1對(duì)應(yīng)的信息素分布圖

3.2 對(duì)比試驗(yàn)

對(duì)上述案例，同時(shí)運(yùn)行多信息素蟻群算法與遺傳算法，兩種算法的最優(yōu)解變化曲線如圖10(a)所示。由圖可知，兩種算法最終求解的結(jié)果相差不大，但多信息素蟻群算法的收斂速度稍快一些，且有多次的下降，而遺傳算法的下降點(diǎn)較少。因此，蟻群算法是在啟發(fā)函數(shù)的指引下逐漸進(jìn)化的，而遺傳算法是更暴力的隨機(jī)尋優(yōu)，多次迭代才會(huì)找到更優(yōu)解，且更優(yōu)解可能效果變化會(huì)更大。

圖10 算法收斂曲線對(duì)比圖

下面對(duì)另一個(gè)復(fù)雜的案例進(jìn)行算法對(duì)比，該復(fù)雜案例中任務(wù)數(shù)量為20，參與平臺(tái)數(shù)目為10，其任務(wù)屬性和平臺(tái)屬性由隨機(jī)產(chǎn)生。兩種算法運(yùn)行結(jié)果對(duì)比如圖10(b)所示。圖中，最終兩種算法求解的結(jié)果分別為6.21 h和6.50 h。多信息素蟻群算法在初始狀態(tài)、收斂速度和收斂結(jié)果上都優(yōu)于遺傳算法。因此，在解空間很大的時(shí)候，遺傳算法的隨機(jī)產(chǎn)生的初始狀態(tài)較差，且需要較長(zhǎng)的時(shí)間搜索找到收斂的方向，而多信息素蟻群算法在啟發(fā)函數(shù)的引導(dǎo)下，初始狀態(tài)的結(jié)果就優(yōu)于遺傳算法，且最優(yōu)解下降速度較快，最終也收斂到了更優(yōu)的解上。

為了測(cè)試兩種算法在任務(wù)數(shù)量與平臺(tái)數(shù)量比例不同時(shí)的表現(xiàn)，在設(shè)定平臺(tái)數(shù)量為8，任務(wù)數(shù)量為8-31之間，隨機(jī)產(chǎn)生多組初始數(shù)據(jù)，算法運(yùn)行后的平均結(jié)果如圖11所示。在平臺(tái)數(shù)量為8的時(shí)候，當(dāng)任務(wù)數(shù)量小于12的時(shí)候，遺傳算法的綜合效果略好于多信息素蟻群算法，當(dāng)任務(wù)數(shù)量大于或者等于12的時(shí)候，多信息素蟻群算法的效果超過(guò)遺傳算法。任務(wù)數(shù)量在8-31范圍時(shí)，多信息素蟻群算法效果平均優(yōu)于遺傳算法5%，分配結(jié)果任務(wù)完成平均時(shí)間差為0.37 h，兩者相差最多的時(shí)候達(dá)到20%，時(shí)間差達(dá)到1.65 h。隨著任務(wù)數(shù)量的增加，多信息素蟻群算法的效果與遺傳算法相差越來(lái)越大。在求解TSP問(wèn)題時(shí)，蟻群算法的效果優(yōu)于遺傳算法。而隨著任務(wù)數(shù)量的增加，聯(lián)合任務(wù)分配問(wèn)題越來(lái)越趨近于TSP問(wèn)題，因而由蟻群算法為基礎(chǔ)的多信息素蟻群算法取得到更好的結(jié)果。因此，多信息素蟻群算法尤其適用于任務(wù)較多的情形。

圖11 不同任務(wù)數(shù)量下算法結(jié)果對(duì)比圖

3.3 算法運(yùn)行時(shí)間

設(shè)定機(jī)群平臺(tái)數(shù)量12，任務(wù)數(shù)量從1開始遞增，算法的每次迭代時(shí)間與任務(wù)數(shù)量的關(guān)系如圖12所示，其中橫坐標(biāo)X數(shù)值為任務(wù)數(shù)量的三次方。由圖可知，算法單次迭代運(yùn)行時(shí)間與任務(wù)數(shù)量的三次方成近似線性關(guān)系，與本文算法分析的結(jié)果相吻合。

圖12 算法單次迭代時(shí)間與任務(wù)數(shù)量曲線圖

4 結(jié) 語(yǔ)

研究工作考慮到平臺(tái)作戰(zhàn)半徑對(duì)聯(lián)合任務(wù)分配的影響，建立了基于平臺(tái)作戰(zhàn)半徑的路線模型，并將聯(lián)合任務(wù)分配問(wèn)題建模為復(fù)雜的多旅行商問(wèn)題，通過(guò)圖的方式將分配結(jié)果進(jìn)行表示，改進(jìn)蟻群算法，為每一個(gè)旅行商提供一種信息素并改變信息素更新策略，以圖學(xué)習(xí)的方法求得圖中邊的組合作為任務(wù)分配的結(jié)果。仿真結(jié)果表明，該方法有效的解決了多類型平臺(tái)共同執(zhí)行多任務(wù)的任務(wù)分配問(wèn)題，提供了穩(wěn)定有效的解決方案。今后的研究重點(diǎn)將是動(dòng)態(tài)環(huán)境下對(duì)分配方案的調(diào)整，以及在任務(wù)平臺(tái)資源化描述的基礎(chǔ)上資源調(diào)度的方法。