馬嘉呈，姚登凱，趙顧顥，孫天馳

（空軍工程大學(xué)空管領(lǐng)航學(xué)院，西安 710051）

0 引言

隨著我國空軍軍事訓(xùn)練轉(zhuǎn)型的推進(jìn)，軍事訓(xùn)練時間、戰(zhàn)術(shù)訓(xùn)練比重不斷提高，多兵機(jī)種合練、體系對抗已成常態(tài)，對空域資源的需求逐年增加。而由于民航業(yè)的持續(xù)快速發(fā)展，其對空域的需求也日益迫切。因此，合理安全地利用航空兵戰(zhàn)術(shù)訓(xùn)練空域，既有利于充分發(fā)揮我軍主戰(zhàn)裝備的優(yōu)勢，又有利于空域結(jié)構(gòu)的合理優(yōu)化，從而實現(xiàn)軍民航的協(xié)調(diào)可持續(xù)發(fā)展。

航空兵戰(zhàn)術(shù)訓(xùn)練空域規(guī)劃是指在某作戰(zhàn)責(zé)任區(qū)內(nèi)，對各個訓(xùn)練科目所需空域的合理規(guī)劃和安排。而對于訓(xùn)練空域的規(guī)劃問題，目前國內(nèi)沒有成熟的計算方法和理論體系，大多是根據(jù)參謀人員的經(jīng)驗人為劃設(shè)，故無法保證空域的利用率和靈活性。根據(jù)計算復(fù)雜理論可知，該問題類似于NP完全問題。近年來，不少學(xué)者應(yīng)用人工神經(jīng)網(wǎng)絡(luò)算法[1-2]、遺傳算法[3-4]、蟻群算法[5-6]等智能算法來解決該問題。隨著智能算法的發(fā)展和人們對排樣問題的深入理解，利用啟發(fā)式排樣算法和人工智能算法的組合算法已成為解決此類的重點研究方向。但訓(xùn)練空域規(guī)劃問題有其自身的獨特性，目前的幾種排樣算法均不適用于解決該問題。其次，作戰(zhàn)責(zé)任區(qū)通常是不規(guī)則形的，而排樣問題大都是解決在矩形區(qū)域內(nèi)的，對于不規(guī)則區(qū)域內(nèi)的排放問題研究較少。而且，由于空域的有限性，無法保證所有的訓(xùn)練科目均被安排。這些都給訓(xùn)練空域的規(guī)劃增加了難度。本文首先將空域進(jìn)行離散化處理，并構(gòu)建空域規(guī)劃模型；根據(jù)空域規(guī)劃的特點，將離散粒子群算法[7-8]與改進(jìn)的最低水平線算法相結(jié)合來獲得最佳的規(guī)劃方案，并與傳統(tǒng)的遺傳算法進(jìn)行比較來驗證該方法的高效性。

1 訓(xùn)練空域規(guī)劃模型

戰(zhàn)術(shù)訓(xùn)練空域規(guī)劃問題是指在指定的作戰(zhàn)責(zé)任區(qū)內(nèi)，對各個訓(xùn)練科目所需空域的合理安排，從而使整個空域的利用率達(dá)到最大。即在指定的作戰(zhàn)責(zé)任區(qū)S內(nèi)，排放N個作戰(zhàn)科目，每個作戰(zhàn)科目所需空域的長為li（1≤i≤N），寬為wi（1≤i≤N）。在排放過程中，使整個空域的利用率E最大。

式中，m為排入的訓(xùn)練科目個數(shù)。由于受到區(qū)域地形、空中禁飛區(qū)、軍民航線等多方面的影響，某機(jī)場所轄的空域范圍通常是不規(guī)則形狀的。故在解決空域規(guī)劃的問題時，需將其離散化處理，抽象為單元格的集合并置于二維坐標(biāo)系中。其約束條件為：

1）范圍約束：各個訓(xùn)練空域均需安排在所轄的作戰(zhàn)責(zé)任區(qū)以內(nèi)，所需的總面積不能大于作戰(zhàn)責(zé)任區(qū)的面積。

2）位置約束：各個科目的訓(xùn)練空域之間不能重疊。

3）方向約束：考慮到實際情況，為使空域的利用率最大化，各個訓(xùn)練科目在排放時需要與坐標(biāo)軸平行，且可以水平旋轉(zhuǎn)90°。具體如下所示

