王里付，朱新平

(1.中國(guó)人民解放軍95337部隊(duì)司令部，廣西 柳州 545112;2.南京航空航天大學(xué)民航學(xué)院，江蘇 南京 210016)

隨著綜合國(guó)力的增強(qiáng)，一大批先進(jìn)戰(zhàn)機(jī)列裝空軍。在這種情況下，為適應(yīng)高強(qiáng)度訓(xùn)練需要，軍航必將占用更多空域，而目前專用的軍航訓(xùn)練空域建設(shè)滯后，因而導(dǎo)致空域資源緊張，尤其對(duì)某些以基地化保障模式為主的機(jī)場(chǎng)，這種現(xiàn)象更為突出[1]。因此，科學(xué)合理地安排飛行訓(xùn)練計(jì)劃，以便高效安全地使用訓(xùn)練空域，成為當(dāng)前航空兵部隊(duì)訓(xùn)練面臨的緊迫問(wèn)題。筆者主要對(duì)航空兵部隊(duì)飛行訓(xùn)練計(jì)劃優(yōu)化編排問(wèn)題開(kāi)展研究。

航空兵部隊(duì)飛行訓(xùn)練通過(guò)飛行計(jì)劃來(lái)組織，而飛行計(jì)劃則由若干科目構(gòu)成，科目是實(shí)際飛行訓(xùn)練的最小組織單元。飛行訓(xùn)練過(guò)程中，各科目對(duì)空域并發(fā)動(dòng)態(tài)占用和釋放，對(duì)訓(xùn)練空域的科學(xué)管理提出了挑戰(zhàn)。在一定條件約束下，如何統(tǒng)籌安排各科目對(duì)訓(xùn)練空域占用的起止時(shí)間，以提高空域利用效率，即為筆者所研究的航空兵部隊(duì)飛行訓(xùn)練計(jì)劃優(yōu)化編排問(wèn)題。

以往關(guān)于航空兵部隊(duì)飛行訓(xùn)練的研究多集中在仿真系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[2－6]，以及飛行訓(xùn)練后勤保障方面[7－9]，對(duì)訓(xùn)練計(jì)劃本身的優(yōu)化編排則缺乏研究。文獻(xiàn)[2]指出飛行訓(xùn)練過(guò)程中，戰(zhàn)機(jī)群運(yùn)行體現(xiàn)出典型的離散事件特征。Petri網(wǎng)作為一種適合描述離散事件動(dòng)態(tài)系統(tǒng)的工具，非常適合用于描述和分析飛行訓(xùn)練科目對(duì)空域的占用[10]。但采用Petri網(wǎng)建模訓(xùn)練科目對(duì)空域占用過(guò)程，模型狀態(tài)的變化受制于初始標(biāo)識(shí)和模型結(jié)構(gòu)，很難實(shí)現(xiàn)托肯所代表的科目對(duì)空域占用過(guò)程的自動(dòng)優(yōu)化?？紤]到遺傳算法(genetic algorithm，GA)具有良好的全局尋優(yōu)能力[11]，筆者采用賦時(shí)庫(kù)所Petri網(wǎng)TPPN建立訓(xùn)練科目對(duì)空域占用過(guò)程模型，并將其與GA結(jié)合，實(shí)現(xiàn)飛行訓(xùn)練計(jì)劃的優(yōu)化編排。

1 基于TPPN的飛行訓(xùn)練空域占用過(guò)程建模

1.1 飛行訓(xùn)練對(duì)空域資源的占用

飛行訓(xùn)練計(jì)劃是指占場(chǎng)時(shí)間之內(nèi)，各科目對(duì)訓(xùn)練空域的占用起止時(shí)間。如表1所示，需要為4 種訓(xùn)練科目制定訓(xùn)練計(jì)劃，A1、A2、A3、A4為可供安排訓(xùn)練科目的空域。在實(shí)際飛行訓(xùn)練過(guò)程中，一個(gè)空域可能同時(shí)安排多個(gè)科目，也可能只安排一個(gè)科目。對(duì)所有空域進(jìn)行邏輯劃分，使得每一邏輯空域只能同時(shí)被一個(gè)科目占用。由于不同空域具有不同的空間結(jié)構(gòu)，因此，同一科目在不同空域運(yùn)行時(shí)可能需要不同的時(shí)間。如表1中，A2/(23)，A3/(12)表示科目1選擇A2作為訓(xùn)練空域需要23個(gè)單位時(shí)間，而在空域A3內(nèi)飛行時(shí)需要12個(gè)單位時(shí)間。

表1 訓(xùn)練飛行科目對(duì)空域資源的占用需求

