《神經(jīng)網(wǎng)絡(luò)》課件第9章

9.1

Hopfield神經(jīng)網(wǎng)絡(luò)9.2反饋網(wǎng)絡(luò)與優(yōu)化計(jì)算9.3

Hopfield網(wǎng)絡(luò)的MATLAB開發(fā)9.4小結(jié)

習(xí)題

反饋型神經(jīng)網(wǎng)絡(luò)又稱為遞歸網(wǎng)絡(luò)或回歸網(wǎng)絡(luò),它是一種反饋動力學(xué)系統(tǒng)。反饋網(wǎng)絡(luò)與前饋網(wǎng)絡(luò)是人工神經(jīng)網(wǎng)絡(luò)中兩種最基本的網(wǎng)絡(luò)模型。從控制的觀點(diǎn)來看,后者屬于靜態(tài)網(wǎng)絡(luò),前者則屬于動態(tài)網(wǎng)絡(luò)。聯(lián)想特性是人工神經(jīng)網(wǎng)絡(luò)的一個重要特性,它主要包括兩個方面：聯(lián)想映射與聯(lián)想記憶。在前饋網(wǎng)絡(luò)的討論中,我們著重介紹了神經(jīng)網(wǎng)絡(luò)中誘人的聯(lián)想映射能力；在反饋網(wǎng)絡(luò)的討論中,我們將著重介紹神經(jīng)網(wǎng)絡(luò)的另一誘人特性——聯(lián)想記憶能力。人類智能的一個重要特點(diǎn)就是具有很強(qiáng)的聯(lián)想記憶能力。人不僅能識別記憶中的完整模式,而且也能根據(jù)記憶由模式的部分信息進(jìn)行正確的識別,由部分信息聯(lián)想或恢復(fù)到完整的信息,這即所謂的自聯(lián)想。前饋網(wǎng)絡(luò)研究的是網(wǎng)絡(luò)的輸出與輸入之間的映射關(guān)系,通常不考慮它們之間在時間上的延遲關(guān)系,其輸出、輸入之間無反饋聯(lián)系,給網(wǎng)絡(luò)的分析帶來了許多方便,討論中心是學(xué)習(xí)算法的收斂速度。對于反饋網(wǎng)絡(luò),由于反饋的存在,使它成為一個復(fù)雜的動力學(xué)系統(tǒng),需要考慮輸出與輸入之間的延遲關(guān)系。反饋網(wǎng)絡(luò)的模型雖然較多,但其中典型的是Hopfield神經(jīng)網(wǎng)絡(luò)。它是目前研究得較充分并得到廣泛應(yīng)用的神經(jīng)網(wǎng)絡(luò)模型之一。該網(wǎng)絡(luò)的變量可以取離散值,也可以取連續(xù)值。因此,Hopfield網(wǎng)絡(luò)可分為兩類：離散型與連續(xù)型。我們關(guān)心的是網(wǎng)絡(luò)的穩(wěn)定性問題,通過無教師的學(xué)習(xí),使網(wǎng)絡(luò)狀態(tài)經(jīng)過演變最終收斂到某一穩(wěn)定狀態(tài),從而實(shí)現(xiàn)聯(lián)想記憶或優(yōu)化計(jì)算的功能。9.1

Hopfield神經(jīng)網(wǎng)絡(luò)

Hopfield網(wǎng)絡(luò)作為一種全連接型的神經(jīng)網(wǎng)絡(luò),曾經(jīng)為人工神經(jīng)網(wǎng)絡(luò)的發(fā)展進(jìn)程開辟了新的研究途徑。它利用與階層型神經(jīng)網(wǎng)絡(luò)不同的結(jié)構(gòu)特征和學(xué)習(xí)方法,模擬生物神經(jīng)網(wǎng)絡(luò)的記憶機(jī)理,獲得了令人滿意的結(jié)果。它是由美國物理學(xué)家J.JHopfield于1982年首先提出的,故稱為Hopfield網(wǎng)絡(luò)。下面對此網(wǎng)絡(luò)進(jìn)行詳細(xì)介紹。9.1.1

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

Hopfield神經(jīng)網(wǎng)絡(luò)是一種單層的反饋型網(wǎng)絡(luò)。若網(wǎng)絡(luò)變量的取值為二值{-1,+1}(或{0,1}),神經(jīng)元的功能函數(shù)為線性閾值函數(shù),則這樣的網(wǎng)絡(luò)稱為離散型Hopfield神經(jīng)網(wǎng)絡(luò),簡稱離散Hopfield網(wǎng)絡(luò)。Hopfield網(wǎng)絡(luò)的基本結(jié)構(gòu)如圖9-1所示。

圖中N1,N2,…,Nn表示網(wǎng)絡(luò)的n個神經(jīng)元,各神經(jīng)元的功能函數(shù)通常均取為相同的符號函數(shù)；

x=(x1,x2,…,xn)T∈{-1,+1}n

為網(wǎng)絡(luò)的輸入(向量)；y=(y1,y2,…,yn)T∈{-1,+1}n為網(wǎng)絡(luò)的輸出(向量)；V(t)=[v1(t),v2(t),…,vn(t)]T∈{-1,+1}n為網(wǎng)絡(luò)在時刻t的狀態(tài)(向量),各狀態(tài)變量vi(t)通常是指神經(jīng)元在時刻t的輸出量,t∈{0,1,2,…}為離散的時間變量。網(wǎng)絡(luò)的動態(tài)特性可由下列一組非線性差分方程來描述：(9-1)(9-2)其中：θj為神經(jīng)元的閾值,通常取各神經(jīng)元的閾值相等,且為了分析簡便,往往均取為零(即θ1=θ2=…=θn=0)；sgn(·)為符號函數(shù),其取值為若采用二值{0,1},則式(9-2)應(yīng)改寫為(9-3)下面的討論均采用二值{+1,-1},所得結(jié)論具有普遍性。對于采用二值{0,1}也是有效的，讀者若有興趣可自行類推,這里不再贅述。圖9-1

Hopfield網(wǎng)絡(luò)結(jié)構(gòu)示意圖當(dāng)網(wǎng)絡(luò)經(jīng)過學(xué)習(xí),建立了連接權(quán)矩陣w=(wji)后,網(wǎng)絡(luò)就處于待工作狀態(tài)。網(wǎng)絡(luò)運(yùn)行時,通過輸出、輸入間的反饋?zhàn)饔?實(shí)現(xiàn)網(wǎng)絡(luò)狀態(tài)的演變,直至收斂到穩(wěn)定狀態(tài)為止。若作用在網(wǎng)絡(luò)上的輸入為x,網(wǎng)絡(luò)各神經(jīng)元就處于一特定的初始狀態(tài),經(jīng)網(wǎng)絡(luò)的作用,可以得到一時刻網(wǎng)絡(luò)的狀態(tài)(即在這一時刻各神經(jīng)元的輸出)。然后通過反饋?zhàn)饔?可得下一時刻的輸入信號；由這個新的輸入信號經(jīng)過網(wǎng)絡(luò)的作用,可得再下一時刻網(wǎng)絡(luò)的狀態(tài),反饋至輸入端又可得新的輸入信號,依次反復(fù)演變。網(wǎng)絡(luò)的狀態(tài)通過反饋?zhàn)饔貌粩嗟厝绱搜葑冎?。如果網(wǎng)絡(luò)是穩(wěn)定的,則隨著狀態(tài)演變不斷地進(jìn)行,網(wǎng)絡(luò)狀態(tài)的變化將不斷減少,直至達(dá)到穩(wěn)定狀態(tài)。因此,網(wǎng)絡(luò)的運(yùn)行方程為(9-4)若達(dá)到t時刻后,網(wǎng)絡(luò)狀態(tài)不再改變,則已收斂至穩(wěn)定點(diǎn),即有：

