一種航跡網(wǎng)絡(luò)圖粒子群優(yōu)化生成方法＊

黃自強(qiáng) 蔡 超 孫希霞

（華中科技大學(xué)自動(dòng)化學(xué)院多譜信息處理技術(shù)國(guó)防科技重點(diǎn)實(shí)驗(yàn)室 武漢 430074）

1 引言

飛行器航跡規(guī)劃是在綜合考慮飛行器到達(dá)時(shí)間、燃料消耗、威脅以及特定飛行區(qū)域等因素的前提下，為飛行器規(guī)劃出一條最優(yōu)，或者是較滿意的飛行航跡，以保證圓滿完成飛行任務(wù)［1］。在現(xiàn)代戰(zhàn)爭(zhēng)中，由于戰(zhàn)場(chǎng)環(huán)境的動(dòng)態(tài)變化以及任務(wù)的不確定性，飛行器的航跡規(guī)劃空間往往非常大，規(guī)劃算法非常耗時(shí)，無(wú)法滿足在線實(shí)時(shí)規(guī)劃的要求。有研究者根據(jù)高速公路網(wǎng)規(guī)劃的思想，提出了基于網(wǎng)絡(luò)圖的分階段航跡規(guī)劃方法［2～6］。第一步，在預(yù)處理階段構(gòu)造滿足一系列約束條件的航跡片段，這些航跡片段構(gòu)成網(wǎng)絡(luò)圖。第二步，給定規(guī)劃任務(wù)，利用網(wǎng)絡(luò)圖搜索出一條從指定發(fā)射點(diǎn)到目標(biāo)點(diǎn)的航跡。這樣路徑規(guī)劃問(wèn)題被轉(zhuǎn)化為一個(gè)網(wǎng)絡(luò)圖的搜索問(wèn)題。這種方法大幅縮減了航跡規(guī)劃過(guò)程的搜索量，從而加快了規(guī)劃速度，能滿足在線實(shí)時(shí)規(guī)劃的要求。類似的方法還有通視圖法、隨機(jī)路線圖法等［7～11］。通視圖是由規(guī)劃空間中的障礙物的相互可見的頂點(diǎn)間的連線構(gòu)成。通視圖可用于求解二維規(guī)劃空間中的最短路徑問(wèn)題，盡管它可用于高維規(guī)劃空間，但此時(shí)生成的路徑將不再是最短的。另外，通視圖不能表達(dá)物體運(yùn)動(dòng)的方向性約束，這樣使得生成網(wǎng)絡(luò)圖可行解較少。隨機(jī)路線圖法是一種針對(duì)多自由度問(wèn)題的路徑規(guī)劃方法。該方法在規(guī)劃空間中隨機(jī)進(jìn)行采樣生成路線圖，然后在該路線圖中搜索路徑。該方法的優(yōu)點(diǎn)之一就是可以在規(guī)劃時(shí)間和路徑的質(zhì)量之間進(jìn)行權(quán)衡，構(gòu)造隨機(jī)路線圖的時(shí)間越長(zhǎng)，得到最優(yōu)路徑的可能性就越大。在確定環(huán)境下，隨機(jī)路線圖一般可以事先構(gòu)造。

已有的航跡網(wǎng)絡(luò)圖生成方法并沒有考慮網(wǎng)絡(luò)圖的最優(yōu)性，包括：1）空間覆蓋能力；2）網(wǎng)絡(luò)圖總體代價(jià)最優(yōu)性；3）重組航跡的最優(yōu)性等。

本文利用粒子群優(yōu)化算法優(yōu)化網(wǎng)絡(luò)圖節(jié)點(diǎn)的分布，使航跡網(wǎng)絡(luò)圖整體代價(jià)較優(yōu)，重組航跡也較優(yōu)。

2 航跡網(wǎng)絡(luò)圖及其優(yōu)化問(wèn)題

