無人機(jī)集群任務(wù)分配中群智能算法性能對(duì)比*

梁智韜，賈高偉，王建峰

（國防科技大學(xué)空天科學(xué)學(xué)院，長(zhǎng)沙 410073）

0 引言

經(jīng)過數(shù)十年的快速發(fā)展，無人機(jī)的自主性能不斷提高，但單架無人機(jī)在復(fù)雜環(huán)境下完成復(fù)雜任務(wù)仍具有局限性。無人機(jī)集群能夠充分發(fā)揮無人機(jī)平臺(tái)機(jī)動(dòng)靈活、成本低廉、應(yīng)用廣泛的優(yōu)勢(shì)，以能力組合的形式協(xié)同高效地完成多樣化任務(wù)，逐漸成為航空武器裝備發(fā)展的重要趨勢(shì)。

無人機(jī)集群任務(wù)分配，是根據(jù)集群中的無人機(jī)數(shù)量、類型、所要執(zhí)行的目標(biāo)任務(wù)及載荷的不同，對(duì)無人機(jī)完成具體任務(wù)的預(yù)先設(shè)定與統(tǒng)籌管理，其本質(zhì)是多約束條件下的優(yōu)化求解問題。在具體實(shí)施過程中，需要考慮無人機(jī)動(dòng)力學(xué)模型及其飛行性能、載荷性能、目標(biāo)特性、通信及環(huán)境限制等約束條件，為無人機(jī)規(guī)劃出合理的任務(wù)執(zhí)行方案和飛行航跡，并確定載荷配置、使用方式與時(shí)間節(jié)點(diǎn)等，確保某一項(xiàng)或多項(xiàng)指標(biāo)最優(yōu)。

概括來講，適合于無人機(jī)集群的任務(wù)架構(gòu)包括集中式、分布式、集散式等多類，其中，集中式是當(dāng)前最直接、最成熟的集群模式，無人機(jī)集群接受單個(gè)或多個(gè)中心控制。集中式任務(wù)分配求解方法又可以分為最優(yōu)化方法和啟發(fā)式方法。一般而言，最優(yōu)化算法具有描述簡(jiǎn)潔、直接等特點(diǎn)，可以靈活調(diào)整約束條件來求解實(shí)際問題，具有理論最優(yōu)解，但規(guī)模不宜過大，一般可用于無人機(jī)集群離線式任務(wù)分配。在啟發(fā)式算法中，智能類算法的應(yīng)用較多，尤其以蟻群算法、遺傳算法、粒子群算法等居多。這幾類算法通常具有較強(qiáng)的穩(wěn)定性，適合分布式計(jì)算機(jī)制，也能夠與多類其他算法結(jié)合。但這些智能類算法之間的相對(duì)優(yōu)勢(shì)缺乏深刻的、具有普遍意義的分析，尤其缺乏幾類算法在運(yùn)算速度、收斂速度、求解優(yōu)化性方面的對(duì)比。

在無人機(jī)集群的諸多應(yīng)用中，對(duì)敵防空打擊（destroy of enemy air defenses，DEAD）涵蓋任務(wù)類型多、有明確的邏輯約束和時(shí)間窗約束，是典型的復(fù)雜任務(wù)集合，是無人機(jī)集群的重要應(yīng)用領(lǐng)域，可以作為研究無人機(jī)集群任務(wù)規(guī)劃的典型對(duì)象。本文以對(duì)敵防空打擊為任務(wù)樣式，量化分析蟻群算法、遺傳算法、粒子群算法在任務(wù)分配方案求解過程中的特性。

1 無人機(jī)集群協(xié)同任務(wù)分配模型

1.1 問題描述

式中，M是攻擊任務(wù)，M是偵察任務(wù)。

無人機(jī)集群協(xié)同分配的根本出發(fā)點(diǎn)是提高對(duì)敵毀傷效能，降低己方損失，為此本文將無人機(jī)的損耗概率、目標(biāo)的價(jià)值收益和飛行航程的長(zhǎng)度作為評(píng)價(jià)作戰(zhàn)效能的主要指標(biāo)。

1.2 代價(jià)與收益