從表1可以看出，為同時(shí)安排上述科目的飛行訓(xùn)練計(jì)劃，需考慮科目－空域占用調(diào)度問(wèn)題，由于科目安排在不同的空域，執(zhí)行的順序不同，完成整個(gè)訓(xùn)練計(jì)劃所需的空域占用時(shí)間也就不同，從而影響空域的使用效率，調(diào)度不合理也會(huì)帶來(lái)空域資源占用沖突問(wèn)題。如科目3和科目4均可占用空域A2，而先被哪一個(gè)科目占用則應(yīng)根據(jù)計(jì)劃優(yōu)化編排的優(yōu)化目標(biāo)來(lái)決定。這里考慮的最優(yōu)調(diào)度是完成所有訓(xùn)練科目，滿足所需空域占用時(shí)間最短、無(wú)科目結(jié)束時(shí)刻相同這兩個(gè)目標(biāo)的科目－空域調(diào)度序列。為了得到最優(yōu)序列，首先建立飛行訓(xùn)練對(duì)空域占用過(guò)程的賦時(shí)庫(kù)所Petri網(wǎng)模型。

1.2 飛行訓(xùn)練科目對(duì)空域占用的TPPN模型

定義 1[12]TPPN 定義為 TPPN={P，T，I，O，M0，φ}。其中，P為庫(kù)所集;T為變遷集，且滿足P∩T≠Φ，P∪T≠Φ;I，O分別為模型的前向和后向關(guān)聯(lián)矩陣;M0為模型初始標(biāo)識(shí);φ:P→D定義為庫(kù)所每次被標(biāo)識(shí)應(yīng)持續(xù)的時(shí)間，其中，D={dτ0，dτ1，…，dτn}為持續(xù)時(shí)間集合。

TPPN變遷使能規(guī)則為:對(duì)變遷t∈T，若庫(kù)所pi∈(p)t被標(biāo)識(shí)的時(shí)刻為xi，對(duì)應(yīng)的持續(xù)標(biāo)識(shí)時(shí)間為 dτi，當(dāng)所有 pi∈(p)t均被標(biāo)識(shí)，且當(dāng)前時(shí)間時(shí)，該變遷被使能。

TPPN變遷激發(fā)規(guī)則為:當(dāng)變遷使能規(guī)則滿足后，便可以激發(fā)。激發(fā)過(guò)程為瞬時(shí)，可以輸出一個(gè)托肯到其輸出庫(kù)所。托肯到達(dá)庫(kù)所后，便可形成新的標(biāo)識(shí)。

結(jié)合一個(gè)實(shí)例，說(shuō)明用TPPN建立科目－空域占用過(guò)程模型的方法和步驟。

(1)用TPPN建立單個(gè)飛行訓(xùn)練科目對(duì)某一空域的占用過(guò)程模型，如圖1所示。在該模型中，有庫(kù)所、變遷、弧和托肯。其中，庫(kù)所Ak表示對(duì)應(yīng)訓(xùn)練空域k(k=1，2，…，n)的狀態(tài)，若該庫(kù)所被標(biāo)識(shí)，則表示對(duì)應(yīng)的訓(xùn)練空域可被占用。其他庫(kù)所則表示該科目所處的執(zhí)行狀態(tài)，分為3種:①psi為科目i(i=1，2，…，n)初始狀態(tài)庫(kù)所，表示對(duì)應(yīng)訓(xùn)練科目的準(zhǔn)備狀態(tài)，其中托肯數(shù)為這類科目的數(shù)量;②pij為科目 i的第 j種執(zhí)行狀態(tài)庫(kù)所，dτij為對(duì)應(yīng)的空域占用時(shí)間;③pei為科目i的執(zhí)行完成狀態(tài)庫(kù)所。當(dāng)其中托肯數(shù)等于psi中的初始托肯數(shù)時(shí)，表明科目i的所有訓(xùn)練任務(wù)均被執(zhí)行完成。

圖1 單個(gè)科目對(duì)某一空域的占用過(guò)程模型

(2)建立飛行訓(xùn)練科目－空域占用關(guān)系表，如表2所示，該表描述了各個(gè)科目可在哪些空域中完成，及其對(duì)應(yīng)的空域占用時(shí)間。為建立與對(duì)應(yīng)的科目－空域占用TPPN模型的聯(lián)系，在表2中還給出了科目每一次空域占用過(guò)程對(duì)應(yīng)的賦時(shí)庫(kù)所，其中，A1、A2、A3、A4表示可占用的訓(xùn)練空域。以科目1為例，該科目有兩種執(zhí)行方案，分別為:①在空域A2中執(zhí)行23個(gè)單位時(shí)間后退出該空域;②在空域A3中執(zhí)行12個(gè)單位時(shí)間后退出該空域。對(duì)應(yīng)的賦時(shí)庫(kù)所分別為p11、p12。