式中，n 為總的訓(xùn)練科目數(shù)；x，y 為空域的坐標(biāo)；l，w為各個科目訓(xùn)練空域所需的長度和寬度；Exy為取值為0或1的變量，表示（x，y）處的空域是否被占用。若被占用則Exy=1，否則為取值為0或1的變量，表示第i個訓(xùn)練科目所需空域是否占用（x，y）處的空域，若被占用則，否則：取值為0或1的變量，表示訓(xùn)練科目i的長是否平行于X軸或Y軸某個軸，若平行于X軸，則lxi=1；Wxi，Wyi，Wzi：取值為0或1的變量，表示訓(xùn)練科目i的寬是否平行于X軸或Y軸某個軸，若平行于Y軸，則Wyi=1，i=1，2，…，n；S 為作戰(zhàn)責(zé)任區(qū)的總面積。

上式中，式（2）、式（5）是保證各個訓(xùn)練科目均被放置在所轄的作戰(zhàn)責(zé)任區(qū)內(nèi)，即范圍約束；式（3）是保證各個訓(xùn)練空域之間不會重疊，即位置約束；式（4）是保證各個訓(xùn)練科目之間均沿坐標(biāo)軸方向放置，即方向約束。

2 改進(jìn)的最低水平線算法

最低水平線算法是以BL算法為基礎(chǔ)的一種排樣搜索算法。它是利用最高輪廓線和最低水平線來完成搜索尋優(yōu)的。最高輪廓線是當(dāng)前排樣過程中各排樣件最大高度的集合，而最低水平線是指最高輪廓線中最低的一段。但傳統(tǒng)的最低水平線法只是利用了各個矩形件的上邊緣，對于之下的空隙則無法利用。這在一定程度上也會造成資源的浪費。而對于訓(xùn)練空域規(guī)劃問題，由于作戰(zhàn)責(zé)任區(qū)是不規(guī)則的，利用傳統(tǒng)的方法也無法充分利用作戰(zhàn)責(zé)任區(qū)的邊緣空域。當(dāng)前的最低水平線無法容納當(dāng)前矩形的時候，采用的辦法是向后搜索一個可容納的矩形，如若沒有則提升最低水平線。但由于其在搜索時只考慮離當(dāng)前排樣矩形最近的一個矩形，這將不能保證資源利用率的最大化。本文對傳統(tǒng)的最低水平線的改進(jìn)如下：不再設(shè)置最高輪廓線，而是建立一個最低水平線庫，即搜索當(dāng)前空域內(nèi)所能利用的所有位置。這將保證邊緣空域的合理利用；在向后搜索的過程中，若對于當(dāng)前最低水平線，有一個以上的可容納的訓(xùn)練科目時，選擇與其寬度最接近的排放，這能保證空域利用的最大化。具體步驟如下：

1）從作戰(zhàn)責(zé)任區(qū)的下邊緣開始，依次向上搜索所有可利用的空域段，并記錄它的起點位置及其長度。

2）從第一個空域段開始，根據(jù)所給的訓(xùn)練科目的寬度，依次尋找該空域段可容納的訓(xùn)練科目：

a）如果該空域段的長度大于訓(xùn)練科目的寬度，且排入后不會占用已利用的空域，則將該訓(xùn)練科目安排在該位置，并更新最低水平線庫。

b）否則，向后搜索選擇與之寬度最接近的訓(xùn)練科目排入，若沒可容納的訓(xùn)練科目，則從下一個空域段繼續(xù)搜索。

3）重復(fù)步驟2）至該作戰(zhàn)責(zé)任區(qū)內(nèi)無法再安排其他訓(xùn)練科目為止。

3 粒子群優(yōu)化算法

粒子群優(yōu)化算法是Kennedy博士和Eberhart博士受自然界中鳥群運動模型的啟發(fā)提出的一種基于種群的搜索算法。該算法建模簡單，且所需的參數(shù)較少。相較于其他進(jìn)化算法，該算法實現(xiàn)時比較簡單并且具有更強(qiáng)大的全局優(yōu)化能力。目前在人工智能、認(rèn)知科學(xué)等多個領(lǐng)域均得到了廣泛的應(yīng)用。而且，大量的實驗結(jié)果表明：對于遺傳算法解決的各類優(yōu)化問題，PSO算法能更加高效地解決此類問題。

3.1 離散粒子群優(yōu)化算法

PSO算法的應(yīng)用大多數(shù)注重連續(xù)、無約束的確定性優(yōu)化問題，在離散、約束等優(yōu)化問題上研究較少。目前，已經(jīng)提出了多種離散粒子群算法，并且在解決旅行商（TSP）問題上取得了不錯的效果。本文利用置換子和置換序列來解決空域規(guī)劃問題。

1）置換子：假設(shè)某個序列位置為Xk，置換子為（ik，jk）。則置換操作為交換位置 Xk中值為 ik，jk的位置來得到新的位置 X′。例如 Xk=（1，2，3，4，5），（ik，jk）=（2，3），則 X′=（1，3，2，4，5）。