航跡網(wǎng)絡(luò)圖是由網(wǎng)絡(luò)節(jié)點(diǎn)和節(jié)點(diǎn)間的航跡片段構(gòu)成如圖1所示。航跡網(wǎng)絡(luò)圖的構(gòu)建過(guò)程，首先是對(duì)規(guī)劃空間進(jìn)行等網(wǎng)格劃分，將規(guī)劃空間劃分為一個(gè)個(gè)相互毗鄰的網(wǎng)格。多個(gè)較小的網(wǎng)格又可以形成一個(gè)較大的網(wǎng)格，這樣實(shí)現(xiàn)了多尺度網(wǎng)格的劃分。在每個(gè)網(wǎng)格內(nèi)，在匹配區(qū)內(nèi)隨機(jī)選取節(jié)點(diǎn)。然后根據(jù)飛行器飛行約束、環(huán)境約束等約束條件進(jìn)行節(jié)點(diǎn)間的航跡片段規(guī)劃。其規(guī)劃結(jié)果就構(gòu)成了一幅初始的航跡網(wǎng)絡(luò)圖。航跡網(wǎng)絡(luò)圖可以表示為G＝（V，E），其中V為圖中節(jié)點(diǎn)的集合，E為航跡片段（圖G中的邊）的集合，節(jié)點(diǎn)具有八個(gè)飛行方向（由匹配區(qū)導(dǎo)航點(diǎn)的性質(zhì)決定），空間位置由坐標(biāo)（x，y，z）表示。

圖1 網(wǎng)絡(luò)節(jié)點(diǎn)及小尺度航跡片段

航跡網(wǎng)絡(luò)圖主要受規(guī)劃空間、網(wǎng)格大小、節(jié)點(diǎn)分布以及航跡片段生成算法等因素的影響。在規(guī)劃空間、網(wǎng)格大小和航跡片段生成算法都已確定的情況下，節(jié)點(diǎn)位置的改變會(huì)造成航跡網(wǎng)絡(luò)圖空間分布的較大改變，相應(yīng)的航跡網(wǎng)絡(luò)總體代價(jià)也會(huì)有較大的改變。這里，我們用航跡網(wǎng)絡(luò)圖中所有航跡片段代價(jià)的和來(lái)表示網(wǎng)絡(luò)圖的總體代價(jià)，航跡片段的代價(jià)考慮航跡長(zhǎng)度、高度、轉(zhuǎn)彎次數(shù)、威脅等因素。

航跡網(wǎng)絡(luò)圖的優(yōu)化，除了考慮網(wǎng)絡(luò)圖的代價(jià)因素外，還要考慮網(wǎng)絡(luò)的密集程度，規(guī)劃空間的覆蓋能力，分布均勻性等。

網(wǎng)格的劃分決定了航跡網(wǎng)絡(luò)的密集程度。航跡片段規(guī)劃算法采用A＊搜索算法，在滿足給定約束條件的情況下，A＊算法能夠規(guī)劃出節(jié)點(diǎn)間的最小代價(jià)航跡片段。改變航跡網(wǎng)絡(luò)節(jié)點(diǎn)位置，將影響航跡片段經(jīng)過(guò)的空間位置及代價(jià)大小，相應(yīng)地改變航跡網(wǎng)絡(luò)的總體代價(jià)和空間覆蓋能力。

結(jié)合上述分析，本文設(shè)計(jì)出一種通過(guò)求解航跡網(wǎng)絡(luò)節(jié)點(diǎn)最優(yōu)分布進(jìn)而獲得最優(yōu)航跡網(wǎng)絡(luò)的優(yōu)化方法。

3 基于粒子群算法的網(wǎng)絡(luò)圖優(yōu)化

3.1 粒子群算法原理

粒子群算法是基于群體的演化算法，其思想來(lái)源是人工生命和演化計(jì)算理論。由于其簡(jiǎn)單、有效的特點(diǎn)，可以用于復(fù)雜高維問(wèn)題的求解，已得到眾多學(xué)者的重視［7］。在粒子群算法中，每個(gè)粒子在搜索空間中的位置代表了所求問(wèn)題的一個(gè)解。每個(gè)粒子還有一個(gè)速度，來(lái)決定它們移動(dòng)的方向和位置。每個(gè)粒子通過(guò)優(yōu)化函數(shù)決定了它當(dāng)前的適應(yīng)值。粒子群算法初始化為一群隨機(jī)的粒子，然后通過(guò)迭代找到最優(yōu)解，在每一次迭代中，粒子通過(guò)兩個(gè)“極值”來(lái)更新自己的位置和速度。其中，第一個(gè)“極值”是粒子本身所找到的最好解（個(gè)體極值pbest）；另一個(gè)“極值”是整個(gè)種群目前所找到的最好的解（全局極值點(diǎn)gbest）［12～15］。粒子更新位置和速度的公式如下：

