退火算法與神經網絡算法結合在路徑規劃中的研究

李江偉，許倫輝

（華南理工大學 土木與交通學院，廣州 510641）

退火算法與神經網絡算法結合在路徑規劃中的研究

李江偉，許倫輝

（華南理工大學 土木與交通學院，廣州 510641）

路徑規劃問題是計算機、數學、交通、機器人等包含了眾多領域在內的經典問題，它可以被描述為一個最優化問題。為了解決經典算法在求解最優路徑時運算時長的問題，該文研究了神經網絡和模擬退火算法的特點，建立了一般路網的數學模型；根據神經網絡和模擬退火算法的特點設計了適合車輛誘導的路網最優路徑算法。結果表明，應用神經網絡算法和模擬退火算法相結合，比單獨使用任何一個算法的效率高。

路徑規劃；神經網絡；模擬退火算法

一個網絡中，在滿足一定的約束條件下，找出一條從任意2點之間的最優路徑，可以是時間少、距離最短，也可以是費用最低，或者有多個優化目標，考慮這幾種因素的綜合影響。路徑規劃在很多領域都有著非常廣泛的應用，例如交通、物流、通信系統的路由搜索、機器人行走路線規劃等，以及近兩年非常熱門的無人機，路徑規劃算法已成為其最為關鍵的核心技術之一。路徑規劃問題可以表示為一個數學上的多目標優化問題，因此在路徑規劃問題就轉化為求解相應的數學優化問題。在此，重點研究利用合適的方法求解最優解。

最短路徑問題是網絡優化中的一個最基本的也是最重要的分支，同時也是所有路徑規劃問題的基礎。許多路徑規劃問題都可以轉化為這樣的最短路徑問題模型來表達，或者可以用最短路算法作為子程序。

為路徑的權值，是特定情況下的約束條件，研究的目的就是在約束條件下求得目標函數的最小值。在實際的交通路網中，路段或者節點的數量都是非常多的，求解的復雜度較高，需要找到一種既能夠較好地找到全局最優解，又有著較快的運算速度的方法。因此，提出了一種基于模擬退火-Hopfield神經網絡的算法（SA-CHNN），并利用神經網絡的高度并行性，借助并行計算技術來提高算法的計算速度，且能夠有效地求得全局最優解。

1 模擬退火算法

1.1 退火算法原理

模擬退火是一種隨機的搜索方法，其靈感來自于退火的過程。它的基本思想是，首先將溫度設置為一個足夠高的水平，此時絕大部分的隨機運動方向都是可行的，可以在比較大的空間內找到一個目標值相對低的區域；隨著溫度根據一定的規則慢慢降低，各個方向被選中的概率會變得不一樣，當然搜索的精度也不斷提高。模擬退火算法的更新迭代過程主要用到MetroPolis準則，具體如下：

①假設狀態在xk時，當使用一定的擾動對系統進行影響，使狀態發送變化，得到一個新的狀態xk+1，前后兩個狀態對應的系統能量分別為E（xk）和E（xk+1），能量差為ΔE；

②ΔE≤0，則轉換為狀態 xk+1；

③ΔE≥0，則轉換為xk+1的概率為

式中：K為波爾茲曼常量；T為溫度；Z（T）為規范化因子。

④設 r＝random（0，1）為（0，1）上的隨機數，與 Pr進行比較。若Pr≥r則接受新狀態，反之狀態維持不變。

溫度較高時可以接受較大的能量差，溫度下降到一定的程度后，只有較小的能量差被接受。利用這一思想，當各個條件滿足的時候，也就是值達到了最優解。通過類比上述的物理過程，可以得到優化問題的解MetroPolis準則，目標函數為xk和xk+1的解，則由xk轉換到xk+1的接受概率為式中：T為退火過程中的溫度值。T0為算法迭代過程開始時的起始溫度，初始解為x=x0。在算法迭代的過程中不斷產生新解，根據上述準則判斷接受新解的概率判斷是否接受。隨著迭代的進行，溫度T下降，直至滿足收斂條件，算法收斂時就可以得到最優解。