2）置換序列：由單個或多個置換子構(gòu)成的有序列就是置換序列。通常情況下，兩個位置作差就會得到一個置換序列。例如：置換序列={（1，2），（2，3）}，序列位置為（1，2，3，4，5），通過置換得到的新位置為（3，1，2，4，5）。注意置換序列是按照置換子的位置依次作用在位置序列上的。

3）加法操作：對于位置和速度之間的加法是指將置換序列中的置換子依次作用于該位置從而得到新的位置。

4）速度的數(shù)乘：將數(shù)乘運算定義為：

其中，Rand（）為一個0～1之間的隨機(jī)數(shù)。而數(shù)乘操作的含義是以一定的概率（1/C）來保留對速度的操作。如當(dāng)C=4時，保留概率為25%。

5）粒子的更新

在離散粒子群中，速度和位置的更新如下所示：

其中，w，C1，C2為速度保留概率，以及全局最優(yōu)值和個體最優(yōu)值對進(jìn)化的影響因數(shù)。

3.2 應(yīng)用離散粒子群算法解決訓(xùn)練空域規(guī)劃問題

針對戰(zhàn)術(shù)訓(xùn)練空域規(guī)劃問題的離散性的特點，本文利用離散粒子群算法來解決此問題。具體算法介紹如下：

3.2.1 編碼與解碼

針對訓(xùn)練空域規(guī)劃問題的離散性，本文采用整數(shù)編碼的方式來進(jìn)行編碼。首先對各個訓(xùn)練科目進(jìn)行編號，再根據(jù)訓(xùn)練科目數(shù)n，生成一個1～n的整數(shù)排列，即為一個排放序列。每個排放序列根據(jù)改進(jìn)的最低水平線算法都能生成一個規(guī)劃方案，從而確定該方案的適應(yīng)度值。

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

對于訓(xùn)練空域規(guī)劃問題，由于空域范圍限制無法同時容納所有的訓(xùn)練科目，故在考慮空域利用率的同時還需要兼顧所能容納的訓(xùn)練科目數(shù)。故目標(biāo)函數(shù)為

其中，S為任一規(guī)劃方案，E為空域的利用率，m為被安排的訓(xùn)練科目數(shù)，N為總的訓(xùn)練科目數(shù)。由于在解決訓(xùn)練空域規(guī)劃問題時，需要考慮其約束條件，故本文利用懲罰函數(shù)來將其轉(zhuǎn)化為無約束問題，對于上文中的3個約束條件，違反任一條此排樣方案均被視為無效方案，故引入?yún)?shù)q來代表懲罰項。q的取值為0或1，當(dāng)滿足約束時q=1，反之為0。故最后的適應(yīng)度函數(shù)應(yīng)為：

3.2.3 算法具體步驟

假定種群的粒子數(shù)為m，最大的迭代次數(shù)為N，個體最優(yōu)位置為Pid，全局最優(yōu)位置為Pgd。

1）產(chǎn)生初始粒子種群。針對戰(zhàn)術(shù)訓(xùn)練空域規(guī)劃問題的離散性，本文選取m個1～n的整數(shù)排列（n為訓(xùn)練科目數(shù)）作為初始粒子群的位置，并且每個位置均賦予一個初始的速度，同時給定參數(shù)W，C1，C2的值。

2）利用改進(jìn)的最低水平線法來計算每個粒子的適應(yīng)度值F，并將其作為每個粒子的初始個體最優(yōu)位置Pid，選取其中適應(yīng)度最大的位置作為全局最優(yōu)位置Pgd。

3）按照上文中粒子更新的方法更新粒子的位置，并同時求出每個新位置的適應(yīng)度值。如果新位置的函數(shù)值大于原函數(shù)值，則更新該粒子的個體最優(yōu)位置。而對于整個粒子群，每更新一代就選取其中最大的適應(yīng)度值與上一代的進(jìn)行比較，若大于，則將此位置作為新的全局最優(yōu)位置。

4）當(dāng)?shù)螖?shù)達(dá)到設(shè)定的最大迭代次數(shù)或者適應(yīng)度不再發(fā)生變化時，終止該算法，并根據(jù)最優(yōu)的規(guī)劃方案畫出空域規(guī)劃圖。

算法的流程如圖1所示。

圖1 訓(xùn)練空域規(guī)劃流程圖

4 算例分析

為了測試該算法的性能，本文以MATLAB R2014為平臺進(jìn)行了下述的實例仿真。