表2 飛行訓(xùn)練科目－空域占用關(guān)系表

(3)利用飛行訓(xùn)練科目－空域占用關(guān)系表，關(guān)聯(lián)已建立的所有單個(gè)科目－空域占用TPPN模型。模型僅通過(guò)庫(kù)所狀態(tài)的變化描述訓(xùn)練科目某次執(zhí)行對(duì)某一個(gè)空域的占用過(guò)程，并沒(méi)有體現(xiàn)科目執(zhí)行過(guò)程對(duì)多個(gè)空域的選擇性占用可能。為了全面直觀地描述所有科目對(duì)空域的占用過(guò)程，必須在此基礎(chǔ)上結(jié)合科目－空域占用關(guān)系表，建立更為完善的科目－空域占用TPPN模型。以科目1和科目2為例，結(jié)合表2，說(shuō)明如何關(guān)聯(lián)起所建立的單個(gè)科目－空域占用TPPN模型，可分3個(gè)步驟進(jìn)行:①對(duì)單個(gè)科目－空域占用過(guò)程模型進(jìn)行擴(kuò)展，增加選擇庫(kù)所sij，描述科目i的第j種執(zhí)行選擇。如圖2(a)中，庫(kù)所s11、s12為科目1對(duì)應(yīng)的兩種執(zhí)行方案的選擇庫(kù)所，當(dāng)某一選擇庫(kù)所被標(biāo)識(shí)時(shí)，表明其對(duì)應(yīng)的科目－空域占用方案被選擇，空域占用時(shí)間則可根據(jù)對(duì)應(yīng)的賦時(shí)庫(kù)所p11和p12以及表2來(lái)確定。②對(duì)步驟①所得到的單個(gè)科目－空域占用擴(kuò)展模型，將其中屬于同一類科目的模型進(jìn)行聯(lián)合，如圖2(b)是由圖2(a)聯(lián)合得到。在圖2(a)中，變遷t0和t1均描述科目1對(duì)空域的占用，可將其前向庫(kù)所集中的科目初始狀態(tài)庫(kù)所合并;同理，變遷t2和t3均描述科目1對(duì)空域的釋放，可將其后向庫(kù)所集中的科目完成狀態(tài)庫(kù)所合并。③對(duì)其他類科目的科目－空域占用過(guò)程模型進(jìn)行上述步驟①和步驟②操作，可得到所有科目－空域占用過(guò)程的完整TPPN模型。需要說(shuō)明的是，在最終得到的TPPN模型中，所有名稱相同的訓(xùn)練空域庫(kù)所作為同一庫(kù)所對(duì)待。為了繪圖方便，同一空域庫(kù)所可多次出現(xiàn)。

圖2 單個(gè)科目－空域的占用TPPN模型關(guān)聯(lián)過(guò)程

2 飛行訓(xùn)練計(jì)劃編排的優(yōu)化

由TPPN模型可知，每一類科目均可選擇不同的空域來(lái)執(zhí)行。飛行訓(xùn)練計(jì)劃編排的優(yōu)化需要考慮多方面的因素，屬于NP難問(wèn)題。在TPPN仿真過(guò)程中，通過(guò)用GA控制模型相關(guān)選擇庫(kù)所中托肯的配置，使得其變遷的激發(fā)過(guò)程得到優(yōu)化，從而滿足設(shè)定的計(jì)劃編排優(yōu)化目標(biāo)。GA的顯著特點(diǎn)是可以同時(shí)對(duì)搜索空間中的多個(gè)解進(jìn)行評(píng)估，具有較好的全局優(yōu)化能力。

2.1 染色體編碼

用GA對(duì)科目－空域占用方案進(jìn)行規(guī)劃，首先需要建立空域占用方案與染色體之間的一種對(duì)應(yīng)關(guān)系。根據(jù)訓(xùn)練計(jì)劃編排的特點(diǎn)，所設(shè)計(jì)染色體根據(jù)科目類型分成多段，每段染色體的長(zhǎng)度為該類型科目將要執(zhí)行的次數(shù)，且每個(gè)基因?qū)?yīng)一個(gè)該類型科目的選擇庫(kù)所。從圖2可以看出，每種類型的科目可選擇不同的空域進(jìn)行訓(xùn)練。如在圖2中，庫(kù)所s11和s12為科目1的選擇庫(kù)所集合。在安排每個(gè)訓(xùn)練科目時(shí)，均可從對(duì)應(yīng)的選擇庫(kù)所集合中隨機(jī)選擇，作為染色體的基因，同時(shí)也就表明對(duì)應(yīng)的空域占用方案被選擇。如選擇了s11作為染色體基因，就表示科目1在執(zhí)行過(guò)程中將選擇占用空域A2。將每種類型科目多次執(zhí)行過(guò)程對(duì)應(yīng)的選擇庫(kù)所依次排列，形成一條染色體，即可表示一個(gè)完整的飛行計(jì)劃編排方案，如圖3所示。