無人機(jī)集群執(zhí)行協(xié)同偵察（攻擊）任務(wù)，其代價(jià)主要來源于兩方面：威脅代價(jià)和航程航時(shí)代價(jià)。由于威脅代價(jià)、航程航時(shí)代價(jià)以及收益指標(biāo)的量綱存在差異，通過線性尺度變換法，將各個(gè)量轉(zhuǎn)化為無量綱數(shù)值，范圍在［0，1］，具體地：

威脅代價(jià)：目標(biāo)陣地配備的高射炮、導(dǎo)彈以及其他武器對(duì)無人機(jī)造成的直接毀傷或者間接干擾而導(dǎo)致的代價(jià)。

航程代價(jià)：根據(jù)無人機(jī)執(zhí)行任務(wù)的航跡計(jì)算航程代價(jià)。一方面，航程越長(zhǎng)，無人機(jī)的攜帶的燃油損耗、機(jī)件損耗越大；另一方面，航程越長(zhǎng)，對(duì)應(yīng)的任務(wù)執(zhí)行時(shí)間也越大。為反應(yīng)集群的整體航程，本文設(shè)定航程代價(jià)由集群整體執(zhí)行任務(wù)的時(shí)間衡量。航程代價(jià)C可表示為：

式中，t表示集群中單機(jī)執(zhí)行任務(wù)的最長(zhǎng)時(shí)間；t表示集群中單機(jī)執(zhí)行任務(wù)的最短時(shí)間。

航時(shí)代價(jià)：僅考慮航程代價(jià)C存在任務(wù)分配平均化但總時(shí)長(zhǎng)較長(zhǎng)的局限性，因此，引入航時(shí)代價(jià)，以具體的時(shí)間指標(biāo)來對(duì)整體任務(wù)分配計(jì)劃進(jìn)行約束。航時(shí)代價(jià)C可表示為：

式中，t 表示集群執(zhí)行任務(wù)的總時(shí)間；t＇表示固定的時(shí)長(zhǎng)衡量指標(biāo)。

協(xié)同偵察（攻擊）收益：定義無人機(jī)i 偵察（攻擊）目標(biāo)j 所獲得的收益為：

1.3 目標(biāo)函數(shù)

對(duì)應(yīng)得到多無人機(jī)任務(wù)分配模型的優(yōu)化目標(biāo)解析表達(dá)式為：

式中，決策變量K是一個(gè)0-1 型變量。當(dāng)K=1 時(shí)，表示無人機(jī)i 執(zhí)行對(duì)目標(biāo)j 的偵察（打擊）任務(wù)。

1.4 約束條件

在無人機(jī)集群對(duì)敵防空打擊系統(tǒng)應(yīng)用過程，結(jié)合實(shí)際需求，有如下條件約束：

1）每架無人機(jī)的任務(wù)最大執(zhí)行能力約束：

式中，L是攻擊無人機(jī)攜帶武器的數(shù)量。定義無人機(jī)每完成一次攻擊任務(wù)消耗一枚導(dǎo)彈（炸彈）。

2）暫不考慮任務(wù)能力冗余配置，假定一項(xiàng)任務(wù)只能由一架無人機(jī)執(zhí)行一次：

3）一般情況下，認(rèn)為無人機(jī)集群能夠?qū)⑺腥蝿?wù)完成：

4）邏輯約束：要求同一個(gè)目標(biāo)需經(jīng)過偵察型無人機(jī)確認(rèn)后，再由打擊型無人機(jī)實(shí)施打擊。具體表示為：

1.5 任務(wù)時(shí)序關(guān)系

在無人機(jī)集群對(duì)敵防空打擊系統(tǒng)作戰(zhàn)應(yīng)用中，設(shè)定其偵察與打擊的邏輯時(shí)序?yàn)椋?/p>

Step 1：開展偵察任務(wù)規(guī)劃，完成對(duì)偵察任務(wù)分配結(jié)果尋優(yōu)，得到偵察任務(wù)時(shí)序表；

Step 2：偵察過程中一旦有目標(biāo)得以確認(rèn)，啟動(dòng)攻擊任務(wù)規(guī)劃，完成對(duì)地攻擊任務(wù)分配結(jié)果尋優(yōu)，得到攻擊任務(wù)時(shí)序表；