v(t+1)=v(t)(9-5)這時由輸出端可得網(wǎng)絡(luò)的穩(wěn)定輸出：

y=v(t)(9-6)

在網(wǎng)絡(luò)的運(yùn)行過程中,網(wǎng)絡(luò)狀態(tài)的演變主要有兩種工作方式。

(1)異步方式。異步方式又稱非同步或串行方式,其特點(diǎn)是：在每個時間節(jié)拍里只對一個神經(jīng)元i進(jìn)行調(diào)整,而其余的神經(jīng)元狀態(tài)保持不變。故異步工作方式的調(diào)整算法為(9-7)每次被調(diào)整的神經(jīng)元序號i可以按隨機(jī)方式選擇,也可以按預(yù)定的序列逐個調(diào)整。

(2)同步方式。同步方式又稱并行方式,其特點(diǎn)是：在同一時間節(jié)拍里,網(wǎng)絡(luò)的所有神經(jīng)元同時進(jìn)行調(diào)整。故同步方式的調(diào)整算法為

(9-8)

有時,也可以是一部分神經(jīng)元的狀態(tài)同時進(jìn)行調(diào)整。通常,只要在同一時間節(jié)拍里進(jìn)行同時調(diào)整的神經(jīng)元不止一個,均稱為同步工作方式。9.1.2

Hopfield網(wǎng)絡(luò)的穩(wěn)定性

作為一個非線性動力學(xué)系統(tǒng),Hopfield網(wǎng)絡(luò)的穩(wěn)定性是非常重要的,在任一初始狀態(tài)作用下,網(wǎng)絡(luò)可能收斂到穩(wěn)定狀態(tài),也可能收斂到極限環(huán)產(chǎn)生振蕩。若將每一記憶樣本均視為網(wǎng)絡(luò)的一個穩(wěn)定狀態(tài),且要具有足夠的穩(wěn)定域,那么從初始狀態(tài)的演變過程和收斂到穩(wěn)定狀態(tài)的過程則是尋找記憶的過程。初始狀態(tài)可認(rèn)為是給定的部分信息,網(wǎng)絡(luò)的演變和收斂到穩(wěn)定狀態(tài)的過程,就是從部分信息找到全部信息實(shí)現(xiàn)聯(lián)想記憶的過程。

1.吸引子和吸引域

若網(wǎng)絡(luò)從初態(tài)出發(fā),通過反饋,狀態(tài)不斷地演變,至某一刻t到達(dá)穩(wěn)定狀態(tài),從此網(wǎng)絡(luò)狀態(tài)不隨時間變化而變化,則稱該網(wǎng)絡(luò)是穩(wěn)定的。其穩(wěn)定狀態(tài)的表達(dá)式為

v(t0+t+Δt)=v(t0+t)

Δt>0(9-9)

若取t0=0,Δt=1,則穩(wěn)定狀態(tài)表達(dá)式可變?yōu)?/p>

v(t+1)=v(t)(9-10)或各分量為(9-11)于是有：(9-12)式(9-12)表明,若v(t)為網(wǎng)絡(luò)的穩(wěn)定狀態(tài),則其各神經(jīng)元的加權(quán)輸入量與輸出量是同號的,因而其乘積大于零。故式(9-12)可作為網(wǎng)絡(luò)穩(wěn)定狀態(tài)的條件表達(dá)式。

為了簡化分析,通常取閾值θj=0,于是,穩(wěn)定狀態(tài)表達(dá)式(9-11)可用向量矩陣簡潔地表示如下：

v(t+1)=sgn(w·v(t))=v(t)(9-13)若輸入模式為網(wǎng)絡(luò)的穩(wěn)定狀態(tài),由上式則應(yīng)有：

網(wǎng)絡(luò)的穩(wěn)定狀態(tài)也稱為“吸引子”

(Attractor)或“不動點(diǎn)”(FixedPoint)。我們希望：需要網(wǎng)絡(luò)記憶的樣本皆為網(wǎng)絡(luò)的穩(wěn)定狀態(tài)；除此之外網(wǎng)絡(luò)不應(yīng)再有別的吸引子,因?yàn)檫@些吸引子是多余的,相應(yīng)的穩(wěn)定狀態(tài)稱為偽(或虛)穩(wěn)定狀態(tài)。(9-14)為了實(shí)現(xiàn)良好的聯(lián)想記憶功能,當(dāng)網(wǎng)絡(luò)輸入受了干擾或?yàn)槿睋p的樣本時,網(wǎng)絡(luò)應(yīng)有能力自動聯(lián)想,由部分信息恢復(fù)全部信息,并吸引到樣本向量所對應(yīng)的吸引子。這就是說,網(wǎng)絡(luò)的吸引子應(yīng)有一定的吸引范圍或稱吸引域,且這種吸引應(yīng)是強(qiáng)吸引的。設(shè)v為網(wǎng)絡(luò)的吸引子。所謂強(qiáng)吸引,是指從x開始的每條狀態(tài)演變路徑都可到達(dá)v,則稱x強(qiáng)吸引到v,并記作；對于吸引子v的鄰域N(v),若對于所有x∈N(v)都有,則稱N(v)為v的強(qiáng)吸引域。與此相對應(yīng),弱吸引是指若存在一條路徑可從x演變到v,則稱x弱吸引到v,并記作；對于吸引子v的鄰域N(v),若對所有x∈N(v)都有,則稱N(v)為v的弱吸引域。

2.漢明距離

為了說明各向量之間的差異程度,需引入某種度量的標(biāo)準(zhǔn)。通常使用信息與編碼理論中廣泛采用的漢明距離dH來作為度量的標(biāo)準(zhǔn)。兩向量v1與v2之間的漢明距離定義為：

dH(v1,v2)=v1與v2中對應(yīng)元素不相同(即v1i≠v2i)的總個數(shù)

(9-15)

對于元素取二值vi∈{-1,+1},則有：

(9-16)

顯然,若v1=v2則dH(v1,v2)=0；若兩個n維向量各元素均相反,則dH(v1,v2)=n。

3.能量函數(shù)

研究動力學(xué)系統(tǒng)的穩(wěn)定性,通常使用“能量函數(shù)”的方法,這是李雅普諾夫穩(wěn)定性第二方法的一種推廣應(yīng)用。這里借用鐵磁材料哈密頓函數(shù)的形式來定義離散Hopfield網(wǎng)絡(luò)的能

量函數(shù)。在鐵磁體中鐵磁分子旋轉(zhuǎn)只有兩個方向,即可認(rèn)為自旋Pi∈{-1,+1},在鐵磁材料中哈密頓函數(shù)為其中：鐵磁分子自旋Pi、Pj只有兩個方向{-1,+1}；Jij為第i個鐵磁分子與第j個鐵磁分子之間的作用,Jij=Jji。整個物質(zhì)相互作用的結(jié)果是使哈密頓函數(shù)H達(dá)到最小。而離散Hopfield網(wǎng)絡(luò)與此很相似，變量也是二值量,相互作用可由連接權(quán)wij表示。因此Hopfield就定義網(wǎng)絡(luò)的能量函數(shù)為(9-17)(9-18)由于vi,vj∈{-1,+1},wij與θi有界,i,j=1,2,…,n,故能