圖3 染色體編碼方案

2.2 適應(yīng)度函數(shù)

研究的目標(biāo)是所有訓(xùn)練科目均完成時(shí)，所需空域占用時(shí)間最短，且空域占用過(guò)程中無(wú)任何兩個(gè)科目結(jié)束時(shí)刻相同，以便實(shí)現(xiàn)高效、安全地利用訓(xùn)練空域。

(1)科目每次執(zhí)行過(guò)程占用空域時(shí)間的取得。根據(jù)染色體所規(guī)定的空域占用方案控制TPPN模型的運(yùn)行，直到所有科目初始狀態(tài)庫(kù)所和執(zhí)行狀態(tài)庫(kù)所中的托肯數(shù)均為0。此時(shí)表明該TPPN模型完成了所有科目的空域占用過(guò)程，在該過(guò)程中，記錄每一次科目執(zhí)行過(guò)程中的空域結(jié)束時(shí)間。

(2)染色體適應(yīng)度函數(shù)。根據(jù)各科目每次執(zhí)行過(guò)程占用空域的時(shí)間，可求得各個(gè)空域占用的時(shí)間time(Ai)。以各空域占用時(shí)間最大值中的最小值作為整個(gè)空域的占用時(shí)間，即取染色體適應(yīng)度函數(shù)為 f=min{max[time(Ai)]}。

2.3 遺傳操作

對(duì)所獲得的初始種群進(jìn)行基本的遺傳操作:

(1)選擇。選擇是為了從當(dāng)前群體中確定優(yōu)良的個(gè)體，使其作為父代繁殖下一代種群。可采用首先計(jì)算適應(yīng)度數(shù)值，然后按照輪盤賭選擇的方法確定新的種群。

(2)交叉。采用兩點(diǎn)交叉方法，即在雙親的染色體上隨機(jī)地選擇兩個(gè)固定的點(diǎn)，然后將這兩個(gè)點(diǎn)之間的基因進(jìn)行交換。圖4(a)為兩個(gè)用于交叉操作的父代染色體，隨機(jī)確定兩個(gè)交叉點(diǎn)P和D，然后交換兩個(gè)交叉點(diǎn)之間的部分染色體，得到子代染色體如圖4(b)所示。

圖4 兩點(diǎn)交叉法

(3)變異。變異是指對(duì)種群中的每個(gè)個(gè)體，以某一概率隨機(jī)地改變某個(gè)或某些基因座上的基因值。操作方法是:在個(gè)體中隨機(jī)選擇一個(gè)位置作為變異點(diǎn)，確定其對(duì)應(yīng)的選擇庫(kù)所集，從中重新隨機(jī)地選擇一個(gè)基因來(lái)替代原來(lái)的基因。

3 試驗(yàn)驗(yàn)證

采用基于Petri網(wǎng)與GA的飛行訓(xùn)練計(jì)劃優(yōu)化編排方法，對(duì)某一預(yù)定的訓(xùn)練任務(wù)計(jì)劃編排進(jìn)行試驗(yàn)研究。該訓(xùn)練任務(wù)包含7種訓(xùn)練科目，其中前4種的執(zhí)行次數(shù)和科目－空域占用關(guān)系表如表1和表2所示，后3種的科目－空域占用關(guān)系表如表3和表4所示。

表3 訓(xùn)練科目及其對(duì)空域資源的占用

表4 科目－空域占用關(guān)系表

根據(jù)表1～表4，并利用所給的TPPN模型建立方法，可構(gòu)建完整的飛行科目－空域占用過(guò)程TPPN模型，利用提出的算法進(jìn)行訓(xùn)練飛行計(jì)劃優(yōu)化編排。在該過(guò)程中，考慮到GA的隨機(jī)性，分別設(shè)置不同的進(jìn)化代數(shù)進(jìn)行20次試驗(yàn)。結(jié)果表明，當(dāng)進(jìn)化代數(shù)為40代時(shí)，優(yōu)化效果已較為理想，整個(gè)試驗(yàn)過(guò)程所得優(yōu)化結(jié)果如表5所示。

