張偉豐

（湖北汽車工業(yè)學(xué)院 經(jīng)濟管理學(xué)院，湖北 十堰 442002）

連續(xù)Hopfield神經(jīng)網(wǎng)絡(luò)（continuous hopfield neural network,CHNN）解決組合優(yōu)化問題是神經(jīng)網(wǎng)絡(luò)應(yīng)用的重要方面，在實際應(yīng)用中將優(yōu)化問題的目標(biāo)函數(shù)轉(zhuǎn)換為連續(xù)Hopfield神經(jīng)網(wǎng)絡(luò)的能量函數(shù)，優(yōu)化變量對應(yīng)于網(wǎng)絡(luò)中神經(jīng)元的狀態(tài)，當(dāng)神經(jīng)元狀態(tài)趨于平衡點時，網(wǎng)絡(luò)的能量函數(shù)趨于最小值，最終達到穩(wěn)定狀態(tài)，問題的最優(yōu)解也隨之求出，網(wǎng)絡(luò)由初始值向穩(wěn)態(tài)收斂的過程即目標(biāo)函數(shù)優(yōu)化計算的過程。由于神經(jīng)網(wǎng)絡(luò)是并行計算的，計算量不會隨維度的增大而指數(shù)性增加，能有效進行快速優(yōu)化計算。網(wǎng)絡(luò)的優(yōu)化效果受參數(shù)的影響較大，因此確定合適的參數(shù)是Hopfield神經(jīng)網(wǎng)絡(luò)需要解決的關(guān)鍵性問題。目前用優(yōu)化算法對其他某些算法的參數(shù)進行優(yōu)化來提高其性能的研究取得了較好的成果，文獻［1-4］分別以改進的粒子群算法或蟻群算法優(yōu)化支持向量機的參數(shù)，以便更好地解決分類問題。文中以此為借鑒，提出了以差分進化算法優(yōu)化Hopfield神經(jīng)網(wǎng)絡(luò)的參數(shù)用來求解組合優(yōu)化問題。差分進化算法進行優(yōu)化計算時，以參數(shù)序列作為編碼來表示個體，網(wǎng)絡(luò)的能量函數(shù)作為適應(yīng)度函數(shù)，以網(wǎng)絡(luò)計算穩(wěn)定后的能量值評價個體好壞，經(jīng)過若干代進化操作后，選擇種群中最優(yōu)個體作為網(wǎng)絡(luò)的參數(shù)，然后以搜索到的最佳參數(shù)構(gòu)建網(wǎng)絡(luò)對組合優(yōu)化問題進行優(yōu)化計算，實驗表明，只要搜索到恰當(dāng)參數(shù)，Hopfield網(wǎng)絡(luò)均能穩(wěn)定收斂，較快地求得最優(yōu)解。

1 Hopfield神經(jīng)網(wǎng)絡(luò)求解TSP問題

連續(xù)Hopfield神經(jīng)網(wǎng)絡(luò)是單層結(jié)構(gòu)的反饋網(wǎng)絡(luò)，由n個神經(jīng)元（N1,N2,…,Nn）組成，每個神經(jīng)元既是輸出單元也是輸入單元，其輸出作為其他神經(jīng)元的輸入，如圖1所示。Hopfield網(wǎng)絡(luò)優(yōu)化計算的步驟描述如下：1）選擇合適的問題表示方法，使神經(jīng)元輸出與問題的解對應(yīng)；2）構(gòu)造能量函數(shù)，使其最小值對應(yīng)問題的最優(yōu)解；3）由能量函數(shù)求得對應(yīng)的權(quán)重和偏置參數(shù)；4）構(gòu)造網(wǎng)絡(luò)的動態(tài)方程；5）初始化網(wǎng)絡(luò)，優(yōu)化計算求解。

圖1 Hopfield網(wǎng)絡(luò)結(jié)構(gòu)圖

TSP問題是典型的組合優(yōu)化問題，當(dāng)城市個數(shù)增加時，計算量會激增，容易收斂到局部解或非法解。根據(jù)連續(xù)Hopfield網(wǎng)絡(luò)優(yōu)化計算特點，將TSP問題的目標(biāo)函數(shù)即最短路徑與約束條件和網(wǎng)絡(luò)的能量函數(shù)對應(yīng)，將經(jīng)過的城市順序與神經(jīng)元狀態(tài)對應(yīng)，當(dāng)網(wǎng)絡(luò)能量趨于最小值時，神經(jīng)元趨于平衡點，對應(yīng)的城市順序即最佳路徑。

