知識引導的智能優(yōu)化算法在航路規(guī)劃中的應用＊

劉 鋼，老松楊，侯綠林，譚東風

（國防科學技術(shù)大學 信息系統(tǒng)工程重點實驗室，湖南 長沙 410073）

航路規(guī)劃是一種多約束多目標非線性優(yōu)化問題，反艦導彈航路規(guī)劃是其中的一類新問題，對它的研究應把握反艦導彈的航路特征而有針對性地展開.反艦導彈航路規(guī)劃是一個空間搜索問題，需要采用基于幾何學的搜索算法進行求解.目前關(guān)于這類尋優(yōu)算法的研究比較深入，智能優(yōu)化算法是其中的一個大類，它是一類基于種群、能夠自適應搜索的優(yōu)化方法.近年來出現(xiàn)了很多基于智能優(yōu)化算法的航路規(guī)劃方法，常用的有遺傳算法[1]、蟻群算法[2]和粒子群算法[3]等.這些算法大都思想簡單，易于操作，且對優(yōu)化函數(shù)沒有特殊的要求.

智能優(yōu)化算法的主要缺點是收斂性問題，包括容易出現(xiàn)早熟收斂和收斂速度慢2個方面[4].導致這些缺點的一個重要原因就是智能優(yōu)化算法中缺乏明確的導向因子[5－6]，引導進化的思想因此而被提出，其目的就是加速收斂和避免早熟收斂.

在現(xiàn)有的求解航路規(guī)劃問題的智能優(yōu)化算法中，還沒有考慮直接挖掘和應用航路規(guī)劃問題領(lǐng)域知識進行引導優(yōu)化的方法.鑒于此，本文直接將航路規(guī)劃問題相關(guān)領(lǐng)域知識平行地融入到智能優(yōu)化算法中，提出一類基于智能優(yōu)化算法的航路規(guī)劃方法.

1 知識引導進化

1.1 引導進化及其存在的問題

引導進化就是利用特定問題領(lǐng)域的啟發(fā)式知識來指導、約束進化過程，它對問題的求解效果依賴于對問題領(lǐng)域認識的深度，并且算法性能也依賴于設(shè)計的技巧[7].針對這個問題，有關(guān)學者[5]提出通過傳統(tǒng)人工智能手段和特定知識模型來實現(xiàn)對智能優(yōu)化算法的進化引導，具體措施是采用知識模型從前期優(yōu)化過程中挖掘有用知識來指導智能優(yōu)化模型的后續(xù)優(yōu)化過程.這種知識存在明顯缺陷：1）這種知識是間接和抽象的“隱式”知識，它需要從前期進化過程中學習和歸納，而可供學習的樣本太少，因此，這種知識的可信度很低；2）它對算法的引導仍然是在對優(yōu)化算法本身后期的進化機制和進化過程逐步進行修補，無法適應進化環(huán)境的改變，缺乏全局性；3）由于它并沒有直接以問題領(lǐng)域為牽引，而是被動地、“守株待兔”式地獲取知識，因此，在求解具體問題時，這種知識具有極大的不確定性，并且無法解決如何運用這種知識引導算法的問題.

1.2 特定領(lǐng)域知識

本文認為在求解航路規(guī)劃問題時，可從問題背景中直接挖掘一些有用的知識，然后應用這些知識對優(yōu)化過程進行全過程引導和監(jiān)督.這里的知識指的是特定的領(lǐng)域知識，首先對它們進行形式化建模，然后結(jié)構(gòu)化為可以融入智能優(yōu)化算法的優(yōu)化策略，具體的智能優(yōu)化算法都可以通過開放的方式對這些策略進行更新和應用.本文所采用的特定領(lǐng)域知識與傳統(tǒng)引導進化所采用知識[5－7]的比較如表1所示.

表1 特定領(lǐng)域知識與傳統(tǒng)引導進化知識的比較Tab.1 Comparison of customizing domain knowledge and the knowledge adopted by conventional conducting evolution

本文所指特定領(lǐng)域知識與智能優(yōu)化算法的關(guān)系如圖1所示.傳統(tǒng)引導進化所采用的知識[5]與智能優(yōu)化算法的關(guān)系如圖2所示.