量函數(shù)E是有界的,即(9-18)如果從任意初態(tài)出發(fā),網(wǎng)絡(luò)狀態(tài)的演變都能滿足ΔE≤0,則表明隨著狀態(tài)演變過程的進(jìn)行,能量函數(shù)E是單調(diào)下降的。也就是說,在吸引子的吸引域內(nèi),當(dāng)狀態(tài)離吸引子較遠(yuǎn)時,其能量是較大的；隨著狀態(tài)演變過程的進(jìn)行,狀態(tài)越趨近吸引子,其能量就越??；當(dāng)能量達(dá)到極小點(diǎn)而不再改變(即ΔE=0)時,網(wǎng)絡(luò)就處于穩(wěn)定狀態(tài)。

4.穩(wěn)定性結(jié)論

結(jié)論1

若網(wǎng)絡(luò)按異步方式工作,且滿足wij=wji，wii=0,i,j,=1,2,…,n,則從任意初態(tài)出發(fā),Hopfield網(wǎng)絡(luò)最終將收斂

到一個穩(wěn)定狀態(tài)。

證明對于離散Hopfield網(wǎng)絡(luò)的單個神經(jīng)元j,其狀態(tài)變化可能為(9-20)當(dāng)網(wǎng)絡(luò)工作在異步方式時,每一節(jié)拍只有一個神經(jīng)元(設(shè)為i)狀態(tài)發(fā)生變化,而其余神經(jīng)元保持不變。于是可得：

由于網(wǎng)絡(luò)對稱,wij=wji,wii=0,故上式可改寫為(9-21)(9-22)因此有：

當(dāng)neti(t)≥0時,Δvi≥0,則ΔE≤0;

當(dāng)neti(t)<0時,Δvi≤0,則ΔE≤0。(9-23)

這表明,在任意初態(tài)下均能夠滿足ΔE≤0,因而保證了網(wǎng)絡(luò)的穩(wěn)定性。

同理可證得下列結(jié)論。結(jié)論2

若網(wǎng)絡(luò)按異步方式工作,且滿足

wij=wji,wii>0(i,j=1,2,…,n),則網(wǎng)絡(luò)是穩(wěn)定的。

結(jié)論3若網(wǎng)絡(luò)按同步方式工作,且滿足wij=wji，當(dāng)權(quán)矩陣為非負(fù)定(w≥0)時,則網(wǎng)絡(luò)從任意初態(tài)出發(fā)的演變過程將收斂到穩(wěn)定狀態(tài)；當(dāng)權(quán)矩陣不滿足非負(fù)定條件時,則將不能保證同步演變過程的收斂性,可能出現(xiàn)狀態(tài)的周期振蕩,形成權(quán)限環(huán)；若權(quán)矩陣為負(fù)定的,則網(wǎng)絡(luò)周期振蕩,出現(xiàn)權(quán)限環(huán)。下面舉例說明。圖9-2所示的由兩個神經(jīng)元構(gòu)成的離散Hopfield網(wǎng)絡(luò),其權(quán)矩陣和閾值分別為

假設(shè)初始狀態(tài)為，則網(wǎng)絡(luò)的狀態(tài)在和

之間來回振蕩。圖9-2同步工作方式的Hopfield網(wǎng)絡(luò)9.1.3基本學(xué)習(xí)規(guī)則

Hopfield網(wǎng)絡(luò)的學(xué)習(xí)采用的是無教師學(xué)習(xí)。學(xué)習(xí)的過程相應(yīng)于形成網(wǎng)絡(luò)的連接權(quán)矩陣。討論的中心問題在于,如何使網(wǎng)絡(luò)對于給定的問題進(jìn)行學(xué)習(xí),建立連接權(quán)矩陣,并使網(wǎng)絡(luò)具有較強(qiáng)的聯(lián)想記憶能力。假設(shè)需要存貯的記憶樣本有x1,x2,…,xp,xi∈{-1,+1}n。

1.Hebb學(xué)習(xí)規(guī)則

1)對一個模式的學(xué)習(xí)

為了分析簡便,首先考慮網(wǎng)絡(luò)對一個模式的學(xué)習(xí)。這時需要存貯的記憶樣本只有1個(設(shè)為x1),它將成為網(wǎng)絡(luò)的穩(wěn)定狀態(tài),并具有最大的吸引域,或者說是具有最大的“糾錯能力”。

將記憶樣本x1輸入到網(wǎng)絡(luò),并作為網(wǎng)絡(luò)的初始狀態(tài),經(jīng)過演變,它將成為網(wǎng)絡(luò)的穩(wěn)定狀態(tài)。設(shè)網(wǎng)絡(luò)的連接權(quán)矩陣為w,有：或(9-24)由符號函數(shù)的性質(zhì)可知，式(9-24)等價于下列關(guān)系式：(9-25)欲使式(9-25)成立，則連接權(quán)應(yīng)和的乘積成比例。故網(wǎng)絡(luò)對記憶樣本的學(xué)習(xí)關(guān)系式為：

其中比例系數(shù)a>0為一常數(shù)。通常取a=1或a=1/n(n為樣本向量的維數(shù))。

式(9-26)的學(xué)習(xí)關(guān)系式是Hebb于20世紀(jì)40年代末首先提出的一種神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)算法,屬于無教師學(xué)習(xí),實(shí)際上它是一種死記式學(xué)習(xí),收斂速度很快。

(9-26)當(dāng)網(wǎng)絡(luò)只有一個輸入模式時,它不僅是網(wǎng)絡(luò)的吸引子,而且可以證明網(wǎng)絡(luò)的觀察向量為x,它與記憶樣本x1的漢明距離設(shè)為,則網(wǎng)絡(luò)的輸出為

yj=sgn(netj)

j=1,2,…,n(9-27)

其中：第j個神經(jīng)元的加權(quán)輸入為將式(9-26)代入上式可得：

式中因子n-k為與x1中相同的各元素乘積之和,即為；-k為與x1中不同的各元素乘積之和。故式(9-27)可改寫為(9-28)(9-29)為使網(wǎng)絡(luò)的輸入觀察向量能收斂到吸引子x1上,根據(jù)穩(wěn)定條件應(yīng)滿足：

(9-30)

而a＞0,故由上式可導(dǎo)出：

(9-31)

式(9-31)表明,當(dāng)Hopfield網(wǎng)絡(luò)只有一個記憶樣本時,網(wǎng)絡(luò)的最大糾錯能力可達(dá)n/2漢明距離。這就是說,輸入50%的信息,網(wǎng)絡(luò)可聯(lián)想出全部的信息。

2)對多個模式的學(xué)習(xí)

當(dāng)網(wǎng)絡(luò)需要學(xué)習(xí)的記憶樣本有p個(x1,x2,…,xp)時,學(xué)習(xí)的算法仍然是Hebb規(guī)則,它是式(9-26)的推廣,則有：