Step 3：查看任務(wù)完成情況；若存在已確認(rèn)目標(biāo)未分配打擊無人機(jī)，重復(fù)Step 2；若所有任務(wù)均已完成，進(jìn)入Step4；

Step 4：輸出對(duì)敵防空打擊任務(wù)分配時(shí)序表。

圖1 對(duì)敵防空打擊任務(wù)分配流程圖

2 算法的選擇與說明

2.1 遺傳算法的設(shè)置

遺傳算法（genetic algorithm，GA）借鑒了進(jìn)化生物學(xué)中的遺傳、突變、自然選擇和交叉等現(xiàn)象，通過建立多維數(shù)組來模擬生物的DNA 堿基序列。

2.1.1 遺傳算法編碼方式

設(shè)定每一個(gè)數(shù)組為一條DNA 序列，序列中DNA 堿基數(shù)目等于任務(wù)數(shù)目，堿基單位由數(shù)字構(gòu)成。關(guān)于無人機(jī)能力和執(zhí)行任務(wù)的準(zhǔn)則在第1 章已經(jīng)闡明。這里堿基單位的整數(shù)部分［A］表示任務(wù)對(duì)應(yīng)的無人機(jī)序號(hào)，整數(shù)部分相同的目標(biāo)任務(wù)分配在同一架無人機(jī)的任務(wù)序列中；小數(shù)部分A-［A］表示目標(biāo)在該無人機(jī)任務(wù)序列中的優(yōu)先程度，以升序關(guān)系對(duì)應(yīng)任務(wù)執(zhí)行次序。下頁表1 給出了編碼的樣例：

表1 遺傳算法編碼示意

表中所示為3 架無人機(jī)對(duì)6 個(gè)目標(biāo)執(zhí)行協(xié)同偵察任務(wù)的編碼表示，DNA 序列長(zhǎng)度為6 維（序列長(zhǎng)度應(yīng)與目標(biāo)數(shù)保持一致）。實(shí)數(shù)2.8 中2 代表無人機(jī)序號(hào)，0.8 代表目標(biāo)1 在無人機(jī)2 對(duì)應(yīng)的執(zhí)行任務(wù)中的優(yōu)先級(jí)，遺傳算法中為了避免陷入局部最優(yōu)，包含了交叉和變異兩類典型操作。圖2 和圖3給出了采用此種堿基編碼方式對(duì)應(yīng)的交叉變異處理過程。

圖2 交叉互換示意

圖3 變異示意

設(shè)定種群中個(gè)體生產(chǎn)子代（即基因交叉互換）的概率為θ，子代出現(xiàn)基因變異的概率為Ω。同時(shí)為提升種群的尋優(yōu)效率，設(shè)立環(huán)境淘汰概率ε。根據(jù)每輪循環(huán)結(jié)束后個(gè)體適應(yīng)度值在種群整體適應(yīng)度值中的占比進(jìn)行淘汰。

2.1.2 遺傳算法參數(shù)設(shè)置

遺傳算法的參數(shù)設(shè)置主要包括：基因變異概率Ω，環(huán)境淘汰概率ε。

在智能算法中，各參數(shù)之間相互耦合，且對(duì)于算法性能產(chǎn)生非線性影響。因此，在參數(shù)選擇的過程中主要采取試探性的實(shí)驗(yàn)，通過遍歷范圍內(nèi)的所有參數(shù)選擇以獲取對(duì)于模型性能最優(yōu)的參數(shù)組合。但隨著參數(shù)數(shù)量的增加，參數(shù)組合遍歷所需的實(shí)驗(yàn)次數(shù)以指數(shù)級(jí)增長(zhǎng)，完全遍歷耗時(shí)長(zhǎng)且效率低下。對(duì)此，通過采取均勻設(shè)計(jì)的方法，以參數(shù)組合空間中的具備代表性的樣本點(diǎn)為依據(jù)，極大地化簡(jiǎn)了參數(shù)選取實(shí)驗(yàn)的復(fù)雜程度。均勻設(shè)計(jì)方案的科學(xué)性已有文獻(xiàn)［15-16］說明，在此不再詳述。

