張偉豐

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

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

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

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

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

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

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

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

2 DE-Hopfield算法模型及流程

2.1 編碼

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

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

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

適應(yīng)度函數(shù)是評價(jià)個(gè)體好壞的標(biāo)準(zhǔn)，當(dāng)個(gè)體分解為參數(shù)后，進(jìn)入Hopfield網(wǎng)絡(luò)的求解過程，以網(wǎng)絡(luò)經(jīng)過若干次計(jì)算后達(dá)到穩(wěn)態(tài)后的最終能量函數(shù)值作為此個(gè)體的適應(yīng)度函數(shù)，能量值越低，說明參數(shù)越合適，即個(gè)體越好。適應(yīng)度函數(shù)可表示為式中：EHop為以此個(gè)體所代表的參數(shù)進(jìn)行網(wǎng)絡(luò)優(yōu)化計(jì)算后的能量值。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)驗(yàn)設(shè)置各自搜索區(qū)間，設(shè)置種群大小，隨機(jī)初始化種群，設(shè)置最大迭代次數(shù)K,記錄最優(yōu)個(gè)體gBest；2）對種群中每個(gè)個(gè)體進(jìn)行差分變異操作，按照前述的擇優(yōu)保留方式保存變異操作后的個(gè)體；3）對每個(gè)個(gè)體進(jìn)行交叉操作，同樣保留較優(yōu)個(gè)體；4）步驟2）和步驟3）擇優(yōu)保存時(shí)需要進(jìn)行適應(yīng)度的計(jì)算，適應(yīng)度即個(gè)體所代表的參數(shù)進(jìn)行網(wǎng)絡(luò)優(yōu)化計(jì)算后的能量函數(shù)值，計(jì)算網(wǎng)絡(luò)優(yōu)化后的能量值；5）從種群中選擇適應(yīng)度最優(yōu)個(gè)體，保存在gBest中，判斷是否達(dá)到K，如果達(dá)到，算法結(jié)束，輸出gBest及其對應(yīng)的參數(shù)，最佳路線和最短距離，否則轉(zhuǎn)步驟2）。

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

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

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

3 仿真實(shí)驗(yàn)

3.1 TSP問題

算法用Python編程實(shí)現(xiàn)，為驗(yàn)證算法的有效性，用多個(gè)TSP問題的測試數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。首先以10城市問題對算法進(jìn)行測試，坐標(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ò)計(jì)算結(jié)果確定大致范圍，然后用差分進(jìn)化算法進(jìn)行最優(yōu)參數(shù)的搜索，確定A∈（10,1200）,D∈（0,800）。在差分進(jìn)化算法種群初始化時(shí)，在上述參數(shù)范圍內(nèi)用隨機(jī)數(shù)產(chǎn)生個(gè)體，種群大小P為20，有4個(gè)參數(shù)需要優(yōu)化，即編碼長度n為4，交叉概率Pc為0.4，每個(gè)個(gè)體計(jì)算適應(yīng)度時(shí)，k為150，返回計(jì)算得到的最低能量值作為適應(yīng)度值，K為60。通過多次仿真實(shí)驗(yàn)，算法均能搜索到最優(yōu)參數(shù)，根據(jù)最優(yōu)參數(shù)，Hopfield網(wǎng)絡(luò)求解到最優(yōu)路徑，結(jié)果如圖2所示。

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

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

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

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

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

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

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

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

用4個(gè)典型的欺騙函數(shù)來測試算法的性能，其中每個(gè)輸入變量的取值均為0或1，u為輸入變量中1的個(gè)數(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ò)和差分進(jìn)化算法的主要參數(shù)設(shè)置和前述TSP問題的實(shí)驗(yàn)參數(shù)相當(dāng)，對goldberg和trap5函數(shù)分別求解，求解過程中能量函數(shù)值、函數(shù)極大值、最優(yōu)參數(shù)變化如圖6～7所示。從圖6c～d和圖7c～d來看，在差分進(jìn)化末期，參數(shù)值趨于穩(wěn)定，算法搜索到了最優(yōu)參數(shù)，同時(shí)也表明求解不同的函數(shù)，網(wǎng)絡(luò)的最佳參數(shù)也不一樣。從圖6a和圖7a可以看出，在算法初期、參數(shù)不合理的情況下，Hopfield網(wǎng)絡(luò)基本不會收斂，求不出函數(shù)最優(yōu)值，隨著進(jìn)化計(jì)算的進(jìn)行，當(dāng)搜索到最佳參數(shù)時(shí)，網(wǎng)絡(luò)能比較穩(wěn)定地收斂，快速求解出函數(shù)最優(yōu)解。圖6b和圖7b顯示的是，進(jìn)化計(jì)算終止后，Hopfield網(wǎng)絡(luò)以最優(yōu)參數(shù)計(jì)算得到的收斂曲線，可以看出網(wǎng)絡(luò)能穩(wěn)定收斂。

圖6 求解goldberg函數(shù)

圖7 求解trap5函數(shù)

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

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

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

總函數(shù)值為

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

各層的函數(shù)值為

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

4 結(jié)語

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