hopfield網(wǎng)絡(luò)學(xué)習(xí)及其在最優(yōu)化問題中的應(yīng)用

1、<p>　　Hopfield網(wǎng)絡(luò)學(xué)習(xí)及其在最優(yōu)化問題中的應(yīng)用</p><p><b>　　金海和</b></p><p>　?。ㄇ迦A大學(xué)經(jīng)濟管理學(xué)院，北京 100084）</p><p>　　摘要 本文針對Hopfield神經(jīng)網(wǎng)絡(luò)（HNN）所存在的極小值問題及缺乏學(xué)習(xí)能力的問題，提出了一種學(xué)習(xí)算法。它是將決定約束條件權(quán)值大小的系數(shù)作

2、為學(xué)習(xí)參數(shù)，在參數(shù)空間里使參數(shù)向著HNN能量上升最快的方向?qū)W習(xí)，使網(wǎng)絡(luò)狀態(tài)能夠有效地從一旦陷入的極小值狀態(tài)中逃脫出來。該算法分別被應(yīng)用于10、20城市的旅行商問題（TSP），結(jié)果能夠以很高的比率收斂于最優(yōu)解。</p><p>　　關(guān)鍵詞 Hopfield 神經(jīng)網(wǎng)絡(luò) 最速上升法 參數(shù)學(xué)習(xí) 最優(yōu)化問題</p><p><b>　　1 引言</b></p>

3、;<p>　　Hopfield等通過用連續(xù)值HNN求解TSP，開辟了運用神經(jīng)網(wǎng)絡(luò)求解最優(yōu)化問題的新途徑[1]。但存在著（1）不能學(xué)習(xí)、（2）產(chǎn)生大量極小值等問題。作為解決極小值問題的方法之一，Hinton等提出了Boltzmann機模型及其學(xué)習(xí)算法[2]，但因速度太慢，難以為現(xiàn)實所接受[3]。對于問題（2），筆者進行過深入的理論分析，并在數(shù)學(xué)上進行了證明[4]。針對問題（1）、（2），筆者提出了登山學(xué)習(xí)算法[5]，但該算法

4、中，為了避免因?qū)W習(xí)使最小值發(fā)生位移，以學(xué)習(xí)后的解為初始解，使網(wǎng)絡(luò)回到未學(xué)習(xí)的HNN狀態(tài)空間里進行狀態(tài)更新至平衡狀態(tài)，顯然增加了計算量。</p><p>　　TSP常被用作研究最優(yōu)化問題的范例[6]，當(dāng)運用HNN求解時，它的解依從于決定約束條件權(quán)值大小的系數(shù)，而這類系數(shù)在選擇上具有一定的自由度。本文提出一種HNN學(xué)習(xí)算法，思想是，將決定約束條件權(quán)值大小的系數(shù)作為學(xué)習(xí)參數(shù)，在參數(shù)空間里使學(xué)習(xí)參數(shù)向著HNN能量上升最快

5、的方向?qū)W習(xí)，使HNN能從一旦陷入的極小值狀態(tài)中逃脫出來，直至找到最優(yōu)解或滿意解。本文將對N=10、20的TSP進行仿真實驗，以證明其有效性。</p><p>　　2 Hopfield神經(jīng)網(wǎng)絡(luò)模型 </p><p>　　HNN是由大量簡單的神經(jīng)處理單元相互結(jié)合而成，并有對稱性，無直接自反饋，非同期動作等約束。由n個單元構(gòu)成的HNN，其能量函數(shù)可表達為</p><p>

6、　　(1) </p><p>　　e是能量，其自身是時間的函數(shù)；wij是單元i和j的權(quán)值；yi是第i個單元的輸出；hi是第i 個單元的閥值；τ是正的常數(shù)。各個單元內(nèi)部電壓隨時間的變化可以用微分方程式（2）記述，xi是第i個單元的輸入總和。單元的輸入輸出可采用sigmoid形的邏輯非線性單調(diào)增加函數(shù)，如式（3）。</p><p>　?。?）

7、 （3）</p><p>　　T是一個對神經(jīng)單元輸入輸出函數(shù)的形狀有影響的參數(shù)。</p><p>　　HNN有收斂特性(證明見[7])，即在適當(dāng)?shù)某跏紬l件下反復(fù)使其更新狀態(tài)，則能量隨時間單調(diào)地減小，狀態(tài)向平衡狀態(tài)的方向更新。能量減至全局最小或局部最小時，狀態(tài)穩(wěn)定在某個平衡狀態(tài)。</p><p>　　3 基于Hopfield神經(jīng)網(wǎng)絡(luò)的TSP解法<

8、;/p><p>　　設(shè)有N個城市的集合{C1，C2，…，CN}，其中任意兩個城市Ci和Ck之間的距離是dik（dik=dki），試找出一條最短的經(jīng)過每個城市各一次（僅一次）并回到出發(fā)地的路徑，這就是TSP。N個城市的TSP，用HNN求解時，需要用N2個神經(jīng)單元?？梢杂梢粋€行代表城市號碼，列代表訪問次序號碼的矩陣來表示。其能量函數(shù)可以寫成式（4）。</p><p>　?。?） （5）&

