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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、，使HNN進(jìn)行狀態(tài)更新，點(diǎn)B′將向谷底C滑去，最后陷入谷底C點(diǎn)（圖2（b））。如此使網(wǎng)絡(luò)在狀態(tài)空間和參數(shù)空間里，按照HNN的收斂特性及最速上升法，反復(fù)地進(jìn)行狀態(tài)更新、參數(shù)學(xué)習(xí)，HNN能量函數(shù)能夠從陷入的極小值中逃脫出來(lái)，最終收斂于最優(yōu)解或滿(mǎn)意解（圖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ù)。因此，對(duì)應(yīng)于式（9），A、B、D的修正量分別是</p><p>　?。?0） （11） （12）</p><p>　　p、q、r是正常數(shù)，稱(chēng)學(xué)習(xí)系數(shù)。由式（4），可以導(dǎo)出能量函數(shù)關(guān)于學(xué)習(xí)參數(shù)A、B、D的偏微分</p><p><b>　?。?3）</b

18、></p><p><b>　　（14）</b></p><p><b>　?。?5）</b></p><p><b>　　6 仿真實(shí)驗(yàn)結(jié)果</b></p><p>　　10城市的坐標(biāo)被隨機(jī)地配置在一個(gè)單位正方形內(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)，隨機(jī)產(chǎn)生100組不同的初始出發(fā)狀態(tài)，其計(jì)算結(jié)果如圖3所示。圖中，非可行解、可行解及最優(yōu)解分別用failure、feasible及optimum表示。由圖可見(jiàn)，不學(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 隨機(jī)給出100組不同初始值的計(jì)算結(jié)果 圖4 20城市TSP的最終解 </p><p>　　20城市的坐標(biāo)被隨機(jī)地配置在一個(gè)單位正方形內(nèi)(圖4)，設(shè)p=q=r=0.0002，T=0.2，A=B=10、D=14。yij的初始值，由[0.000000,1.000000]內(nèi)的隨機(jī)數(shù)隨機(jī)地給出，計(jì)算結(jié)果如表1及圖4所示，（表1中，s、

21、t、e、d、r分別是學(xué)習(xí)次數(shù)、狀態(tài)更新次數(shù)、能量、距離、訪問(wèn)路徑）。</p><p>　　表1 20城市TSP的能量、距離、路徑變化過(guò)程</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)中逃脫出來(lái)，并能以很高的比率收斂于最優(yōu)解。因此，本算法在最優(yōu)化問(wèn)題的應(yīng)用方面將會(huì)比HNN更有效更廣泛。</p><p>　　(2) 該學(xué)習(xí)算法并不局限于求解TSP，更適用于求解狀態(tài)到達(dá)全局最優(yōu)解時(shí)有明確定性特征的最優(yōu)化問(wèn)題。</p><p>　?。?）因算法簡(jiǎn)明，可望易于硬件實(shí)現(xiàn)。</p><p><b>　　參考文獻(xiàn)</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