楊國(guó)利 成浩 溫薈琦 劉偉

1.北京大數(shù)據(jù)先進(jìn)技術(shù)研究院北京100195 2.解放軍66136 部隊(duì)北京100042

停駐于各個(gè)前沿機(jī)場(chǎng)電子偵察飛機(jī)是遂行多目標(biāo)平時(shí)/戰(zhàn)時(shí)偵察任務(wù)的主要手段, 當(dāng)前正逐漸由單機(jī)作業(yè)向多機(jī)協(xié)同偵察轉(zhuǎn)變, 其核心問(wèn)題是多機(jī)協(xié)同下的偵察調(diào)度與任務(wù)規(guī)劃.現(xiàn)代戰(zhàn)爭(zhēng)中,偵察調(diào)度與路徑規(guī)劃研究為解決多機(jī)多目標(biāo)偵察問(wèn)題提供了重要的技術(shù)支撐.受限于作戰(zhàn)目的、戰(zhàn)場(chǎng)環(huán)境、機(jī)場(chǎng)位置、飛機(jī)性能、功能屬性等條件的約束,空中偵察調(diào)度需通過(guò)進(jìn)行合理的任務(wù)規(guī)劃來(lái)保證整個(gè)偵察任務(wù)的飛行總代價(jià)達(dá)到最優(yōu).

利用解決多旅行商問(wèn)題(Multiple Travelling Salesman Problem, MTSP)[1?7]的方法思路, 研究多偵察機(jī)多目標(biāo)條件下的空中偵察調(diào)度問(wèn)題, 是一個(gè)切實(shí)可行的解決方案.目前應(yīng)用較為廣泛的算法包括: 遺傳算法、蟻群算法、禁忌搜索算法、粒子群優(yōu)化算法、模擬退火算法等.近年來(lái),一些學(xué)者[1]通過(guò)對(duì)多無(wú)人機(jī)多目標(biāo)偵察任務(wù)進(jìn)行分析, 將無(wú)人機(jī)航路規(guī)劃調(diào)度問(wèn)題轉(zhuǎn)化成多旅行商問(wèn)題, 并利用改進(jìn)的遺傳算法對(duì)該問(wèn)題模型進(jìn)行智能尋優(yōu)計(jì)算, 最終求得滿足實(shí)際偵察需求的分配方案.文獻(xiàn)[2]在研究多無(wú)人機(jī)協(xié)同搜索的航路規(guī)劃問(wèn)題中, 首先利用聚類算法將MTSP 問(wèn)題分解成多個(gè)獨(dú)立的旅行商問(wèn)題(Travelling Salesman Problem,TSP)問(wèn)題,再利用改進(jìn)遺傳算法求解問(wèn)題模型, 提高了優(yōu)化算法的計(jì)算效率.文獻(xiàn)[3]綜合考慮多種任務(wù)因素約束建立多無(wú)人機(jī)協(xié)同任務(wù)規(guī)劃模型, 并提出改進(jìn)的人工蜂群算法對(duì)其進(jìn)行求解.

通過(guò)求解多旅行商問(wèn)題, 人們可以獲取各個(gè)飛機(jī)的調(diào)度方案和偵察路徑, 同時(shí)也為衡量各個(gè)機(jī)場(chǎng)的重要性提供了量化手段, 用以指導(dǎo)節(jié)點(diǎn)重要性排序.眾所周知,打擊目標(biāo)選擇是聯(lián)合作戰(zhàn)指揮決策的重要環(huán)節(jié), 同時(shí)也是彈目匹配和毀傷評(píng)估的前提和基礎(chǔ), 其工作質(zhì)量對(duì)戰(zhàn)爭(zhēng)成敗起著巨大作用.文獻(xiàn)[8] 對(duì)聯(lián)合作戰(zhàn)條件下打擊目標(biāo)選擇理論進(jìn)行研究,給出了一種可操作性的系統(tǒng)分析方法.文獻(xiàn)[9]從空襲作戰(zhàn)理論角度分析影響空襲目標(biāo)選擇的影響因素,并建立模糊神經(jīng)網(wǎng)絡(luò)模型對(duì)重點(diǎn)目標(biāo)進(jìn)行重要性分析.此外,“對(duì)敵有效性”作為目標(biāo)選擇的重要指標(biāo)通常被用來(lái)表征目標(biāo)在敵方作戰(zhàn)體系中的地位和作用,不同的目標(biāo)選擇對(duì)敵方作戰(zhàn)體系影響不同[8].因此,在衡量各個(gè)機(jī)場(chǎng)重要性過(guò)程, 既需充分考慮這些目標(biāo)本身的價(jià)值(停駐飛機(jī)數(shù)量、種類, 跑道長(zhǎng)度),還需要考慮這些目標(biāo)與其他目標(biāo)共同作用產(chǎn)生的涌現(xiàn)特性[10].