通過隨機的方法來產生新的解[1]。假設當前解為，候選解為。當前解xi的某一個分量在一定領域內進行隨機變化，產生出新的值，候選解xi+1的計算公式為

式中：r為區間［-1，1］的隨機數；d為領域調整因子。在連續模擬退火算法的開始階段，d可以取較大值，目的是使d能夠在較大范圍內進行搜索，然后再逐漸減小d，縮小搜索范圍。常取d為線性函數d=ηd，其中0＜η＜1。此外，新產生的候選解必須滿足優化問題的約束條件。當滿足式（3）的2個條件的時候，候選解也可以采取以下形式[2]：

1.2 參數的設置

在利用模擬退火算法求解優化問題，尤其是非凸優化問題時，參數設置是否合理在很大程度上影響到算法的性能。雖然從理論上來說，只要初始溫度夠高、下降速度夠慢、迭代次數夠多，算法就能以1的概率收斂于全局最小值。但是在實際的應用中，不可能花費近乎無限的時間來等待結果，只要求算法能夠在合理的時間內給出滿足精度的解。為了滿足精度和效率的要求，需要對模擬退火算法的幾個主要參數進行分析設計并合理設置大小。

1）初始溫度T0的選擇

初始溫度T0是算法開始階段的系統溫度。模擬退火算法在迭代早期需要在比較大的范圍內進行搜索，也就是說此時的算法接受新解的概率非常高，所以初始溫度需要取得比較大，使得exp（-Δ f/T0）接近于1，能進行全局性、大范圍的搜索。實踐表明，當初始的溫度越高時，獲得高質量解的可能性也越大，這使得算法從一開始就達到準平衡的狀態，否則退火過程將變成局部搜索的過程，只能得到低質量的解。然而，過大的初始溫度又會導致算法效率的下降，需要非常長的迭代過程才能收斂。T0的具體取值，要在實際應用過程中根據實驗結果進行適當調整，總的原則是在保證效率能夠接受的情況下，盡可能提高初始溫度。

2）Markvo鏈長度 Lk的設置

Markvo鏈長度Lk是在某溫度T下的總迭代次數，用于控制生產的候選解的數量。要達到熱平衡狀態，Lk不能太短。理論上，Lk與溫度下降速度有關，如果溫度下降越快，就需要越長的Markov鏈，以確保模擬退火算法能夠搜索到全局最優解。一般地，Lk取定值L=100d比較合適，式中d為優化向量的維度。

3）溫度下降函數的選擇

為避免算法產生過長的Markov鏈，系統溫度T的下降速度都比較小，這也是選取溫度下降函數的一個重要原則。應用中，使用最多的是線性下降函數Tk+1=αTk，式中α為小于1但接近1的數，一般取α=0.95～0.98之間，用于控制溫度下降的速率。除此之外，還有許多不同的降溫方案，如經典退火、快速退火、超快速退火等。

4）算法終止的條件

在理論上，模擬退火算法必須在溫度足夠接近0或者解不在發生變化時才能停止。合適的終止條件，不但能夠保證算法在多項式時間內收斂于某一近似解，而且能使最終解具有較高的質量。根據研究經驗，常用的終止條件有以下2種：

①溫度下降到冷卻閾值以下；

②經過多次降溫，當前最優解一直無法得到進一步改善等。

1.3 計算示例

求解Camel函數的全局最優點，所求問題的數學模型為

式中：Camel函數含有 2 個自變量，在區間 x∈［-3，3］，y∈［-2，2］上有6個局部極小值點，其中有對稱的全局極小值點，為（0.0898，-0.7126），由其取得全局極小值為1.31628。

采用C++編寫模擬退火算法。CPU為i5-5200U，內存12 G，設置初始溫度T0=30，去掉 Markvo鏈Lk=200，降溫速率α=0.98，領域范圍內取定值scale=0.05，初始點為（2，1）。