本文采取文獻(xiàn)［16］附錄中的均勻設(shè)計(jì)表，對(duì)遺傳算法的參數(shù)：基因變異概率Ω 和環(huán)境淘汰概率ε進(jìn)行設(shè)計(jì)實(shí)驗(yàn)，每組試驗(yàn)重復(fù)20 次，隨后采用基因變異概率為0.02，環(huán)境淘汰概率0.05。

2.2 粒子群優(yōu)化算法的設(shè)置

將無人機(jī)集群對(duì)敵防空打擊系統(tǒng)任務(wù)分配模型與粒子群優(yōu)化算法各要素建立映射關(guān)系，完成模型與算法的結(jié)合，這是粒子群優(yōu)化算法（particle swarm optimization，PSO）應(yīng)用的關(guān)鍵。

2.2.1 粒子群優(yōu)化算法編碼方式

結(jié)合無人機(jī)集群特點(diǎn)，本節(jié)采用基于實(shí)數(shù)向量的編碼方式。編碼的基本思想與遺傳算法中表1 對(duì)應(yīng)的編碼方式類似，這有利于后期的算法性能對(duì)比。為準(zhǔn)確闡述，這里說明如下：設(shè)定粒子的維度等于任務(wù)數(shù)目、粒子位置的整數(shù)部分［B］表示任務(wù)對(duì)應(yīng)的無人機(jī)序號(hào)，整數(shù)部分相同的目標(biāo)任務(wù)分配在同一架無人機(jī)的任務(wù)序列中；粒子位置的小數(shù)部分B-［B］表示目標(biāo)在該無人機(jī)任務(wù)序列中的優(yōu)先程度，以升序關(guān)系對(duì)應(yīng)任務(wù)執(zhí)行次序。表2 給出了粒子編碼的樣例：

表2 粒子編碼示意

表1 和表2 所述的編碼方式簡(jiǎn)潔易懂，可在不增加維數(shù)的前提下，將無人機(jī)及其對(duì)應(yīng)的目標(biāo)序列在編碼中表示出來，解碼處理僅需進(jìn)行一次排序和取整運(yùn)算即可。當(dāng)進(jìn)行粒子狀態(tài)更新時(shí)，重新調(diào)整各個(gè)粒子的狀態(tài)也比較方便。

2.2.2 粒子群優(yōu)化算法的調(diào)整

標(biāo)準(zhǔn)粒子群優(yōu)化算法主要根據(jù)下列公式進(jìn)行更新迭代：

粒子在優(yōu)化問題定義范圍進(jìn)行搜索的物理含義是每個(gè)粒子的位置代表一個(gè)解，并構(gòu)成解空間；解的適應(yīng)度值與虛擬環(huán)境下的每個(gè)位置相對(duì)應(yīng)。粒子群的更新機(jī)制，即是利用當(dāng)前位置、全局極值和個(gè)體極值3 個(gè)信息，指導(dǎo)粒子的下一步迭代位置。粒子個(gè)體充分利用自身經(jīng)驗(yàn)和群體經(jīng)驗(yàn)調(diào)整自身的狀態(tài)是粒子群優(yōu)化算法具有優(yōu)異特性的關(guān)鍵。

在應(yīng)用中，傳統(tǒng)粒子群優(yōu)化算法面臨的主要不足表現(xiàn)為：1）搜索擴(kuò)張因子是粒子群優(yōu)化算法的主要控制參數(shù)，當(dāng)搜索過程較為復(fù)雜時(shí)（對(duì)敵防空打擊任務(wù)屬性），控制參數(shù)的線性調(diào)整不能很好地適應(yīng)實(shí)際搜索過程，有必要對(duì)控制參數(shù)進(jìn)行自適應(yīng)調(diào)整。2）容易早熟收斂（尤其是在處理多峰搜索問題中），全局尋優(yōu)能力較差等。

追求完全的全局搜索會(huì)帶來巨大的時(shí)間消耗，因此，有必要引入改進(jìn)機(jī)制，其核心機(jī)理是通過調(diào)整控制參數(shù)，優(yōu)化搜索策略，規(guī)避局部最優(yōu)并盡可能地獲取全局最優(yōu)解。具體引入以下兩種修改機(jī)制：

1）自適應(yīng)參數(shù)控制

2）混合更新機(jī)制