表5 優(yōu)化結(jié)果

圖5為其中一次最佳優(yōu)化過(guò)程對(duì)應(yīng)的曲線，對(duì)應(yīng)各試驗(yàn)參數(shù)設(shè)置為:代溝GGAP=0.9，交叉概率XOVR=0.8，變異概率MUTR=0.2，初始種群數(shù)量NIND=20，迭代次數(shù)為MAXGEN=40。此時(shí)空域占用時(shí)間為99個(gè)單位時(shí)間，其對(duì)應(yīng)的染色體為s12s11s21s21s33s32s31s41s41s53s53s51s61s61s61s71s72，且各科目占用空域 A1、A2、A3、A4的甘特圖如圖6所示。

圖5 訓(xùn)練計(jì)劃編排仿真優(yōu)化過(guò)程曲線

圖6 飛行訓(xùn)練計(jì)劃中科目占用空域甘特圖

4 結(jié)論

根據(jù)航空兵部隊(duì)飛行訓(xùn)練對(duì)空域占用的特點(diǎn)，建立了科目－空域占用過(guò)程的TPPN模型，并基于該模型對(duì)訓(xùn)練計(jì)劃優(yōu)化編排問(wèn)題進(jìn)行了研究。一方面描述了各科目對(duì)空域的并發(fā)占用和釋放，以及空域占用之間的約束關(guān)系;另一方面，把建立的TPPN模型與飛行訓(xùn)練計(jì)劃優(yōu)化編排聯(lián)系起來(lái)，采用GA對(duì)模型中的選擇庫(kù)所托肯配置進(jìn)行優(yōu)化，滿足了既定的優(yōu)化目標(biāo)。仿真結(jié)果表明，該方法為航空兵部隊(duì)飛行訓(xùn)練計(jì)劃的自動(dòng)優(yōu)化編排提供了有效的技術(shù)支持。下一步的研究主要包括降低大規(guī)模訓(xùn)練科目－空域占用過(guò)程TPPN模型建立的難度，以及在計(jì)劃編排時(shí)考慮更多的限制因素，如飛行人員和指揮員的指揮能力等。

[1] 王里付.軍航使用條件下的空域容量評(píng)估及優(yōu)化方法研究[D].南京:南京航空航天大學(xué)圖書館，2010.

[2] 劉志勤.基于Petri網(wǎng)模型的航空兵仿真研究[J].陜西師范大學(xué)學(xué)報(bào):自然科學(xué)版，2005，33(1):221－223.

[3] 高惠英，王恒霖.美國(guó)空軍的分布式仿真訓(xùn)練系統(tǒng)[J].飛航導(dǎo)彈，1999(2):35 －37.

[4] 石玉峰，蒲建春.空軍戰(zhàn)役訓(xùn)練仿真系統(tǒng)體系結(jié)構(gòu)及典型模型研究[J].兵工自動(dòng)化，2010，29(1):47 －49.

[5] 李杰，陳蕾，周俊杰，等.基于仿真的飛行模擬器優(yōu)化配置研究[J].系統(tǒng)仿真技術(shù)，2010，6(4):323 －327.

[6] 堯豐，韓松臣，朱新平.低空空域綜合管理系統(tǒng)軟件架構(gòu)研究[J].武漢理工大學(xué)學(xué)報(bào):信息與管理工程版，2010，32(2):257 －260.

[7] 張榮培，邢建春.軍用機(jī)場(chǎng)場(chǎng)務(wù)保障決策支持系統(tǒng)研究[J].四川兵工學(xué)報(bào)，2010，31(8):32 －35.

[8] 邵曉根.應(yīng)用混合遺傳算法求解飛機(jī)牽引調(diào)度問(wèn)題[J].微電子學(xué)與計(jì)算機(jī)，2009，26(10):82 －85.

[9] 張兵，韓曉明，賀沁榮.空軍機(jī)場(chǎng)綜合評(píng)價(jià)模型[J].四川兵工學(xué)報(bào)，2009，30(7):95 －97.

[10] 袁崇義.Petri網(wǎng)原理[M].北京:北京大學(xué)出版社，1999:21－26.

[11] 雷英杰，張善，李續(xù)武，等.MATLAB遺傳算法工具箱及其應(yīng)用[M].西安:西安電子科技大學(xué)出版社，2009:12－14.

[12] 李慧芳，范玉順.基于Petri網(wǎng)仿真的批處理過(guò)程動(dòng)態(tài)調(diào)度[J].系統(tǒng)仿真學(xué)報(bào)，2002，14(7):928 －931.