圖1 特定領(lǐng)域知識與智能優(yōu)化算法的關(guān)系Fig.1 The relation between customizing domain knowledge and intelligent optimization algorithms

從圖1和圖2可以看出，特定領(lǐng)域知識直接來源于待優(yōu)化問題，而在傳統(tǒng)的引導進化方法[5]中，所采用的知識來源于對智能優(yōu)化算法進化過程的學習，智能優(yōu)化算法也只是十分隱含地從待優(yōu)化問題所輸出的適應度中獲得極為有限的“暗示”，其知識模型與待優(yōu)化問題之間并無直接交互.因此，對于求解待優(yōu)化問題，特定領(lǐng)域知識的針對性更強，引導效果更好.

圖2 傳統(tǒng)引導進化的知識與智能優(yōu)化算法的關(guān)系Fig.2 The relation between knowledge adopted by conventional conducting evolution and intelligent optimization algorithms

2 知識引導型智能優(yōu)化算法的航路規(guī)劃求解框架

本節(jié)擬建立一個知識引導型智能優(yōu)化算法的航路規(guī)劃問題求解框架.該框架采用智能優(yōu)化算法和航路規(guī)劃中的特定領(lǐng)域知識相結(jié)合的集成建模思路：首先，通過分析反艦導彈的航路特征提煉出某種特定領(lǐng)域知識；其次，將這種特定領(lǐng)域知識形式化并結(jié)構(gòu)化為某種能夠改進算法性能的元策略；最后，將元策略實例化為與具體優(yōu)化算法相匹配的優(yōu)化策略，這將是個開放式的問題，不同的智能優(yōu)化算法就有不同的匹配策略.特定領(lǐng)域知識以元策略的形式對智能優(yōu)化算法的優(yōu)化過程進行引導和監(jiān)督.

2.1 知識引導方式

對于同一個待優(yōu)化問題，采用的智能優(yōu)化算法不同，所對應的編碼形式就不同，其算法搜索空間和約束條件表示形式也是不一樣的.因此，本文把算法搜索空間和約束條件表示形式歸于智能優(yōu)化算法范疇.為了描述引導方式，將智能優(yōu)化算法形式化定義為3個引導對象的集合.

定義1 智能優(yōu)化算法的集合論定義.

式中：IOA表示智能優(yōu)化算法；CC表示約束條件表示形式；SS表示算法搜索空間；EMP表示算法進化機制和過程.

從上述形式化定義中可以看出，對智能優(yōu)化算法的引導方式無非就是對它的3個引導對象進行單獨引導或者是組合引導，那么，這里一共有7（即23－1）類引導方式.可以將每一類引導方式看作一個集合，每一類引導方式又包括多種引導方法和策略.7類引導方式的集合論描述如圖3所示，其中，Ⅰ，Ⅱ，Ⅲ類為分別引導；Ⅳ，Ⅴ，Ⅵ，Ⅶ類為組合引導.

圖3 7類引導方式的集合論描述Fig.3 The set theory description of 7kinds of conducting manner

實際上，現(xiàn)有的對智能優(yōu)化算法的許多改進工作都可以歸結(jié)為這幾類引導方式.例如，精英保留[4，8－9]和引入子群[10－11]這2種策略都屬于對算法搜索空間SS的設(shè)計，它們的出發(fā)點是使算法的搜索空間更加合理，但最終只在一定程度上達到了維持個體多樣性以及使早熟收斂局部化的效果，對進化過程的引導并不明確.其他比如采用自適應操作算子[12]屬于對約束條件表示形式CC的設(shè)計，用機器學習來控制進化[13]屬于引導進化機制和過程EMP，它們都沒有考慮到個體進化（環(huán)境和特點）的復雜性，并且對進化過程的引導都不明確.以上都是從單獨引導的角度進行闡述，事實上各類引導方式之間往往是互相耦合的，更多的時候以組合引導的形式呈現(xiàn).

2.2 反艦導彈航路規(guī)劃的特定領(lǐng)域知識

通過對反艦導彈航路規(guī)劃問題進行分析研究，得到了一些特定領(lǐng)域知識，這些知識主要來源于反艦導彈的航路特征[14]，包括功能區(qū)域簇及其幾何學漸變規(guī)律以及其他航路性能約束.現(xiàn)將本文主要采用幾個相關(guān)知識歸納如下[14－15]：

