傅立葉混沌神經(jīng)網(wǎng)絡模型中的模擬退火策略.doc

傅立葉混沌神經(jīng)網(wǎng)絡模型中的模擬退火策略徐耀群，秦峰哈爾濱商業(yè)大學系統(tǒng)工程研究所 哈爾濱 150028哈爾濱商業(yè)大學計算機與信息工程學院,黑龍江哈爾濱150028(E-mail: )摘要：本文分析了傅立葉混沌神經(jīng)網(wǎng)絡模型的動力學特性對自反饋連接權(quán)值的敏感性,研究了退火函數(shù)對優(yōu)化過程中的準確性和計算速度的影響。并利用暫態(tài)混沌神經(jīng)網(wǎng)絡退火過程分段的思想對傅立葉混沌神經(jīng)網(wǎng)絡模型進行改進, 提出了一種具有隨機性和確定性并存的優(yōu)化算法，在保證優(yōu)化算法準確性的基礎(chǔ)上,加快收斂速度,并利用對經(jīng)典旅行商( TSP) 的研究,表明算法具有很強的克服陷入局部極小能力,較大程度提高了優(yōu)化、時間和對初值的魯棒性能, 驗證了這種優(yōu)化策略的有效性，同時給出了模型參數(shù)對性能影響的一些結(jié)論. 關(guān)鍵詞： 傅立葉混沌神經(jīng)網(wǎng)絡；模擬退火；TSPFourier chaotic neural network model of simulated annealing strategyYaoqun Xu, Feng QinInstitute of System Engineering, Harbin University of Commerce, Harbin, 150028School of computer and Information Engineering, Harbin University of Commerce, Harbin, 150028(E-mail: ) Abstract: Fourier analysis of the chaotic neural network model of the dynamics of the feedback since the value of the sensitivity of the right to connect to study the function of the annealing process of optimizing the accuracy and speed of impact. And using transient chaotic neural network of sub-annealing process of thinking of the Fourier chaotic neural network model to improve, a co-exist with uncertainty and randomness of the optimization algorithm, to ensure accuracy of optimization algorithm, on the basis of speeding up Convergence rate, and using the classic traveling salesman (TSP) study showed that the algorithm is very strong capacity to overcome a local minimum, the greater the increase optimization, time and the initial value of robust performance, the certification of this optimization The effectiveness of strategies, given the model parameters on the performance of some of the conclusions.Keywords：Fourier chaotic neural network；Simulated Annealing；TSP0引 言在過去幾年里，Hopfield神經(jīng)網(wǎng)絡已經(jīng)被證明是解決組合優(yōu)化問題的有效工具，但是由于其利用梯度下降的動力學,因此這種網(wǎng)絡在求解許多實際優(yōu)化問題時所遇到的最大困難是極易陷入局部極小點1。為了解決這一問題,人們將混沌動力學的全局搜索特性引入神經(jīng)網(wǎng)絡之中,提出了多種混沌神經(jīng)網(wǎng)絡模型,其中大多數(shù)是通過在Hopfield網(wǎng)絡中引入自反饋而使自身表現(xiàn)出暫態(tài)的混沌動力學行為以避免陷入組合優(yōu)化問題的局部極小點，因此網(wǎng)絡的動態(tài)特性很敏感地依賴于自反饋連接權(quán)值，類似于隨機模擬退火中的溫度, 其一般按指數(shù)退火函數(shù)動態(tài)變化,對網(wǎng)絡的優(yōu)化性能和收斂速度有很大的影響。有許多學者針對這一問題，提出了改進方法。例如：修等2通過指數(shù)遞減的自反饋提出了激勵函數(shù)由Sigmoid和Gauss函數(shù)組合的線性自反饋混沌神經(jīng)網(wǎng)絡，費等3通過指數(shù)遞減的自反饋提出了內(nèi)外方法結(jié)合的線性混沌神經(jīng)網(wǎng)絡，Zhou等4通過控制非線性函數(shù)中的參數(shù)提出了具有非線性自反饋的混沌神經(jīng)網(wǎng)絡。本文通過引入徐耀群,孫明等提出的一種傅立葉混沌神經(jīng)元模型，該混沌神經(jīng)元模型的激勵函數(shù)由Sigmoid函數(shù)和三角函數(shù)加和組成，并利用一種改進的變指數(shù)退火函數(shù),提出對自反饋權(quán)值 的一種新優(yōu)化策略,既充分利用混沌的動態(tài)特性進行搜索,又克服其帶來的速度問題,減少收斂時間。仿真分析與驗證表明，本模型能夠有效減少網(wǎng)絡運算的迭代步數(shù)，提高了網(wǎng)絡的搜索效率，顯示出更為優(yōu)良的性能。1 傅立葉暫態(tài)混沌神經(jīng)網(wǎng)絡 通過把以往的單調(diào)遞增的Sigmoid激勵函數(shù)轉(zhuǎn)換成非單調(diào)的激勵函數(shù)，利用自反饋項引入混沌特性，提出了一種傅立葉混沌神經(jīng)元模型，基于該模型構(gòu)造如下傅立葉暫態(tài)混沌神經(jīng)網(wǎng)絡： (1) (2) (3) (4) (5) (6)式中， 和 為第i個神經(jīng)元的輸出,內(nèi)部狀態(tài)和輸入偏置，;（0）為自反饋連接項；(0 1) 為時變參量zi ( t) 的衰減因子；為從神經(jīng)元到神經(jīng)元的連接權(quán)值； 、和是激勵函數(shù)的陡度參數(shù)；（）為神經(jīng)隔膜的阻尼因子；為不應度參數(shù)；為一正參數(shù)； 、是三角函數(shù)前的系數(shù)。隨著時間變化,當自反饋連接權(quán) 以指數(shù)方式(即: )趨于零時, 此網(wǎng)絡逐漸退化為一個Hopfield神經(jīng)網(wǎng)絡。故此網(wǎng)絡用來求解非線性優(yōu)化問題的過程可分為兩個階段：混沌搜索階段和梯度收斂階段。在第一個階段,由自反饋項來產(chǎn)生一個混沌過程以避免陷入網(wǎng)絡的局部最小問題。第一階段結(jié)束后,可以為第二階段提供一個全局最優(yōu)解附近的初始值?？梢娙绾慰刂频谝浑A段產(chǎn)生的混沌搜索過程, 是利用混沌神經(jīng)網(wǎng)絡解決非線性優(yōu)化問題的關(guān)鍵。所以 的演變策略對優(yōu)化的性能和時間有很大的影響。2模擬退火策略的優(yōu)化算法為了更好的理解上述網(wǎng)絡模型的運行機理, 以單個神經(jīng)元為例來檢驗該網(wǎng)絡的動力學行為： (7) (8) (9) (10) (11) (12)下面分析該模型的混沌特性：選取適當?shù)膮?shù)，能使神經(jīng)元表現(xiàn)出暫態(tài)混沌行為。下面通過神經(jīng)元的倒分岔圖和最大Lyapunov指數(shù)時間演化圖來分析該模型的動力學特性。取=0.02，=2，=2，=1/3，=1/3，=0.283，=0.4，=1，=0.65，則=0.002的倒分岔圖和最大Lyapunov指數(shù)時間演化圖如圖14所示。圖1： 取0.002的倒分叉圖圖2 ：取0.002的最大Lyapunov指數(shù)譜圖下面通過改變網(wǎng)絡參數(shù)而保持其余參數(shù)不變來研究其對網(wǎng)絡混沌動態(tài)行為的影響。圖3和圖4是網(wǎng)絡參數(shù)取 0. 004時的網(wǎng)絡輸出x ( t) ,自反饋連接權(quán)z ( t) 的時間演化圖。圖3： 取0.004的倒分叉圖圖4 ：取0.004的最大Lyapunov指數(shù)譜圖從圖3和圖4可以看出,隨著參數(shù)的增大,網(wǎng)絡輸出x ( t) 的混沌動態(tài)消失得更快;而且因為自反饋連接權(quán)以指數(shù)方式(即: 衰減,所以其趨于0的收斂速度也隨著參數(shù)的增大而加快了。由上面倒分叉圖和最大Lyapunov指數(shù)譜圖分析可知：網(wǎng)絡的混沌動態(tài)特性很敏感地依賴于自反饋連接權(quán)值 , 的下降速度直接影響到判斷優(yōu)化算法的兩個重要指標:準確性和速度。在該傅立葉暫態(tài)混沌神經(jīng)網(wǎng)絡模型中，隨著自反饋連接項的減小，對網(wǎng)絡的影響越來越小，網(wǎng)絡逐漸趨于穩(wěn)定的平衡點，這個過渡過程表現(xiàn)在網(wǎng)絡的單神經(jīng)元就是一個倒分岔的過程。在前半段表現(xiàn)出混沌現(xiàn)象，當下降到某一程度時，混沌消失，轉(zhuǎn)為收斂階段。當下降速度很快時，將通過短暫的搜索階段直接進入收斂過程，因此算法的速度很快，但因為沒有充分利用混沌的豐富動態(tài)特征，容易陷入局部最小值，準確性大大降低；相反地, 如果 變化小,可以提高準確性而犧牲了優(yōu)化速度。通過研究大量利用混沌神經(jīng)網(wǎng)絡進行函數(shù)優(yōu)化的文獻3、4,發(fā)現(xiàn)其雖然都能得到全局最優(yōu)解, 但收斂速度太慢。究其原因主要有兩個: 1) 在整個優(yōu)化過程中只采用單一的參數(shù),使得 的動態(tài)特性變化過于單一,造成網(wǎng)絡退火策略無法同時滿足準確性和速度兩方面的要求; 2) 當網(wǎng)絡的輸出趨于穩(wěn)態(tài)后,即得到了一個全局最優(yōu)解附近的值,其自反饋項 還是存在較小的數(shù)值,每次疊代對網(wǎng)絡第二階段的梯度收斂過程有擾動, 使得網(wǎng)絡不得不用較長的時間來收斂到全局最優(yōu)解。下面針對以上情況提出一個對自反饋項的優(yōu)化策略:文獻5針對 的動態(tài)特性變化過于單一的問題,采用分段指數(shù)退火函數(shù)(13) 來代替原網(wǎng)絡模型中的式(3) : (13)式中1 ,2 為常數(shù),1 2。開始時 的值較大,而參數(shù)值較小可以充分利用混沌的豐富動態(tài)特征,使得網(wǎng)絡輸出值能在大范圍內(nèi)進行遍歷搜索,使算法可以從局部最優(yōu)值中跳出, 而得到全局最優(yōu)解;隨著 值的減小,網(wǎng)絡輸出逐漸收斂于分岔點, 所以可以采用比較大的指數(shù)衰減,減小收斂時間。通過以上分析，如果在傅立葉混沌神經(jīng)網(wǎng)絡模型中加入分段指數(shù)退火函數(shù)，在時，采用相對比較小的指數(shù)衰減，充分利用混沌的動態(tài)特性進行搜索，使網(wǎng)絡可以跳出局部最優(yōu)的陷阱，將更有可能求得組合優(yōu)化問題的整體最優(yōu)解；在收斂階段采用比較大的指數(shù)衰減，克服小指數(shù)衰減帶來的速度問題，減小收斂時間11。所以基于此提出了基于分段指數(shù)退火的傅立葉暫態(tài)混沌混沌神經(jīng)網(wǎng)絡。3分段指數(shù)退火傅立葉混沌神經(jīng)網(wǎng)絡 基于以上分析在此提出了基于分段指數(shù)退火的傅立葉暫態(tài)混沌混沌神經(jīng)網(wǎng)絡模型： (14) (15) (16) (17) (18) (19)在上述網(wǎng)絡模型中、是分段模擬退火參數(shù)，且；是分段參數(shù)，其余參數(shù)與上面相同?；煦缟窠?jīng)網(wǎng)絡模型的動態(tài)特性很敏感的依賴于、和的取值。為網(wǎng)絡記憶保留或遺忘內(nèi)部狀態(tài)的能力；自反饋連接項是動態(tài)減小的，類似于隨機模擬退火中的溫度，退火速度依賴于、和的大小。當=0時，退火速度依賴于，當=1時，退火速度依賴于，在這兩種情況下網(wǎng)絡相當于僅有一個退火參數(shù)。只有當時，網(wǎng)絡才是分段網(wǎng)絡，其退火速度才依賴于、，最終使網(wǎng)絡收斂到一個平衡點；也具有很重要的作用，它代表著能量函數(shù)對動態(tài)特性的影響；在解決組合優(yōu)化問題的時，它們的搭配必須適合，如果太大，則能量函數(shù)的影響太強，以至于無法得到暫態(tài)混沌現(xiàn)象；如果太小，能量函數(shù)的影響太弱，將無法收斂到最優(yōu)解。通過其神經(jīng)元模型分析其動力學特性：取=0.02，=2，=2，=1/3，=1/3，=0.283，=0.4，=1，=0.65，=0.002，=0.004和=0.6的倒分岔圖和最大Lyapunov指數(shù)時間演化圖如圖56所示。圖5 取0.002的倒分叉圖圖6 取0.004的最大Lyapunov指數(shù)譜圖由于=0.0020.004，所以圖5與圖3、圖6與圖4相比較，分段傅立葉混沌神經(jīng)元因為比傅立葉混沌神經(jīng)元晚進入了收斂階段；由于=0.0040.002，所以圖5與圖1、圖6與圖2相比較，分段傅立葉混沌神經(jīng)元因為比傅立葉混沌神經(jīng)元早進入了收斂階段。所以分段傅立葉混沌神經(jīng)網(wǎng)絡的混沌搜索能力是介于傅立葉混沌神經(jīng)網(wǎng)絡分別在=和=時的混沌搜素能力之間的。4 仿真實驗結(jié)果與分析為驗證基于分段退火策略的改進傅立葉混沌神經(jīng)網(wǎng)絡模型在優(yōu)化問題求解上的穩(wěn)定性和普適性，針對不同的參數(shù)取值情況下，使用該網(wǎng)絡模型對TSP問題進行了仿真研究，同時通過與傅立葉網(wǎng)絡模型的仿真實驗結(jié)果觀察，對模型特征和性能進行了分析和對比。在旅行商( TSP)問題中的應用旅行商( TSP)問題是一個經(jīng)典的組合優(yōu)化問題，是一個NP-困難問題，可描述為“尋找一條遍歷N個城市的最短路徑，每個城市必須而且只能訪問一次，且最后回到起始點”對于N個城市的對稱TSP問題的可能路徑有(N-1)!/2條。本文將分段傅立葉混沌神經(jīng)網(wǎng)絡應用于10城市旅行商問題。達到最短路徑并滿足所有限制條件的一個能量函數(shù)可以描述如式(22)13。在（22）中：為神經(jīng)元輸出，代表第x個城市在第i次序上被訪問，為城市x、y之間的距離。由于行列式的對稱性，系數(shù)A=B，一個全局最小的值代表一條最短的有效路徑。此時，分段傅立葉混沌神經(jīng)網(wǎng)絡模型(15)可以描述為(23)式。本文采用以下經(jīng)典歸一化后的10城市坐標：(0.4, 0.4439); ( 0.2439, 0.1463); ( 0.1707, 0.2293); ( 0.2293, 0.716); ( 0.5171,0.9414); ( 0.8732, 0.6536); ( 0.6878, 0.5219); ( 0.8488, 0.3609); ( 0.6683, 0.2536); ( 0.6195, 0.2634). 該10城市最短路徑為2.6776，見圖7。9 (20) (21) (22) (23)圖7 10城市TSP問題的最優(yōu)本文研究同一下，不同的參數(shù)和的分段指數(shù)退火思想對求解10城市TSP的影響。越接近1，分段傅立葉混沌神經(jīng)網(wǎng)絡的退火速度越依賴于，當=1時，退火速度僅依賴于；越接近0，分段傅立葉混沌神經(jīng)網(wǎng)絡的退火速度越依賴于，當=0時，退火速度僅依賴于。取=0.01，=0.01，=20，=20，=1/30，=1，=0.6，=0.1，=0.2，A=1.5，t=0.04， D=2，=0.0008。下表是在不同參數(shù)和時2000次隨機分配初始值的仿真試驗數(shù)據(jù)。 合法路徑最優(yōu)路徑合法比最優(yōu)比平均迭代次數(shù)020001998100%99.9%14410.40.00120001996100%99.8%14320.00320001998100%99.9%13630.00520001998100%99.9%13390.50.00120001998100%99.9%14010.00320001997100%99.85%12320.00520001996100%99.8%11850.60.00120001998100%99.9%13560.00320001999100%99.95%11010.00520001997100%99.85%10300.70.00120001999100%99.95%13140.00320001998100%99.9%954.250.00520002000100%100%80120001998100%99.9%12690.00320001998100%99.9%798.380.00520001998100%99.9%689.390.90.00120002000100%100%12200.00320001998100%99.9%633.160.00520001998100%99.9%507.97不同參數(shù)和下仿真結(jié)果通過上表仿真數(shù)據(jù)分析：1）當=0時，該分段傅立葉混沌神經(jīng)網(wǎng)絡只有一個模擬退火參數(shù)，此時只是一個普通的傅立葉混沌神經(jīng)網(wǎng)絡。因此可通過該行與其他行的比較來分析分段指數(shù)退火的傅立葉混沌神經(jīng)網(wǎng)絡的優(yōu)越性。2）通過上表中第一行與其余各行的平均迭代次數(shù)進行比較分析，可以看出基于分段指數(shù)退火的傅立葉混沌神經(jīng)網(wǎng)絡的平均迭代次數(shù)比普通傅立葉混沌神經(jīng)網(wǎng)絡的平均迭代次數(shù)都有著不同程度的減小，這說明了分段指數(shù)退火思想對網(wǎng)絡的收斂速度確實有所提高。3）下面詳細分析了參數(shù)所起的重要作用：通過上表可以看出其收斂速度的提高程度依據(jù)參數(shù)和的不同而有所差異。例如：當=0.4時，平均迭代次數(shù)減少的就很有限。所以要想使分段指數(shù)退火的傅立葉混沌神經(jīng)網(wǎng)絡達到高的收斂速度，則就不能取得太??；只有當0.5時，才會達到較好的收斂效果。越大，此時分段傅立葉混沌神經(jīng)網(wǎng)絡的收斂速度越依賴于，因為，所以此時，網(wǎng)絡的收斂速度越快。通過對比參數(shù)分析：當=0.4，=0.005時，分段指數(shù)退火的傅立葉混沌神經(jīng)網(wǎng)絡的收斂速度與普通傅立葉混沌神經(jīng)網(wǎng)絡的收斂速度幾乎沒有多少提高。當=0.8，=0.005時，分段指數(shù)退火傅立葉混沌神經(jīng)網(wǎng)絡的收斂速度比普通傅立葉混沌神經(jīng)網(wǎng)絡的收斂速度提高一倍以上。4）總的來說，當和在一定的范圍內(nèi)差距比較大的時候，同時既不是很大又不是很小的時候，網(wǎng)絡在收斂速度方面的提高比較明顯，同時網(wǎng)絡的求解精度幾乎沒有受到影響；這也說明了參數(shù)的適當選取對于實際應用問題起著重要的作用。5 結(jié)論本文重點研究了傅立葉混沌神經(jīng)網(wǎng)絡中的模擬退火參數(shù)對求解10城市旅行商問題的影響，并將分段指數(shù)退火函數(shù)的思想引入到傅立葉混沌神經(jīng)網(wǎng)絡，提出了一種有效的分段指數(shù)退火傅立葉暫態(tài)混沌神經(jīng)網(wǎng)絡模型，并將其應用于解決TSP問題，與原傅立葉混沌神經(jīng)網(wǎng)絡相比尋優(yōu)能力較好，網(wǎng)絡收斂速度有了較大的提高，并且具有較高的非線性度。結(jié)果顯示，分段指數(shù)退火的傅立葉混沌神經(jīng)網(wǎng)絡能夠充分利用混沌動態(tài)特性進行搜索，能夠跳出局部最優(yōu)的陷阱，又能夠加快收斂速度，減少收斂時間。縱觀全文，本文提出的基于分段指數(shù)退火函數(shù)的傅立葉混沌神經(jīng)網(wǎng)絡模型是一種很有潛力的傅立葉混沌神經(jīng)網(wǎng)絡模型。因此，分段傅立葉混沌神經(jīng)網(wǎng)絡有待進一步深入研究，其應用領(lǐng)域有待拓展，以充分發(fā)揮模型優(yōu)勢解決實際問題。1 CHEN L , A IHARA K. Chaotic simulated annealing by a neuralnetwork model with transient chaos J . Neural networks, 1995, 8(6) : 915 - 930.2修春波，劉向東一種新的混沌神經(jīng)網(wǎng)絡及其應用J. 電子學報，2005, 33(5): 868-870.3費春國，韓正之，唐厚君，魏國自適應混合混沌神經(jīng)網(wǎng)絡及其在TSP 中的應用J系統(tǒng)