模擬退火算法在飛機(jī)巡航最佳路線問題中的應(yīng)用

牛迎春　曾璐璐　包勇

摘要：飛機(jī)巡航最佳路線問題可歸結(jié)為大型TSP問題。TSP問題是典型的NP完全問題，模擬退火算法是求解NP完全問題的一種理想方法。在構(gòu)造了飛機(jī)巡航路線問題的模型后，采用加權(quán)的哈密頓方法，結(jié)合模擬退火策略對(duì)該問題進(jìn)行分析求解。重點(diǎn)介紹了模擬退火解決此問題的具體算法和過程。試驗(yàn)結(jié)果表明：采用模擬退火算法求解飛機(jī)巡航線路問題效果很好，與其它算法相比優(yōu)勢(shì)明顯。

關(guān)鍵詞：飛機(jī)巡航；哈密爾頓圈；模擬退火

DOIDOI：10.11907/rjdk.151318

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)文章編號(hào)：16727800（2015）008009402

0 引言

本文首先介紹了旅行商[1]問題，先列舉TSP問題的應(yīng)用，對(duì)其進(jìn)行數(shù)學(xué)描述，然后介紹了哈密爾頓圈。之后重點(diǎn)介紹模擬退火算法，主要介紹其基本思想和關(guān)鍵技術(shù)，在此基礎(chǔ)上將模擬退火的思想引入飛機(jī)巡航問題求解，并用MATLAB語言編程予以實(shí)現(xiàn)。

旅行商問題（Traveling Salesman Problem，TSP）是一個(gè)經(jīng)典的圖論問題 ， 在物流配送、 計(jì)算機(jī)網(wǎng)絡(luò)、 電子地圖、

交通誘導(dǎo)、電氣布線、VLSI 單元布局等方面都有重要的工程和理論價(jià)值 ， 引起了許多學(xué)者的關(guān)注。TSP可簡(jiǎn)單描述為 ： 設(shè)所有城市間兩兩連通，旅行商需要跑遍n個(gè)城市去推銷其商品，而這些城市之間的距離都不一樣。推銷員要從其中一個(gè)城市出發(fā)把所有城市跑遍，最后回到出發(fā)地。

飛機(jī)巡航問題是典型的旅行商問題。假設(shè)我方有一個(gè)基地，派一架飛機(jī)從基地出發(fā)，偵察完敵方所有目標(biāo)，再返回原來的基地。敵方每一目標(biāo)點(diǎn)偵察時(shí)間不計(jì)，求該飛機(jī)所花費(fèi)的最短時(shí)間。

模擬退火（Simulated Annealing）算法[2]是一種通過模擬金屬物理退火過程的一種啟發(fā)式算法，利用了物理中固體物質(zhì)的退火過程與一般優(yōu)化問題的相似性，從某一初始溫度開始，伴隨溫度的不斷下降，結(jié)合概率突跳特性，在解空間中隨機(jī)尋找全局最優(yōu)解。

1 數(shù)學(xué)規(guī)則模型

VRP[3]問題在圖論上一般描述為：記G=（V，E）為無向圖，其中V={vi|i=0，1，2，，n-1}為頂點(diǎn)集合，E={（vi，vj）|vi，vj∈V，i≠j}為各頂點(diǎn)相互連接組成的邊集，在該無向圖中頂點(diǎn)v1，v2，…，vn-1表示飛機(jī)巡航的目標(biāo)數(shù)，dij表示vi，vj兩點(diǎn)的距離。

2 飛機(jī)巡航問題的求解方法

人們解決問題一般采用就近原則。本文先給出了一個(gè)在隨機(jī)狀態(tài)下的路徑圖，這在實(shí)際生產(chǎn)生活中會(huì)對(duì)資源造成巨大浪費(fèi)，影響生產(chǎn)效率。

圖1 隨機(jī)路徑

2.1 哈密頓回路算法解決飛機(jī)巡航問題

給定圖G，若存在一條路，經(jīng)過圖中每個(gè)節(jié)點(diǎn)恰好一次，這條路稱作哈密爾頓路。若存在一條回路，經(jīng)過圖中每個(gè)節(jié)點(diǎn)恰好一次，這條路稱為哈密爾頓回路。具有漢密爾頓回路的圖稱作哈密爾頓圖。上述問題就是在哈密頓圖中找到一個(gè)權(quán)數(shù)最小的哈密頓圈C，然后用Matlab編程得到哈密爾頓最優(yōu)路徑總長(zhǎng)度為：