1）功能區(qū)域簇及其幾何學漸變規(guī)律.

規(guī)律1 由于受最大有效射程的限制，滿足導彈航路距離約束的所有航路轉(zhuǎn)向點（導彈航向發(fā)生改變的航路點）必然在功能區(qū)域之內(nèi)；

規(guī)律2 由于受剩余最大有效射程的限制，滿足導彈航路距離約束條件的所有航路點必然在與其對應的剩余功能區(qū)域之內(nèi)；逆之，也成立；

規(guī)律3 在逆向航路規(guī)劃過程中，剩余功能區(qū)域逐漸變小，最后收斂于發(fā)射點；對于相鄰兩功能區(qū)域而言，后者包含于前者，并且兩者必內(nèi)切于一點.

2）其他航路性能約束 .最大轉(zhuǎn)向角度的約束；最小直線航段距離的約束.

2.3 航路規(guī)劃的求解框架及其運行機制

根據(jù)上述知識各自的特點，它們對智能優(yōu)化算法的引導方式也是不同的：其他航路性能約束用來設(shè)計約束條件表示形式CC，屬于Ⅰ類引導方式；功能區(qū)域（規(guī)律1）用來設(shè)計合理的算法搜索空間SS，屬于Ⅱ類引導方式；功能區(qū)域簇及其幾何學漸變規(guī)律（規(guī)律2和規(guī)律3）也是對算法搜索空間SS的引導，并且其所引導的是算法實時搜索空間，這似乎也屬于Ⅱ類引導方式，但前提是它必須被結(jié)構(gòu)化為某種元策略來引導算法的進化機制和過程EMP，這又屬于Ⅲ類引導方式，因此本質(zhì)上它是一種組合引導方式.知識引導型智能優(yōu)化算法的航路規(guī)劃基本求解框架如圖4所示.知識引導型智能優(yōu)化算法的航路規(guī)劃求解框架的運行機制分別如圖5和圖6所示.

圖4 知識引導型智能優(yōu)化算法的航路規(guī)劃求解框架Fig.4 The framework of knowledge－conducting intelligent optimization algorithms for solving path planning

圖5 特定領(lǐng)域知識引導進化的過程Fig.5 The process of evolution conducted by customizing domain knowledge

圖6 每次迭代中的分步更新元策略Fig.6 The sequential update meta－strategy in every iteration

圖5中描述了特定領(lǐng)域知識引導進化的過程.圖5中上部描述了智能優(yōu)化算法的優(yōu)化進程，不同的智能優(yōu)化算法按照各自的進化機制對航路規(guī)劃問題的可行空間進行搜索，經(jīng)過k次迭代，最終收斂到最優(yōu)或近似最優(yōu)的個體 .圖5中下部描述了獲取特定領(lǐng)域知識以及引導進化的過程，先從航路規(guī)劃問題中獲取特定領(lǐng)域知識，然后根據(jù)它們各自特點選擇對應的引導方式對智能優(yōu)化算法的優(yōu)化進程進行引導.圖6描述的是算法每次迭代中個體的更新機制及過程.圖6中所刻畫的功能區(qū)域（簇）及其幾何學漸變規(guī)律對算法（實時）搜索空間的引導是十分直觀的，實現(xiàn)這種引導的前提條件是需要元策略的支持，即必須引入某種元策略來改進進化機制，使得特定領(lǐng)域知識與智能優(yōu)化算法相匹配.為此，作如下定義.

定義2 功能區(qū)域的幾何學漸變規(guī)律使得航路的相鄰節(jié)點間存在關(guān)聯(lián)關(guān)系，即后一個節(jié)點的合法范圍受到前一個節(jié)點的約束，需要將其映射為智能優(yōu)化算法中個體分量之間的關(guān)聯(lián)關(guān)系，為了在算法中實現(xiàn)這種約束關(guān)聯(lián)性，對個體中參與更新的各分量按順序逐步進行更新，將這種策略稱為分步更新元策略.