于是權(quán)矩陣為：(9-32)(9-33)可見,當(dāng)系數(shù)a=1時,根據(jù)Hebb規(guī)則,網(wǎng)絡(luò)的連接權(quán)矩陣可表示為各學(xué)習(xí)模式x1,x2,…,xp的外積和。

在實(shí)際應(yīng)用中往往取wii=0,因?yàn)椴粠ё原h(huán)的Hopfield網(wǎng)絡(luò)的穩(wěn)定性易于保證。對于這種不帶自環(huán)的網(wǎng)絡(luò),式(9-32)和式（9-33)可改寫為(9-34)和

學(xué)習(xí)過程一旦結(jié)束,連接權(quán)矩陣就形成,網(wǎng)絡(luò)便可進(jìn)入工作狀態(tài)。輸入觀察向量(或未知向量)x,則網(wǎng)絡(luò)進(jìn)行狀態(tài)演變,直至收斂到穩(wěn)定狀態(tài)。這時網(wǎng)絡(luò)的穩(wěn)定輸出就是聯(lián)想的結(jié)果。(9-35)

2.多個記憶模式間的相互干擾

如果網(wǎng)絡(luò)只記憶一個模式,則該模式肯定是網(wǎng)絡(luò)的不動點(diǎn),且具有最大的糾錯能力,可達(dá)n/2漢明距離。但當(dāng)記憶的模式增多時,各個模式間的相互影響不可避免地存在,這主要表

現(xiàn)為以下幾種方式。

1)權(quán)值移動

根據(jù)Hebb學(xué)習(xí)規(guī)則,網(wǎng)絡(luò)對輸入模式x1,x2,…,xp的學(xué)習(xí)記憶是逐個實(shí)現(xiàn)的。比如,對無自環(huán)網(wǎng)絡(luò)的權(quán)矩陣,其學(xué)習(xí)記憶過程為

w←0

for

k=1,2,…,p,w←w+[axk(axk)T-I]

當(dāng)k=1時,網(wǎng)絡(luò)能準(zhǔn)確地記住模式x1；當(dāng)k=2時,為了記憶模式x2,連接權(quán)值需要在原有基礎(chǔ)上移動。這樣,對模式x1式(9-25)可能不再對所有j∈{1,2,…,n}都成立，可能會部分遺忘以前的記憶；對模式x2,由于權(quán)矩陣w已學(xué)習(xí)了x1,其起始值不再是零,因而條件(9-25)也未必對所有的j∈{1,2,…,n}都成立,這就是說,難以保證網(wǎng)絡(luò)對x2一定能準(zhǔn)確地記憶。余可類推。從動力學(xué)觀點(diǎn)來看,當(dāng)k較小時,經(jīng)學(xué)習(xí)可使輸入模式成為網(wǎng)絡(luò)的吸引子；然而隨著k增大,可能不僅難以使后來的模式成為吸引子,而且將原來吸引子的吸引域變小,甚至使原處于吸引子的模式發(fā)生移動或淡忘。對于一定規(guī)模的網(wǎng)絡(luò)(即節(jié)點(diǎn)數(shù)n一定時),存在能學(xué)習(xí)記憶的模式數(shù)上限pmax,這時網(wǎng)絡(luò)不但無力記憶以后輸入的模式,而且對以前的記憶也將逐漸淡忘。產(chǎn)生這種網(wǎng)絡(luò)“疲勞”的原因就在于交叉干擾。

2)交叉干擾

設(shè)網(wǎng)絡(luò)的權(quán)矩陣已經(jīng)建立,若輸入向量為x,希望它成為網(wǎng)絡(luò)的吸引子,其條件為

x=sgn(wx)

(9-36)

其中網(wǎng)絡(luò)的加權(quán)輸入：(9-37)設(shè)輸入；令，

由于，于是得：(9-38)由式(9-37)可得網(wǎng)絡(luò)的加權(quán)輸入為：(9-39)分析式(9-39)可以看到：當(dāng)網(wǎng)絡(luò)學(xué)習(xí)記憶多個模式時,根據(jù)符號函數(shù)的性質(zhì)可知，式(9-39)右邊的第一項(xiàng)能使網(wǎng)絡(luò)建立與xl相應(yīng)的吸引子；而其右邊的第二項(xiàng)是表示學(xué)習(xí)其它模式時所產(chǎn)生的對第一項(xiàng)的干擾,故稱為交叉干擾項(xiàng)。因此,網(wǎng)絡(luò)對于學(xué)習(xí)模式集合中某一模式能否正確地記憶與聯(lián)想,完全取決于式(9-39)右邊第一項(xiàng)與第二項(xiàng)的大小及其符號關(guān)系。9.1.4

Hopfield網(wǎng)絡(luò)的聯(lián)想特性

綜上分析可以看到,Hopfield網(wǎng)絡(luò)是利用穩(wěn)定狀態(tài)來對信息進(jìn)行記憶的,利用從初態(tài)到穩(wěn)定狀態(tài)的演變過程來實(shí)現(xiàn)對信息的聯(lián)想。下面討論Hopfield網(wǎng)絡(luò)的主要聯(lián)想特性

1.記憶樣本與穩(wěn)定狀態(tài)方面

結(jié)論1設(shè)網(wǎng)絡(luò)各神經(jīng)元的閾值為零,若模式x為網(wǎng)絡(luò)的

穩(wěn)定狀態(tài),則-x也是網(wǎng)絡(luò)的穩(wěn)定狀態(tài)。證明若x為穩(wěn)定狀態(tài),則有：

x=sgn(wx)

(9-40)

若對換網(wǎng)絡(luò)輸入-x,則網(wǎng)絡(luò)的狀態(tài)演變?yōu)?/p>

sgn[w(-x)]=sgn(-wx)=-sgn(wx)=-x

(9-41)因此-x也為網(wǎng)絡(luò)的穩(wěn)定狀態(tài)。結(jié)論2對于無自環(huán)網(wǎng)絡(luò),若有兩個模式x1和x2,dN(x1,x2)=1,則x1和x2不可能同時成為網(wǎng)絡(luò)的穩(wěn)定狀態(tài)。

證明

dN(x1,x2)=1,這表明x1和x2只有一個元素不同。不妨假定它們的第一個元素不同,即,而其余的元素均相同,即,i=2,3,…,n。若x1為穩(wěn)定狀態(tài),則網(wǎng)絡(luò)第一個神經(jīng)元的輸出應(yīng)為

對網(wǎng)絡(luò)輸入x2,若x2也為穩(wěn)定狀態(tài),則第一個神經(jīng)元的輸出應(yīng)為

(9-42)(9-43)式(9-42)和式(9-43)的右端相同。于是可導(dǎo)出其左端也應(yīng)相等,即。這與假定條件矛盾。故x1和x2不可能同時成為網(wǎng)絡(luò)的穩(wěn)定狀態(tài)。結(jié)論3若dN(x1,x2)=n-1,則模式x1和x2也不可能同時成為網(wǎng)絡(luò)的穩(wěn)定狀態(tài)。

證明證明過程參考結(jié)論2。

對于離散Hopfield網(wǎng)絡(luò),我們的目的是企圖使所有的記憶樣本都能成為網(wǎng)絡(luò)的穩(wěn)定狀態(tài)。除此之外,網(wǎng)絡(luò)再沒有別的穩(wěn)定狀態(tài)。但從上述討論中可以看到：①并不是任意的輸入