為探索解決空中偵察調(diào)度與機(jī)場(chǎng)重要性問(wèn)題,深度挖掘不同機(jī)場(chǎng)在空中偵察任務(wù)中的地位作用,本文主要對(duì)以下兩個(gè)方面展開(kāi)深入研究, 一是將空中偵察調(diào)度與路徑規(guī)劃問(wèn)題轉(zhuǎn)化成MTSP 問(wèn)題, 通過(guò)對(duì)該問(wèn)題進(jìn)行分析建立相應(yīng)模型, 并改進(jìn)遺傳算法進(jìn)行最優(yōu)路徑求解; 二是通過(guò)節(jié)點(diǎn)移除法計(jì)算各機(jī)場(chǎng)目標(biāo)失效后對(duì)整個(gè)體系空中偵察任務(wù)的影響,并選擇出能夠帶來(lái)總飛行代價(jià)最大變化的關(guān)鍵機(jī)場(chǎng).本文將任務(wù)優(yōu)化和節(jié)點(diǎn)重要性分析相結(jié)合, 為任務(wù)驅(qū)動(dòng)下的指揮決策提供了量化手段.

1 MTSP 問(wèn)題

TSP 是組合優(yōu)化算法中經(jīng)典的NP-hard 問(wèn)題[4],單個(gè)旅行商從某一城市出發(fā),經(jīng)過(guò)n個(gè)目標(biāo)城市,除起始城市外必須且只訪問(wèn)一次其他城市, 最后再回到出發(fā)點(diǎn).如何規(guī)劃訪問(wèn)路線以使旅行成本代價(jià)最低是旅行商問(wèn)題的關(guān)鍵.MTSP 是旅行商問(wèn)題的延伸, 其假設(shè)有多個(gè)旅行商人, 要訪問(wèn)n個(gè)目標(biāo)城市,除起始城市外必須且只訪問(wèn)一次其他城市.每個(gè)商人各從任一城市出發(fā),經(jīng)過(guò)不同的訪問(wèn)路線,最終回到各自出發(fā)點(diǎn), 如何規(guī)劃尋求各個(gè)旅行商最優(yōu)的訪問(wèn)路線是該問(wèn)題的關(guān)鍵.現(xiàn)實(shí)生活中很多問(wèn)題都可轉(zhuǎn)化為MTSP 問(wèn)題[11?15],比如多無(wú)人機(jī)協(xié)同航路規(guī)劃[1?3]、物流配送路徑優(yōu)化[5?7]問(wèn)題等.其具體模型如下:

其中,z表示旅行商訪問(wèn)城市總路線的距離,di j表示從城市i到城市j的距離,xij表示從城市i到城市j的訪問(wèn)情況.

約束條件:每個(gè)城市必須且只能被訪問(wèn)一次,轉(zhuǎn)化成數(shù)學(xué)表述即為式(2).

MTSP 問(wèn)題可以通過(guò)枚舉的方式求得最優(yōu)解,但隨著城市數(shù)目的增多,計(jì)算時(shí)間會(huì)急劇增加,無(wú)法滿足算法的實(shí)用性需求,因此,必須選擇合適的啟發(fā)式優(yōu)化算法, 在龐大的搜索空間中快速準(zhǔn)確地找到最優(yōu)可行解.

2 遺傳算法

遺傳算法是由自然界生物進(jìn)化理論演變而來(lái)的一種群體尋優(yōu)算法.它構(gòu)成的種群具有自組織自適應(yīng)的特征, 通過(guò)對(duì)構(gòu)成的種群進(jìn)行一系列評(píng)估、選擇、交叉和變異等操作最終求得問(wèn)題最優(yōu)解.算法通用流程如圖1 所示, 其中針對(duì)不同的問(wèn)題如何設(shè)計(jì)科學(xué)的編碼方式, 實(shí)現(xiàn)問(wèn)題解空間與編碼空間的一一對(duì)應(yīng), 是遺傳算法首先需要解決的問(wèn)題, 其次針對(duì)種群個(gè)體編碼, 采取何種遺傳操作有助于搜索最優(yōu)解是算法的核心, 最后如何權(quán)衡搜索和利用(exploration vs exploitation)之間的關(guān)系,避免陷入局部最優(yōu)是算法的重要環(huán)節(jié).