其他航路性能約束對進化過程的引導則通過適應值函數(shù)的設(shè)計來實現(xiàn).

將知識引導型智能優(yōu)化算法的航路規(guī)劃求解框架實例化為采用具體智能優(yōu)化算法的航路規(guī)劃方法，這是一個開放式問題，智能優(yōu)化算法不同，優(yōu)化策略就不同.將（分步更新）元策略實例化為具體優(yōu)化策略的過程必須要適應所采用智能優(yōu)化算法的特征.下面以粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法為例，驗證上述基本框架的正確性和有效性.

3 仿真實驗及分析

3.1 選用算法及其基本設(shè)計

本文選用PSO算法主要是考慮兩個方面的原因.一方面是PSO算法本身具有的性能優(yōu)勢 .首先，PSO算法具有概念簡單，實現(xiàn)容易，易于操作，調(diào)整參數(shù)少等優(yōu)點 .其次，PSO算法的魯棒性好，收斂速度快，這兩個顯著特點使得它非常適合于對實時性要求較高的復雜問題進行求解.另一方面是PSO算法對航路規(guī)劃問題的適應性 .首先，PSO算法無論是從編碼方式還是進化過程來說，都具有與其他智能優(yōu)化算法無可比擬的幾何表達能力，從幾何空間到解空間（搜索空間）的映射十分直觀 .其次，作為一種全局連續(xù)搜索算法，其進化公式和進化過程都是連續(xù)的，這兩點與非網(wǎng)格拓撲的航路規(guī)劃問題的幾何學特點十分吻合.

知識引導的航路規(guī)劃PSO算法是知識引導型智能優(yōu)化算法的航路規(guī)劃求解框架的驗證及應用實例，它是在通用求解框架下采用PSO算法來求解反艦導彈航路規(guī)劃問題，技術(shù)方法就是運用元策略來改進算法性能，需要采用合適的編碼方式和進化過程將通用求解框架中的元策略映射為與PSO算法相匹配的進化策略.算法基本設(shè)計如下：1）為了記錄每個航路轉(zhuǎn)向點的位置信息，采用定長實數(shù)編碼粒子結(jié)構(gòu).一個粒子表示搜索空間中的一條備選航路，粒子中的相應分量代表航路點的位置分量.2）采用文獻[15]中的多屬性模糊優(yōu)化方法建立適應度函數(shù).

3.2 實驗方案設(shè)計和實驗環(huán)境

實驗方案：為了測試本文提出的不同引導方式對PSO算法的引導效果，在相同的實驗條件下，分別在不采用知識引導進化和采用Ⅰ，Ⅳ，Ⅶ3類引導方式的情況下對PSO算法進行4組仿真實驗.

實驗1 不采用知識引導進化.

實驗2 采用引導方式Ⅰ.使用航路性能的限制對算法進行約束引導，具體方法是將航路性能約束條件以懲罰代價的形式加入適應值函數(shù)的“加權(quán)和”.

實驗3 采用引導方式Ⅳ，它是引導方式Ⅰ和Ⅱ的組合形式.使用功能區(qū)域?qū)λ惴ǖ乃阉骺臻g（解空間）進行引導，具體方法是將功能區(qū)域映射到粒子所存在的R2n空間中.

實驗4 采用引導方式Ⅶ，它是引導方式Ⅰ，Ⅱ和Ⅲ的組合形式.使用功能區(qū)域簇及其幾何學漸變規(guī)律所指代的航路規(guī)劃領(lǐng)域知識的結(jié)構(gòu)化元策略對算法的進化機制和過程進行引導，具體方法是將功能區(qū)域簇及其幾何學漸變規(guī)律（粒子分量之間的關(guān)聯(lián)性）映射到粒子進化過程中.為了體現(xiàn)這種關(guān)聯(lián)性，算法并不是對粒子的整個速度（或位置）分量同時進行更新，而是采用遞歸思想對粒子各分量按順序逐步進行更新的分步遞歸進化策略.

可以看出，以上4組實驗所采用的引導方式是逐漸加強的.