圖2 最優(yōu)哈密爾頓路徑

從圖2可以看出，哈密爾頓最優(yōu)路徑與隨機(jī)路徑比起來，訪問目標(biāo)有了巨大進(jìn)步，有了最優(yōu)路徑。但由于初始路徑不同，得到的最終路徑也不一樣，為解決這一問題，引入模擬退火算法。

2.2 模擬退火算法

模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻。加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。模擬退火算法從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解[4]。

2.2.1 模擬退火算法步驟

模擬退火算法[5]可以分解為解空間、目標(biāo)函數(shù)和初始解3部分。

①初始化：初始溫度T（充分大），初始解狀態(tài)S（是算法迭代的起點(diǎn)），每個(gè)T值的迭代次數(shù)L；②對(duì)k=1，……，L做第（3）至第6步；③產(chǎn)生新解S′；④計(jì)算增量Δf=C（S′）-C（S），其中C（S）為評(píng)價(jià)函數(shù)；⑤若Δf<0，則接受S′作為新的當(dāng)前解，否則以概率exp（-ΔfT）接受S′作為新的當(dāng)前解；⑥如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。終止條件通常為連續(xù)若干個(gè)新解都沒有被接受；⑦T逐漸減少，且T→0，然后轉(zhuǎn)第②步。

2.2.2 模擬退火算法過程描述（1）解空間S可表示為{1，2，3…102}的所有固定起點(diǎn)和終點(diǎn)的集合，為了方便編程，把出發(fā)地定位編號(hào)1，最后回到出發(fā)地的編號(hào)定位102，中間的目標(biāo)位置為{2，3，4，…101}。

（2）目標(biāo)函數(shù)：目標(biāo)函數(shù)就是代價(jià)函數(shù)為巡視所有目標(biāo)的路徑長(zhǎng)度，滿足：

為產(chǎn)生明顯對(duì)比，本文給出3種方法求解飛機(jī)巡航問題。隨機(jī)路徑圖在數(shù)據(jù)量較小的情況下，對(duì)資源沒有太大影響。但隨著數(shù)據(jù)量的增大，對(duì)資源的損耗也會(huì)成倍增長(zhǎng)。哈密爾頓最優(yōu)路徑與隨機(jī)路徑比有了很大進(jìn)步，但哈密爾頓最優(yōu)路徑是由局部最優(yōu)逐步擴(kuò)充到全局最優(yōu)的，選取不同的初始圈，得到的最終結(jié)果就會(huì)不一樣。模擬退火

算法是一種隨機(jī)性解決組合優(yōu)化方法，結(jié)合了概率突跳性，可以求解出優(yōu)化問題的全局最優(yōu)或近似全局最優(yōu)解[6]。

圖3 模擬退火求得的最優(yōu)路徑

通過實(shí)驗(yàn)數(shù)據(jù)的比較與分析，可知模擬退火是3種方法中最優(yōu)的。因此，用模擬退火算法求解飛機(jī)巡航問題最有效。

3 結(jié)語

本文給出了圖論中的哈密爾頓圈算法、模擬退火算法，通過算法對(duì)比，使問題得到了很好的解決。模擬退火算法可以有限度地接受劣解、跳出局部最優(yōu)解、原理簡(jiǎn)單、使用靈活、適合求解出優(yōu)化問題的全局最優(yōu)或近似全局最優(yōu)解。

參考文獻(xiàn)：

[1] 曲曉麗，潘昊，柳向斌.旅行商問題的一種模擬退火算法求解[J].現(xiàn)代電子技術(shù)，2007（18）：7882.

[2] 高尚.求解旅行商問題的模擬退火算法[J].華東船舶工業(yè)學(xué)院學(xué)報(bào)：自然科學(xué)版，2003，17（3）：1316.

[3] 左孝凌.離散數(shù)學(xué)[M].北京：經(jīng)濟(jì)科學(xué)出版社，2000：117134.

[4] 朱顥東，鐘勇.一種改進(jìn)的模擬退火算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2009，19（6）：3235.

[5] 宋燕子.基于模擬退火算法的啟發(fā)式算法在VRP中的應(yīng)用[D].武漢：華中師范大學(xué)，2013.

[6] 王如梅，王書銘，王戰(zhàn)軍.一種車輛路由問題的定向模擬退火算法[J].制造技術(shù)研究，2007，2（1）：1619.

（責(zé)任編輯：杜能鋼）