圖1 經(jīng)典遺傳算法流程圖Fig.1 Procedures of classical genetic algorithm

由于遺傳算法不受搜索空間的約束, 無(wú)需復(fù)雜的推導(dǎo)過(guò)程,以適應(yīng)度函數(shù)來(lái)引導(dǎo)整個(gè)搜索過(guò)程,對(duì)問(wèn)題本身的依賴性很小[10],因此,該方法廣泛運(yùn)用于生物工程、生產(chǎn)調(diào)度、自動(dòng)控制、工業(yè)工程和人工智能等領(lǐng)域.

3 問(wèn)題建模

3.1 問(wèn)題描述

停駐于前沿機(jī)場(chǎng)的各型電子偵察機(jī)是執(zhí)行戰(zhàn)場(chǎng)態(tài)勢(shì)感知、探測(cè)電子信號(hào)、發(fā)現(xiàn)兵力動(dòng)向的主要力量.一般情況下,電子偵察機(jī)的任務(wù)通常為從某一機(jī)場(chǎng)起飛, 沿規(guī)劃好的路徑飛抵沿途目標(biāo)上空進(jìn)行偵察并最終返回出發(fā)機(jī)場(chǎng), 期間每架飛機(jī)僅需對(duì)部分目標(biāo)實(shí)施偵察,其余目標(biāo)則由其他飛機(jī)完成,最終需實(shí)現(xiàn)所有目標(biāo)有且僅有一次被偵察.組織空中偵察任務(wù)需充分考慮偵察機(jī)的部署位置、最大航程、多機(jī)協(xié)同等問(wèn)題, 合理分配各個(gè)執(zhí)行偵察任務(wù)的飛機(jī)需要前往的目標(biāo)以及先后次序, 使得整個(gè)偵察過(guò)程代價(jià)最小.

假設(shè)現(xiàn)有m個(gè)機(jī)場(chǎng):A={A1,A2,··· ,Am}每個(gè)機(jī)場(chǎng)位置由唯一坐標(biāo)點(diǎn)確定,即〈axi,ayi〉為機(jī)場(chǎng)Ai的坐標(biāo)位置.

各個(gè)機(jī)場(chǎng)停駐的電子偵察機(jī)數(shù)目分別為n1,n2,··· ,nm,飛機(jī)數(shù)目總和為M=

i ni,即:

每架飛機(jī)最大航程為L(zhǎng), 存在映射函數(shù)θ :Pi∈P→Aj∈A表示各個(gè)飛機(jī)對(duì)應(yīng)的機(jī)場(chǎng).

現(xiàn)需調(diào)度偵察機(jī)實(shí)現(xiàn)對(duì)n個(gè)目標(biāo)實(shí)施偵察,即:

其中,每個(gè)目標(biāo)的位置坐標(biāo)記為〈txi,tyi〉.

任意兩點(diǎn)之間的距離可通過(guò)下式求得:

假設(shè)飛機(jī)在任意兩點(diǎn)之間沿直線飛行, 每架飛機(jī)最大航程約束為L(zhǎng),飛機(jī)p飛行路徑所包含的目標(biāo)集合記為PTp,該集合中目標(biāo)的排列順序即為飛機(jī)的偵察次序,完成任務(wù)后返回出發(fā)基地,整個(gè)行程距離記為lp.將參與偵察任務(wù)的所有飛機(jī)飛行距離之和作為目標(biāo)函數(shù),得到如下表達(dá)式:

為實(shí)現(xiàn)所有目標(biāo)有且僅有一次被飛機(jī)偵察且飛行路徑之和最短, 需合理指派各個(gè)執(zhí)行偵察任務(wù)的飛機(jī)沿特定順序航線對(duì)目標(biāo)進(jìn)行偵察, 而如何實(shí)現(xiàn)“機(jī)場(chǎng)–飛機(jī)–目標(biāo)” 之間的調(diào)度與路徑規(guī)劃是一個(gè)NP 難問(wèn)題.