將上文中提到的遺傳算法中的變異和交叉操作（如圖2～圖3 所示）引入粒子群優(yōu)化算法，通過粒子同個(gè)體極值和群體極值的交叉以及粒子自身變異的方式來搜索最優(yōu)解，以此提高粒子群優(yōu)化算法的全局尋優(yōu)能力。

2.2.3 粒子群優(yōu)化算法的參數(shù)設(shè)置

粒子群優(yōu)化算法的參數(shù)設(shè)置主要包括：自適應(yīng)參數(shù)控制中收斂性指標(biāo)與聚集性指標(biāo)的系數(shù)。同樣采取文獻(xiàn)［16］附錄中的均勻設(shè)計(jì)表，對(duì)粒子群優(yōu)化算法的參數(shù)進(jìn)行設(shè)計(jì)實(shí)驗(yàn)，每組試驗(yàn)重復(fù)20 次。采用收斂性指標(biāo)0.4，聚集性指標(biāo)為0.18。

2.3 蟻群算法的設(shè)置

2.3.1 蟻群算法的模型映射

蟻群算法（ant colony optimization，ACO）在無人機(jī)集群任務(wù)分配中的應(yīng)用基礎(chǔ)仍在于模型映射，這里給出映射模型如下：

2.3.2 蟻群算法的調(diào)整

不同于遺傳算法和粒子群優(yōu)化算法，在基于蟻群算法的任務(wù)分配過程中，約束條件的增多使得求解規(guī)模和求解時(shí)間大幅增加。為此，另一種優(yōu)化的調(diào)整方案是適當(dāng)減少任務(wù)約束。在任務(wù)分配中，如果對(duì)于出現(xiàn)沖突的任務(wù)，受領(lǐng)該任務(wù)的無人機(jī)可以將此任務(wù)以拍賣的形式轉(zhuǎn)交給其他有富余能力的無人機(jī)。這樣處理僅對(duì)局部的無人機(jī)任務(wù)分配產(chǎn)生影響，帶來的運(yùn)算量較小，具有較好的實(shí)用性。

拍賣作為一種社會(huì)化的協(xié)商機(jī)制，通過“招標(biāo)-投標(biāo)-中標(biāo)”機(jī)制實(shí)現(xiàn)任務(wù)的委派和遷移。一般包括以下4 個(gè)步驟：

Step 1 任務(wù)宣布：當(dāng)無人機(jī)發(fā)現(xiàn)自己沒有足夠的能力處理當(dāng)前的任務(wù)，就作為招標(biāo)者把任務(wù)向外界公布。

Step 2 招標(biāo)：其他無人機(jī)接收到招標(biāo)信息后，根據(jù)任務(wù)要求和自己的能力，選擇最合適的任務(wù)進(jìn)行投標(biāo)，公布自己參與投標(biāo)的代價(jià)。

Step 3 中標(biāo)：在達(dá)到預(yù)定的投標(biāo)截止時(shí)間后，投標(biāo)者對(duì)投標(biāo)進(jìn)行處理，挑出最合適的投標(biāo)并對(duì)外廣播。

Step 4 任務(wù)執(zhí)行：中標(biāo)無人機(jī)將中標(biāo)任務(wù)加入到自己的任務(wù)執(zhí)行序列中，完成任務(wù)的轉(zhuǎn)接。

2.3.3 蟻群算法的參數(shù)設(shè)置

蟻群算法的參數(shù)設(shè)置主要包括：將式（10）所示約束略去，改用拍賣算法調(diào)整不可完成任務(wù)；信息素蒸發(fā)系數(shù)ρ，信息素權(quán)重系數(shù)α，啟發(fā)因子權(quán)重系數(shù)β。同樣采取文獻(xiàn)［15］中的均勻設(shè)計(jì)表U（12），對(duì)蟻群算法的參數(shù)進(jìn)行設(shè)計(jì)實(shí)驗(yàn)，每組試驗(yàn)重復(fù)20次。得到信息素蒸發(fā)系數(shù)1.7，信息素權(quán)重系數(shù)2，啟發(fā)因子權(quán)重系數(shù)0.57。

3 任務(wù)分配的仿真

3.1 仿真環(huán)境設(shè)置

