一種改進遺傳算法在UCAV快速航跡規(guī)劃中的應(yīng)用*

顧潮琪，周德云

（西北工業(yè)大學(xué)電子信息學(xué)院，西安710129）

一種改進遺傳算法在UCAV快速航跡規(guī)劃中的應(yīng)用*

顧潮琪，周德云

（西北工業(yè)大學(xué)電子信息學(xué)院，西安710129）

針對無人作戰(zhàn)飛機（Unmanned Combat Aerial Vehicle，UCAV）航跡規(guī)劃約束條件復(fù)雜、不確定因素多、實時性要求高的特點，提出了一種基于Voronoi圖和改進遺傳算法的快速航跡規(guī)劃方法。該方法采取分層航跡規(guī)劃的思想，首先根據(jù)Voronoi圖生成初始航跡，并綜合考慮約束條件，賦予各條航跡相應(yīng)的權(quán)值；然后應(yīng)用改進的遺傳算法在生成的航跡空間中尋優(yōu)，最終得到滿意的航跡。該算法利用多處理機并行計算技術(shù)對傳統(tǒng)遺傳算法進行改進，大大縮短尋優(yōu)時間。仿真結(jié)果表明基于Voronoi圖和改進遺傳算法的航跡規(guī)劃提高了實時性，增強了UCAV的動態(tài)戰(zhàn)場適應(yīng)能力和突發(fā)威脅應(yīng)對能力。

無人作戰(zhàn)飛機，改進遺傳算法，Voronoi圖，航跡規(guī)劃，實時性

0 引言

在防空技術(shù)日益先進且防空體系日益完善的現(xiàn)代戰(zhàn)爭環(huán)境中，航跡規(guī)劃是提高UCAV作戰(zhàn)效能、實施遠程精確打擊的有效手段［1］。其核心內(nèi)容就是在任務(wù)空間內(nèi)找到一條能夠到達指定區(qū)域的飛行航線，在滿足相關(guān)約束前提下使某種性能指標最優(yōu)［2］。當UCAV在作戰(zhàn)過程中遇到突發(fā)威脅，或需要攻擊時間敏感性目標時，時間作為一個不可忽視的因素越來越受到人們的關(guān)注和重視，快速航跡規(guī)劃已成為提高飛行器環(huán)境適應(yīng)性和生存能力的重要方法。傳統(tǒng)求解方法如動態(tài)規(guī)劃法、Dijkstra算法、A*算法等需要對規(guī)劃空間進行全面搜索，并行計算效果差，存在組合爆炸的問題；而智能規(guī)劃算法如模擬退火算法［3］、遺傳算法（Genetic Algorithm，GA）［4］、神經(jīng)網(wǎng)絡(luò)［5］以及群智能算法中的蟻群算法［6］、粒子群算法［7］等無法適應(yīng)優(yōu)化目標的動態(tài)變化，并且計算時間長，多用于離線尋優(yōu)。

因此，本文提出了一種能進行動態(tài)決策的改進遺傳算法（Improved Genetic Algorithm，IGA），該算法是在傳統(tǒng)遺傳算法的基礎(chǔ)上，借助于并行計算技術(shù)，在確定優(yōu)化目標（決策）期間對可能的多個優(yōu)化目標函數(shù)的優(yōu)良個體進行培養(yǎng)，一旦優(yōu)化目標確定后就能根據(jù)預(yù)先培養(yǎng)的優(yōu)良個體進行快速尋優(yōu)，使遺傳算法具有動態(tài)性能，能夠適應(yīng)優(yōu)化目標的動態(tài)變化，提高尋優(yōu)的實時性。

1 基于Voronoi圖的戰(zhàn)場空間構(gòu)建

1.1 初始航跡集合

Voronoi圖是計算幾何學(xué)中的一種重要幾何結(jié)構(gòu)，它應(yīng)用在航跡規(guī)劃中的最大特點是能夠根據(jù)已知戰(zhàn)場威脅源分布情況建立規(guī)劃空間模型并生成初始可選航跡集合［8］。根據(jù)Voronoi圖的性質(zhì)，UCAV沿著Voronoi邊進行飛行將獲得最大的安全性。如果任意加入一個威脅點，也只影響該點鄰近威脅點所組成的多邊形內(nèi)Voronoi圖的構(gòu)造，不影響該多邊形以外Voronoi圖的重新構(gòu)造。因此，Voronoi圖適用于戰(zhàn)場環(huán)境變化情況下UCAV局部航跡重規(guī)劃，如突發(fā)威脅體下航跡重規(guī)劃的情況。

基于構(gòu)建的戰(zhàn)場環(huán)境Voronoi圖，UCAV的初始航跡集合可以表示為：Voronoi圖的頂點為航跡中途點，邊為航跡段，從UCAV起始點到目標點的Voronoi圖邊的組合構(gòu)成許多條航跡。從這些組合中選擇從UCAV起始點到目標點的n條航跡，構(gòu)成UCAV的初始航跡集合。