其中，是粒子i在第k次迭代中第d維的速度。C1、C2是加速系數(shù)（學(xué)習(xí)因子）表示每個(gè)粒子飛向pbest和gbest位置的隨機(jī)加速項(xiàng)的權(quán)重。合適的值可以加快收斂不易陷入局部最優(yōu)。一般取C1＝C2＝2。rand1和rand2是［0，1］之間的隨機(jī)數(shù)。粒子i的位置用D維向量Xi＝（xi1，xi2，…，xiD）T來(lái)表示，速度為Vi＝（vi1，vi2，…，viD）T。

算法流程如下：

1）初始化。以隨機(jī)的方式產(chǎn)生出每一個(gè)粒子的初始位置與速度。

2）評(píng)價(jià)每一個(gè)粒子。根據(jù)適應(yīng)度函數(shù)計(jì)算出粒子當(dāng)前的適應(yīng)值，并更新個(gè)體和全局極值。

3）粒子的更新。用式（1）和式（2）對(duì)每一個(gè)粒子的速度和位置進(jìn)行更新。

4）檢驗(yàn)是否符合結(jié)束條件。如果當(dāng)前的迭代次數(shù)達(dá)到了預(yù)先設(shè)定的最大次數(shù)或最小錯(cuò)誤要求，則停止迭代，輸出最優(yōu)解。否則轉(zhuǎn)到步驟2）。

利用粒子群優(yōu)化算法獲得優(yōu)化航跡網(wǎng)絡(luò)需要解決粒子位置坐標(biāo)與航跡網(wǎng)絡(luò)空間分布的對(duì)應(yīng)關(guān)系問(wèn)題，還需要解決粒子適應(yīng)度函數(shù)與航跡網(wǎng)絡(luò)代價(jià)的關(guān)系。下面將分別進(jìn)行討論。

3.2 基于粒子群算法的航跡網(wǎng)絡(luò)圖優(yōu)化

航跡網(wǎng)絡(luò)圖的優(yōu)化有其特殊性。第一，航跡片段的代價(jià)是由航跡規(guī)劃算法中的評(píng)價(jià)函數(shù)確定的。節(jié)點(diǎn)發(fā)生改變時(shí)，航跡片段的代價(jià)值往往沒有明確的變化趨向。相應(yīng)地，代價(jià)值的變化給出的節(jié)點(diǎn)變化引導(dǎo)往往也是不可靠的。換句話說(shuō)，代價(jià)值的變化與節(jié)點(diǎn)的變化沒有明確的關(guān)聯(lián)。而航跡片段的代價(jià)值是優(yōu)化函數(shù)的主要變量，這就造成了優(yōu)化函數(shù)值影響因素的復(fù)雜性問(wèn)題。第二，網(wǎng)絡(luò)圖往往含有大量的節(jié)點(diǎn)，任意一個(gè)節(jié)點(diǎn)的改變都會(huì)造成網(wǎng)絡(luò)圖的改變，進(jìn)而對(duì)網(wǎng)絡(luò)圖的優(yōu)劣產(chǎn)生影響。因此網(wǎng)絡(luò)圖的優(yōu)化是一個(gè)高維復(fù)雜優(yōu)化問(wèn)題。

采用經(jīng)典的數(shù)學(xué)規(guī)劃方法解決此問(wèn)題時(shí)，必須在精度和求解效率間做某種折中。其中，線性規(guī)劃法計(jì)算速度快，但將該模型線性化存在困難；非線性規(guī)劃法可以較精確地計(jì)及模型的非線性，但一般要求目標(biāo)函數(shù)連續(xù)可導(dǎo)，且定義于凸可行域；動(dòng)態(tài)規(guī)劃法對(duì)目標(biāo)函數(shù)無(wú)嚴(yán)格限制，容易計(jì)及約束條件，但對(duì)于高維問(wèn)題將面臨維數(shù)災(zāi)難。而人工智能算法為求解這類問(wèn)題提供了新的思路。其中，粒子群優(yōu)化算法簡(jiǎn)單、有效，依賴的經(jīng)驗(yàn)參數(shù)少，可以求解復(fù)雜的高維非線性函數(shù)優(yōu)化。

