退火算法與神經(jīng)網(wǎng)絡(luò)算法結(jié)合在路徑規(guī)劃中的研究

李江偉，許倫輝

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

退火算法與神經(jīng)網(wǎng)絡(luò)算法結(jié)合在路徑規(guī)劃中的研究

李江偉，許倫輝

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

路徑規(guī)劃問題是計(jì)算機(jī)、數(shù)學(xué)、交通、機(jī)器人等包含了眾多領(lǐng)域在內(nèi)的經(jīng)典問題，它可以被描述為一個最優(yōu)化問題。為了解決經(jīng)典算法在求解最優(yōu)路徑時(shí)運(yùn)算時(shí)長的問題，該文研究了神經(jīng)網(wǎng)絡(luò)和模擬退火算法的特點(diǎn)，建立了一般路網(wǎng)的數(shù)學(xué)模型；根據(jù)神經(jīng)網(wǎng)絡(luò)和模擬退火算法的特點(diǎn)設(shè)計(jì)了適合車輛誘導(dǎo)的路網(wǎng)最優(yōu)路徑算法。結(jié)果表明，應(yīng)用神經(jīng)網(wǎng)絡(luò)算法和模擬退火算法相結(jié)合，比單獨(dú)使用任何一個算法的效率高。

路徑規(guī)劃；神經(jīng)網(wǎng)絡(luò)；模擬退火算法

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

最短路徑問題是網(wǎng)絡(luò)優(yōu)化中的一個最基本的也是最重要的分支，同時(shí)也是所有路徑規(guī)劃問題的基礎(chǔ)。許多路徑規(guī)劃問題都可以轉(zhuǎn)化為這樣的最短路徑問題模型來表達(dá)，或者可以用最短路算法作為子程序。

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

1 模擬退火算法

1.1 退火算法原理

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

①假設(shè)狀態(tài)在xk時(shí)，當(dāng)使用一定的擾動對系統(tǒng)進(jìn)行影響，使?fàn)顟B(tài)發(fā)送變化，得到一個新的狀態(tài)xk+1，前后兩個狀態(tài)對應(yīng)的系統(tǒng)能量分別為E（xk）和E（xk+1），能量差為ΔE；

②ΔE≤0，則轉(zhuǎn)換為狀態(tài) xk+1；

③ΔE≥0，則轉(zhuǎn)換為xk+1的概率為

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

④設(shè) r＝random（0，1）為（0，1）上的隨機(jī)數(shù)，與 Pr進(jìn)行比較。若Pr≥r則接受新狀態(tài)，反之狀態(tài)維持不變。

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

通過隨機(jī)的方法來產(chǎn)生新的解[1]。假設(shè)當(dāng)前解為，候選解為。當(dāng)前解xi的某一個分量在一定領(lǐng)域內(nèi)進(jìn)行隨機(jī)變化，產(chǎn)生出新的值，候選解xi+1的計(jì)算公式為

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

1.2 參數(shù)的設(shè)置

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

1）初始溫度T0的選擇

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

2）Markvo鏈長度 Lk的設(shè)置

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

3）溫度下降函數(shù)的選擇

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

4）算法終止的條件

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

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

②經(jīng)過多次降溫，當(dāng)前最優(yōu)解一直無法得到進(jìn)一步改善等。

1.3 計(jì)算示例

求解Camel函數(shù)的全局最優(yōu)點(diǎn)，所求問題的數(shù)學(xué)模型為

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

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

針對2種不同的終止條件進(jìn)行測試。第1種條件，溫度下降到終止溫度Te=0.001后，系統(tǒng)達(dá)到平衡后也就達(dá)到最優(yōu)解，則算法結(jié)束；第2種條件，連續(xù)k次降溫最優(yōu)解不在發(fā)生變化時(shí)，算法結(jié)束，取k=200。優(yōu)化結(jié)果見表1。

表1 退火算法優(yōu)化結(jié)果Tab.1 Simulated annealing algorithm optimization results

2 退火算法與Hopfield神經(jīng)網(wǎng)絡(luò)結(jié)合

2.1 算法結(jié)合原理

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

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

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

根據(jù)Hopfield神經(jīng)網(wǎng)絡(luò)理論，將優(yōu)化問題中的變量 x（x∈R）神經(jīng)網(wǎng)絡(luò)的輸出 v（v∈R）相對應(yīng)起來，就可以將優(yōu)化問題映射到CHNN中去。利用罰函數(shù)的思想將有約束的優(yōu)化模型轉(zhuǎn)換為無約束的函數(shù)：

