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

傅立葉混沌神經(jīng)網(wǎng)絡(luò)模型中的模擬退火策略徐耀群，秦峰哈爾濱商業(yè)大學(xué)系統(tǒng)工程研究所 哈爾濱 150028哈爾濱商業(yè)大學(xué)計算機與信息工程學(xué)院,黑龍江哈爾濱150028(E-mail: )摘要：本文分析了傅立葉混沌神經(jīng)網(wǎng)絡(luò)模型的動力學(xué)特性對自反饋連接權(quán)值的敏感性,研究了退火函數(shù)對優(yōu)化過程中的準(zhǔn)確性和計算速度的影響。并利用暫態(tài)混沌神經(jīng)網(wǎng)絡(luò)退火過程分段的思想對傅立葉混沌神經(jīng)網(wǎng)絡(luò)模型進(jìn)行改進(jìn), 提出了一種具有隨機性和確定性并存的優(yōu)化算法，在保證優(yōu)化算法準(zhǔn)確性的基礎(chǔ)上,加快收斂速度,并利用對經(jīng)典旅行商( TSP) 的研究,表明算法具有很強的克服陷入局部極小能力,較大程度提高了優(yōu)化、時間和對初值的魯棒性能, 驗證了這種優(yōu)化策略的有效性，同時給出了模型參數(shù)對性能影響的一些結(jié)論. 關(guān)鍵詞： 傅立葉混沌神經(jīng)網(wǎng)絡(luò)；模擬退火；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)絡(luò)已經(jīng)被證明是解決組合優(yōu)化問題的有效工具，但是由于其利用梯度下降的動力學(xué),因此這種網(wǎng)絡(luò)在求解許多實際優(yōu)化問題時所遇到的最大困難是極易陷入局部極小點1。為了解決這一問題,人們將混沌動力學(xué)的全局搜索特性引入神經(jīng)網(wǎng)絡(luò)之中,提出了多種混沌神經(jīng)網(wǎng)絡(luò)模型,其中大多數(shù)是通過在Hopfield網(wǎng)絡(luò)中引入自反饋而使自身表現(xiàn)出暫態(tài)的混沌動力學(xué)行為以避免陷入組合優(yōu)化問題的局部極小點，因此網(wǎng)絡(luò)的動態(tài)特性很敏感地依賴于自反饋連接權(quán)值，類似于隨機模擬退火中的溫度, 其一般按指數(shù)退火函數(shù)動態(tài)變化,對網(wǎng)絡(luò)的優(yōu)化性能和收斂速度有很大的影響。有許多學(xué)者針對這一問題，提出了改進(jìn)方法。例如：修等2通過指數(shù)遞減的自反饋提出了激勵函數(shù)由Sigmoid和Gauss函數(shù)組合的線性自反饋混沌神經(jīng)網(wǎng)絡(luò)，費等3通過指數(shù)遞減的自反饋提出了內(nèi)外方法結(jié)合的線性混沌神經(jīng)網(wǎng)絡(luò)，Zhou等4通過控制非線性函數(shù)中的參數(shù)提出了具有非線性自反饋的混沌神經(jīng)網(wǎng)絡(luò)。本文通過引入徐耀群,孫明等提出的一種傅立葉混沌神經(jīng)元模型，該混沌神經(jīng)元模型的激勵函數(shù)由Sigmoid函數(shù)和三角函數(shù)加和組成，并利用一種改進(jìn)的變指數(shù)退火函數(shù),提出對自反饋權(quán)值 的一種新優(yōu)化策略,既充分利用混沌的動態(tài)特性進(jìn)行搜索,又克服其帶來的速度問題,減少收斂時間。仿真分析與驗證表明，本模型能夠有效減少網(wǎng)絡(luò)運算的迭代步數(shù)，提高了網(wǎng)絡(luò)的搜索效率，顯示出更為優(yōu)良的性能。1 傅立葉暫態(tài)混沌神經(jīng)網(wǎng)絡(luò) 通過把以往的單調(diào)遞增的Sigmoid激勵函數(shù)轉(zhuǎn)換成非單調(diào)的激勵函數(shù)，利用自反饋項引入混沌特性，提出了一種傅立葉混沌神經(jīng)元模型，基于該模型構(gòu)造如下傅立葉暫態(tài)混沌神經(jīng)網(wǎng)絡(luò)： (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)隔膜的阻尼因子；為不應(yīng)度參數(shù)；為一正參數(shù)； 、是三角函數(shù)前的系數(shù)。隨著時間變化,當(dāng)自反饋連接權(quán) 以指數(shù)方式(即: )趨于零時, 此網(wǎng)絡(luò)逐漸退化為一個Hopfield神經(jīng)網(wǎng)絡(luò)。故此網(wǎng)絡(luò)用來求解非線性優(yōu)化問題的過程可分為兩個階段：混沌搜索階段和梯度收斂階段。在第一個階段,由自反饋項來產(chǎn)生一個混沌過程以避免陷入網(wǎng)絡(luò)的局部最小問題。第一階段結(jié)束后,可以為第二階段提供一個全局最優(yōu)解附近的初始值?？梢娙绾慰刂频谝浑A段產(chǎn)生的混沌搜索過程, 是利用混沌神經(jīng)網(wǎng)絡(luò)解決非線性優(yōu)化問題的關(guān)鍵。所以 的演變策略對優(yōu)化的性能和時間有很大的影響。2模擬退火策略的優(yōu)化算法為了更好的理解上述網(wǎng)絡(luò)模型的運行機理, 以單個神經(jīng)元為例來檢驗該網(wǎng)絡(luò)的動力學(xué)行為： (7) (8) (9) (10) (11) (12)下面分析該模型的混沌特性：選取適當(dāng)?shù)膮?shù)，能使神經(jīng)元表現(xiàn)出暫態(tài)混沌行為。下面通過神經(jīng)元的倒分岔圖和最大Lyapunov指數(shù)時間演化圖來分析該模型的動力學(xué)特性。取=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)絡(luò)參數(shù)而保持其余參數(shù)不變來研究其對網(wǎng)絡(luò)混沌動態(tài)行為的影響。圖3和圖4是網(wǎng)絡(luò)參數(shù)取 0. 004時的網(wǎng)絡(luò)輸出x ( t) ,自反饋連接權(quán)z ( t) 的時間演化圖。圖3： 取0.004的倒分叉圖圖4 ：取0.004的最大Lyapunov指數(shù)譜圖從圖3和圖4可以看出,隨著參數(shù)的增大,網(wǎng)絡(luò)輸出x ( t) 的混沌動態(tài)消失得更快;而且因為自反饋連接權(quán)以指數(shù)方式(即: 衰減,所以其趨于0的收斂速度也隨著參數(shù)的增大而加快了。由上面倒分叉圖和最大Lyapunov指數(shù)譜圖分析可知：網(wǎng)絡(luò)的混沌動態(tài)特性很敏感地依賴于自反饋連接權(quán)值 , 的下降速度直接影響到判斷優(yōu)化算法的兩個重要指標(biāo):準(zhǔn)確性和速度。在該傅立葉暫態(tài)混沌神經(jīng)網(wǎng)絡(luò)模型中，隨著自反饋連接項的減小，對網(wǎng)絡(luò)的影響越來越小，網(wǎng)絡(luò)逐漸趨于穩(wěn)定的平衡點，這個過渡過程表現(xiàn)在網(wǎng)絡(luò)的單神經(jīng)元就是一個倒分岔的過程。在前半段表現(xiàn)出混沌現(xiàn)象，當(dāng)下降到某一程度時，混沌消失，轉(zhuǎn)為收斂階段。當(dāng)下降速度很快時，將通過短暫的搜索階段直接進(jìn)入收斂過程，因此算法的速度很快，但因為沒有充分利用混沌的豐富動態(tài)特征，容易陷入局部最小值，準(zhǔn)確性大大降低；相反地, 如果 變化小,可以提高準(zhǔn)確性而犧牲了優(yōu)化速度。通過研究大量利用混沌神經(jīng)網(wǎng)絡(luò)進(jìn)行函數(shù)優(yōu)化的文獻(xiàn)3、4,發(fā)現(xiàn)其雖然都能得到全局最優(yōu)解, 但收斂速度太慢。究其原因主要有兩個: 1) 在整個優(yōu)化過程中只采用單一的參數(shù),使得 的動態(tài)特性變化過于單一,造成網(wǎng)絡(luò)退火策略無法同時滿足準(zhǔn)確性和速度兩方面的要求; 2) 當(dāng)網(wǎng)絡(luò)的輸出趨于穩(wěn)態(tài)后,即得到了一個全局最優(yōu)解附近的值,其自反饋項 還是存在較小的數(shù)值,每次疊代對網(wǎng)絡(luò)第二階段的梯度收斂過程有擾動, 使得網(wǎng)絡(luò)不得不用較長的時間來收斂到全局最優(yōu)解。下面針對以上情況提出一個對自反饋項的優(yōu)化策略:文獻(xiàn)5針對 的動態(tài)特性變化過于單一的問題,采用分段指數(shù)退火函數(shù)(13) 來代替原網(wǎng)絡(luò)模型中的式(3) : (13)式中1 ,2 為常數(shù),1 2。開始時 的值較大,而參數(shù)值較小可以充分利用混沌的豐富動態(tài)特征,使得網(wǎng)絡(luò)輸出值能在大范圍內(nèi)進(jìn)行遍歷搜索,使算法可以從局部最優(yōu)值中跳出, 而得到全局最優(yōu)解;隨著 值的減小,網(wǎng)絡(luò)輸出逐漸收斂于分岔點, 所以可以采用比較大的指數(shù)衰減,減小收斂時間。通過以上分析，如果在傅立葉混沌神經(jīng)網(wǎng)絡(luò)模型中加入分段指數(shù)退火函數(shù)，在時，采用相對比較小的指數(shù)衰減，充分利用混沌的動態(tài)特性進(jìn)行搜索，使網(wǎng)絡(luò)可以跳出局部最優(yōu)的陷阱，將更有可能求得組合優(yōu)化問題的整體最優(yōu)解；在收斂階段采用比較大的指數(shù)衰減，克服小指數(shù)衰減帶來的速度問題，減小收斂時間11。所以基于此提出了基于分段指數(shù)退火的傅立葉暫態(tài)混沌混沌神經(jīng)網(wǎng)絡(luò)。3分段指數(shù)退火傅立葉混沌神經(jīng)網(wǎng)絡(luò) 基于以上分析在此提出了基于分段指數(shù)退火的傅立葉暫態(tài)混沌混沌神經(jīng)網(wǎng)絡(luò)模型： (14) (15) (16) (17) (18) (19)在上述網(wǎng)絡(luò)模型中、是分段模擬退火參數(shù)，且；是分段參數(shù)，其余參數(shù)與上面相同?；煦缟窠?jīng)網(wǎng)絡(luò)模型的動態(tài)特性很敏感的依賴于、和的取值。為網(wǎng)絡(luò)記憶保留或遺忘內(nèi)部狀態(tài)的能力；自反饋連接項是動態(tài)減小的，類似于隨機模擬退火中的溫度，退火速度依賴于、和的大小。當(dāng)=0時，退火速度依賴于，當(dāng)=1時，退火速度依賴于，在這兩種情況下網(wǎng)絡(luò)相當(dāng)于僅有一個退火參數(shù)。只有當(dāng)時，網(wǎng)絡(luò)才是分段網(wǎng)絡(luò)，其退火速度才依賴于、，最終使網(wǎng)絡(luò)收斂到一個平衡點；也具有很重要的作用，它代表著能量函數(shù)對動態(tài)特性的影響；在解決組合優(yōu)化問題的時，它們的搭配必須適合，如果太大，則能量函數(shù)的影響太強，以至于無法得到暫態(tài)混沌現(xiàn)象；如果太小，能量函數(shù)的影響太弱，將無法收斂到最優(yōu)解。通過其神經(jīng)元模型分析其動力學(xué)特性：取=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)元晚進(jìn)入了收斂階段；由于=0.0040.002，所以圖5與圖1、圖6與圖2相比較，分段傅立葉混沌神經(jīng)元因為比傅立葉混沌神經(jīng)元早進(jìn)入了收斂階段。所以分段傅立葉混沌神經(jīng)網(wǎng)絡(luò)的混沌搜索能力是介于傅立葉混沌神經(jīng)網(wǎng)絡(luò)分別在=和=時的混沌搜素能力之間的。4 仿真實驗結(jié)果與分析為驗證基于分段退火策略的改進(jìn)傅立葉混沌神經(jīng)網(wǎng)絡(luò)模型在優(yōu)化問題求解上的穩(wěn)定性和普適性，針對不同的參數(shù)取值情況下，使用該網(wǎng)絡(luò)模型對TSP問題進(jìn)行了仿真研究，同時通過與傅立葉網(wǎng)絡(luò)模型的仿真實驗結(jié)果觀察，對模型特征和性能進(jìn)行了分析和對比。在旅行商( TSP)問題中的應(yīng)用旅行商( TSP)問題是一個經(jīng)典的組合優(yōu)化問題，是一個NP-困難問題，可描述為“尋找一條遍歷N個城市的最短路徑，每個城市必須而且只能訪問一次，且最后回到起始點”對于N個城市的對稱TSP問題的可能路徑有(N-1)!/2條。本文將分段傅立葉混沌神經(jīng)網(wǎng)絡(luò)應(yīng)用于10城市旅行商問題。達(dá)到最短路徑并滿足所有限制條件的一個能量函數(shù)可以描述如式(22)13。在（22）中：為神經(jīng)元輸出，代表第x個城市在第i次序上被訪問，為城市x、y之間的距離。由于行列式的對稱性，系數(shù)A=B，一個全局最小的值代表一條最短的有效路徑。此時，分段傅立葉混沌神經(jīng)網(wǎng)絡(luò)模型(15)可以描述為(23)式。本文采用以下經(jīng)典歸一化后的10城市坐標(biāo)：(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)絡(luò)的退火速度越依賴于，當(dāng)=1時，退火速度僅依賴于；越接近0，分段傅立葉混沌神經(jīng)網(wǎng)絡(luò)的退火速度越依賴于，當(dā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）當(dāng)=0時，該分段傅立葉混沌神經(jīng)網(wǎng)絡(luò)只有一個模擬退火參數(shù)，此時只是一個普通的傅立葉混沌神經(jīng)網(wǎng)絡(luò)。因此可通過該行與其他行的比較來分析分段指數(shù)退火的傅立葉混沌神經(jīng)網(wǎng)絡(luò)的優(yōu)越性。2）通過上表中第一行與其余各行的平均迭代次數(shù)進(jìn)行比較分析，可以看出基于分段指數(shù)退火的傅立葉混沌神經(jīng)網(wǎng)絡(luò)的平均迭代次數(shù)比普通傅立葉混沌神經(jīng)網(wǎng)絡(luò)的平均迭代次數(shù)都有著不同程度的減小，這說明了分段指數(shù)退火思想對網(wǎng)絡(luò)的收斂速度確實有所提高。3）下面詳細(xì)分析了參數(shù)所起的重要作用：通過上表可以看出其收斂速度的提高程度依據(jù)參數(shù)和的不同而有所差異。例如：當(dāng)=0.4時，平均迭代次數(shù)減少的就很有限。所以要想使分段指數(shù)退火的傅立葉混沌神經(jīng)網(wǎng)絡(luò)達(dá)到高的收斂速度，則就不能取得太??；只有當(dāng)0.5時，才會達(dá)到較好的收斂效果。越大，此時分段傅立葉混沌神經(jīng)網(wǎng)絡(luò)的收斂速度越依賴于，因為，所以此時，網(wǎng)絡(luò)的收斂速度越快。通過對比參數(shù)分析：當(dāng)=0.4，=0.005時，分段指數(shù)退火的傅立葉混沌神經(jīng)網(wǎng)絡(luò)的收斂速度與普通傅立葉混沌神經(jīng)網(wǎng)絡(luò)的收斂速度幾乎沒有多少提高。當(dāng)=0.8，=0.005時，分段指數(shù)退火傅立葉混沌神經(jīng)網(wǎng)絡(luò)的收斂速度比普通傅立葉混沌神經(jīng)網(wǎng)絡(luò)的收斂速度提高一倍以上。4）總的來說，當(dāng)和在一定的范圍內(nèi)差距比較大的時候，同時既不是很大又不是很小的時候，網(wǎng)絡(luò)在收斂速度方面的提高比較明顯，同時網(wǎng)絡(luò)的求解精度幾乎沒有受到影響；這也說明了參數(shù)的適當(dāng)選取對于實際應(yīng)用問題起著重要的作用。5 結(jié)論本文重點研究了傅立葉混沌神經(jīng)網(wǎng)絡(luò)中的模擬退火參數(shù)對求解10城市旅行商問題的影響，并將分段指數(shù)退火函數(shù)的思想引入到傅立葉混沌神經(jīng)網(wǎng)絡(luò)，提出了一種有效的分段指數(shù)退火傅立葉暫態(tài)混沌神經(jīng)網(wǎng)絡(luò)模型，并將其應(yīng)用于解決TSP問題，與原傅立葉混沌神經(jīng)網(wǎng)絡(luò)相比尋優(yōu)能力較好，網(wǎng)絡(luò)收斂速度有了較大的提高，并且具有較高的非線性度。結(jié)果顯示，分段指數(shù)退火的傅立葉混沌神經(jīng)網(wǎng)絡(luò)能夠充分利用混沌動態(tài)特性進(jìn)行搜索，能夠跳出局部最優(yōu)的陷阱，又能夠加快收斂速度，減少收斂時間?？v觀全文，本文提出的基于分段指數(shù)退火函數(shù)的傅立葉混沌神經(jīng)網(wǎng)絡(luò)模型是一種很有潛力的傅立葉混沌神經(jīng)網(wǎng)絡(luò)模型。因此，分段傅立葉混沌神經(jīng)網(wǎng)絡(luò)有待進(jìn)一步深入研究，其應(yī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)絡(luò)及其應(yīng)用J. 電子學(xué)報，2005, 33(5): 868-870.3費春國，韓正之，唐厚君，魏國自適應(yīng)混合混沌神經(jīng)網(wǎng)絡(luò)及其在TSP 中的應(yīng)用J系統(tǒng)