基于粒子群算法的網(wǎng)絡(luò)圖優(yōu)化是通過(guò)調(diào)整網(wǎng)絡(luò)圖中節(jié)點(diǎn)的分布，使網(wǎng)絡(luò)圖的代價(jià)降低同時(shí)保持網(wǎng)絡(luò)圖的豐富性。當(dāng)網(wǎng)絡(luò)圖中的節(jié)點(diǎn)位置改變時(shí)，網(wǎng)絡(luò)圖中的航跡片段需重新生成，進(jìn)而形成一個(gè)新的航跡網(wǎng)絡(luò)圖。這類似于粒子群優(yōu)化算法中的粒子從一個(gè)位置移動(dòng)到另一個(gè)位置。粒子通過(guò)相互引導(dǎo)向最優(yōu)值靠攏，多個(gè)網(wǎng)絡(luò)圖之間也可以相互引導(dǎo)，從而使網(wǎng)絡(luò)圖向最優(yōu)的網(wǎng)絡(luò)圖靠攏。因此可以將網(wǎng)絡(luò)圖看作一個(gè)粒子，應(yīng)用粒子群優(yōu)化算法求解網(wǎng)絡(luò)圖的優(yōu)化問(wèn)題。

將網(wǎng)絡(luò)圖看作一個(gè)粒子，每個(gè)節(jié)點(diǎn)坐標(biāo)p作為粒子坐標(biāo)Q的一個(gè)分量。則粒子的坐標(biāo)標(biāo)為：Qk＝（，，，…，，）T由第k張航跡網(wǎng)絡(luò)圖中所有節(jié)點(diǎn)坐標(biāo)構(gòu)成，其中N為節(jié)點(diǎn)個(gè)數(shù)。（xj，yj）為航跡網(wǎng)絡(luò)中第j個(gè)節(jié)點(diǎn)pj的坐標(biāo)，1≤j≤N。構(gòu)造如下目標(biāo)函數(shù)：

其中f（，）為節(jié)點(diǎn)間對(duì)應(yīng)的航跡片段的代價(jià)，由航跡片段規(guī)劃算法求得。如果之間沒有規(guī)劃出可行航跡，則定義f）為一個(gè)懲罰常量值，以使節(jié)點(diǎn)朝向能規(guī)劃出航跡的方向移動(dòng)。Ωj為第j個(gè)網(wǎng)格包含的區(qū)域，表示限定第j個(gè)節(jié)點(diǎn)的位置落在第j個(gè)網(wǎng)格內(nèi)，該限定的目的是航跡網(wǎng)絡(luò)的節(jié)點(diǎn)的分布比較均勻，避免過(guò)度集中和過(guò)度稀疏的情況發(fā)生。

實(shí)現(xiàn)過(guò)程中，Ωj是一個(gè)正方形網(wǎng)格。在網(wǎng)絡(luò)圖中，設(shè)定節(jié)點(diǎn)坐標(biāo)表示為pj＝（xj，yj），1?j?N。由于節(jié)點(diǎn)限制在正方形網(wǎng)格內(nèi)，節(jié)點(diǎn)坐標(biāo)滿足：

Xj、Xj＋1為節(jié)點(diǎn)pj所在網(wǎng)格的豎直方向邊界的橫坐標(biāo)。Yj、Yj＋1為節(jié)點(diǎn)pj所在網(wǎng)格的水平方向邊界的縱坐標(biāo)。粒子的速度Vk為

vjx、vjy分別為節(jié)點(diǎn)pj＝（xj，yj）的x和y方向上的運(yùn)動(dòng)速度。粒子每一維速度限定在一定范圍內(nèi)，滿足約束條件：

調(diào)整Vdmax可以限定粒子的運(yùn)動(dòng)速度。如果粒子速度過(guò)大，可能會(huì)飛躍最優(yōu)解；粒子速度太小，則容易陷入局部最優(yōu)。

在優(yōu)化模型的目標(biāo)函數(shù)中，懲罰代價(jià)可以根據(jù)航跡片段的數(shù)目以及片段的平均代價(jià)來(lái)設(shè)定：