如圖2 所示的偵察調(diào)度示例中, 機(jī)場(chǎng)A1 和A2分別駐有偵察機(jī)3 架和2 架,需要遍歷6 個(gè)藍(lán)色節(jié)點(diǎn)目標(biāo),其中機(jī)場(chǎng)A1 派出一架飛機(jī)沿路徑A1 →T1 →T2 →T3 →A1 對(duì)T1、T2 和T3 進(jìn)行偵察,機(jī)場(chǎng)A2派出一架飛機(jī)沿路徑A2 →T5 →T4 →T6 →A2 對(duì)T4、T5 和T6 進(jìn)行偵察.

圖2 空中偵察調(diào)度示意圖Fig.2 A schematic diagram for aerial scout scheduling

3.2 模型分析

空中偵察調(diào)度與路徑規(guī)劃問(wèn)題, 實(shí)質(zhì)上是一個(gè)運(yùn)籌學(xué)領(lǐng)域的尋優(yōu)問(wèn)題, 假設(shè)飛行空域沒(méi)有空中禁區(qū),且任意兩點(diǎn)之間都可以沿直線飛行.通過(guò)對(duì)飛機(jī)偵察路徑進(jìn)行規(guī)劃, 最終實(shí)現(xiàn)的優(yōu)化結(jié)果主要需考慮滿足以下因素:

1)參與任務(wù)的每架飛機(jī)按一定順序飛抵其需要偵察的目標(biāo), 且各個(gè)任務(wù)飛機(jī)最后均需返回各自出發(fā)機(jī)場(chǎng).

2)參與偵察任務(wù)的飛機(jī)飛行路徑距離之和為模型的目標(biāo)函數(shù),旨在實(shí)現(xiàn)總距離的最短.

3)每個(gè)目標(biāo)只被一架飛機(jī)進(jìn)行一次偵察.

4)執(zhí)行偵察任務(wù)的飛機(jī)飛行距離均滿足最大航程約束.

MTSP 用于求解多個(gè)個(gè)體在多個(gè)地點(diǎn)之間的路線規(guī)劃問(wèn)題,其使每個(gè)個(gè)體從某地點(diǎn)出發(fā),沿一條路線行進(jìn),使得每個(gè)地點(diǎn)有且僅有一個(gè)個(gè)體走過(guò),最后所有個(gè)體回到原來(lái)出發(fā)地點(diǎn),且總旅程最短.這類問(wèn)題通常關(guān)注于讓所有個(gè)體參與到地點(diǎn)遍歷過(guò)程中,盡可能實(shí)現(xiàn)各個(gè)個(gè)體路徑距離的平衡.上述各個(gè)機(jī)場(chǎng)的電子偵察機(jī)調(diào)度與路徑規(guī)劃問(wèn)題, 可以抽象成一個(gè)典型的多旅行商問(wèn)題,由于機(jī)場(chǎng)位置不同,各個(gè)機(jī)場(chǎng)停駐的飛機(jī)數(shù)量也不同,該問(wèn)題具備以下特點(diǎn):

1)需要明確哪些飛機(jī)將參與偵察任務(wù).

2)需要規(guī)劃飛機(jī)偵察目標(biāo)的先后順序.

3)需要確保飛機(jī)的飛行距離滿足約束.

3.3 模型求解

鑒于遺傳算法具有運(yùn)算簡(jiǎn)單、快速收斂等特點(diǎn),為求解該偵察調(diào)度優(yōu)化問(wèn)題, 研究嘗試通過(guò)改進(jìn)遺傳算法搜索最優(yōu)解,并針對(duì)問(wèn)題背景特點(diǎn),設(shè)計(jì)了可行的實(shí)現(xiàn)方法和操作流程.具體步驟包括: 1)種群個(gè)體編碼; 2)目標(biāo)函數(shù)設(shè)計(jì);3)種群個(gè)體選擇;4)個(gè)體交叉變異;5)局部?jī)?yōu)化搜索;6)選擇最優(yōu)個(gè)體.

種群個(gè)體編碼: 需要具有問(wèn)題解空間的完備特性,編碼空間和解空間最好能夠一一映射,將個(gè)體編碼代入目標(biāo)函數(shù)可產(chǎn)生相應(yīng)的適應(yīng)度值, 同時(shí)其還需體現(xiàn)個(gè)體的遺傳特性.為實(shí)現(xiàn)上述目的,編碼設(shè)計(jì)需能夠同時(shí)滿足飛機(jī)指派和飛行路徑規(guī)劃這兩個(gè)問(wèn)題背景,研究采用整數(shù)編碼進(jìn)行問(wèn)題求解.