模式都可以同時成為網(wǎng)絡(luò)的吸引子,它們必須是互不相似且差異較大的,結(jié)論1~3是記憶樣本欲成為網(wǎng)絡(luò)吸引子必須滿足的必要條件。②在網(wǎng)絡(luò)中存在一些非記憶樣本的多余穩(wěn)定狀態(tài)

,通常稱之為偽(或虛)穩(wěn)定狀態(tài)。因此,在實(shí)際應(yīng)用上應(yīng)注意這種情況的存在,同時為了得到良好的聯(lián)想特性,從初態(tài)演變到穩(wěn)定狀態(tài)應(yīng)當(dāng)是強(qiáng)吸引的。

【例9-1】Hopfield網(wǎng)絡(luò)n=3,m=3,三個記憶樣本為x1=(1,1,-1)T,x2=(1,1,-1)T,x3=(1,1,-1)T。

解根據(jù)Hebb學(xué)習(xí)規(guī)則,取a=1,于是可得網(wǎng)絡(luò)的連接權(quán)矩陣為

可以驗(yàn)證：

sgn(wx1)=x1,

sgn(wx2)=x2

即模式x1和x2均為網(wǎng)絡(luò)的穩(wěn)定狀態(tài)。而dH(x3,x2)=1,由結(jié)論2可知,既然x2為穩(wěn)定狀態(tài),那么,模式x3不可能成為網(wǎng)絡(luò)的穩(wěn)定狀態(tài)。當(dāng)輸入模式x3時,網(wǎng)絡(luò)的輸出為網(wǎng)絡(luò)具有較好的聯(lián)想記憶能力。例如當(dāng)輸入觀察向量x=(-1,1,-1)時,網(wǎng)絡(luò)的輸出為

因?yàn)??？梢?未知的觀察向量x是按漢明距離最小的意義下,收斂于網(wǎng)絡(luò)的吸引子x1；也就是說受了干擾的不完全信息,在Hopfield網(wǎng)絡(luò)的聯(lián)想作用下,使信息得到了恢復(fù)。

2.網(wǎng)絡(luò)容量方面

結(jié)論4設(shè)p個模式向量x1,x2,…,xp,當(dāng)0<a<1/2時：

an≤dH(xi,xj)≤(1-a)ni≠j

(9-44)

若下列條件成立：

(9-45)

則當(dāng)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)n足夠大時,x1,x2,…,xp為網(wǎng)絡(luò)的穩(wěn)定狀態(tài)。證明設(shè)，于是有：

(xi)Txj=(xi與xj中相同元素之乘積和)-(xi與xj中不同元素

之乘積和)

=(n-dij)-dij=n-2dij

即

|(xi)Txj|=|n-2dij|≤n-2an=(1-2a)n(9-46)

由Hebb學(xué)習(xí)規(guī)則,取a=1,則有：

(9-47)

設(shè)輸入向量x=xl,l∈{1,2,…,p},于是：

上式右邊第二項(xiàng)為交叉干擾項(xiàng),現(xiàn)估計(jì)其大小?？紤]到式(9-47),該干擾項(xiàng)為n維列向量,其第i個元素的大小為

(9-48)(9-49)分析式(9-49)可以看到：如果交叉干擾項(xiàng)的符號與第一項(xiàng)相反,則當(dāng)干擾項(xiàng)第i個元素的絕對值大于第一項(xiàng)對應(yīng)元素的值時,由符號函數(shù)性質(zhì)可知,這將造成網(wǎng)絡(luò)輸出的第i位出錯

。因此,為了使模式xl成為網(wǎng)絡(luò)的穩(wěn)定狀態(tài),其條件是式(9-49)

的第一項(xiàng)起主導(dǎo)作用,即：

(n-p)>(p-1)(1-2α)n

或(9-50)當(dāng)n足夠大時,上式可化簡為

這就是說,當(dāng)p滿足條件式(9-51)時,則對于p個模式向量,有：

即它們均為網(wǎng)絡(luò)的穩(wěn)定狀態(tài)。

結(jié)論4表明：模式向量一般來說不一定都能成為網(wǎng)絡(luò)的吸引子,但當(dāng)滿足一定的條件時,則可同時成為網(wǎng)絡(luò)的穩(wěn)定狀態(tài)。(9-51)(9-52)結(jié)論5當(dāng)α=1/2時,則結(jié)論4中的p個模式向量x1,x2,…,xp為正交向量,且它們都是網(wǎng)絡(luò)的穩(wěn)定狀態(tài)。

證明當(dāng)α=1/2時,由結(jié)論1可知：

因?yàn)楦髂Ｊ较蛄渴钦坏?所以有：

(xi)Txj=0

i≠j

而由式(9-48)可得,當(dāng)網(wǎng)絡(luò)輸入模式向量xl時,對應(yīng)的交叉干擾項(xiàng)：

因此,對所有模式向量xl,l∈{1,2,…,p}均滿足式(9-52),

即各模式向量均為網(wǎng)絡(luò)的吸引子。

結(jié)論6當(dāng)模式向量為正交向量時,網(wǎng)絡(luò)可穩(wěn)定存貯的模式數(shù)等于網(wǎng)絡(luò)的神經(jīng)元數(shù),皆為n。

證明若網(wǎng)絡(luò)的神經(jīng)元數(shù)為n,通常稱該網(wǎng)絡(luò)為n維的,相應(yīng)地,網(wǎng)絡(luò)的輸入狀態(tài)和輸出也均為n維向量。對于n維向量空間,其最大正交向量子集中量的個數(shù)為n。于是由結(jié)論5令p=n,則得證。綜上述分析可以看到,網(wǎng)絡(luò)可存貯的記憶樣本數(shù)的上限,即網(wǎng)絡(luò)的容量問題,是一重要且相當(dāng)復(fù)雜的研究課題。它不僅取決于網(wǎng)絡(luò)的結(jié)構(gòu)和算法,而且也取決于被存貯的模式向量。因此,很難得到一般的結(jié)論,只能給出一些基本的特點(diǎn)。當(dāng)存貯的模式為正交向量時,網(wǎng)絡(luò)容量最大,可為網(wǎng)絡(luò)的維數(shù),即pmax=n。然而,要求存貯的模式向量為正交的,很難實(shí)現(xiàn)。有關(guān)網(wǎng)絡(luò)的容量問題,有待進(jìn)一步研究。9.2反饋網(wǎng)絡(luò)與優(yōu)化計(jì)算

Hopfield網(wǎng)絡(luò)是一單層的反饋型網(wǎng)絡(luò),網(wǎng)絡(luò)的基本結(jié)構(gòu)在前面已做了介紹。連續(xù)Hopfield網(wǎng)絡(luò)與以上介紹的離散Hopfield網(wǎng)絡(luò)相比較,主要的不同點(diǎn)有：①連續(xù)Hopfield網(wǎng)絡(luò)神經(jīng)元的功能函數(shù)采用的不是符號函數(shù),而是連續(xù)可微單調(diào)非減的S型函數(shù)；②網(wǎng)絡(luò)的輸入狀態(tài)和輸出變量的取值,不是離散的二值量,而是在一定范圍內(nèi)變化的連續(xù)量。因而連續(xù)Hopfield網(wǎng)絡(luò)的狀態(tài)演變不再是異步方式或同步方式,而是連續(xù)的方式,即網(wǎng)絡(luò)的所有神經(jīng)元均連續(xù)地隨時間t并行地更新。對于網(wǎng)絡(luò)的單個神經(jīng)元(設(shè)為第i個神經(jīng)元)而言,其輸入的累加值為