1.2 航跡代價計算

UCAV航跡規(guī)劃通?？紤]的約束條件有［9］：①威脅因素；②航跡長度約束；③UCAV的機動能力；④最小航跡段長度；⑤飛行高度限制。因此，本文UCAV的航跡代價包括威脅代價Jthreat、燃油代價Jfuel、最大拐彎角代價Jangle和最小航跡段代價Jlength。各種代價的計算公式如下：

綜合考慮上述威脅代價、燃油代價、最大拐彎角代價和最小航跡段代價之后，可以得到UCAV航跡規(guī)劃的最小性能指標為：

其中k1、k2、k3和k4為權(quán)衡系數(shù)且k1+k2+k3+k4=1，取4個代價之間一個折衷的數(shù)，加權(quán)的大小取決于權(quán)項的重要性和可行性的綜合指標，本文采用層次分析法確定航跡代價函數(shù)中的權(quán)系數(shù)。

2 基于改進遺傳算法的航跡規(guī)劃

2.1 改進遺傳算法

改進遺傳算法的設(shè)計思想借鑒了多處理機并行處理技術(shù)［10-11］，在一臺處理機做決策時，用另外一臺處理機對所有可能的目標進行預(yù)先進化，培養(yǎng)每一個可能的優(yōu)化目標函數(shù)的優(yōu)良個體。一旦決策做出，種群內(nèi)部就已經(jīng)包含著對所有目標函數(shù)（決策）的，非常接近于最優(yōu)解的優(yōu)良個體。在此基礎(chǔ)上進行具體目標函數(shù)的尋優(yōu)，則可以大大縮短尋優(yōu)時間，提高實時性，并且可以使遺傳算法能夠適應(yīng)優(yōu)化目標的動態(tài)變化。

根據(jù)上述設(shè)計思想，改進遺傳算法的關(guān)鍵在于進化過程中對各個目標的優(yōu)良個體進行保留，如果有n個可能的目標函數(shù)，則只要一個個體對某一個函數(shù)較優(yōu)，就可保留。假定有n個候選的目標函數(shù)，可以根據(jù)先驗知識選擇一個作為主目標函數(shù)，例如f1，而f2……fn作為隱含目標函數(shù)。當前種群中的個體對每一個目標函數(shù)都有目標函數(shù)值，在f1進化時，通過正常的選擇、交叉和變異操作形成新個體集合。新個體對每一個目標函數(shù)也有不同的適應(yīng)度和函數(shù)值，在用新個體替換原來種群中的部分個體時，就不能僅僅按照對f1的適應(yīng)度來考慮，還要考慮其對所有目標函數(shù)的適應(yīng)度。因此，需要替換掉那些對所有函數(shù)都不優(yōu)的個體，而不僅僅是替換掉所有對f1不優(yōu)的個體。對此，設(shè)置一個綜合適應(yīng)度，它是個體對各個目標函數(shù)適應(yīng)度的加權(quán)。

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

基于改進遺傳算法航跡規(guī)劃的關(guān)鍵在于適應(yīng)度函數(shù)的設(shè)計，通過對約束條件的處理即進化過稱中采用并行計算技術(shù)對UCAV航跡規(guī)劃的各種代價函數(shù)進行計算以形成綜合適應(yīng)度，一旦戰(zhàn)場環(huán)境發(fā)生變化，可以通過調(diào)整代價函數(shù)而形成新的綜合適應(yīng)度來滿足需求。

對于單條UCAV航跡，可將式（5）作為其適應(yīng)度函數(shù)，并且假定威脅代價值最小、燃油代價值最小、最大拐彎角代價最小和最小航跡段代價最小為4個可能的目標函數(shù)，即：

根據(jù)作戰(zhàn)經(jīng)驗，規(guī)避威脅是UCAV對地打擊過程中需要首先考慮的，因此，將f1作為主目標函數(shù)，f2，f3和f4作為隱含目標函數(shù)。進化過程中，在f1尋優(yōu)時保留對f2，f3和f4較優(yōu)的個體于種群之中，培養(yǎng)每一個可能尋優(yōu)的目標函數(shù)的優(yōu)良個體，這樣一旦優(yōu)化目標發(fā)生變化，如出現(xiàn)突發(fā)威脅時，通過調(diào)整加權(quán)系數(shù)使綜合適應(yīng)度發(fā)生變化，在此種群基礎(chǔ)上對新的綜合適應(yīng)度的尋優(yōu)能夠很快收斂。

2.3 基于改進遺傳算法的航跡搜索流程