具體而言,每個(gè)個(gè)體包含兩部分,一是對(duì)n個(gè)目標(biāo)進(jìn)行編碼:記為[1,2,3···n];二是對(duì)m個(gè)機(jī)場(chǎng)中的全部飛機(jī)進(jìn)行編碼,飛機(jī)數(shù)目總和為M=i ni,故所有飛機(jī)的對(duì)應(yīng)編碼為[n+1,n+2,n+3···n+M],該編碼中每一點(diǎn)位都對(duì)應(yīng)唯一的停駐機(jī)場(chǎng).將目標(biāo)編碼和飛機(jī)編碼進(jìn)行組合,得到一個(gè)編碼長(zhǎng)度為n+M的個(gè)體,其中,編碼中數(shù)值大于n的點(diǎn)位表示飛機(jī),數(shù)值小于等于n的點(diǎn)位表示偵察目標(biāo).為使個(gè)體編碼能夠完全表達(dá)問(wèn)題解的形式, 定義某飛機(jī)點(diǎn)位n+i其后相鄰且不間斷的目標(biāo)點(diǎn)位為該飛機(jī)需要偵察的目標(biāo)PTi, 飛行路徑為相應(yīng)的目標(biāo)點(diǎn)位先后順序.例如, 編碼為的個(gè)體片段中,數(shù)值為n+i的點(diǎn)位表示某飛機(jī)i,其后相鄰點(diǎn)位為偵察目標(biāo),數(shù)值為2 和3 的點(diǎn)位表示該飛機(jī)需要偵察的目標(biāo)T2和T3, 于是PTi= {T2,T3}, 假設(shè)該飛機(jī)位于機(jī)場(chǎng)Ai,那么其飛行路徑為Ai→T2→T3→Ai;數(shù)值為n+j的點(diǎn)位表示某飛機(jī)j, 由于其后一點(diǎn)位數(shù)值不代表目標(biāo),于是PTj= ?, 故該飛機(jī)不需要執(zhí)行偵察任務(wù).特別指出的是,如果某個(gè)體第一個(gè)點(diǎn)位數(shù)值不大于n, 則代表其為目標(biāo)節(jié)點(diǎn), 那么在對(duì)該個(gè)體進(jìn)行解析時(shí)需將該個(gè)體編碼向左進(jìn)行平移, 直至第一點(diǎn)位數(shù)值大于n.通過(guò)平移操作,可以實(shí)現(xiàn)所有的目標(biāo)點(diǎn)位都有相對(duì)應(yīng)的飛機(jī)點(diǎn)位, 也保證了飛機(jī)偵察路徑上包含了所有的目標(biāo).

如圖3 示例中, 目標(biāo)節(jié)點(diǎn)數(shù)目為n= 6, 即編碼數(shù)值為{1,2,3,4,5,6}.機(jī)場(chǎng)數(shù)目為n= 2, 即A={A1,A2},其中,機(jī)場(chǎng)A1停駐飛機(jī)3 架,相應(yīng)編碼數(shù)值為{7,8,9}, 機(jī)場(chǎng)A2停駐飛機(jī)2 架, 相應(yīng)編碼數(shù)值為{10,11}.對(duì)于圖3 所示個(gè)體,初始條件下生成的第1點(diǎn)位數(shù)值為5,表示目標(biāo)節(jié)點(diǎn),第2 點(diǎn)位數(shù)值為10,表示飛機(jī)節(jié)點(diǎn),故解析該編碼時(shí)需向左平移一位.平移后的個(gè)體編碼中第3 點(diǎn)位和第8 點(diǎn)位數(shù)值分別為8和10,表示執(zhí)行偵察任務(wù)的飛機(jī)節(jié)點(diǎn),且其后相鄰不間斷的目標(biāo)節(jié)點(diǎn)為對(duì)應(yīng)飛機(jī)的飛行路徑順序, 即飛機(jī)8 的飛行路徑記為:A1→T2→T3→T6→A1,飛機(jī)11 的飛行路徑記為:A2→T1→T4→T5→A2.

圖3 遺傳算法編碼示意圖Fig.3 A schematic diagram for the coding of genetic algorithm