本節(jié)通過仿真分析驗(yàn)證上述所提出的遺傳算法、粒子群優(yōu)化算法和蟻群算法。具體地，設(shè)有12架無人機(jī)執(zhí)行任務(wù)，其中，7 架為偵察無人機(jī)，5 架為打擊無人機(jī)。目標(biāo)數(shù)量為15 個(gè)，目標(biāo)屬性為地面固定目標(biāo)且方位已知，需要偵察無人機(jī)予以確認(rèn)，并安排打擊無人機(jī)予以消除。戰(zhàn)場(chǎng)區(qū)域面積設(shè)置為120×120 km，目標(biāo)與無人機(jī)機(jī)場(chǎng)布置如圖4 所示。

圖4 戰(zhàn)場(chǎng)環(huán)境示意圖（紅星號(hào)代表無人機(jī)機(jī)場(chǎng)，藍(lán)圓點(diǎn)代表目標(biāo)點(diǎn)）

無人機(jī)集群和敵方目標(biāo)的參數(shù)設(shè)置如表3～表5 所示。在不影響任務(wù)分配算法驗(yàn)證的前提下簡(jiǎn)化仿真實(shí)驗(yàn)過程，設(shè)定偵察無人機(jī)的探測(cè)半徑同轉(zhuǎn)彎半徑一致，且當(dāng)目標(biāo)進(jìn)入飛機(jī)的探測(cè)半徑即代表已完成偵察任務(wù)。

表3 目標(biāo)參數(shù)

表4 偵察無人機(jī)參數(shù)

表5 攻擊無人機(jī)參數(shù)

3.2 各算法仿真分配結(jié)果

3.2.1 遺傳算法仿真結(jié)果

結(jié)合2.1.1 節(jié)闡述的遺傳算法編碼方式，將交叉互換概率θ，基因變異概率Ω，環(huán)境淘汰概率ε分別設(shè)定為1、0.05、2%。得到的任務(wù)分配結(jié)果如表6、表7 所示。

表6 偵察任務(wù)分配結(jié)果

表7 打擊任務(wù)分配結(jié)果

引入甘特圖展示任務(wù)執(zhí)行的時(shí)間屬性，如圖5所示。圖中縱坐標(biāo)代表無人機(jī)序號(hào)，時(shí)間條中編碼對(duì)應(yīng)目標(biāo)序號(hào)。綠色矩形代表偵察任務(wù)部分，藍(lán)色矩形部分代表打擊任務(wù)部分；橫坐標(biāo)代表任務(wù)執(zhí)行時(shí)間。

圖5 遺傳算法求解得到任務(wù)分配甘特圖

繪制基于Dubins 優(yōu)化的無人機(jī)飛行軌跡，如圖6 所示。

圖6 任務(wù)執(zhí)行航跡圖

3.2.2 粒子群優(yōu)化算法仿真結(jié)果

表8 偵察任務(wù)分配結(jié)果

表9 打擊任務(wù)分配結(jié)果

引入甘特圖進(jìn)行表征，如圖7 所示。

圖7 粒子群優(yōu)化算法求解得到任務(wù)分配甘特圖

根據(jù)甘特圖所得結(jié)果，同樣可以得到任務(wù)執(zhí)行航跡圖，為簡(jiǎn)潔篇幅，這里不再展示。

3.2.3 蟻群算法仿真結(jié)果

針對(duì)蟻群算法，設(shè)蟻群規(guī)模M=20，最大尋優(yōu)次數(shù)NC_Max=500。將信息素增加強(qiáng)度系數(shù)Q，信息素蒸發(fā)系數(shù)ρ，信息素權(quán)重系數(shù)α，啟發(fā)因子權(quán)重系數(shù)的值分別設(shè)定為1、1.7、2、0.57。得到的任務(wù)分配結(jié)果如表10、表11 所示。

表10 偵察任務(wù)分配結(jié)果

表11 打擊任務(wù)分配結(jié)果

引入甘特圖展示任務(wù)執(zhí)行的時(shí)間屬性，如圖8所示。

圖8 蟻群算法求解得到任務(wù)分配甘特圖

3.3 仿真結(jié)果的對(duì)比分析