(9-53)式中,vj為網(wǎng)絡(luò)的第j個神經(jīng)元的輸出；Ii為作用在第i個神經(jīng)元的外部刺激或該神經(jīng)元的閾值“-θi”。第i個神經(jīng)元的狀態(tài)ui與輸入累加值之間的關(guān)系,可用下列狀態(tài)方程表示：

上式中為該神經(jīng)元動態(tài)特性的時間常數(shù)。于是該神經(jīng)元的輸出為：

vi=f(ui)(9-54)(9-55)通常神經(jīng)元的功能函數(shù)f(·)為S型函數(shù)。由于Hopfield網(wǎng)絡(luò)是一動態(tài)網(wǎng)絡(luò),因此網(wǎng)絡(luò)的穩(wěn)定性分析是需要關(guān)注的主要問題。

Hopfield網(wǎng)絡(luò)已經(jīng)有很多成功的應(yīng)用,現(xiàn)在還在不斷地發(fā)展。這種網(wǎng)絡(luò)的應(yīng)用形式主要有聯(lián)想記憶和優(yōu)化計(jì)算兩種,而其具體的應(yīng)用領(lǐng)域有圖像、語音和信號處理、模式分類和識別、知識處理、控制、容錯計(jì)算、數(shù)據(jù)查詢等。這里介紹在優(yōu)化計(jì)算中遇到的一些基本概念和方法。9.2.1

Hopfield網(wǎng)絡(luò)的電路模型與動態(tài)方程

根據(jù)Hopfield網(wǎng)絡(luò)的結(jié)構(gòu)(如圖9-1所示),利用模擬電子線路,建立反饋型人工神經(jīng)網(wǎng)絡(luò)的電路模型,如圖9-3所示。圖9-3連續(xù)Hopfield網(wǎng)絡(luò)電路模型連續(xù)Hopfield網(wǎng)絡(luò)模擬電路主要由以下部分構(gòu)成：

(1)運(yùn)算放大器用來模擬神經(jīng)元的非線性功能函數(shù)。通常,神經(jīng)元的功能函數(shù)采用的是連續(xù)可微單調(diào)非減的Sigmoid函數(shù)。

(2)運(yùn)算放大器輸入端的電阻Ri與電容Ci的并聯(lián)電路用來模擬神經(jīng)元動態(tài)特性的時間常數(shù)。

(3)連接電導(dǎo)wij建立了由vj產(chǎn)生第i個運(yùn)算放大器輸入電流之間的聯(lián)系,用它來模擬生物神經(jīng)元的突觸作用。在圖中反饋線與輸入線的交叉處,以小圓圈示意表示wij,也可以改用電阻Rij表示,

如圖9-4所示。圖9-4第i個神經(jīng)元的模擬電路圖

(4)外加偏置電流Ii用來模擬神經(jīng)元的閾值“-θi”或外部的刺激。

單個神經(jīng)元的模擬電路如圖9-4所示。根據(jù)電路的克希荷夫定律可列寫單個神經(jīng)元的方程如下：

經(jīng)整理后可得：(9-56)式中,

假定網(wǎng)絡(luò)共有n個神經(jīng)元,各神經(jīng)元模擬電路的參數(shù)相同,且取令，由式(9-53)則可得描述圖9-3所示的連續(xù)Hopfield網(wǎng)絡(luò)的非線性動態(tài)方程為(9-57)或?qū)懗上蛄烤仃嚨男问绞街?，w為n×n的加權(quán)陣。9.2.2

Hopfield網(wǎng)絡(luò)的能量函數(shù)與穩(wěn)定性

由網(wǎng)絡(luò)的動態(tài)方程式(9-56)可以看到,給定一組初值后可求出該方程的解,若其解為一組確定值,則表明網(wǎng)絡(luò)狀態(tài)演變的最終結(jié)果將達(dá)到一個穩(wěn)定的狀態(tài)。如果能設(shè)計(jì)出w和I,使網(wǎng)絡(luò)的穩(wěn)定狀態(tài)與要求的解一致,網(wǎng)絡(luò)就可完成優(yōu)化計(jì)算之功能。網(wǎng)絡(luò)的穩(wěn)定性分析是一重要但又困難的問題,尚待進(jìn)一步研究。目前應(yīng)用較廣的是Hopfield提出的利用李雅普諾夫第二方法來研究網(wǎng)絡(luò)的穩(wěn)定性。他所提出的能量函數(shù)(即通常所謂的Hopfield能量函數(shù))具有明確的物理意義,是建立在能量基礎(chǔ)之上的。它的離散形式就是在鐵磁材料中鐵磁分子自旋的一種哈密頓能量。

1.Hopfield能量函數(shù)的定義

Hopfield為連續(xù)Hopfield網(wǎng)絡(luò)建立的能量函數(shù)為

或改寫成向量矩陣形式：

其中,(9-58)(9-59)將式(9-58)與上一節(jié)離散Hopfield網(wǎng)絡(luò)的能量函數(shù)表達(dá)式相比較可知,它們的差別只是連續(xù)Hopfield網(wǎng)絡(luò)的能量函數(shù)式(9-58)增加了一個積分項(xiàng)。該積分項(xiàng)表示運(yùn)算放大器輸入ui對輸出vi曲線包圍之面積,具有能量的量綱。由于運(yùn)放的放大系數(shù)通常較大,積分項(xiàng)的值較小,往往可忽略不計(jì)。于是式(9-59)可化簡為

可見,此能量函數(shù)為具有能量量綱的“二次型”函數(shù)。

2.網(wǎng)絡(luò)的穩(wěn)定性

通常vi∈[-1,1],能量函數(shù)E是一可正可負(fù)但有界的函數(shù)。利用李雅普諾夫穩(wěn)定性第二方法,可以證明網(wǎng)絡(luò)的穩(wěn)定性具有下列結(jié)論。

穩(wěn)定性定理對于連續(xù)Hopfield網(wǎng)絡(luò),若網(wǎng)絡(luò)對稱wij,Ci>

0,且神經(jīng)元的功能函數(shù)f(·)為連續(xù)單調(diào)遞增函數(shù),則有：且上式等號成立的充要條件為對一切i∈{1,2,…,n},有：證明由式(9-58)可得：

而故由于Ci>0,f-1(·)為連續(xù)單調(diào)遞增函數(shù),故可得：

且可知,若,則對一切i(i=1,2,…,n),均成立,反之亦然。

該定理表明：若連續(xù)Hopfield網(wǎng)絡(luò)是對稱的,則網(wǎng)絡(luò)的狀態(tài)演變總是朝著能量減小的方向運(yùn)動,而且網(wǎng)絡(luò)的穩(wěn)定平衡點(diǎn)就是能量函數(shù)的極小值點(diǎn)。

上述定理只提出了網(wǎng)絡(luò)穩(wěn)定性的充分條件但并非必要的,而且能量函數(shù)也不是唯一的。

3.Hopfield能量函數(shù)的基本性質(zhì)