9、lt;/p><p>　　yij是神經(jīng)單元的狀態(tài)變量，表示第i個城市第j回是否訪問，且yij∈[0，1]。當(dāng)yij≥0.5時，yij發(fā)火，意義是第i個城市在第j回被訪問；當(dāng)yij〈0.5時，yij不發(fā)火，意義是第i個城市在第j回不被訪問。dik是城市i與城市k之間的距離。A，B是控制項系數(shù)，D是距離項系數(shù)，其取值，一般算法是憑經(jīng)驗給出的。式中的第一項是行控制項，各行中只有一個“1”（一個城市只訪問一次），第二項是列控制

10、項，各列中只有一個“1”（一次只訪問一個城市），第三項是距離項，是路徑的全長。</p><p>　　將式（4）和式（1）的各項對應(yīng)，可導(dǎo)出其權(quán)值如式（5），閥值如式（6），同時定義符號式（7）: </p><p>　　（6）

11、 （7）</p><p>　　TSP能量函數(shù)曲面復(fù)雜，存在許多極小值，只靠減小能量是不可能求得全局最優(yōu)解或滿意解。</p><p>　　4 Hopfeild神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法</p><p>　　圖1是學(xué)習(xí)算法的流程圖?？騃是用學(xué)習(xí)后的新參數(shù)（第一次用初始給出的參數(shù)值），使HNN在狀態(tài)空間里進行狀態(tài)更新至平衡狀態(tài)，t是狀態(tài)更新

12、次數(shù)，被定義為時間?？騃I是網(wǎng)絡(luò)到達平衡狀態(tài)后，在參數(shù)空間里進行學(xué)習(xí)，s（離散值）是學(xué)習(xí)次數(shù)。 </p><p>　　為了簡明起見，舉一個只含二個極小值的HNN為例，說明其學(xué)習(xí)過程。圖2是能量和狀態(tài)的關(guān)系，屬概念性圖示，橫坐標(biāo)表示狀態(tài)，縱坐標(biāo)表示與之對應(yīng)的能量（為了便于理解，用一維表示）。網(wǎng)絡(luò)的初始狀態(tài)和所對應(yīng)的能量可以被定義為“山岳地形”上的某一點，這個點在特定“山谷”的斜面上。在狀態(tài)空間里，由HNN的收斂特性

13、可知，隨著HNN狀態(tài)的更新，這個點將滑向谷底。如初始狀態(tài)是圖2（a）上的點A，隨著HNN狀態(tài)的更新，將向谷底滑去，最終陷入谷底B點（極小值）。</p><p>　　(b) (d)</p><p>　　圖1 學(xué)習(xí)算法的流程圖 圖2 含二個極小值HNN的學(xué)習(xí)過程</p>

14、<p>　　HNN能量函數(shù)的形狀是由各種參數(shù)值決定的。因此，對于一旦陷入極小值的點，在參數(shù)空間里，讓參數(shù)向著使能量函數(shù)最速上升的方向?qū)W習(xí)。為此，用參數(shù)對能量函數(shù)進行微分，在它的最速上升方向（能量函數(shù)的微分系數(shù)更大的方向），即正的梯度方向上對參數(shù)進行修正，這里我們稱之為最速上升法。下面就此作進一步闡述。</p><p>　　首先，考慮一個含有許多參數(shù)的系統(tǒng)，把這些參數(shù)歸納起來用向量表示，在參數(shù)空間里，將按

15、照式（8）進行學(xué)習(xí)，這里設(shè)ε是正的常數(shù)，的修正量可以由式（9）求得，</p><p>　?。?） （9） </p><p>　　▽e是e關(guān)于的梯度。如果能使ε取得足夠小，隨著學(xué)習(xí)，能量函數(shù)e是上升的。</p><p>　　因此，學(xué)習(xí)后上升了的B點，又成為“山谷”斜面上的一點B′。這時，在狀態(tài)空間里

16、，使HNN進行狀態(tài)更新，點B′將向谷底C滑去，最后陷入谷底C點（圖2（b））。如此使網(wǎng)絡(luò)在狀態(tài)空間和參數(shù)空間里，按照HNN的收斂特性及最速上升法，反復(fù)地進行狀態(tài)更新、參數(shù)學(xué)習(xí)，HNN能量函數(shù)能夠從陷入的極小值中逃脫出來，最終收斂于最優(yōu)解或滿意解（圖2（d））。</p><p>　　5 基于Hopfield 神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)的TSP解法</p><p>　　TSP能量函數(shù)式（4）中，A、B、D是