目標(biāo)函數(shù)設(shè)計(jì): 能夠針對(duì)每個(gè)個(gè)體編碼生成相應(yīng)的適應(yīng)度, 并通過(guò)懲罰策略將約束條件引入目標(biāo)函數(shù)中, 將帶約束問(wèn)題轉(zhuǎn)化為無(wú)約束問(wèn)題.本研究注重每架飛機(jī)的飛行距離小于其最大航程, 且所有飛機(jī)飛行距離之和最小.對(duì)于P= {P1,P2,··· ,PM}中的任一飛機(jī)Pi, 其在個(gè)體編碼中對(duì)應(yīng)的數(shù)值為n+i, 停駐機(jī)場(chǎng)為Aj= θ(Pi), 執(zhí)行偵察任務(wù)的路徑長(zhǎng)度記為li, 飛行路徑所包含的目標(biāo)節(jié)點(diǎn)為PTi={Ts,··· ,Td},其中節(jié)點(diǎn)順序即為飛行過(guò)程中的偵察順序,那么該飛機(jī)飛行路徑長(zhǎng)度計(jì)算結(jié)果為:

綜上所述,所有飛行路徑距離總和記為:

將約束條件帶入目標(biāo)函數(shù)中, 得到個(gè)體適應(yīng)度計(jì)算表達(dá)式為:

其中,λ>1 為違背約束條件的懲罰系數(shù).

種群個(gè)體選擇: 有利于將當(dāng)前適應(yīng)度較高的個(gè)體保留到下一代中,經(jīng)典的方法包括輪盤賭方法、錦標(biāo)賽方法、精英個(gè)體保留方法等.為確保最優(yōu)個(gè)體遺傳到下一代的同時(shí), 適應(yīng)度值大的個(gè)體也能盡量保留, 本研究采取精英個(gè)體保留方法與輪盤賭方法相結(jié)合的策略進(jìn)行種群個(gè)體選擇, 其中在整個(gè)種群中選擇k個(gè)精英個(gè)體優(yōu)先予以保留,然后按照正比選擇的方法選取剩余N?k個(gè)個(gè)體.具體操作步驟為:

1)將當(dāng)前種群中所有個(gè)體按照適應(yīng)度大小順序進(jìn)行排序.

2)選取top-k個(gè)體進(jìn)入下一代.

3)以概率選取種群中第i個(gè)個(gè)體進(jìn)入下一代.

4)重復(fù)步驟3),直至下一代群體規(guī)模到達(dá)N.

個(gè)體交叉變異:是遺傳算法的精髓,其通過(guò)對(duì)當(dāng)前種群個(gè)體解進(jìn)行交叉與變異,產(chǎn)生更優(yōu)的個(gè)體.基于上述個(gè)體編碼方式, 研究采用部分匹配交叉和反轉(zhuǎn)變異的方式進(jìn)行遺傳操作,其中,交叉事件發(fā)生的概率為pc, 變異事件發(fā)生的概率為pm, 其主要模擬生物學(xué)中的基因突變,所以概率一般較低.

對(duì)于部分匹配交叉, 首先從種群中隨機(jī)選取兩個(gè)個(gè)體Ia和Ib,然后隨機(jī)選擇兩個(gè)切點(diǎn),將兩個(gè)切點(diǎn)之間的點(diǎn)位片段互換,生成的兩個(gè)新個(gè)體和由于新個(gè)體編碼可能存在重復(fù)或遺漏,因此,需要對(duì)其進(jìn)行相應(yīng)的修復(fù), 以恢復(fù)個(gè)體與解之間映射關(guān)系的合法性, 具體而言需要對(duì)交叉片段之外編碼進(jìn)行去重,并依次補(bǔ)入缺失的點(diǎn)位.在圖4 所示的種群個(gè)體交叉過(guò)程示意圖中, 由于交叉后的片段點(diǎn)位編碼與已有點(diǎn)位編碼相同(例如左側(cè)個(gè)體中的編碼4),同時(shí)又有一些編碼存在缺失(例如左側(cè)個(gè)體中的編碼3),這就需要將已有片段中相同的編碼進(jìn)行去重, 同時(shí)將缺失的編碼按順序補(bǔ)入即可.

圖4 種群個(gè)體交叉示意圖Fig.4 A schematic diagram for crossover of individuals

對(duì)于個(gè)體變異操作, 該操作有利于增加種群多樣性, 避免陷入局部最優(yōu).本研究采取反轉(zhuǎn)變異, 具體而言需在個(gè)體中隨機(jī)選擇兩個(gè)切點(diǎn), 并將二者之間的點(diǎn)位編碼完全反轉(zhuǎn)如圖5 所示.