同傳統(tǒng)遺傳算法的航跡搜索流程一樣，只是改進的遺傳算法在進化過程中對適應(yīng)度函數(shù)的確定是一個動態(tài)變化的過程，因此，基于Voronoi圖模型與改進遺傳算法的UCAV快速航跡搜索流程圖如圖1所示。

圖1 基于改進遺傳算法的航跡搜索流程

3 仿真實驗及結(jié)果分析

仿真采用雙線程方式，第1個線程實時地接受戰(zhàn)場環(huán)境信息，確定綜合適應(yīng)度函數(shù)；第2個線程則進行預(yù)先進化操作，對航跡威脅、燃油、最大拐彎角、最小航跡段代價培養(yǎng)優(yōu)良個體。一旦綜合適應(yīng)度函數(shù)確定，根據(jù)遺傳算法獲得最優(yōu)解。

（1）實驗1：靜態(tài)環(huán)境下的航跡規(guī)劃

在本組實驗中，根據(jù)預(yù)先設(shè)定的威脅源建立戰(zhàn)場空間Voronoi圖并生成初始化航跡，如圖3所示。然后采用IGA和GA進行航跡搜索，在分別循環(huán)60次和61次后得到的最優(yōu)航跡如圖4所示。從圖中可以看出，兩種算法都可以搜索到最優(yōu)航跡并且規(guī)劃結(jié)果相同。

圖2 IGA和GA的初始化航跡

圖3 IGA和GA的最優(yōu)化航跡

圖4是IGA與GA綜合適應(yīng)度隨進化代數(shù)的變化曲線，由于在本次實驗中未出現(xiàn)新的威脅，綜合適應(yīng)度函數(shù)沒發(fā)生變化，因此，兩種算法的綜合適應(yīng)度變化過程基本相兩種算法的計算過程相同。

圖4 IGA與GA綜合適應(yīng)度變化曲線

圖5 突發(fā)威脅下的最優(yōu)化航跡

（2）實驗2：突發(fā)威脅情況下的航跡規(guī)劃

在本組實驗過程中，突發(fā)威脅出現(xiàn)在坐標的位置，其他參數(shù)與實驗一設(shè)置相同。圖5給出了突發(fā)威脅情況下基于IGA和GA的最優(yōu)化航跡，兩種算法的規(guī)劃結(jié)果仍然相同。

兩種算法在規(guī)劃過程中對突發(fā)威脅的處理方式是不同的。當出現(xiàn)突發(fā)威脅時，引起局部Voronoi圖重構(gòu)，由于GA在搜索航跡過程中，事先已經(jīng)確定好適應(yīng)度函數(shù)，先前通過遺傳進化產(chǎn)生的種群中只有較少部分個體能適應(yīng)這一變化，影響最終規(guī)劃結(jié)果，甚至無法獲得最優(yōu)航跡。因此，GA需要重新進行初始航跡生成并進行航跡搜索，這樣會造成大量的時間消耗。而基于IGA的航跡規(guī)劃在搜索過程中保留了對所有可能目標函數(shù)的最優(yōu)個體，當出現(xiàn)突發(fā)威脅后，通過調(diào)整所有可能目標函數(shù)的加權(quán)系數(shù)，形成新的綜合適應(yīng)度以滿足優(yōu)化目標要求。綜合適應(yīng)度隨進化代數(shù)的變化曲線如圖6所示，表1給出了突發(fā)威脅情況下兩種算法航跡規(guī)劃的部分實驗數(shù)據(jù)。

圖6 突發(fā)威脅下的綜合適應(yīng)度變化曲線

表1 突發(fā)威脅下基于IGA和GA的航跡規(guī)劃部分實驗數(shù)據(jù)

從圖6和表1可以看出，威脅出現(xiàn)前，兩種算法計算過程類似，綜合適應(yīng)度的變化趨勢一致，進化代數(shù)和所需時間基本相同。第22代，出現(xiàn)了突發(fā)威脅，基于IGA的航跡規(guī)劃調(diào)整綜合適應(yīng)度函數(shù)，又經(jīng)過45次迭代搜索到最優(yōu)航跡，總的進化代數(shù)和時間與實驗一基本相同，可見突發(fā)威脅對利用IGA進行的航跡規(guī)劃影響不大；而傳統(tǒng)遺傳算法需重新生成初始航跡并進行搜索，綜合適應(yīng)度變化劇烈，經(jīng)過83代才重新搜索到最優(yōu)航跡，與基于IGA的航跡規(guī)劃相比，進化代數(shù)增加了38代，所需時間也增加了將近1 s。由于突發(fā)威脅無法預(yù)知，這要求航跡規(guī)劃算法必須能夠迅速更新環(huán)境信息，同時還要在指定時間內(nèi)得出較為滿意的規(guī)劃結(jié)果，而基于IGA的航跡規(guī)劃通過調(diào)整綜合適應(yīng)度函數(shù)，提高了航跡搜索的快速性。