上已指出,Hopfield能量函數(shù)可正可負(fù),但是有界的。它與李雅普諾夫函數(shù)的差別在于：李雅普諾夫函數(shù)為正定的,而Hopfield能量函數(shù)(簡稱E函數(shù))可以是負(fù)的,是有界的,但E(0)不一定為零。因此,Hopfield函數(shù)是一廣義的李雅普諾夫函數(shù)。只有當(dāng)E函數(shù)滿足E(V)>0,E(0)=0條件時,Hopfield能量函數(shù)才是李雅普諾夫函數(shù),這時才可完全應(yīng)用李雅普諾夫穩(wěn)定性定理來分析網(wǎng)絡(luò)的穩(wěn)定性。9.2.3

Hopfield網(wǎng)絡(luò)的優(yōu)化計(jì)算

應(yīng)用連續(xù)Hopfield網(wǎng)絡(luò)解決優(yōu)化計(jì)算問題,其大致過程可歸納如下。

(1)首先對具體的優(yōu)化問題選擇適當(dāng)?shù)谋硎痉椒?使網(wǎng)絡(luò)的輸出與優(yōu)化問題的解相對應(yīng)。

(2)根據(jù)特定的優(yōu)化問題,構(gòu)造網(wǎng)絡(luò)的能量函數(shù),使其最小值對應(yīng)問題的最優(yōu)解。

(3)將所得能量函數(shù)與Hopfield能量函數(shù)的規(guī)范表達(dá)式(9-58)相比較,則可導(dǎo)出網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)：神經(jīng)元之間的聯(lián)接電導(dǎo)wij和偏流Ii。

(4)根據(jù)網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)構(gòu)造Hopfield網(wǎng)絡(luò),讓其運(yùn)行,則網(wǎng)絡(luò)穩(wěn)定時的輸出就對應(yīng)優(yōu)化問題的解。Hopfield網(wǎng)絡(luò)的實(shí)現(xiàn)方法可以有兩種：硬件實(shí)現(xiàn)或計(jì)算機(jī)仿真。在仿真時,由網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)可確定網(wǎng)絡(luò)的數(shù)學(xué)模型式(9-56),然后在計(jì)算機(jī)上仿真,即可得到問題的滿意解答。

下面以A/D變換器和人工智能的典型問題——TSP問題為例,具體說明用人工神經(jīng)網(wǎng)絡(luò)解決優(yōu)化計(jì)算問題的基本原理和大致過程。

【例9-2】A/D變換器問題。

用神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)A/D變換器,與傳統(tǒng)的A/D變換器電路相比較,具有結(jié)構(gòu)簡單、可提高工作速度等優(yōu)點(diǎn)。下面以4位A/D變換器為例說明它的工作原理,圖9-5所示為Tank與Hopfield給出的神經(jīng)網(wǎng)絡(luò)A/D變換器的電路原理示意圖。圖9-5人工神經(jīng)網(wǎng)絡(luò)A/D變換器的電路原理示意圖圖中為了實(shí)現(xiàn)4位A/D變換之功能,用4個運(yùn)算放大器模擬神經(jīng)元構(gòu)成Hopfield網(wǎng)絡(luò),將轉(zhuǎn)換的模擬量以及參考電源-U從右上端輸入,各反饋線與運(yùn)放輸入線之交叉處以小圓圈表示相應(yīng)的電導(dǎo)值wij,而運(yùn)放的輸出即給出A/D變換后的4位數(shù)字量。首先建立網(wǎng)絡(luò)的能量函數(shù)。A/D變換可作為一優(yōu)化問題來處理,要求變換的精度最高,或要求模擬量x與變換后輸出的數(shù)字量之差最小?，F(xiàn)取最優(yōu)性條件為方差最小,即取目標(biāo)函數(shù)為

式中：vi(i=0,1,2,3)為各運(yùn)放輸出的數(shù)字量,vi∈{0,1}；2i表示數(shù)字量vi的二進(jìn)制位數(shù)。顯然J(v)≥0。(9-60)一般來說,運(yùn)算放大器的輸出vi為0~1之間變化的模擬量,為了確保電路輸出的有效性,使vi為最靠近0或1的數(shù)字量,于是取約束條件為(9-61)由約束條件可知：僅當(dāng)輸出為數(shù)字量vi∈{0,1}時,g(v)=0；否則,當(dāng)vi為非數(shù)字量(即vi為0與1之間的任意實(shí)數(shù))時,g(v)>0。式中系數(shù)的設(shè)置是為了保證網(wǎng)絡(luò)無自反饋,即wii=0。

由于運(yùn)放的放大系數(shù)較大,故式(9-58)的積分項(xiàng)較小,往往可略去不計(jì)。于是將式(9-60)與式(9-61)相加,并去除與變量vi無關(guān)的量(即常數(shù)項(xiàng)x2/2),則可建立網(wǎng)絡(luò)的能量函數(shù)為(9-62)將上式與Hopfield能量函數(shù)的規(guī)范表達(dá)式相比較,則可求得網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)為(式中負(fù)號利用運(yùn)放的反相輸出來實(shí)現(xiàn))具體參數(shù)值如圖9-5中小圓圈旁所示。

【例9-3】旅行商問題(TravelingSalemanProblem,TSP)。

TSP問題是指有一商人要巡回n個城市,從某城市出發(fā),要求尋找一條最優(yōu)的路徑,使其距離最短。TSP問題是一典型的人工智能難題,其算法的復(fù)雜性屬于NP(NondeterministicPol

ynomial)難題,沒有確定的算法能夠在多項(xiàng)式界時間內(nèi)得到問題的解。對于該問題,若采用窮舉搜索算法,隨著城市數(shù)n的增加,算法的復(fù)雜性是難以接受的。

設(shè)n個城市為C1,C2,…,Cn,一條有效的路徑可視為這n個城市的某種排列Ci1,Ci2,…,Cin,其中i1,i2,…,in為自然序列

1,2,…,n的一種排列。ik=j表示在該條路徑中的城市Ci被訪問的順序?yàn)榈趉個。n個城市的全排列有n!種。但TSP問題不限定路徑的起點(diǎn)和路徑的方向,于是排列Ci1,Ci2,…,Cin和逆序

Cin,Cin-1,…,Ci1以及其所有的循環(huán)移動所構(gòu)成的排列(如Ci2

Ci3CinCi1,CinCi1,Ci3Ci4…CinCi2等)均應(yīng)視為同一條路徑。因此,n個城市的TSP路徑總數(shù)為由斯特林(Stirlin)

公式,上式可改寫為

表9-1表示路徑數(shù)與城市數(shù)的關(guān)系?？梢?路徑總數(shù)隨著城市數(shù)按指數(shù)律增長。當(dāng)城市數(shù)很多時,窮舉搜索算法實(shí)際上是不可行的。

(9-63)表9-1

TPS的可能路徑數(shù)

應(yīng)用神經(jīng)網(wǎng)絡(luò)方法,可將TSP作為一優(yōu)化問題來處理。