17、決定約束條件權(quán)值大小的系數(shù)，并且在選擇范圍上有一定的自由度，可作為學(xué)習(xí)參數(shù)。因此，對應(yīng)于式（9），A、B、D的修正量分別是</p><p>　　（10） （11） （12）</p><p>　　p、q、r是正常數(shù)，稱學(xué)習(xí)系數(shù)。由式（4），可以導(dǎo)出能量函數(shù)關(guān)于學(xué)習(xí)參數(shù)A、B、D的偏微分</p><p><b>　?。?3）</b

18、></p><p><b>　?。?4）</b></p><p><b>　?。?5）</b></p><p><b>　　6 仿真實驗結(jié)果</b></p><p>　　10城市的坐標(biāo)被隨機地配置在一個單位正方形內(nèi)，設(shè)p=q=r=0.001，T=0.25，學(xué)習(xí)參數(shù)初始值A(chǔ)

19、=B=1、D=2。在[0.000000,1.000000]范圍內(nèi)，隨機產(chǎn)生100組不同的初始出發(fā)狀態(tài)，其計算結(jié)果如圖3所示。圖中，非可行解、可行解及最優(yōu)解分別用failure、feasible及optimum表示。由圖可見，不學(xué)習(xí)的HNN（學(xué)習(xí)次數(shù)是0），failure、feasible、optimum的收斂率分別是23%、77%、0%。隨著學(xué)習(xí)次數(shù)的增加，optimum的收斂率增高，學(xué)習(xí)23次后，100%的解收斂于optimum。&l

20、t;/p><p>　　圖3 隨機給出100組不同初始值的計算結(jié)果 圖4 20城市TSP的最終解 </p><p>　　20城市的坐標(biāo)被隨機地配置在一個單位正方形內(nèi)(圖4)，設(shè)p=q=r=0.0002，T=0.2，A=B=10、D=14。yij的初始值，由[0.000000,1.000000]內(nèi)的隨機數(shù)隨機地給出，計算結(jié)果如表1及圖4所示，（表1中，s、

21、t、e、d、r分別是學(xué)習(xí)次數(shù)、狀態(tài)更新次數(shù)、能量、距離、訪問路徑）。</p><p>　　表1 20城市TSP的能量、距離、路徑變化過程</p><p><b>　　7 結(jié)論</b></p><p>　　(1) 本文提出的學(xué)習(xí)算法，即把決定約束條件權(quán)值大小的系數(shù)作為學(xué)習(xí)參數(shù)，在參數(shù)空間里使參數(shù)向著HNN能量高速上升的方向?qū)W習(xí)，能夠有效地使網(wǎng)

22、絡(luò)從極小值狀態(tài)中逃脫出來，并能以很高的比率收斂于最優(yōu)解。因此，本算法在最優(yōu)化問題的應(yīng)用方面將會比HNN更有效更廣泛。</p><p>　　(2) 該學(xué)習(xí)算法并不局限于求解TSP，更適用于求解狀態(tài)到達全局最優(yōu)解時有明確定性特征的最優(yōu)化問題。</p><p>　?。?）因算法簡明，可望易于硬件實現(xiàn)。</p><p><b>　　參考文獻</b>&l

23、t;/p><p>　　1 Hopfield J J, Tank D W. ‘Neural’ computation of decision in optimization problems. Bio. Cybern., 1985, 52: 141-152 </p><p>　　2 Ackley D H, Hinton G E, Sejnowski T J. A learning algor

24、ithm for Boltzman Machines. Cognitive Sci, 1985, 9: 147-169</p><p>　　3 Murata J, Fuchikami T, Hirasawa K. Heuristic optimization using long, medium, and short term memories. T.IEE, 1998, 118- C (9): 1315-1

25、321</p><p>　　4 Tang Z, Jin H H, Ishizuka O, et al. An investigation on a unique solution of the Hopfield and the T-model neural networks. T.IEE, 1998, 118-C (2): 150-160 </p><p>　　5 Tang

26、Z, Jin H H, Murao K, et al. A gradient ascent learning for Hopfield networks. T.IEICE, 2000, J83-A (3): 319-331</p><p>　　6 Lawler E L, Lenstra J K, Rinnooy A H G, et al. The Travelling Salesman Problem. Chi

27、chester: Wiley, eds, 1985</p><p>　　7 Hopfield J J. Neurons with graded response have collective computational properties like those of two-state neurons. Proc. of the Natl. Acad. of Sci., USA, 1984, 81: 30

28、88-3092</p><p>　　Hopfield Network Learning and Its Application in Optimization Problems</p><p><b>　　Jin Haihe</b></p><p>　　(School of Economics and Management, Tsinghua

29、University, Beijing 100084, China)</p><p>　　Abstract This paper proposes a learning algorithm of solving the local minimum problem and the un-learnable problem for the Hopfield neural networks. The learning

30、 algorithm defines the coefficients of deciding constraint weight degrees as the learning parameters, and increases the energy of the Hopfield network by modifying its learning parameters in parameter space, thus making

31、the network escape from the local minimum which the network once falls into. This learning algorithm is applied to 10</p><p>　　Key words Hopfield Neural Networks Gradient Ascent Method Parameter Learning