實驗環(huán)境：硬件環(huán)境為Genuine Intel（R）CPU 1.80GHz，1G內(nèi)存的PC機，運行環(huán)境為Windows XP Professional，編 程 環(huán) 境 為 Matlab Release 2009a.綜合考慮航路質(zhì)量（精度）與規(guī)劃時間，通過反復實驗，設(shè)定種群大小為100，航路轉(zhuǎn)向點個數(shù)為3，即粒子維數(shù)為6，最大迭代次數(shù)為200.

3.3 算法性能測度和實驗結(jié)果

本文仿真實驗的目的是測試算法的尋優(yōu)精度和收斂速度，算法性能測試采用以下3個評價指標：1）平均最優(yōu)適應值fmean；2）最優(yōu)適應值的標準差σ；3）平均迭代次數(shù)MIT.其中，MIT是指所得適應值結(jié)果滿足規(guī)定閾值時，算法所需平均迭代次數(shù).對最大迭代次數(shù)內(nèi)仍不能滿足規(guī)定閾值的實驗，不參與此測度計算.

每個實驗獨立進行20次仿真，對于第i次仿真，分別記錄第j次迭代結(jié)束時生成的最優(yōu)航路的適應值fi，j以及達到規(guī)定閾值所需的迭代次數(shù)ITi，再記錄每組實驗中迭代200次時仍不能滿足規(guī)定閾值的仿真次數(shù)jn.則每組實驗第j次迭代后的平均最優(yōu)適應值fmeanj、迭代200次以后平均最優(yōu)適應值的標準差σ以及MIT分別為：

經(jīng)整理后的實驗結(jié)果數(shù)據(jù)如表2所示.4組實驗的平均最優(yōu)適應值的收斂曲線如圖7所示.

表2 4組實驗的算法性能測度結(jié)果比較Tab.2 Comparison of performance measures results produced by 4experiments

圖7 4組實驗的平均最優(yōu)適應值收斂曲線Fig.7 The convergence curve of mean best fitness respectively generated by 4experiments

3.4 實驗結(jié)果比較與分析

對實驗結(jié)果進行比較，可以得到以下結(jié)論：

1）從fmean的角度比較來說，除了實驗1和實驗2相差無幾以外，隨著引導方式的逐漸加強，得到的fmean越來越大，說明算法的尋優(yōu)質(zhì)量和精度逐漸提高.2）從σ的角度比較來說，除了實驗1和實驗2相差無幾以外，隨著引導方式的逐漸加強，得到的σ越來越小，并且是成數(shù)量級地減小，表明算法的魯棒性和穩(wěn)定性得到了很大的提高.3）從MIT的角度比較來說，實驗4的MIT明顯小于其他3組實驗，實驗2和實驗3的MIT又比實驗1的小了許多，表明算法的收斂速度也得到了不同程度的提高.

從以上結(jié)論可以看出：采用了知識引導的各組實驗都比沒有采用知識引導的實驗1在算法的整體性能上有了不同程度的提高，這充分說明了知識引導進化的有效性.但實驗4所提高的幅度要比其他各組實驗的大很多，而實驗2與實驗1的比較卻并不明顯，這同時也說明了不同引導方式所產(chǎn)生的引導效果有很大的差別.具體分析如下：

1）實驗1和實驗2的實驗結(jié)果在整體上相差不多，這說明對適應值函數(shù)的懲罰“加權(quán)和”形式的引導效果十分有限，究其原因是適應值函數(shù)只對個體的優(yōu)劣進行排序，其對算法性能沒有太大的影響.

2）實驗3的實驗結(jié)果在整體上比前2組實驗有了一定程度的提高，說明對搜索空間的引導效果比較好，究其原因是其排除了種群中比較劣質(zhì)的個體，從整體上提高了種群的質(zhì)量.

3）實驗4的實驗結(jié)果在各方面均有很大幅度的提高，這說明對算法進化機制的引導效果非常好，究其原因是種群中的個體全部為非劣個體，每一代種群的質(zhì)量都很好.

4 結(jié)束語