某機(jī)場不同機(jī)型的不同訓(xùn)練科目所需空域大小如表1所示。

而該機(jī)場的作戰(zhàn)責(zé)任區(qū)如圖2所示。

根據(jù)上述方法，首先需要對該機(jī)場的作戰(zhàn)責(zé)任區(qū)進(jìn)行離散化處理，以便利用離散粒子群算法來求解戰(zhàn)術(shù)訓(xùn)練空域規(guī)劃問題。其離散化后的圖形如圖2所示。

表1 各訓(xùn)練科目所需空域大小

圖2 作戰(zhàn)責(zé)任區(qū)

圖3 作戰(zhàn)責(zé)任區(qū)離散圖

根據(jù)上述方法，首先需要對該機(jī)場的作戰(zhàn)責(zé)任區(qū)進(jìn)行離散化處理，以便利用離散粒子群算法來求解戰(zhàn)術(shù)訓(xùn)練空域規(guī)劃問題。其離散化后的圖形如圖3所示。

在離散化處理完成后，利用離散粒子群算法結(jié)合改進(jìn)的最低水平線法來對問題進(jìn)行求解。在求解過程中，假定粒子群的種群個數(shù)為20，迭代次數(shù)為100代，個體經(jīng)驗保留概率C1=0.85，全局經(jīng)驗保留概率C2=0.85。通過仿真，發(fā)現(xiàn)當(dāng)?shù)降?3代時已經(jīng)趨于穩(wěn)定，而此時的適應(yīng)度值為11.855 3。最后生成的空域訓(xùn)練圖以及在迭代過程中每代的最優(yōu)適應(yīng)度值和平均適應(yīng)度值的變化過程如圖4和圖5所示。

圖4 適應(yīng)度值變化曲線圖

圖5 戰(zhàn)術(shù)訓(xùn)練空域規(guī)劃圖

為確定該算法的高效性，本文與解決排樣問題中常用的智能算法（遺傳算法）來進(jìn)行比較，同樣，在利用遺傳算法求解過程中，設(shè)定種群大小為20，迭代次數(shù)為100代，選擇和變異概率均為0.8。通過仿真發(fā)現(xiàn)：當(dāng)?shù)降?0代的時候，基本趨于穩(wěn)定，而此時的適應(yīng)度值為10.789 9。最后生成的空域訓(xùn)練圖以及在迭代過程中每代的最優(yōu)適應(yīng)度值和平均適應(yīng)度值的變化過程如圖6和圖7所示。

圖6 適應(yīng)度值變化曲線圖

圖7 戰(zhàn)術(shù)訓(xùn)練空域規(guī)劃圖

通過對比兩組數(shù)據(jù)，不難看出：本文算法對于戰(zhàn)術(shù)訓(xùn)練空域規(guī)劃問題的求解要明顯優(yōu)于傳統(tǒng)的遺傳算法。利用本文算法得到的訓(xùn)練空域規(guī)劃方案對空域的利用率要更大，且在作戰(zhàn)責(zé)任區(qū)內(nèi)安排的訓(xùn)練科目數(shù)也更多；通過比較兩組數(shù)據(jù)趨于穩(wěn)定時的代數(shù)，發(fā)現(xiàn)遺傳算法的搜索性能要明顯弱于離散粒子群算法；而從程序運行的時間上看，利用離散粒子群算法所用的求解時間要明顯小于人工排樣的時間，且短于遺傳算法所需要的時間。由此可見，本文提出的離散粒子群算法結(jié)合改進(jìn)最低水平線算法在解決戰(zhàn)術(shù)訓(xùn)練空域規(guī)劃問題上具有良好的性能，并且要優(yōu)于傳統(tǒng)的遺傳算法求解。

5 結(jié)論

隨著我國軍民航持續(xù)穩(wěn)定高效地發(fā)展，對空域資源的需求日益迫切。因此，合理高效地利用空域?qū)τ诰徑廛娒窈接每諞_突具有重大意義。本文將戰(zhàn)術(shù)訓(xùn)練空域規(guī)劃問題通過離散化處理將其抽象為數(shù)學(xué)問題來進(jìn)行求解，通過利用離散粒子群算法結(jié)合改進(jìn)的最低水平算法來尋找最優(yōu)的規(guī)劃方案。最后與傳統(tǒng)遺傳算法的比較來驗證算法的合理性。相比于人為排樣規(guī)劃，該算法在進(jìn)行戰(zhàn)術(shù)訓(xùn)練空域規(guī)劃時要更為高效，同時也為以后空域的靈活使用提供了一定的參考價值。但是對于求解過程中參數(shù)的設(shè)定以及求解的精度上還有待一步的討論和研究。