4 結(jié)束語

本文根據(jù)分層航跡規(guī)劃的思想，將一種改進的遺傳算法應(yīng)用到UCAV的快速航跡規(guī)劃中。在深入分析了UCAV航跡規(guī)劃的約束條件和戰(zhàn)場環(huán)境基礎(chǔ)上，利用Voronoi圖的拓撲特性，建立了基于Voronoi圖航跡規(guī)劃空間模型；并在計算航跡代價時，全面考慮了威脅代價、燃油代價、最大拐彎角代價以及最小航跡段代價。而改進的遺傳算法通過預(yù)先進化策略對遺傳算法進行改進，即通過多處理機并行計算技術(shù)，在確定優(yōu)化目標的過程中先進行預(yù)先進化，培養(yǎng)每一個可能尋優(yōu)的目標函數(shù)的優(yōu)良個體，在優(yōu)化目標確定之后進行快速尋優(yōu)，使其能夠在目標函數(shù)是動態(tài)確定的情況下使用。因此，該方法運用在UCAV航跡規(guī)劃中保證了實時性，實現(xiàn)了環(huán)境改變時，優(yōu)化目標就改變并快速尋優(yōu)的進化。

［1］王俊，周樹道，朱國濤，等.無人機航跡規(guī)劃常用算法［J］.火力與指揮控制，2012，37（8）:5-8.

［2］Wang Y Y，Wei T T，Qu X J.Study of Multi-objective Fuzzy Optimization for Path Planning［J］.Chinese Journal of Aeronautics，2012，25（4）:51-56.

［3］Tavares R S，Martins T C，Tsuzuki M S G.Simulated Annealing with Adaptive Neighborhood:A Case Study in Off-line Robot Path Planning［J］.Expert Systems with Applications，2011，38（4）:2951-2965.

［4］嚴江江，丁明躍，周成平.基于K均值聚類和遺傳算法的多航跡規(guī)劃方法［J］.火力與指揮控制，2010，35（3）: 147-150.

［5］Howard L，Simon X Y，Yevgen B.Neural Network Based Path Planning for A Multi-Robot System with Moving Obstacles［C］//The 4th IEEE Conference on Automation Science and Engineering，Washington DC，2008.

［6］Chen M，Wu Q X，Jiang C H.A Modify Ant Optimization Algorithm for Path Planning of UCAV［J］.Applied Soft Computing Journal，2008，8（4）:1712-1718.

［7］Foo J L，Knutzon J S，Oliver J H.Three-Dimensional Multi-Objective Path Planning of Unmanned Aerial Vehicles Using Particle Swarm Optimization［C］//AIAA 2007-1881.

［8］李華超，吳潛，陳春俊.VORONOI圖的無人機航路快速初始規(guī)劃［J］.火力與指揮控制，2009，34（1）:79-81.

［9］Yan P，Ding M Y，Zheng C W.Coordinated Route Planning via Nash Equilibrium and Evolutionary Computation［J］. Chinese Journal of Aeronautics，2006，19（1）:18-23.

［10］李少華，魏海光，周成平，等.一種海上無人飛行器的快速航跡規(guī)劃方法［J］.四川兵工學(xué)報，2011，32（12）: 73-76.

［11］史建國，高曉光，李相民.“預(yù)先”進化遺傳算法研究［J］.宇航學(xué)報，2005，26（2）:168-173.

Application of an Improved Genetic Algorithm in Fast Path Planning for UCAV

GU Chao-qi，ZHOU De-yun
（School of Electronic Information，Northwestern Polytechnical University，Xi’an 710129，China）

Due to the complex constraints，more uncertain factors and critical real-time demand of path planning for UCAV，an approach of fast path planning based on Voronoi diagram and improved genetic algorithm is proposed，which makes use of the principle of hierarchical path planning.First the Voronoi diagram is utilized to generate the initial paths and calculate the weight of the paths by considering the constraints.Then the optimal path is searched by using the improved genetic algorithm. Multiprocessors parallel computing techniques are used to improve the traditional genetic algorithm and the optimal time is greatly reduced.Simulation results verify that path planning based on Voronoi diagram and IGA is more favorable in the real-time operation.It can improve the adaptability of dynamic battlefield and unexpected threats for UCAV.

unmanned combat aerial vehicle，improved genetic algorithm，Voronoi diagram，path planning，real-time

TP391.9

A

1002-0640（2015）02-0070-04

2013-12-08

2014-01-24

航空科學(xué)基金（20115553021）；西北工業(yè)大學(xué)基礎(chǔ)研究基金資助項目（JC20110222）

顧潮琪（1979-），男，浙江金華人，博士生。研究方向：航空火力與指揮控制，先進綜合控制理論及應(yīng)用。