基于Petri網(wǎng)和遺傳算法的飛行訓(xùn)練計劃優(yōu)化編排

王里付，朱新平

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 單個科目對某一空域的占用過程模型

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

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

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

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

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

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

2.1 染色體編碼

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

圖3 染色體編碼方案

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

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

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

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

2.3 遺傳操作

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

(1)選擇。選擇是為了從當(dāng)前群體中確定優(yōu)良的個體，使其作為父代繁殖下一代種群?？刹捎檬紫扔嬎氵m應(yīng)度數(shù)值，然后按照輪盤賭選擇的方法確定新的種群。

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

圖4 兩點交叉法

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

3 試驗驗證

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

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

[4] 石玉峰，蒲建春.空軍戰(zhàn)役訓(xùn)練仿真系統(tǒng)體系結(jié)構(gòu)及典型模型研究[J].兵工自動化，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é)報:信息與管理工程版，2010，32(2):257 －260.

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

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

[9] 張兵，韓曉明，賀沁榮.空軍機場綜合評價模型[J].四川兵工學(xué)報，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)仿真的批處理過程動態(tài)調(diào)度[J].系統(tǒng)仿真學(xué)報，2002，14(7):928 －931.