針對(duì)無人機(jī)集群對(duì)敵防空打擊協(xié)同任務(wù)分配，按照前文的任務(wù)設(shè)定，在Windows10 操作系統(tǒng)上，基于Matlab 環(huán)境實(shí)現(xiàn)本文算法的仿真實(shí)驗(yàn)，PC 機(jī)配置為Intel（R）Corel（TM）i7-9750H CPU E5300@2.60 GHz 2.59 GHz，16 G 內(nèi)存。在相同的目標(biāo)和無人機(jī)參數(shù)設(shè)置情況下，設(shè)定一致的迭代（進(jìn)化）次數(shù)500 次，對(duì)于3 類智能算法及其改進(jìn)形式進(jìn)行50 次蒙特卡洛仿真，將計(jì)算結(jié)果對(duì)比如下。

3.3.1 蟻群算法改進(jìn)結(jié)果分析

圖9 展示了經(jīng)典蟻群算法和改進(jìn)蟻群算法的50 次仿真運(yùn)行時(shí)間，可以看出拍賣機(jī)制的引入有效降低了算法的運(yùn)行時(shí)間，符合前文中的預(yù)期。

圖9 蟻群算法運(yùn)行時(shí)間對(duì)比圖

3.3.2 粒子群優(yōu)化算法改進(jìn)結(jié)果分析

圖10 展示了粒子群優(yōu)化算法和改進(jìn)粒子群優(yōu)化算法在50 次蒙特卡洛仿真過程中的適應(yīng)度值收斂結(jié)果?？梢钥闯鐾ㄟ^參數(shù)自適應(yīng)控制和交叉變異操作，粒子群優(yōu)化算法的尋優(yōu)能力有所提升，易陷入局部最優(yōu)解的情況也有所改善。

圖10 粒子群優(yōu)化算法運(yùn)行結(jié)果對(duì)比圖

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

圖11 展示了3 種算法在50 次運(yùn)算中花費(fèi)的時(shí)間。蟻群算法的平均運(yùn)行時(shí)間為69.89 s，粒子群優(yōu)化算法的平均運(yùn)行時(shí)間為18.31 s，遺傳算法的平均運(yùn)行時(shí)間為17.57 s。圖11 表明粒子群優(yōu)化算法和遺傳算法的運(yùn)行時(shí)間相近，而蟻群算法所需時(shí)間遠(yuǎn)超于粒子群優(yōu)化算法和遺傳算法。其原因?yàn)椋簩?duì)于粒子群和遺傳算法來說，其編碼形式和進(jìn)化方式相似，因此，運(yùn)行時(shí)間相近。其簡(jiǎn)易的編碼方式也大大降低了程序的運(yùn)算量，在耗時(shí)上更具優(yōu)勢(shì)。而蟻群算法為了實(shí)現(xiàn)察打一體任務(wù)的時(shí)間約束，采用的定時(shí)響應(yīng)機(jī)制導(dǎo)致算法需要以固定時(shí)間間隔逐步推進(jìn)，因而耗時(shí)較大，盡管它已經(jīng)采用拍賣步驟減小了求解空間。

圖11 算法運(yùn)行時(shí)間對(duì)比圖

3.3.4 算法收斂速度在50 次蒙特卡洛過程中，分別對(duì)每次迭代的適應(yīng)度值進(jìn)行平均，并隨迭代次數(shù)呈現(xiàn)出來，得到圖12 所示收斂曲線。由圖可知，遺傳算法收斂速度緩慢，且收斂程度低。粒子群優(yōu)化算法和蟻群算法收斂趨勢(shì)明顯，尤其是蟻群算法的收斂結(jié)果優(yōu)于其他算法。其原因是蟻群算法中螞蟻始終統(tǒng)一從蟻巢出發(fā)向目標(biāo)點(diǎn)前進(jìn)尋優(yōu)的方式優(yōu)于遺傳算法和粒子群優(yōu)化算法中個(gè)體在解空間內(nèi)部“灑點(diǎn)”式的尋優(yōu)方式。因此，使得蟻群算法在運(yùn)行前期就存在顯著的優(yōu)勢(shì)。

圖12 算法收斂速度對(duì)比圖

3.3.5 分配結(jié)果優(yōu)化性對(duì)比