對于N個城市的TSP問題，采用N×N換位矩陣（各行和各列的和均為1的矩陣）來表示，需要用N×N個神經(jīng)元來實現(xiàn)，考慮到所求解的實際意義，即換位矩陣的每行每列只有1個1，網(wǎng)絡(luò)的能量函數(shù)由目標(biāo)函數(shù)和約束項組成，定義如下：

通過求導(dǎo)，網(wǎng)絡(luò)的動態(tài)方程為

式中：A為能量函數(shù)的系數(shù)；D為動態(tài)方程的系數(shù)。根據(jù)研究經(jīng)驗，按式（3）對網(wǎng)絡(luò)輸入進行初始化：

式中：N為城市個數(shù)；U0為方程系數(shù)；σ為[-1,1]的隨機數(shù)。綜上所述，需要優(yōu)化的參數(shù)有A、D、U0和σ，找到合適的參數(shù)值對網(wǎng)絡(luò)的計算至關(guān)重要。

2 DE-Hopfield算法模型及流程

2.1 編碼

利用差分進化算法解決優(yōu)化問題，首先需要解決編碼問題，由于優(yōu)化的是Hopfield網(wǎng)絡(luò)參數(shù)，文中采用實數(shù)編碼的方式，即直接以參數(shù)序列表示某個個體。需要優(yōu)化的參數(shù)有4個，設(shè)Pt為第t代個體，編碼表示為

在個體初始化時，根據(jù)給定的各參數(shù)的取值范圍，分別產(chǎn)生給定范圍的隨機數(shù)，生成第1代種群。

2.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是評價個體好壞的標(biāo)準(zhǔn)，當(dāng)個體分解為參數(shù)后，進入Hopfield網(wǎng)絡(luò)的求解過程，以網(wǎng)絡(luò)經(jīng)過若干次計算后達到穩(wěn)態(tài)后的最終能量函數(shù)值作為此個體的適應(yīng)度函數(shù)，能量值越低，說明參數(shù)越合適，即個體越好。適應(yīng)度函數(shù)可表示為式中：EHop為以此個體所代表的參數(shù)進行網(wǎng)絡(luò)優(yōu)化計算后的能量值。fitness取負(fù)數(shù)表示能量值越低，適應(yīng)度越大。

2.3 算法流程

算法輸入為各參數(shù)搜索區(qū)間、TSP問題城市坐標(biāo)值、種群大小、迭代次數(shù)；算法輸出為最優(yōu)參數(shù)、最低能量函數(shù)值、最優(yōu)路徑和最短距離。算法如下：1）對需要優(yōu)化的參數(shù)A、D、U0、σ，根據(jù)以往的經(jīng)驗設(shè)置各自搜索區(qū)間，設(shè)置種群大小，隨機初始化種群，設(shè)置最大迭代次數(shù)K,記錄最優(yōu)個體gBest；2）對種群中每個個體進行差分變異操作，按照前述的擇優(yōu)保留方式保存變異操作后的個體；3）對每個個體進行交叉操作，同樣保留較優(yōu)個體；4）步驟2）和步驟3）擇優(yōu)保存時需要進行適應(yīng)度的計算，適應(yīng)度即個體所代表的參數(shù)進行網(wǎng)絡(luò)優(yōu)化計算后的能量函數(shù)值，計算網(wǎng)絡(luò)優(yōu)化后的能量值；5）從種群中選擇適應(yīng)度最優(yōu)個體，保存在gBest中，判斷是否達到K，如果達到，算法結(jié)束，輸出gBest及其對應(yīng)的參數(shù)，最佳路線和最短距離，否則轉(zhuǎn)步驟2）。

網(wǎng)絡(luò)優(yōu)化后的能量值計算步驟如下：1）讀取城市坐標(biāo)數(shù)據(jù)，并計算各城市間的距離，根據(jù)個體編碼解析出網(wǎng)絡(luò)參數(shù)，初始化網(wǎng)絡(luò)，設(shè)置最大迭代次數(shù)k；2）利用式（2），用一階歐拉法計算

3）計算網(wǎng)絡(luò)輸出為

4）利用式（1）計算能量函數(shù)E；5）判斷是否達到最大迭代次數(shù)k，如果t大于k，則輸出能量函數(shù)值、路徑、距離，否則t=t+1，轉(zhuǎn)步驟2）。

3 仿真實驗

3.1 TSP問題

算法用Python編程實現(xiàn)，為驗證算法的有效性，用多個TSP問題的測試數(shù)據(jù)集進行實驗。首先以10城市問題對算法進行測試，坐標(biāo)數(shù)據(jù)見表1。