為了解決傳統(tǒng)智能優(yōu)化算法的早熟收斂問題，本文引入知識引導進化的策略求解反艦導彈航路規(guī)劃問題，提出了一種知識引導型智能優(yōu)化算法的航路規(guī)劃求解框架.以PSO算法為例，根據(jù)航路規(guī)劃特定領(lǐng)域知識的各自特點選擇相應的引導方式對不同的引導對象進行引導，實現(xiàn)了特定領(lǐng)域知識和引導對象之間的良好匹配以及問題領(lǐng)域背景和智能優(yōu)化算法的良好結(jié)合.本文提出的對于智能優(yōu)化算法的3個引導對象和7類引導方式具有普適意義，特定領(lǐng)域知識引導的智能優(yōu)化算法問題求解框架也可以運用到其他優(yōu)化問題中，具有很好的借鑒意義.

[1] TAL S，COREY S.Assignment of cooperating UAVs to simultaneous tasks using genetic algorithms[R].San Francisco：AIAA，2005：5829－5843.

[2] NAUYEN H V，NGO A V，SEUNG G L，etal.Obstacle avoidance path planning for mobile robot based on multi colony ant algorithm[C]／／First International Conference on Advances in Computer－Human Interaction.Martinique：IEEE，2008：285－289.

[3] JUNG L F，JARED S K，VIJAY K，etal.Path planning of unmanned aerial vehicles using B－splines and particle swarm optimization[J].Journal of Aerospace Computing，Information，and Communication，2009，6（4）：271－290.

[4] RUDOLPH G.Convergence analysis of canonical genetic algorithms[J].IEEE Transactions on Neural Networks，1994，5（1）：96－101.

[5] 邢立寧.演化學習型智能優(yōu)化方法及其應用研究[D].長沙：國防科學技術(shù)大學信息系統(tǒng)與管理學院，2009.XING Li－ning.Research on the learnable intelligent optimization approaches and its applications[D].Changsha：School of Information Systems and Management，National University of Defense and Technology，2009.（In Chinese）

[6] 曹先彬，許凱，章潔，等.基于生命期引導的生態(tài)進化模型[J].軟件學報，2000，11（6）：823－828.CAO Xian－bin，XU Kai，ZHANG Jie，etal.Ecological evolution model guided by life period[J].Journal of Software，2000，11（6）：823－828.（In Chinese）

[7] 范磊，阮懷忠，焦譽，等.用歸納學習引導進化[J].中國科學技術(shù)大學學報，2001，31（5）：565－570.FAN Lei，RUAN Huai－zhong，JIAO Yu，etal.Conduct evolution using induction learning[J].Journal of China University of Science and Technology，2001，31（5）：565－570.（In Chinese）

[8] DEJONG K A.An analysis of the behavior of a class of genetic adaptive systems[D].Michigan：University of Michigan，1975.

[9] BHANDARI D.Genetic algorithm with elitist model and its convergence[J].International Journal of Pattern Recognition and Artificial Intelligence，1996，10（6）：731－747.

[10] JONES T.Crossover，macromutation and population－based search[C]／／Eshelman Led.Proceedings of the 6th International Conference on Genetic Algorithms.San Francisco：Morgan Kaufmann Publishers，1995：73－80.

[11] SCHRADOPH N N.Dynamic parameter encoding for genetic algorithms[J].Machine learning，1992，9（1）：9－21.

[12] SRINIVAS M.Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Transactions on Systems，Man and Cybernetics，1994，24（4）：656－667.

[13] SEBAG M，RAVISE C，SCHOENAUER M.Controlling evolution by means of machine learning[C]／／Proceedings of the Fifth Annual Conference on Evolutionary Programming.San Diego，California：The MIT Press，1996：57－66.

[14] 劉鋼，老松楊，譚東風，等.反艦導彈航路規(guī)劃圖形化快速逆推方法[J].彈道學報，2011，23（2）：52－56.LIU Gang，LAO Song－yang，TAN Dong－feng，etal.Fast graphic converse calculating method for anti－ship missile path planning[J].Journal of Ballistics，2011，23（2）：52－56.（In Chinese）

[15] 劉鋼，老松楊，譚東風.基于功能區(qū)域的反艦導彈逆向航路規(guī)劃[J].系統(tǒng)工程與電子技術(shù)，2011，33（4）：799－805.LIU Gang，LAO Song－yang，TAN Dong－feng.Converse path planning for anti－ship missiles based on operational area[J].Systems Engineering and Electronics，2011，33（4）：799－805.（In Chinese）