其中，fave為已生成的航跡片段的平均代價(jià)，α為懲罰系數(shù)，nall為理論上網(wǎng)絡(luò)圖能夠生成的航跡片段數(shù)，nr為實(shí)際生成的航跡片段數(shù)。nall取值與節(jié)點(diǎn)個(gè)數(shù)和網(wǎng)格尺度有關(guān)。節(jié)點(diǎn)個(gè)數(shù)越多，nall值就越大；反之，就越小。懲罰代價(jià)與航跡片段數(shù)目成反比：當(dāng)節(jié)點(diǎn)個(gè)數(shù)和網(wǎng)格尺度確定時(shí)，實(shí)際生成的片段數(shù)nr越大，懲罰代價(jià)就越小，否則懲罰代價(jià)越大。

因此，兩節(jié)點(diǎn)間的代價(jià)函數(shù)定義為

基于粒子群算法的網(wǎng)絡(luò)圖優(yōu)化流程：

1）初始化種群。以隨機(jī)的方式產(chǎn)生出每一個(gè)粒子的初始位置與速度。若有匹配區(qū)限制，則節(jié)點(diǎn)必須分布在匹配區(qū)上。

2）生成航跡片段。對(duì)每個(gè)粒子，利用A＊算法生成航跡片段，從而生成航跡網(wǎng)絡(luò)圖。

3）求得適應(yīng)度值。根據(jù)式（3）求得每個(gè)粒子當(dāng)前的適應(yīng)度值，并更新個(gè)體和全局極值。

4）更新粒子位置和速度。根據(jù)新得到的個(gè)體和全局極值更新粒子的位置和速度。判斷每個(gè)粒子中節(jié)點(diǎn)是否滿足網(wǎng)格邊界約束和匹配區(qū)約束條件。若節(jié)點(diǎn)不滿足約束條件，則調(diào)整節(jié)點(diǎn)使其滿足約束條件。

5）檢驗(yàn)是否符合結(jié)束條件。如果達(dá)到了預(yù)先設(shè)定的最大迭代次數(shù)或最小錯(cuò)誤要求，則停止迭代，輸出最優(yōu)解。否則轉(zhuǎn)到步驟2）。

算法流程圖：

圖2 粒子群算法優(yōu)化網(wǎng)絡(luò)圖的流程圖

算法初始化中，在每個(gè)網(wǎng)格內(nèi)隨機(jī)生成一個(gè)節(jié)點(diǎn)，并判斷節(jié)點(diǎn)是否在匹配區(qū)上，若在匹配區(qū)上，則節(jié)點(diǎn)位置確定；否則在網(wǎng)格內(nèi)按一定策略逐點(diǎn)搜索匹配區(qū)。若找到匹配區(qū)則節(jié)點(diǎn)確定，否則該網(wǎng)格內(nèi)不設(shè)定節(jié)點(diǎn)，粒子在該節(jié)點(diǎn)對(duì)應(yīng)的分量上不予考慮。所有的節(jié)點(diǎn)生成后，利用A＊算法規(guī)劃出航跡片段。按式（3）求取各粒子個(gè)體最優(yōu)值的初值，其中所有粒子適應(yīng)度值的最小值為全局最優(yōu)值的初值。

在航跡網(wǎng)絡(luò)圖的優(yōu)化過(guò)程中，節(jié)點(diǎn)必須滿足網(wǎng)格邊界約束和匹配區(qū)約束條件。在每一次迭代過(guò)程中，節(jié)點(diǎn)移動(dòng)后，可能移動(dòng)到相鄰網(wǎng)格或超出規(guī)劃空間，也有可能不在匹配區(qū)上。這時(shí)必須對(duì)不滿足約束條件的節(jié)點(diǎn)進(jìn)行調(diào)整。當(dāng)節(jié)點(diǎn)不滿足網(wǎng)格邊界約束時(shí)，將該節(jié)點(diǎn)置于節(jié)點(diǎn)運(yùn)動(dòng)路線與網(wǎng)格邊界的交點(diǎn)處，并將其速度反向。這樣處理可使粒子盡早脫離“非法區(qū)域”，盡可能多地探索合理的規(guī)劃空間。當(dāng)節(jié)點(diǎn)不滿足匹配區(qū)約束時(shí)，調(diào)整策略是讓節(jié)點(diǎn)從當(dāng)前位置沿著移動(dòng)方向v逐點(diǎn)探索直到找到匹配區(qū)。若按上述方式搜索至網(wǎng)格邊界仍未找到匹配區(qū)，則使節(jié)點(diǎn)從當(dāng)前位置逐點(diǎn)回退，運(yùn)動(dòng)方向?yàn)椋璿，直到找到匹配區(qū)。由于粒子的初始位置是在匹配區(qū)上，故回退一定能夠找到匹配區(qū)。這種調(diào)整策略能確保粒子在移動(dòng)過(guò)程中的兩個(gè)“極值”對(duì)粒子運(yùn)動(dòng)的引導(dǎo)性不變。