表1 10城市問題坐標(biāo)數(shù)據(jù)

參數(shù)設(shè)置如下：U0取0.01～03，σ取-2～2，對Hopfield神經(jīng)網(wǎng)絡(luò)性能影響較大的參數(shù)A和D，根據(jù)事先用Hopfield神經(jīng)網(wǎng)絡(luò)計算結(jié)果確定大致范圍，然后用差分進化算法進行最優(yōu)參數(shù)的搜索，確定A∈（10,1200）,D∈（0,800）。在差分進化算法種群初始化時，在上述參數(shù)范圍內(nèi)用隨機數(shù)產(chǎn)生個體，種群大小P為20，有4個參數(shù)需要優(yōu)化，即編碼長度n為4，交叉概率Pc為0.4，每個個體計算適應(yīng)度時，k為150，返回計算得到的最低能量值作為適應(yīng)度值，K為60。通過多次仿真實驗，算法均能搜索到最優(yōu)參數(shù)，根據(jù)最優(yōu)參數(shù)，Hopfield網(wǎng)絡(luò)求解到最優(yōu)路徑，結(jié)果如圖2所示。

圖2 能量函數(shù)值、最短距離和參數(shù)變化圖

圖2a為各代最優(yōu)個體所對應(yīng)的Hopfield網(wǎng)絡(luò)計算的能量函數(shù)值變化情況，可以看出：算法初始迭代時，差分進化算法尚未找到合適的參數(shù)，Hopfield網(wǎng)絡(luò)能量值比較慢的下降或者不能收斂；而在差分進化計算的末期、已找到合適參數(shù)時，網(wǎng)絡(luò)能量能很快下降并穩(wěn)定下來，這時網(wǎng)絡(luò)能有效地求出最短距離。圖2b為各代最短距離變化曲線，可以看出：所求最短距離呈單調(diào)下降，算法初始時，Hopfield網(wǎng)絡(luò)難以收斂，從而不能有效地求解；而在末期，搜索到合適參數(shù)的情況下，Hopfield網(wǎng)絡(luò)很快收斂，能較快地達到穩(wěn)定狀態(tài)，求出最短距離。圖2c～d為參數(shù)A和D的變化情況，從各代最優(yōu)個體編碼中解析得到，可以看出：在差分進化計算后期，參數(shù)值基本處于穩(wěn)定，表明算法找到了針對優(yōu)化問題的最佳參數(shù)。根據(jù)搜索到的最佳參數(shù)，用Hopfield網(wǎng)絡(luò)求解10城市問題的結(jié)果如圖3所示。圖3b為網(wǎng)絡(luò)優(yōu)化計算后得到的最短路徑圖，可以看出，網(wǎng)絡(luò)迭代計算達到穩(wěn)態(tài)后求得最短路徑。圖3c為網(wǎng)絡(luò)能量函數(shù)值收斂曲線，只需經(jīng)過400多次迭代，輸出能量即可達到穩(wěn)定狀態(tài)。

圖3 用最優(yōu)參數(shù)求解10城市問題結(jié)果

為檢驗算法求解較為復(fù)雜的TSP問題的性能，從TSPLIB測 試 庫 中 選 擇 了kroC100、ch150、a_gr666、pcb442、pr1002、pr2392城市規(guī)模較大的6個TSP問題實例進行測試，由于計算量和問題復(fù)雜性增加，為了確保算法能求解到較好的解，算法迭代次數(shù)和主要參數(shù)搜索范圍適當(dāng)取大一點，參數(shù)A,D∈( 0,120000)，P為100，k為800，K為2000，其他參數(shù)設(shè)置不變，進行10次仿真計算后求平均值，將算法所求解和實例的最優(yōu)解進行對比，如表2所示。算法求解的結(jié)果如圖4～5所示。從表2可以看出，文中算法所求解基本接近當(dāng)前的最優(yōu)解，表明算法在復(fù)雜TSP問題求解上效果良好。

圖4 TSP實例優(yōu)化路徑圖

表2 TSP實例求解結(jié)果

圖5 算法在6個測試實例運行能量函數(shù)曲線

3.2 欺騙函數(shù)與等級函數(shù)問題

用4個典型的欺騙函數(shù)來測試算法的性能，其中每個輸入變量的取值均為0或1，u為輸入變量中1的個數(shù)，函數(shù)如下：

1）goldberg三階欺騙函數(shù)

2）deceptive三階欺騙函數(shù)

3）trap5五階陷阱函數(shù)

4）bipolar六階雙極欺騙函數(shù)

按如下連接方式構(gòu)成大規(guī)模欺騙函數(shù)：