(1)將TSP問題轉(zhuǎn)化為適于神經(jīng)網(wǎng)絡(luò)處理的形式。對于n個城市的TSP問題,可使用n×n個神經(jīng)元,用神經(jīng)元的狀態(tài)表示某一城市在某條路徑中被訪問的順序。神經(jīng)元xi的狀態(tài)用vxi表示,其中第一個下標(biāo)表示城市名,第二個下標(biāo)i∈{1,2,…,n}表示途經(jīng)的順序。vxi=1表示城市x在路徑中是第i個被訪問的；vxi=0表示城市x在路徑中是第i個位置上沒有被訪問的。這樣就可用一個n×n關(guān)聯(lián)矩陣來描述n個城市的TSP問題。一條有效路徑對應(yīng)的關(guān)聯(lián)矩陣是每行有且只有一個元素為1,其余的均為0,這表明每個城市均被訪問,且只被訪問一次；在每一列中只有一個元素為1,其余均為0,這表明每次只訪問一個城市。表9-2為5個城市的一條有效路徑的關(guān)聯(lián)矩陣,由關(guān)聯(lián)矩陣可以得到,訪問城市的順序?yàn)镃3C1C5C2C4C3,相應(yīng)的路徑總長度d=d31+d15+d52+d24+d43。表9-2

5城市TSP問題一條有效路徑的關(guān)聯(lián)矩陣

(2)根據(jù)TSP優(yōu)化問題,構(gòu)造網(wǎng)絡(luò)的能量函數(shù)。TSP問題是一最優(yōu)路徑問題,其最優(yōu)性條件為路徑最短。于是,可取目標(biāo)函數(shù)(9-64)式中dxy表示x、y兩個不同城市之間的距離。若vxi=0,則表明該神經(jīng)元對J(v)無影響；若vxi=1,表示城市x在路徑中是在第i個位置上被訪問的,那么尋找與i相鄰順序的被訪問城市,并將這些城市間的距離加起來。以表9-2為例,取,于是可找到與其相鄰的城市為C3和C5,即,

相應(yīng)地將城市C3和C5與城市C1的距離和

相加。因此,式(9-64)表示將商人走過的路程累加起來,但式中每個距離都計(jì)算兩次,故系數(shù)“1/2”是為消去重復(fù)計(jì)算而設(shè)置的。為了確保路徑的有效性,使網(wǎng)絡(luò)的輸出矩陣為一關(guān)聯(lián)矩陣,取優(yōu)化問題的約束條件為

式中等號右邊的第一項(xiàng)為列約束條件,保證每次只訪問一個城市,滿足此條件時,該項(xiàng)的值為零；第二項(xiàng)為行約束條件,保證每個城市只能訪問一次；第三項(xiàng)為全局約束條件,確保vxi=1的總數(shù)為n。因此,當(dāng)路徑有效時,g(v)=0。(9-63)構(gòu)造網(wǎng)絡(luò)的能量函數(shù)為(9-66)

(3)確定網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù),則網(wǎng)絡(luò)的穩(wěn)態(tài)輸出就對應(yīng)TSP問題的最優(yōu)解。將式(9-66)與Hopfield能量函數(shù)的規(guī)范表達(dá)式

相比較,并考慮到系數(shù)B只影響同一列各神經(jīng)元之間的連接電導(dǎo)值,C只影響同一行各神經(jīng)元之間的連接電導(dǎo)值,D與全部的連接電導(dǎo)值都有關(guān),而A只涉及路徑順序的相鄰項(xiàng)。于是可得網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)為其中根據(jù)參數(shù)值構(gòu)造網(wǎng)絡(luò)并讓其運(yùn)行,則網(wǎng)絡(luò)穩(wěn)定時能量函數(shù)E達(dá)到極小值。這時網(wǎng)絡(luò)的穩(wěn)態(tài)輸出就對應(yīng)TSP問題的最優(yōu)解。若采用計(jì)算機(jī)仿真的方法來實(shí)現(xiàn),考慮到神經(jīng)元的功能函數(shù)不一定有硬限幅特性,需在E函數(shù)表達(dá)式中增加f-1(vi)函數(shù)的積分項(xiàng)。于是可導(dǎo)出網(wǎng)絡(luò)的數(shù)學(xué)模型為這是n×n個神經(jīng)元動態(tài)方程的一般表達(dá)式。聯(lián)立求解這組n×n個非線性一階微分方程組,則可得到TSP問題的最優(yōu)解。

必須指出,起始狀態(tài)選擇的不同,所得結(jié)果可能會不一樣。這說明用神經(jīng)網(wǎng)絡(luò)解決優(yōu)化計(jì)算問題,所得答案并不能保證是最優(yōu)的,但它們是相當(dāng)接近最優(yōu)的滿意解。9.3

Hopfield網(wǎng)絡(luò)的MATLAB開發(fā)

MATLAB為設(shè)計(jì)Hopfield網(wǎng)絡(luò)提供了強(qiáng)有力的工具函數(shù),本節(jié)將對這些函數(shù)的功能、調(diào)用格式以及使用方法進(jìn)行詳細(xì)的介紹。

1.網(wǎng)絡(luò)函數(shù)(newhop)

功能：設(shè)計(jì)一個Hopfield神經(jīng)網(wǎng)絡(luò)。

指令格式：net=newhop(T)

參數(shù)意義：T為目標(biāo)向量(元素的值為1或-1)。

Hopfield神經(jīng)網(wǎng)絡(luò)經(jīng)常被用于模式的聯(lián)想記憶。Hopfield神經(jīng)網(wǎng)絡(luò)僅有一層,其輸入用netsum函數(shù),權(quán)函數(shù)用dotprod函數(shù),傳遞函數(shù)用satlins函數(shù)。層中的神經(jīng)元有來自它自身的連接權(quán)和閾值。

【例9-4】設(shè)計(jì)一個Hopfield神經(jīng)網(wǎng)絡(luò),具有兩個三維的穩(wěn)定點(diǎn)(本例M文件見光盤中的FLch9eg1)。

創(chuàng)建該網(wǎng)絡(luò)：

net=newhop(T)

下面檢驗(yàn)該網(wǎng)絡(luò)是否穩(wěn)定在這兩個點(diǎn)上。由于Hopfield神經(jīng)網(wǎng)絡(luò)沒有輸入項(xiàng),所以sim()函數(shù)的第二個參數(shù)等于2。程序如下：

Ai=T；

[Y,Pf,Af]=sim(net,2,{},Ai)；

Y

%打印神經(jīng)網(wǎng)絡(luò)輸出Y

程序運(yùn)行結(jié)果如下：再通過其它的初始條件Ai來檢驗(yàn)該網(wǎng)絡(luò)的性能。程序如下：

Ai={[-0.9;-0.8;0.7]}；

[Y,Pf,Af]=sim(net,{15},{},Ai)；

Y{1}

%打印網(wǎng)絡(luò)輸出

程序運(yùn)行結(jié)果如下：

ans=[JB(]-1-1

1[JB)]

從以上仿真結(jié)果可以看出,Ai與設(shè)計(jì)的第一個初始條件比較接近,所以它使網(wǎng)絡(luò)收斂到第一個穩(wěn)定點(diǎn)。2.傳遞函數(shù)(satlins)

功能：對稱飽和線性傳遞函數(shù)。

指令格式：A=satlins(N)

inf=satlins(code)

參數(shù)意義：N為輸入向量。

對稱飽和線性傳遞函數(shù)從網(wǎng)絡(luò)的輸入計(jì)算一層的輸出。Satlins函數(shù)的算法為：

(1)當(dāng)N<-1時,satlins(N)＝-1；

(2)當(dāng)-1≤N≤1時,satlins(N)＝N；

(3)當(dāng)N>1時,satlins(N)＝1。

satlins(code)返回如下信息：

(1)deriv,返回導(dǎo)數(shù)函數(shù)名稱；

(2)name,