4 試驗(yàn)結(jié)果與分析

本文給出的算法在6000×6000像素的數(shù)字地形高程圖上實(shí)驗(yàn)，其中，每個(gè)像素代表的實(shí)際距離是90m。實(shí)驗(yàn)中，網(wǎng)格的大小為500×500像素，考慮匹配區(qū)限制。粒子群算法的參數(shù)設(shè)定為：粒子個(gè)數(shù)，迭代次數(shù)90次，粒子每一維的最大速度Vmax＝200，加權(quán)系數(shù)C1＝C2＝2。本文進(jìn)行兩類實(shí)驗(yàn)：先對(duì)同一幅初始航跡網(wǎng)絡(luò)圖進(jìn)行三組粒子群優(yōu)化實(shí)驗(yàn)，然后在優(yōu)化前后的航跡網(wǎng)絡(luò)圖上進(jìn)行航跡重組的對(duì)比實(shí)驗(yàn)。

圖3所示是航跡網(wǎng)絡(luò)圖代價(jià)的變化情況。從圖中可以看出，航跡網(wǎng)絡(luò)的代價(jià)是震蕩下降的，這是由優(yōu)化函數(shù)值的影響因素比較復(fù)雜造成的。這也會(huì)造成算法的收斂精度不高，使得曲線最終在收斂值附近波動(dòng)。迭代開始時(shí)，粒子的代價(jià)從1487.25開始快速下降，之后下降趨勢(shì)逐漸減緩，最后穩(wěn)定地在1430附近波動(dòng)。表明該算法能有效地優(yōu)化網(wǎng)絡(luò)圖的代價(jià)。圖4是優(yōu)化后的航跡片段網(wǎng)絡(luò)圖，從中可以看出網(wǎng)絡(luò)圖能夠比較均勻地覆蓋規(guī)劃空間，并且網(wǎng)絡(luò)圖中片段也很豐富。

圖3 粒子群優(yōu)化代價(jià)變化

圖5是在給定同一組發(fā)射點(diǎn)和目標(biāo)點(diǎn)的條件下，在經(jīng)粒子群算法優(yōu)化的航跡網(wǎng)絡(luò)和沒有優(yōu)化的航跡網(wǎng)絡(luò)上重組出的航跡對(duì)比。從圖中可以看出，在優(yōu)化過(guò)的網(wǎng)絡(luò)圖上重組得到的航跡比較平滑。表1記錄的是進(jìn)行6次不同任務(wù)得到的航跡的長(zhǎng)度、水平轉(zhuǎn)彎次數(shù)、垂直機(jī)動(dòng)次數(shù)的對(duì)比結(jié)果。其中，任務(wù)1是圖5中這兩條航跡的相關(guān)參數(shù)的對(duì)比。

圖4 優(yōu)化后的網(wǎng)絡(luò)圖

圖5 網(wǎng)絡(luò)圖優(yōu)化前后重組出的航跡

表1 航跡相關(guān)參數(shù)的對(duì)比

任務(wù)1中，基于優(yōu)化的網(wǎng)絡(luò)圖重組的航跡長(zhǎng)度為287.726km，較基于未優(yōu)化的網(wǎng)絡(luò)圖重組的航跡長(zhǎng)度315.2km短。在水平機(jī)動(dòng)次數(shù)上的對(duì)比是9次低于14次。在垂直機(jī)動(dòng)的次數(shù)上的對(duì)比是34次低于43次。從表1可以看出，每組任務(wù)中，左邊的航跡長(zhǎng)度均比右邊的航跡長(zhǎng)度短，水平機(jī)動(dòng)次數(shù)少。在垂直機(jī)動(dòng)次數(shù)上，左邊的航跡在大多數(shù)情況下要優(yōu)于右邊的航跡。在統(tǒng)計(jì)意義上，基于較優(yōu)的網(wǎng)絡(luò)圖重組出的航跡要優(yōu)于基于未優(yōu)化的航跡網(wǎng)絡(luò)圖重組出的航跡。