圖5 反轉(zhuǎn)變異操作示意圖Fig.5 A schematic diagram for mutation of individuals

局部?jī)?yōu)化搜索: 是遺傳算法中為了加速進(jìn)化采取的一種操作,通過(guò)局部搜索針對(duì)一個(gè)較小的區(qū)域,致力于找到更好、更精確的解.一般來(lái)說(shuō),遺傳算法在起始階段注重廣域搜索,隨著迭代的進(jìn)行,局部搜索的作用逐漸顯現(xiàn).在上述經(jīng)典的遺傳算法基礎(chǔ)上,本研究對(duì)相鄰偵察路徑編碼片段進(jìn)行合并操作, 搜索其中性能最優(yōu)的個(gè)體.通過(guò)局部?jī)?yōu)化搜索,能夠減少無(wú)效的交叉變異操作, 驅(qū)動(dòng)可行解向最優(yōu)解方向移動(dòng),這也是改進(jìn)遺傳算法的核心.

例如在局部?jī)?yōu)化操作中, 隨機(jī)選取一組相鄰的飛行路徑Pi+PTi和Pj+PTj,將二者合并共產(chǎn)生如下所示8 種可能路徑, 進(jìn)行局部?jī)?yōu)化搜索需從中選擇最優(yōu)方案:

其中,為PTi編碼的逆序.在下述案例中,某個(gè)體一段編碼形式為[···n+i,2,3,n+j,4,5,n+k···],其中由飛機(jī)n+i進(jìn)行偵察的目標(biāo)編碼為[2,3],由飛機(jī)n+j進(jìn)行偵察的目標(biāo)編碼為[4,5],而且這兩段編碼相鄰, 那么進(jìn)行局部?jī)?yōu)化搜索需要將二者進(jìn)行合并,生成一條新的路徑,可行的合并方式如圖6 所示.

圖6 局部搜索示例圖Fig.6 A schematic diagram for local search

選擇最優(yōu)個(gè)體:在經(jīng)過(guò)多次遺傳迭代之后,在種群中選取性能最優(yōu)的個(gè)體作為最終解.最終解的穩(wěn)定性和收斂性是評(píng)價(jià)遺傳算法的一項(xiàng)重要指標(biāo).

3.4 重要性排序

鑒于各個(gè)機(jī)場(chǎng)的位置不同, 且停駐的飛機(jī)數(shù)量也不相同, 為衡量各個(gè)機(jī)場(chǎng)在偵察調(diào)度中的重要性程度, 研究采取節(jié)點(diǎn)移除的方法, 從中移除某機(jī)場(chǎng),然后求解剩余機(jī)場(chǎng)中飛機(jī)完成偵察任務(wù)的最小路徑長(zhǎng)度之和S.比較機(jī)場(chǎng)移除前后S的變化情況,即可確定該機(jī)場(chǎng)的重要性程度,即

其中,S(A)為所有機(jī)場(chǎng)不變情況下最小路徑長(zhǎng)度之和,S(AAi)為移除機(jī)場(chǎng)Ai之后的最小路徑長(zhǎng)度之和.

4 案例分析

在本案例中,5 個(gè)機(jī)場(chǎng)共18 架偵察機(jī)需對(duì)20 個(gè)目標(biāo)實(shí)施偵察,如圖7 所示.

圖7 機(jī)場(chǎng)與目標(biāo)位置示意圖Fig.7 The location map of airports and targets

本案例共有5 個(gè)機(jī)場(chǎng)A={A0,A1,A2,A3,A4},其坐標(biāo)位置及停駐電子偵察機(jī)數(shù)目如表1 所示, 其中每架偵察機(jī)最大航程為L(zhǎng)=3 000 km.

表1 機(jī)場(chǎng)坐標(biāo)及飛機(jī)配置表Table 1 The coordinates and airplanes of airports

各電子偵察機(jī)需對(duì)20 個(gè)目標(biāo)實(shí)施偵察,各個(gè)目標(biāo)的位置數(shù)據(jù)為:

表2 偵察目標(biāo)坐標(biāo)位置表Table 2 The coordinates of targets

4.1 經(jīng)典遺傳算法