圖13 展示了3 種算法在50 次仿真運(yùn)算中的最優(yōu)收斂結(jié)果。結(jié)果與收斂速度圖一致，蟻群算法尋優(yōu)結(jié)果最好，遺傳算法最差。粒子群優(yōu)化算法由于引入了遺傳算法的交叉變異操作，因此，在尋優(yōu)結(jié)果上優(yōu)于遺傳算法。但同樣因?yàn)榍拔奶峒暗膶?yōu)原理差異導(dǎo)致粒子群優(yōu)化算法和遺傳算法的尋優(yōu)結(jié)果不穩(wěn)定，最優(yōu)適應(yīng)度值震蕩幅度大，能夠產(chǎn)生出優(yōu)于蟻群算法的結(jié)果，也會(huì)產(chǎn)生出劣于蟻群算法的結(jié)果。而蟻群算法的運(yùn)行結(jié)果更為穩(wěn)定。

圖13 算法運(yùn)行結(jié)果對(duì)比圖

4 結(jié)論

在無人機(jī)集群任務(wù)分配與應(yīng)用中，需要完成對(duì)復(fù)雜任務(wù)的分解與數(shù)學(xué)描述、目標(biāo)函數(shù)與代價(jià)函數(shù)的設(shè)置、準(zhǔn)確的特征描述方法。在此基礎(chǔ)上，模型的求解同樣至關(guān)重要，影響求解結(jié)果的最優(yōu)性、時(shí)效性和魯棒性。

本文以相同的約束條件、優(yōu)化目標(biāo)以及任務(wù)規(guī)劃策略，對(duì)比分析了3 種群智能算法在任務(wù)分配中的性能。從仿真分析結(jié)果可以看出，3 種算法均可適應(yīng)于無人機(jī)集群對(duì)敵防空打擊任務(wù)分配，最終得到可行的分配結(jié)果。但從優(yōu)化效益看，蟻群算法的最終收斂結(jié)果更好，且尋優(yōu)結(jié)果更穩(wěn)定，耗時(shí)較長(zhǎng)，更適用于對(duì)任務(wù)的事前規(guī)劃。粒子群優(yōu)化算法和遺傳算法的尋優(yōu)結(jié)果隨機(jī)性強(qiáng)，耗時(shí)較短，能夠應(yīng)對(duì)戰(zhàn)場(chǎng)突發(fā)情況，動(dòng)態(tài)適應(yīng)性更強(qiáng)。具體分析包括：

1）粒子群優(yōu)化算法對(duì)應(yīng)的參數(shù)較少，通過搜索到的當(dāng)前最優(yōu)解共享信息，本質(zhì)上是一種單項(xiàng)信息共享策略，因此，對(duì)問題維數(shù)的敏感度不高。且自適應(yīng)參數(shù)控制機(jī)制和交叉變異機(jī)制的引入對(duì)于增大粒子尋優(yōu)范圍和避免陷入局部最優(yōu)解的起到了一定的效果。

2）蟻群算法是基于正反饋機(jī)制的進(jìn)化算法，但僅能感知局部信息，不能利用全局信息，因此，蟻群算法往往需要更長(zhǎng)的搜索時(shí)間。不過“螞蟻”尋優(yōu)過程中信息素機(jī)制使得其更易受到適應(yīng)度值的影響，因此，收斂效率和最優(yōu)性強(qiáng)于粒子群優(yōu)化算法和遺傳算法。但信息素機(jī)制對(duì)于尋優(yōu)結(jié)果的固化使蟻群算法也存在陷入局部最優(yōu)解的可能性。

3）對(duì)于遺傳算法而言，僅僅依靠交叉變異和自然淘汰的方式尋優(yōu)效率過低。算法易受到初始種群在解空間中生成位置的影響。因?yàn)榻徊婊Q和自然淘汰僅僅作用于種群內(nèi)部，對(duì)于解空間其他位置的搜索僅依靠堿基變異的方式效率很低且結(jié)果不穩(wěn)定。

本文綜合分析了3 類算法在無人機(jī)集群任務(wù)分配中的特點(diǎn)與優(yōu)勢(shì)，這對(duì)任務(wù)分配求解算法的選擇，具有重要參考意義。