5 結(jié)語(yǔ)

航跡網(wǎng)絡(luò)圖的優(yōu)化存在優(yōu)化函數(shù)值影響因素的復(fù)雜性問(wèn)題。并且網(wǎng)絡(luò)節(jié)點(diǎn)通常較多，使得網(wǎng)絡(luò)圖的優(yōu)化是一個(gè)高維復(fù)雜優(yōu)化問(wèn)題。實(shí)驗(yàn)結(jié)果表明，本文提出的方法能生成代價(jià)較優(yōu)、片段豐富的航跡網(wǎng)絡(luò)圖。在統(tǒng)計(jì)意義上，優(yōu)化后航跡網(wǎng)絡(luò)圖重組出的航跡要優(yōu)于優(yōu)化前網(wǎng)絡(luò)圖重組出的航跡。

航跡網(wǎng)絡(luò)圖優(yōu)化的后續(xù)研究，可以在進(jìn)一步提高優(yōu)化效率等方面展開。

［1］鄭昌文，嚴(yán)平，丁明躍，等.飛行器航跡規(guī)劃研究現(xiàn)狀與趨勢(shì)［J］.宇航學(xué)報(bào)，2007，28（6）：1441－1446.

［2］Li ShiDong，Ding Mingyue，Cai Chao.A novel path planning method based on path network［C］／／Proceedings of the SPIE 6thInternational Symposium on Multispectral Image Processing and Pattern Recognition，2009.

［3］Li S，Ding M，Cai C，et al.Fast online path planning method based on path network［C］／／Computer Application and System Modeling（ICCASM），2010International Conference on.IEEE，2010，10：V10－224－V10－227.

［4］Li S，Ding M，Cai C.Path planning using FMM with direction and curvature constrained［C］／／Sixth International Symposium on Multispectral Image Processing and Pattern Recognition.International Society for Optics and Photonics，2009：749847－749847－8.

［5］Changuien Z，Mingyue D，Chengping Z.An evolutionary real－time 3Droute planner for aircraft［J］.Systems Engineering and Electronics，Journal of，2003，14（1）：47－53.

［6］Li S，Ding M，Cai C.A new roadmap constitution method based on fividing grid and level－set［C］／／Intelligence Information Processing and Trusted Computing（IPTC），2010International Symposium on.IEEE，2010：647－650.

［7］Kavraki L E，Svestka P，Latombe J C，et al.Probabilistic roadmaps for path planning in high－dimensional configuration spaces［J］.Robotics and Automation，IEEE Transactions on，1996，12（4）：566－580.

［8］Kavraki L E，Kolountzakis M N，Latombe J C.Analysis of probabilistic roadmaps for path planning［J］.Robotics and Automation，IEEE Transactions on，1998，14（1）：166－171.

［9］Siméon T，Laumond J P，Nissoux C.Visibility－based probabilistic roadmaps for motion planning［J］.Advanced Robotics，2000，14（6）：477－493.

［10］Nissoux C，Siméon T，Laumond J P.Visibility based probabilistic roadmaps［C］／／Intelligent Robots and Systems，1999.IROS'99.Proceedings.1999IEEE／RSJ International Conference on.IEEE，1999，3：1316－1321.

［11］Lulu L，Elnagar A.A comparative study between visibility－based roadmap path planning algorithms［C］／／Intelligent Robots and Systems，2005.（IROS 2005）.2005IEEE／RSJ International Conference on.IEEE，2005：3263－3268.

［12］Kennedy J，Eberhart R C.Particle swarm optimization［C］／／Proceedings of IEEE International Conference on Neutral Networks，Perth，Australia，1995：1942－1984.

［13］Shi Y H，Eberhart R C.A modified particle swarm optimizer［C］／／IEEE International Conference of Evolutionary Computation，Anchorage，Alaska， May 1998.

［14］Shi Y H，Eberhart R C.Parameter selection in particle swarm optimization［C］／／Annual，1998.

［15］Clerc M，Kennedy J.The particle swarm－explosion，stability，and convergence in a multidimensional complex space［J］.Evolutionary Computation，IEEE Transactions on，2002，6（1）：58－73.