首先, 采用經(jīng)典的遺傳算法求解該問(wèn)題, 其中編碼方式、目標(biāo)函數(shù)和交叉變異的操作如上所述,不進(jìn)行局部?jī)?yōu)化操作.種群規(guī)模N= 200, 遺傳代數(shù)T= 20 000, 交叉概率為pc= 0.5, 變異概率為pm=0.05,在精英保留和輪盤賭混合策略中選取top-3 最優(yōu)個(gè)體優(yōu)先予以保留,目標(biāo)函數(shù)中違背約束條件的懲罰系數(shù)λ = 5.重復(fù)獨(dú)立運(yùn)行200 次實(shí)驗(yàn), 得到一系列偵察路徑最短距離,其均值與最大值、最小值如表3 所示.

表3 經(jīng)典遺傳算法求解性能Table 3 Performance of classical genetic algorithm

運(yùn)用經(jīng)典遺傳算法求解得到的最優(yōu)解如圖8 所示, 其中可以發(fā)現(xiàn)最優(yōu)解依賴于從機(jī)場(chǎng)A2 和A4 起飛的飛機(jī),其中,最優(yōu)路徑有兩條,即:

圖8 不同情況下最優(yōu)偵察路徑示意圖Fig.8 The optimal path for aerial scout in different cases

移除機(jī)場(chǎng)A2 和機(jī)場(chǎng)A4 對(duì)最優(yōu)解的影響較大,故二者重要性較高, 整個(gè)機(jī)場(chǎng)重要性排序結(jié)果為:A2>A4>A0=A1=A3

4.2 改進(jìn)遺傳算法

在改進(jìn)的遺傳算法中, 編碼方式、目標(biāo)函數(shù)和交叉變異操作如上所述,同時(shí)增加局部?jī)?yōu)化操作.種群規(guī)模N= 200, 遺傳代數(shù)T= 20 000, 交叉概率為pc= 0.5, 變異概率為pm= 0.05, 局部搜索概率為ps=0.2,在精英保留和輪盤賭混合策略中選取top-3最優(yōu)個(gè)體優(yōu)先予以保留, 目標(biāo)函數(shù)中違背約束條件的懲罰系數(shù)λ = 5.重復(fù)獨(dú)立運(yùn)行200 次實(shí)驗(yàn), 得到一系列偵察路徑最短距離,其均值與最大值、最小值如表4 所示.

由表4 可以看出, 改進(jìn)的遺傳算法在求解性能上要優(yōu)于經(jīng)典的遺傳算法, 盡管二者在偵察路徑最短距離的最小值上并無(wú)差異, 但是通過(guò)加入局部?jī)?yōu)化搜索, 改進(jìn)的遺傳算法能夠有效降低偵察路徑最短距離的均值,使其更接近最優(yōu)解.另外,機(jī)場(chǎng)A2 和A4 的移除,能夠帶來(lái)最短距離的提升,表明了二者在偵察任務(wù)中的重要地位.癱瘓機(jī)場(chǎng)A2 或A4 能夠?qū)е抡麄€(gè)偵察任務(wù)性能的下降, 然而癱瘓其他機(jī)場(chǎng)則不會(huì)帶來(lái)相應(yīng)的變化, 凸顯了任務(wù)優(yōu)化和目標(biāo)排序二者之間內(nèi)在的關(guān)聯(lián).

表4 改進(jìn)遺傳算法求解性能Table 4 Performance of improved genetic algorithm

5 結(jié)論

本文圍繞多機(jī)場(chǎng)、多架次、多目標(biāo)空中偵察調(diào)度和目標(biāo)重要性分析問(wèn)題, 以MTSP 問(wèn)題為基礎(chǔ)構(gòu)建偵察機(jī)調(diào)度與路徑規(guī)劃模型, 并設(shè)計(jì)了一種改進(jìn)的遺傳算法對(duì)該模型進(jìn)行求解, 來(lái)獲取其最優(yōu)的偵察目標(biāo)分配方案和飛行航跡路線.為衡量不同機(jī)場(chǎng)在偵察任務(wù)中的重要程度, 本研究采用節(jié)點(diǎn)移除法量化某個(gè)機(jī)場(chǎng)癱瘓失效后, 對(duì)整個(gè)偵察任務(wù)完成性能的影響, 并以偵察飛行距離變化量為指標(biāo)對(duì)機(jī)場(chǎng)目標(biāo)進(jìn)行重要性排序, 從而為目標(biāo)選擇和打擊決策提供支持.最后,一系列實(shí)驗(yàn)結(jié)果驗(yàn)證了該方法的有效性和科學(xué)性.