針對2種不同的終止條件進行測試。第1種條件，溫度下降到終止溫度Te=0.001后，系統達到平衡后也就達到最優解，則算法結束；第2種條件，連續k次降溫最優解不在發生變化時，算法結束，取k=200。優化結果見表1。

表1 退火算法優化結果Tab.1 Simulated annealing algorithm optimization results

2 退火算法與Hopfield神經網絡結合

2.1 算法結合原理

雖然模擬退火算法具有很強的全局搜索能力，而且不要求目標函數為凸函數，它能夠以一定概率接受次最優解，使得算法在迭代過程中不會像Hopfield神經網絡一樣陷入局部最優。理論上只要有初始的系統溫度夠高、溫度下降夠慢、迭代次數夠多，算法收斂于全局最優解的概率即為100%。但是，也是由于模擬退火算法是一種隨機性的算法，在效率上還有一定欠缺，單純使用模擬退火算法尚存在一定問題。

按照網絡輸出值的類型，一般將神經網絡劃分為離散型（DHNN）和連續性（CHNN）2種不同的類型[3]，這2種類型的Hopfield神經網絡原理是一致的。在此主要研究連續性神經網絡。Hopfield神經網絡具有快速收斂的特性，而且因其網絡結構并具有高度的并行性，適合于進行并行化或者分布式的計算，能夠大幅度提高算法的運行速度。由于其在整個迭代過程中，能量函數只能沿著減小的方向變化，這一特點決定了Hopfield神經網絡在解決非凸優化問題時很可能會陷入局部最優，最終所得到的解與初始點的設置關系密切，不容易得到全局最優解[4]。因此，可以將兩者有效結合起來求解優化問題，能夠較為快速地得到全局最優解，將該方法命名為SA-CHNN[5]。

使用SA-CHNN求解全局最優化問題時，仍以CHNN為主，利用CHNN找到1個極小值點時，再用模擬退火算法在對此極小值點的領域進行若干次的搜索；Markov鏈的長度可以定得比較大，以確保能夠跳出局部最優。然后，繼續使用CHNN尋優，不斷循環，如果經過若干次如次循環仍未找到比當前更優的解，則該點即作為全局極小值點。

根據Hopfield神經網絡理論，將優化問題中的變量 x（x∈R）神經網絡的輸出 v（v∈R）相對應起來，就可以將優化問題映射到CHNN中去。利用罰函數的思想將有約束的優化模型轉換為無約束的函數：

由于原始的CHNN的神經元輸出值被限制于［0，1］之間，但在優化問題中，許多變化的范圍超出這個界限，為了對神經元節點的sigmoid的函數進行定義：

根據網絡CHNN的迭代方程就可以對網絡進行迭代更新，當網絡收斂于穩定狀態時，神經元的輸出值就是相應優化問題的解。

對于遞歸網絡函數來說，穩定性是一個非常關鍵的指標，決定了網絡能否收斂到一個穩定狀態。目前使用最多的Hopfield提出的lyapunov函數[6]，定義如下：

式中：δ-1為 δ（.）的反函數，一般來說 τ會取一個很大的值，所以能量函數中積分項的值會非常小，故網絡能量函數也可以寫為

通過對上述公式中能量函數進行分析，可以很容易得到Hopefield神經網絡的重要參數，包括連接權重和偏置。ωr的比例因子分別為ky=kz＝35/6。

如果一個優化問題可以表示為上述公式，那么就可以利用Hopfield神經網絡來求解這個優化問題，得到相應的解。Hopefield和Tank在1985年發表的論文中指出，如果需要利用Hopefield神經網絡來求解優化問題，那么能量函數必須是一個可收斂的函數[7]，并給出了證明。算法流程如圖1所示。

圖1 算法流程Fig.1 Algorithm flow chart

2.2 計算示例