對goldberg、deceptive和bipolar函數(shù)，取變量長度為60，最優(yōu)解為全1或全0，函數(shù)極大值分別為600、20、10；對trap5函數(shù)，取變量長度為100，最優(yōu)解為全1，函數(shù)極大值為100。Hopfield網(wǎng)絡(luò)和差分進化算法的主要參數(shù)設(shè)置和前述TSP問題的實驗參數(shù)相當(dāng)，對goldberg和trap5函數(shù)分別求解，求解過程中能量函數(shù)值、函數(shù)極大值、最優(yōu)參數(shù)變化如圖6～7所示。從圖6c～d和圖7c～d來看，在差分進化末期，參數(shù)值趨于穩(wěn)定，算法搜索到了最優(yōu)參數(shù)，同時也表明求解不同的函數(shù)，網(wǎng)絡(luò)的最佳參數(shù)也不一樣。從圖6a和圖7a可以看出，在算法初期、參數(shù)不合理的情況下，Hopfield網(wǎng)絡(luò)基本不會收斂，求不出函數(shù)最優(yōu)值，隨著進化計算的進行，當(dāng)搜索到最佳參數(shù)時，網(wǎng)絡(luò)能比較穩(wěn)定地收斂，快速求解出函數(shù)最優(yōu)解。圖6b和圖7b顯示的是，進化計算終止后，Hopfield網(wǎng)絡(luò)以最優(yōu)參數(shù)計算得到的收斂曲線，可以看出網(wǎng)絡(luò)能穩(wěn)定收斂。

圖6 求解goldberg函數(shù)

圖7 求解trap5函數(shù)

選取等級函數(shù)HIFF和HtrapI進行實驗，輸入變量作為最底層，按映射函數(shù)將下層映射到上層，構(gòu)成樹狀結(jié)構(gòu)，每層的函數(shù)值之和即最終函數(shù)值。

HIFF函數(shù)的映射函數(shù)將下層的2個變量映射為上層1個變量，問題規(guī)模n為2level，映射函數(shù)為

式中：level為層數(shù)。每層的函數(shù)值為

總函數(shù)值為

HtrapI函數(shù)和HIFF函數(shù)映射過程類似，將下層的3個變量映射為上層的1個變量，問題規(guī)模n為3level。映射函數(shù)為

各層的函數(shù)值為

為比較優(yōu)化性能，引入其他3個性能較好的優(yōu)化算法進行對比，分別為差分進化算法（DE）、模擬退火算法（SA）和量子進化算法（QEA），文中算法記為DE-Hopfield。對goldberg函數(shù)，取n為60、90、120、150進行實驗；對trap5函數(shù)，取n為50、100、150、200進行實驗；對HIFF函數(shù)，取n為25、26、27進行實驗；對HtrapI函數(shù)，取n為33、34、35進行實驗。n取不同值時每種算法分別運行10次，并將結(jié)果計算平均值，具體運行結(jié)果如表3所示。

4 結(jié)語

針對Hopfield網(wǎng)絡(luò)在求解優(yōu)化問題時對參數(shù)過于敏感的問題，提出了用差分進化算法搜索最優(yōu)參數(shù)的方法。文中方法在求解時，對于具體的優(yōu)化問題，通過差分進化算法的優(yōu)化計算，尋找到適合此問題的最佳參數(shù)，以優(yōu)化問題和適合此問題的參數(shù)構(gòu)造的Hopfield網(wǎng)絡(luò)進行優(yōu)化計算，從而快速、準(zhǔn)確地解決各種優(yōu)化問題。差分進化算法在連續(xù)值優(yōu)化上有良好的效果，利用差分向量更新個體來尋求新的解，能更好地進行全局搜索，再通過優(yōu)勝劣汰的選擇機制保證了種群中的個體逐步朝最優(yōu)解方向進化，通過上述算子的聯(lián)合作用，網(wǎng)絡(luò)參數(shù)得到優(yōu)化。通過對TSP問題和欺騙函數(shù)問題這類組合優(yōu)化問題的實驗表明，文中方法提高了求解的穩(wěn)定性，有效避免了Hopfield網(wǎng)絡(luò)在給定參數(shù)不合適時不收斂的情況。對于超大規(guī)模的組合優(yōu)化問題，隨著問題復(fù)雜性增加，計算量會成倍增加，Hopfield網(wǎng)絡(luò)的尋優(yōu)效果也會變得越來越差，如何對參數(shù)搜索范圍動態(tài)縮小、減小計算量、提高優(yōu)化效果，是后續(xù)研究方向。