由于原始的CHNN的神經(jīng)元輸出值被限制于［0，1］之間，但在優(yōu)化問題中，許多變化的范圍超出這個界限，為了對神經(jīng)元節(jié)點(diǎn)的sigmoid的函數(shù)進(jìn)行定義：

根據(jù)網(wǎng)絡(luò)CHNN的迭代方程就可以對網(wǎng)絡(luò)進(jìn)行迭代更新，當(dāng)網(wǎng)絡(luò)收斂于穩(wěn)定狀態(tài)時(shí)，神經(jīng)元的輸出值就是相應(yīng)優(yōu)化問題的解。

對于遞歸網(wǎng)絡(luò)函數(shù)來說，穩(wěn)定性是一個非常關(guān)鍵的指標(biāo)，決定了網(wǎng)絡(luò)能否收斂到一個穩(wěn)定狀態(tài)。目前使用最多的Hopfield提出的lyapunov函數(shù)[6]，定義如下：

式中：δ-1為 δ（.）的反函數(shù)，一般來說 τ會取一個很大的值，所以能量函數(shù)中積分項(xiàng)的值會非常小，故網(wǎng)絡(luò)能量函數(shù)也可以寫為

通過對上述公式中能量函數(shù)進(jìn)行分析，可以很容易得到Hopefield神經(jīng)網(wǎng)絡(luò)的重要參數(shù)，包括連接權(quán)重和偏置。ωr的比例因子分別為ky=kz＝35/6。

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

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

2.2 計(jì)算示例

仍以選取Camel函數(shù)為例對SA-CHNN進(jìn)行驗(yàn)證[5]。 設(shè)置 CHNN 的神經(jīng)元個數(shù)為 2，η＝200，sigmoid函數(shù)調(diào)節(jié)參數(shù) λ＝0.01，更新步長 step為 0.01，τ＝5000，收斂條件 ΔE＜10-6。 起點(diǎn) x0＝（2，1）T網(wǎng)絡(luò)能量函數(shù)為

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

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

2.3 結(jié)果對比

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

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

3 結(jié)語

針對Hopfield神經(jīng)網(wǎng)絡(luò)在求解非凸優(yōu)化問題上的局限性，將其與連續(xù)性的模擬退火算法進(jìn)行相結(jié)合，利用其局部優(yōu)化能力求解非凸優(yōu)化問題，并用算例對這一算法進(jìn)行了驗(yàn)證。結(jié)果表明，神經(jīng)網(wǎng)絡(luò)與退火算法相結(jié)合，即克服了Hopfield神經(jīng)網(wǎng)絡(luò)求解非凸優(yōu)化問題的局限性，又比單用模擬退火算法的效率高。

[1] 江加和，宋子善，沈?yàn)槿?，?模擬退火算法在連續(xù)變量全局優(yōu)化問題中應(yīng)用[J].北京航空航天大學(xué)學(xué)報(bào)，2001，27（5）：556-559.

[2] 羅亞中，唐國金.兩層非線性規(guī)劃問題的并行模擬退火全局優(yōu)化[J].系統(tǒng)仿真學(xué)報(bào)，2005，17（5）：1040-1044.

[3] 王林山.時(shí)滯遞歸神經(jīng)網(wǎng)絡(luò)[M].北京：科學(xué)出版社，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] 張華燁.基于神經(jīng)網(wǎng)絡(luò)的路徑規(guī)劃并行算法的設(shè)計(jì)與實(shí)現(xiàn)[D].廣州：華南理工大學(xué)，2013.

[6] 張捍東，鄭睿.岑豫皖.移動機(jī)器人路徑規(guī)劃技術(shù)的現(xiàn)狀與展望[J].系統(tǒng)仿真學(xué)報(bào)，2005，17（2）：439-443.

[7] 陳科.基于并行思維的設(shè)計(jì)理念和設(shè)計(jì)方法研究[D].合肥：合肥工業(yè)大學(xué)，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—），男，碩士研究生，研究方向?yàn)榻煌ㄟ\(yùn)輸工程；許倫輝（1965—），男，教授，博士生導(dǎo)師，研究方向?yàn)橹悄芸刂评碚摷皯?yīng)用、智能交通系統(tǒng)等。