仍以選取Camel函數為例對SA-CHNN進行驗證[5]。 設置 CHNN 的神經元個數為 2，η＝200，sigmoid函數調節參數 λ＝0.01，更新步長 step為 0.01，τ＝5000，收斂條件 ΔE＜10-6。 起點 x0＝（2，1）T網絡能量函數為

設置模擬退火算法的初始溫度T0＝30，取Markvo鏈 Lk＝200，降溫速率 α＝0.98，領域范圍因子 scale＝0.05，收斂條件為模擬退火經過200次。

應用算法，可以得到運行結果，算法從初始點（2，1）開始執行，使用CHNN進行迭代，收斂于局部極小值點（1.601，0.574）；使用模擬退火算法的隨機性搜索，并跳出該局部極小值點，以這個點作為CHNN的初始點再次進行迭代，收斂于另一個極小值點（1.698，-0.799）。SA-CHNN算法不斷進行“尋優—陷入局部最優—跳出—再次尋優”的迭代過程，直到模擬退火算法無法找到最好的解，可以得到算法收斂于點（0.901，0.7111）。該點即為全局最小值點，最小值為1.6026，運行時間 0.688 s。

2.3 結果對比

通過退火算法得到的最優結果為1.6163，耗時1.319 s；通過算法融合得到的最優值為1.6026，耗時0.688 s。在結果相差不大的情況下，后者較前者快了近1/2，結果的對比見表2。

表2 不同算法的結果對比Tab.2 Results comparison of different algorithms

3 結語

針對Hopfield神經網絡在求解非凸優化問題上的局限性，將其與連續性的模擬退火算法進行相結合，利用其局部優化能力求解非凸優化問題，并用算例對這一算法進行了驗證。結果表明，神經網絡與退火算法相結合，即克服了Hopfield神經網絡求解非凸優化問題的局限性，又比單用模擬退火算法的效率高。

[1] 江加和，宋子善，沈為群，等.模擬退火算法在連續變量全局優化問題中應用[J].北京航空航天大學學報，2001，27（5）：556-559.

[2] 羅亞中，唐國金.兩層非線性規劃問題的并行模擬退火全局優化[J].系統仿真學報，2005，17（5）：1040-1044.

[3] 王林山.時滯遞歸神經網絡[M].北京：科學出版社，2008.

[4] Ghatee M，Mohades A.Motion planning in order to optimize the length and clearance applying a hopfield neural network[J].Expert Systems with Applications，2009，36（3）：4688-4695.

[5] 張華燁.基于神經網絡的路徑規劃并行算法的設計與實現[D].廣州：華南理工大學，2013.

[6] 張捍東，鄭睿.岑豫皖.移動機器人路徑規劃技術的現狀與展望[J].系統仿真學報，2005，17（2）：439-443.

[7] 陳科.基于并行思維的設計理念和設計方法研究[D].合肥：合肥工業大學，2001.

Research on Path Planning Based on Simulated Annealing Algorithm and Neural Network Algorithm

LI Jiang-wei，XU Lun-hui
（School of Civil Engineering and Transportation，South China University of Technology，Guangzhou 510641，China）

The problem of path planning is a classical problem including computer，mathematics，traffic，robot and so on.It can be described as an optimization problem.In order to solve the problem of long operation time of classical algorithm in solving optimal path，the characteristics of neural network and simulated annealing algorithm are studied，and the mathematical model of general road network is established.According to the characteristics of neural network and simulated annealing algorithm，the optimal path algorithm for vehicle guidance is designed.The results show that the combination of neural network algorithm and simulated annealing algorithm is more efficient than any single algorithm alone.

path planning；neural network；simulated annealing algorithm

TP273.4

A

1001-9944（2017）11-0006-04

10.19557/j.cnki.1001-9944.2017.11.002

2017-04-20；

2017-09-25

李江偉（1990—），男，碩士研究生，研究方向為交通運輸工程；許倫輝（1965—），男，教授，博士生導師，研究方向為智能控制理論及應用、智能交通系統等。