第10章 隨機神經(jīng)網(wǎng)絡(luò)及模擬退火算法

第10章非確定方法確定的方法前幾章所給方法的共同特征非確定的方法生物神經(jīng)網(wǎng)絡(luò)按照概率運行別稱統(tǒng)計方法（StatisticalMethod）。既可以用于訓(xùn)練，又可以用于運行

1機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc基本的非確定訓(xùn)練算法

基本思想從所給的網(wǎng)絡(luò)中“隨機地選取一個聯(lián)接權(quán)”，對該聯(lián)接權(quán)提出一個“偽隨機調(diào)整量”，當用此調(diào)整量對所選的聯(lián)接權(quán)進行修改后，如果“被認為”修改改進了網(wǎng)絡(luò)的性能，則保留此調(diào)整；否則放棄本次調(diào)整。

2機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc基本的非確定訓(xùn)練算法基本數(shù)據(jù)結(jié)構(gòu)樣本集：S={(X1,Y1),(X2,Y2),…,(Xs,Ys)}輸入向量：X=(x1，x2，…，xn)理想輸出向量：Y=(y1，y2，…，ym)L層：W(1)

，W(2)

，…，W(L)

3機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc基本的非確定訓(xùn)練算法拓撲結(jié)構(gòu)

x1o1輸出層隱藏層輸入層x2o2omxn…………………W(1)

W(L)W(2)4機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc算法10-1基本統(tǒng)計訓(xùn)練算法

1從樣本集S中取一樣本（X,Y）；2將X輸入到網(wǎng)絡(luò)中，計算出實際輸出O；3求出網(wǎng)絡(luò)關(guān)于Y，O的誤差測度E；4隨機地從W(1)

，W(2)

，…，W(L)中選擇一個聯(lián)接權(quán)wij(p)；5生成一個小隨機數(shù)Δwij(p)；6用Δwij(p)修改wij(p)；5機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc算法10-1基本統(tǒng)計訓(xùn)練算法7用修改后的W(1)

，W(2)

，…，W(L)重新計算X對應(yīng)的實際輸出O′；8求出網(wǎng)絡(luò)關(guān)于Y，O′的誤差測度E′；9如果E′<E，則保留本次對W(1)

，W(2)

，…，W(L)的修改，否則，根據(jù)概率判斷本次修改是否有用，如果認為有用，則保留本次對W(1)

，W(2)

，…，W(L)的修改，如果認為本次修改無用，則放棄它；10重復(fù)上述過程，直到網(wǎng)絡(luò)滿足要求。6機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc算法10-1基本統(tǒng)計訓(xùn)練算法目標函數(shù)（ObjectiveFunction）誤差測度函數(shù)：實際輸出與理想輸出方差和

計算量從W(1)

，W(2)

，…，W(L)中隨機地選擇wij

共有n×H1+H1×H2+H2×H3+…+HM-1×m個“變量”可供選擇偽隨機數(shù)偽隨機數(shù)發(fā)生器來產(chǎn)生Δwij(p)；按照所謂的“能量”函數(shù)的分布去計算它7機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc算法10-1基本統(tǒng)計訓(xùn)練算法局部極小點當E′<E不成立時，考慮使網(wǎng)絡(luò)從局部極小點中逃離出來，必須允許目標函數(shù)暫時變壞

循環(huán)控制判斷標準用一個樣本對網(wǎng)絡(luò)的某一個聯(lián)接權(quán)進行修改后，是隨機地抽取另一個聯(lián)接權(quán)進行重復(fù)，還是再選擇下一個樣本進行重復(fù)對一個選定的樣本，每次是否可以選取若干個聯(lián)接權(quán)進行修改？如果可以，還應(yīng)做什么工作？

8機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc逃離局部極小點

聯(lián)接權(quán)修改量

太?。郝涞紸點后很難逃離

太大：導(dǎo)致在A、B兩點來回抖動

解決辦法

控制聯(lián)接權(quán)修改量的大小：權(quán)修改量由大變小

允許暫時變壞

修改量的大小和網(wǎng)絡(luò)的“能量”相關(guān)

模擬退火

ABD9機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc逃離局部極小點DBA10機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc模擬退火算法

金屬中原子的能量與溫度有關(guān)原子能量高的時候，有能力擺脫其原來的能量狀態(tài)而最后達到一個更加穩(wěn)定的狀態(tài)——全局極小能量狀態(tài)在金屬的退火過程中，能量的狀態(tài)分布P(E)——系統(tǒng)處于具有能量E的狀態(tài)的概率；k——Boltzmann常數(shù)；T——系統(tǒng)的絕對溫度(Kelvin)P(E)∝11機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc步長和能量、溫度的關(guān)系

降溫過程高溫低溫原子運動平穩(wěn)原子激烈隨機運動能量與溫度相關(guān)步長與能量和溫度相關(guān)步長與能量相關(guān)大步長小步長可逃離難逃離金屬熱加工大小高低高能量低能量目標函數(shù)的值網(wǎng)絡(luò)的能量訓(xùn)練12機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc能量與溫度高溫情況下：T足夠大，對系統(tǒng)所能處的任意能量狀態(tài)E，有

將趨近于113機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc能量與溫度中溫情況下：T比較小，E的大小對P(E)有較大的影響，設(shè)E1>E2

P(E2)>P(E1)。即，系統(tǒng)處于高能量狀態(tài)的可能性小于處于低能量狀態(tài)的可能性14機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc能量與溫度15機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc能量與溫度低溫情況下：T非常小，E的大小對P(E)的影響非常大，設(shè)E1>E2

P(E2)>>P(E1)。即，當溫度趨近于0時，系統(tǒng)幾乎不可能處于高能量狀態(tài)16機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc

模擬退火算法（SimulatedAnnealing)來源于固體退火原理，將固體加溫至充高，再讓其徐徐冷卻，加溫時，固體內(nèi)部粒子隨溫度升高變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。它由Metropolis算法和退火過程（AnnealingProcedure，AP）組成。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc17

模擬退火算法的基本思路：首先在高溫下進行搜索，此時各狀態(tài)出現(xiàn)概率相差不大，可以很快進入“熱平衡狀態(tài)”，這時進行的是一種“粗搜索”，也就是大致找到系統(tǒng)的低能區(qū)域；隨著溫度的逐漸降低，各狀態(tài)出現(xiàn)概率的差距逐漸被擴大，搜索精度不斷提高。這就可以越來越準確的找到網(wǎng)絡(luò)能量函數(shù)的全局最小點。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc18模擬退火的最初目的是尋找代表復(fù)雜系統(tǒng)的代價函數(shù)的全局最小值。因此，這種方法為解決凹平面最優(yōu)問題提供了一個強有力的工具，其中心思想在于：在用模擬退火最優(yōu)化一個復(fù)雜系統(tǒng)（如：一個擁有很多自由度的系統(tǒng)）時，誤差或能量函數(shù)絕大部分的時間在下降，但不是一直下降，即誤差或能量函數(shù)的總趨勢向減小的方向變化，但有時也向增大的方向變化，這樣可跳出局部極小點，向全局最小點收斂。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc19模擬退火與傳統(tǒng)迭代最優(yōu)算法的比較：（1）當系統(tǒng)在非零溫度下時，從局部最優(yōu)中跳出是非?？赡艿模虼瞬粫萑刖植孔顑?yōu)。（2）系統(tǒng)最終狀態(tài)的總特征可以在較高溫度下看到，而狀態(tài)的好的細節(jié)卻在低溫下表現(xiàn)，因此，模擬退火是自適應(yīng)的.。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc20模擬退火原理

1. Metropolis抽樣過程假定一隨機變量在某一時刻的狀態(tài)為vi。在另一時刻的狀態(tài)為vj。假設(shè)這種狀態(tài)的轉(zhuǎn)移滿足以下條件：ΔE表示系統(tǒng)從狀態(tài)vi轉(zhuǎn)移至狀態(tài)vj所引起的能量差。如果能量差ΔE為負，這種轉(zhuǎn)移就導(dǎo)致狀態(tài)能量的降低，這種轉(zhuǎn)移就被接受。接下來，新狀態(tài)作為算法下一步的起始點。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc21若能量差為正，算法在這一點進行概率操作。首先，選定一個在[0,1]內(nèi)服從均勻分布的隨機數(shù)ξ。如果ξ<e-ΔE/T，則接受這種轉(zhuǎn)移。否則，拒絕這種轉(zhuǎn)移；即在算法的下一步中拒絕舊的狀態(tài)。如此反復(fù)，達到系統(tǒng)在此溫度下的熱平衡。這個過程稱作Metropolis抽樣過程。Metropolis抽樣過程就是在一確定溫度下，使系統(tǒng)達到熱平衡的過程。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc222. 退火過程（降溫過程）在Metropolis抽樣過程中溫度T緩慢的降低。模擬退火過程就是通過T參數(shù)的變化使狀態(tài)收斂于最小能量處。因而，T參數(shù)的選擇對于算法最后的結(jié)果有很大影響。初始溫度和終止溫度設(shè)置的過低或過高都會延長搜索時間。降溫步驟太快，往往會漏掉全局最優(yōu)點，使算法收斂至局部最優(yōu)點。降溫步驟太慢，則會大大延長搜索全局最優(yōu)點的計算時間，從而難以實際應(yīng)用。因此，T可以理解為一個控制參數(shù)。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc23

為尋找在有限時間逼近全局最優(yōu)的模擬退火算法，設(shè)置了許多控制算法收斂的參數(shù)。在退火過程中指定了有限的退火溫度值和在每一溫度下的轉(zhuǎn)移數(shù)目。Kirlpatrick等人在退火步驟中設(shè)定的參數(shù)如下：（1）初始溫度值：初始溫度值T0要選的足夠高，保證模擬退火算法中所有可能的轉(zhuǎn)移都能被接受。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc24（2）溫度的下降：原先使用指數(shù)函數(shù)實現(xiàn)溫度的下降。但是這種方法使降溫幅度過小，從而延長搜索時間。在實際中，通常使用下式：此處λ是一小于卻接近于1的常數(shù)。λ通常的取值在0.8至0.99之間。在每一溫度下，實驗足夠多的轉(zhuǎn)移次數(shù)。

機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc25（3）終止溫度：如果在連續(xù)的若干個溫度下沒有可接受的新狀態(tài)，系統(tǒng)凍結(jié)或退火停止。模擬退火尤其適合解決組合優(yōu)化問題，下面以模擬退火算法解決組合優(yōu)化問題來進一步介紹模擬退火算法的步驟。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc26模擬退火算法用于組合優(yōu)化問題

許多工程上和理論上的問題，其目標都是在一個很大的解空間中尋求一個最優(yōu)解，這些問題統(tǒng)稱為組合優(yōu)化問題。在許多組合優(yōu)化問題中，一個解通常是滿足一定規(guī)則的一些離散對象的排列，所有這些解的集合叫做解空間。通常用一個“代價函數(shù)”C(x)來衡量一個解的優(yōu)劣，目標就是選擇一個解使其代價函數(shù)C(x)最小，如TSP問題、大規(guī)模集成電路布局布線問題等。

機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc27模擬退火與組合優(yōu)化問題的對應(yīng)關(guān)系機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc

模擬退火算法

組合優(yōu)化問題樣本問題舉例狀態(tài)解能量代價函數(shù)溫度控制參數(shù)熱平衡時的能量最小代價熱平衡狀態(tài)最優(yōu)解28設(shè)V={V1,V2,…,Vn}為所有可能的組合（或狀態(tài)）所構(gòu)成的集合。C(﹒)是V的函數(shù)，且，反映取狀態(tài)Vi為解的代價，目標是尋找使模擬退火算法應(yīng)用于組合優(yōu)化問題的基本思想就是把每種組合狀態(tài)Vi看成某一物質(zhì)體系的微觀狀態(tài)，C(Vi)可看成該物質(zhì)體系在Vi下的能量，溫度T為控制參數(shù)。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc29讓T從一個足夠高的值慢慢下降，對于每個T，對當前狀態(tài)V作隨機擾動產(chǎn)生一個新狀態(tài)V’，計算其增量ΔC=C(V)-C(V’’)，并以概率e-ΔC/kT接受V’作為新的當前狀態(tài)。根據(jù)統(tǒng)計力學(xué)的知識，當重復(fù)如此隨機擾動足夠次數(shù)后，狀態(tài)Vi的出現(xiàn)概率如下：

服從Boltzmann分布。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc30模擬退火用于組合優(yōu)化問題算法實現(xiàn)步驟：第一步：初始化。依據(jù)所要解決的組合優(yōu)化問題，確定代價函數(shù)C(﹒)的表達式，隨機選擇初始狀態(tài)V=V(0)，設(shè)定初始溫度T0，終止溫度Tfinal，概率閾值ξ。第二步：Metropolis抽樣過程（1）在溫度T下依據(jù)某一規(guī)定的方式，根據(jù)當前解所處的狀態(tài)V，產(chǎn)生一個近鄰子集N(V)（可包括V，也可不包括V），在N(V)內(nèi)隨機尋找一個新狀態(tài)S’作為下一個當前解的候選解，計算ΔC’=C(V’’)-C(V)。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc31（2）若ΔC’<0,則V=V’，作為下一狀態(tài)；若ΔC’>0，則計算概率e-ΔC`/T，若其大于給定概率閾值ξ，則取下一狀態(tài)為V=V’，否則，保留這一狀態(tài)。（3）按某一給定的收斂算法檢查算法在溫度T下是否應(yīng)停止，若符合收斂條件則表示已達到熱平衡，轉(zhuǎn)向第三步的退火過程，若不符合收斂條件，則轉(zhuǎn)向（1）繼續(xù)迭代，直至在此溫度下收斂。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc32

第三步：退火過程。

按照一定的降溫方法得到一個新的溫度T，檢查T是否小于給定的溫度終止閾值Tfinal。若小于，則退火過程結(jié)束，當前狀態(tài)V即為算法最終輸出解。若溫度T大于等于給定閾值，則轉(zhuǎn)至Metropolis抽樣過程，在新的溫度下搜索狀態(tài)。注意：在上述退火過程中，模擬退火算法是否能達到能量E的最小值，取決于T0是否足夠高，和T下降得是否充分慢，以及對每個T時系統(tǒng)是否穩(wěn)定。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc33模擬退火算法的參數(shù)控制問題（1）T0的選擇方法：

a.均勻隨機抽樣{Vi}，取此時C(Vi)的方差為T0b.在所有可能的組合狀態(tài)中，選兩個狀態(tài)使ΔC’

最大，取T0為ΔC’的若干倍；

c.按經(jīng)驗給出。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc34(2)退火過程中Tfinal

的選取方法：

a依據(jù)經(jīng)驗確定

b檢驗系統(tǒng)的熵是已否達到最小，若達到最小， 即可認為溫度已達到終止溫度。

cT下降n次后都沒有改善，即可認為能量已降 到最低，沒有必要再降溫。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc35（3）Metropolis抽樣過程的收斂算法：

a.檢驗?zāi)繕撕瘮?shù)C(﹒)的均值是否穩(wěn)定；

b.繼續(xù)若干步，C(﹒)變化很?。ㄔO(shè)定閾值）；c.按一個固定步數(shù)抽樣。（4）降溫方法的確定：根據(jù)Kirlpatrick的方法令，機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc36模擬退火算法是一種通用的隨機搜索算法，它可用于解決眾多的優(yōu)化問題，并已經(jīng)廣泛的應(yīng)用于其他領(lǐng)域。如VLSL設(shè)計、圖像識別等。當待解決的問題復(fù)雜性較高，而且規(guī)模較大時，在對問題的領(lǐng)域知識甚少的情況下，采用模擬退火算法最合適。因為模擬退火算法不像其他確定型啟發(fā)式算法那樣，需要依賴于問題的領(lǐng)域知識來提高算法的性能。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc37但是，從另一方面來說，已知有關(guān)待解決問題的一些知識后，模擬退火算法卻無法充分利用它們，這使得模擬退火算法的優(yōu)點就成了缺點。如何把傳統(tǒng)的啟發(fā)式搜索方法和模擬退火隨機搜索算法結(jié)合起來，這是一個有待研究的十分有意義的課題。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc38模擬退火算法具有跳出局部最優(yōu)陷阱的能力，因此被Ackley、Hinton和Sejnowski用作Boltzmann機學(xué)習(xí)算法，從而使Boltzmann機克服了Hopfield網(wǎng)絡(luò)經(jīng)常收斂到局部最優(yōu)點的缺點。在Boltmann機中，即使系統(tǒng)落入局部最優(yōu)的陷阱，經(jīng)過一段時間后，它還能重新跳出來，使系統(tǒng)最終將往全局最優(yōu)點的方向收斂。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc39模擬退火算法在求解規(guī)模較大的實際問題時，往往存在以下缺點：（1）收斂速度比較慢。（2）盡管理論上只要計算時間足夠長，模擬退火法就可以保證以概率1收斂于全局最優(yōu)點。但是在實際算法的實現(xiàn)過程中，由于計算速度和時間的限制，在優(yōu)化效果和計算時間二者之間存在矛盾，因而難以保證計算結(jié)果為全局最優(yōu)點，優(yōu)化效果不甚理想。

(3)在每一溫度下很難判定是否達到了平衡狀態(tài)。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc40為此，人們對模擬退火算法提出了各種各樣的改進，其中包括并行模擬退火算法、快速模擬退火算法（Cauchy機）和對模擬退火算法中各個函數(shù)和參數(shù)的重新設(shè)計等。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc41模擬退火組合優(yōu)化法

目標函數(shù)——能量函數(shù)人工溫度T——一個初值較大的數(shù)依據(jù)網(wǎng)絡(luò)的能量和溫度來決定聯(lián)接權(quán)的調(diào)整量（稱為步長）。與金屬的退火過程（Annealing）非常相似42機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc模擬退火組合優(yōu)化法基本思想隨機地為系統(tǒng)選擇一個初始狀態(tài){wij(p)}，在此初始狀態(tài)下，給系統(tǒng)一個小的隨機擾動Δwij(p)，計算系統(tǒng)的能量變化ΔE=E({wij(p)+Δwij(p)})-E({wij(p)})

若ΔE<0則接受若ΔE≥0則依據(jù)概率判斷是否被接受若接受，則系統(tǒng)從狀態(tài){wij(p)}變換到狀態(tài){wij(p)+Δwij(p)}；否則，系統(tǒng)保持不變

43機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc模擬退火組合優(yōu)化法在這個過程中，逐漸地降低溫度T。所得的系統(tǒng)狀態(tài)序列{wij(p)}將滿足下列分布

44機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc算法10-2模擬退火算法

1初始化各層的聯(lián)接權(quán)矩陣W；定義人工溫度T的初值；2

對每一個溫度T重復(fù)如下過程：

2.1

取一樣本，計算其輸出與目標函數(shù)E({wij(p)})；

2.2

隨機地從{wij(p)}中選取一個wij(p)；

2.3

按一定的算法產(chǎn)生wij(p)

的一個調(diào)整量Δwij(p)

；

2.4

按照{(diào)wij(p)+Δwij(p)}重新計算相應(yīng)輸出和目標函數(shù)E({wij(p)+Δwij(p)})；

2.5

ΔE=E({wij(p)+Δwij(p)})-E({wij(p)})；45機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc算法10-2模擬退火算法

2.6

ifΔE>0then 2.6.1按均勻分布在[0,1]區(qū)間取一隨機數(shù)r；

2.6.2按Boltzmann分布計算接受本次調(diào)整的概率：

P(E({wij(p)+Δwij(p)}))= 2.6.3ifP(E({wij(p)+Δwij(p)}))<rthen轉(zhuǎn)2.2；46機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc算法10-2模擬退火算法

2.7用{wij(p)+Δwij(p)}代替{wij(p)}；

2.8if樣本集中還有未被選用的樣本then轉(zhuǎn)2.1；3判斷在此溫度下，檢驗Metropolis抽樣是否穩(wěn)定。如不穩(wěn)定，則直接轉(zhuǎn)2；4降低溫度T；5如果T足夠小，則結(jié)束，否則，轉(zhuǎn)2。

47機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc算法10-2模擬退火算法算法的第2步原則上應(yīng)該對每一個樣本調(diào)整每一個權(quán)，調(diào)整的順序是隨機的；溫度T的降低T=λT

λ叫做冷卻率，一般情況下可以在[0.8，0.9]之間取值

Geman(1984年)：溫度下降必須與時間的對數(shù)成反比，網(wǎng)絡(luò)最終才能收斂到全局極小點

48機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc算法10-2模擬退火算法T的初值T0

T0=

E({w(h)})；即：取初始系統(tǒng)目標函數(shù)（能量）的值

T0=z

E({w(h)})。即：取初始系統(tǒng)目標函數(shù)（能量）值的若干倍

按照經(jīng)驗給出

49機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc算法10-2模擬退火算法調(diào)整量Δwij(p)的計算

可以根據(jù)Boltzmann分布或者Gaussian分布來計算。也可以用其它的方法。下面討論按Gaussian分布進行計算的方法。我們?nèi)∪缦滦问降腉aussian分布函數(shù)。簡潔起見，用符號w代替符號wij(p)：

p(Δw)=

50機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rincMonteCarlo法

數(shù)值積分法

根據(jù)網(wǎng)絡(luò)的精度要求，設(shè)一個積分步長δ，然后通過數(shù)值積分構(gòu)造出如下形式的表格

機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc51Δwδ2δ3δ4δ…NδC1C2C3C4…CNMonteCarlo法首先按照均勻分布在[C1，CN]中隨機地取一個值C，然后，從

{C1，C2，C3，…，CN}中選取Ck滿足：|Ck-C|=min{|C-C1|,|C-C2|,|C-C3|,…,|C-CN|}Ck對應(yīng)的kδ就是所需要的聯(lián)接權(quán)調(diào)整量Δw

機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc52Cauchy訓(xùn)練

Boltzmann分布Boltzmann訓(xùn)練

1987年，S.Szu和R.Hartley提出用Cauchy分布去取代Gaussian分布機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc53Cauchy分布p(x)=Cauchy訓(xùn)練——優(yōu)點對于[C1，CN]中的任意一個C，它按照Cauchy分布所能取到的聯(lián)接權(quán)的調(diào)整量要大于按照Boltzmann分布所能取到的聯(lián)接權(quán)的調(diào)整量

用Cauchy分布取代Boltzmann分布后，溫度可以下降得更快。這時，溫度的下降變得與時間成反比：T0/(1+t)Cauchy分布函數(shù)可以用常規(guī)的方法進行積分運算

機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc54Cauchy分布函數(shù)積分運算機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc55Cauchy分布函數(shù)積分運算MonteCarlo法：在(0,1)中按照均勻分布隨機取一數(shù)為P(Δw)，再取當前的溫度，就可以直接地計算出Δw

Cauchy訓(xùn)練算法：將算法10-2中的Boltzmann分布換成Cauchy分布

機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc56Δw=αTtg(P(Δw))人工熱問題

特殊熱——溫度關(guān)于能量的變化率系統(tǒng)在能量躍變邊界處的溫度叫做臨界溫度人工特殊熱/“偽特殊熱”

系統(tǒng)的人工溫度關(guān)于系統(tǒng)的能量函數(shù)（目標函數(shù)）的平均變化率

臨界溫度臨界溫度時的小量下降，會引起能量函數(shù)值的較大變化

系統(tǒng)正處于一個局部極小點附近

臨界溫度點可以通過考察所定義的人工特殊熱的變化情況得到

機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc57BP算法與Cauchy訓(xùn)練的結(jié)合

Cauchy訓(xùn)練的速度比Boltzmann訓(xùn)練快

Cauchy訓(xùn)練的速度比BP算法慢Cauchy訓(xùn)練有可能使網(wǎng)絡(luò)逃離局部極小點由BP算法提供直接計算部分，Cauchy算法提供隨機部分wij=wij+?wij?wij=α((1-β)δjoi+β?wij′)+(1-α)?wij(c)α∈(0,1)為學(xué)習(xí)率,β∈(0,1)為沖量系數(shù)

機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc58

隨機神經(jīng)網(wǎng)絡(luò)是統(tǒng)計力學(xué)思想引入神經(jīng)網(wǎng)絡(luò)研究的結(jié)果。統(tǒng)計力學(xué)是研究大系統(tǒng)宏觀平衡性質(zhì)的學(xué)科，這種大系統(tǒng)的組成元素服從微觀機制。統(tǒng)計力學(xué)的主要目的是尋找從微觀粒子（原子、電子）的運動開始的宏觀物體的熱力學(xué)性質(zhì)，由于所遇到的自由度數(shù)目很大，因此只能使用概率的方法進行研究。59機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc

隨機神經(jīng)網(wǎng)絡(luò)與其他網(wǎng)絡(luò)的比較

名稱

網(wǎng)絡(luò)類型

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

學(xué)習(xí)算法BP網(wǎng)絡(luò)多層前向網(wǎng)絡(luò)含輸入層、隱層、輸出層。層內(nèi)神經(jīng)元無連接網(wǎng)絡(luò)按誤差減少的最大梯度方向調(diào)整權(quán)值Hopfield

網(wǎng)絡(luò)反饋神經(jīng)網(wǎng)絡(luò)單層神經(jīng)網(wǎng)絡(luò)，層內(nèi)神經(jīng)元全互連網(wǎng)絡(luò)按照其用途來設(shè)計或訓(xùn)練網(wǎng)絡(luò)權(quán)值Boltzmann機隨機神經(jīng)網(wǎng)絡(luò)含輸入部、輸出部和中間部。神經(jīng)元互連網(wǎng)絡(luò)向誤差減小的方向運行概率大，但也可能向誤差增大方向運行BP網(wǎng)絡(luò)是一種“貪心”算法，容易陷入局部最小點。Hopfield網(wǎng)絡(luò)很難避免出現(xiàn)偽狀態(tài)，網(wǎng)絡(luò)是嚴格按照能量減小的方向運行的，容易陷入局部極小點，而無法跳出。所以，在用BP網(wǎng)絡(luò)和Hopfield網(wǎng)絡(luò)進行最優(yōu)化的計算時，由于限定條件的不足，往往會使網(wǎng)絡(luò)穩(wěn)定在誤差或能量函數(shù)的局部最小點，而不是全局最小點，即所得的解不是最優(yōu)解。61機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc網(wǎng)絡(luò)陷入局部最小點的原因主要有兩點：（1）網(wǎng)絡(luò)結(jié)構(gòu)上存在著輸入到輸出之間的非線性函數(shù)關(guān)系，從而使網(wǎng)絡(luò)誤差或能量函數(shù)所構(gòu)成的空間是一個含有多極點的非線性空間。（2）在算法上，網(wǎng)絡(luò)的誤差或能量函數(shù)只能單方向減小，不能有一點上升。62機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc隨機神經(jīng)網(wǎng)絡(luò)的基本思想：網(wǎng)絡(luò)向誤差或能量函數(shù)減小方向運行的概率大，同時向誤差或能量函數(shù)增大方向運行的概率存在，這樣網(wǎng)絡(luò)跳出局部極小點的可能性存在，而且向全局最小點收斂的概率最大。63機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc

20世紀80年代，Ackley,Hinton和Sejnowski等人以模擬退火思想為基礎(chǔ)，對Hopfield網(wǎng)絡(luò)引入了隨機機制，推出Boltzmann機。

Boltzmann機是第一個受統(tǒng)計力學(xué)啟發(fā)的多層學(xué)習(xí)機，它是典型的隨機神經(jīng)網(wǎng)絡(luò)。其命名來源于Boltzmann機在統(tǒng)計力學(xué)中的早期工作和網(wǎng)絡(luò)本身的動態(tài)分布行為（其平衡狀態(tài)服從Boltzmann分布），其運行機制服從模擬退火算法。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc6410.1Boltzmann機10.1.1Boltzmann機的網(wǎng)絡(luò)結(jié)構(gòu)10.1.2Boltzmann機的工作原理10.1.3Boltzmann機的運行步驟10.1.4Boltzmann機的學(xué)習(xí)規(guī)則機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc6510.1.1Boatman機的網(wǎng)絡(luò)結(jié)構(gòu)機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc圖10-1boltzmann機的網(wǎng)絡(luò)結(jié)構(gòu)

Boltzmann機由輸入部、輸出部和中間部構(gòu)成。輸入神經(jīng)元和輸出神經(jīng)元可稱為顯見神經(jīng)元，它們是網(wǎng)絡(luò)與外部環(huán)境進行信息交換的媒介。中間部的神經(jīng)元稱為隱見神經(jīng)元，它們通過顯見神經(jīng)元與外部進行信息交換。每一對神經(jīng)元之間的信息傳遞是雙向?qū)ΨQ的，即wij=wji

，而且自身無反饋即wii=0。學(xué)習(xí)期間，顯見神經(jīng)元將被外部環(huán)境“約束”在某一特定的狀態(tài)，而中間部隱見神經(jīng)元則不受外部環(huán)境約束。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc67機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc68Boltzmann機中單個

神經(jīng)元的運行特性機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc

式中bi是該神經(jīng)元的閾值?？梢詫i歸并到總的加權(quán)和中去，即得：69

Boltzmann機中每個神經(jīng)元的興奮或抑制具有隨機性，其概率取決于神經(jīng)元的輸入。神經(jīng)元i的全部輸入信號的總和為ui為：

神經(jīng)元的輸出vi依概率取1或0：

vi取1的概率：

vi取0的概率：

機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc

由此可見，vi取1的概率受兩個因素的影響：（1）

ui越大vi則取1的概率越大，而取0的概 率越小。（2）參數(shù)T稱為“溫度”，在不同的溫度下vi 取1的概率P隨ui的變化如圖所示。70機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc

p~u的關(guān)系71可見，T越高時，曲線越平滑，因此，即使ui有很大變動，也不會對vi取1的概率變化造成很大的影響；反之，T越低時，曲線越陡峭，當ui有稍許變動時就會使概率有很大差異。即溫度高時狀態(tài)變化接近隨機，隨著溫度的降低向確定性的動作靠近。當T→0時，每個神經(jīng)元不再具有隨機特性，而具有確定的特性，激勵函數(shù)變?yōu)殡A躍函數(shù)，這時Boltzmann機趨向于Hopfield網(wǎng)絡(luò)。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc7210.1.1Boltzmann機的工作原理

Boltzmann機采用下式所示的能量函數(shù)作為描述其狀態(tài)的函數(shù)。

將Boltzmann機視為一動力系統(tǒng)，能量函數(shù)的極小值對應(yīng)系統(tǒng)的穩(wěn)定平衡點，由于能量函數(shù)有界，當網(wǎng)絡(luò)溫度以某種方式逐漸下降到某一特定值時，系統(tǒng)必趨于穩(wěn)定狀態(tài)Boltzmann機的運行過程就是逐步降低其能量函數(shù)的過程。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc73Boltzmann機在運行時，假設(shè)每次只改變一個神經(jīng)元的狀態(tài)，如第i個神經(jīng)元，設(shè)vi取0和取1時系統(tǒng)的能量函數(shù)分別為0和，它們的差值為ΔEi

ΔEi的取值可能有兩種情況:ΔEi>0或ΔEi<0。

機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc74（1）當

ΔEi>0即>0時，

神經(jīng)元取1的概率：神經(jīng)元取0的概率：機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc當＝ΔEi>0時，這時神經(jīng)元i的狀態(tài)取1的可能性比取0的可能性大，即網(wǎng)絡(luò)狀態(tài)取能量低的可能性大。75（2）同理當ΔEi<0時，即那么此時即神經(jīng)元i的狀態(tài)取0的可能性比取1的可能 性大。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc網(wǎng)絡(luò)狀態(tài)取能量低的可能性大。運行過程中總的趨勢是朝能量下降的方向運動，但也存在能量上升的可能性。76

有一個凹凸不平的盆，要使一個小球穩(wěn)定在最低的地方，如果把小球輕輕地放入盆中，那么結(jié)果必然是小球穩(wěn)定在距放入地方最近的低洼處。但是穩(wěn)定所在的地方并不保證是最低的地方，這一動作與Hopfield網(wǎng)絡(luò)相當。Boltzmann機則是大幅度搖晃剛放入小球的盆子，然后逐漸減小搖晃的幅度。這樣，小球才有可能到盆子的最低處B處。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc舉例說明Boltzmann機的學(xué)習(xí)算法假定Boltzmann機中有V1和V2兩種狀態(tài)：在V1狀態(tài)下神經(jīng)元i的輸出vi=1，V2狀態(tài)下神經(jīng)元i的輸出vi=0，而所有其他神經(jīng)元在這兩種狀態(tài)下的取值都是一致的，另外假設(shè)兩種狀態(tài)出現(xiàn)的概率分別是和：

機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc78

對于網(wǎng)絡(luò)中任意兩個狀態(tài)V1和V2的出現(xiàn)概率分別為和。它們之間的關(guān)系為

上式符合統(tǒng)計理學(xué)中己知的Boltzmann分布。Boltzmann機由此得名。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc79一方面：這就說明了能量低的狀態(tài)出現(xiàn)的概率大，能量高的狀態(tài)出現(xiàn)的概率小。另一方面：溫度參數(shù)T也會影響boltzmann機處于某種狀態(tài)的概率。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc80（1）T很高時，各狀態(tài)出現(xiàn)的概率差異大大減小，也就是說網(wǎng)絡(luò)停留在全局最小點的概率，并不比局部最小點的概率甚至非局部最小點高很多。也即網(wǎng)絡(luò)不會陷在某個極小點中拔不出來，網(wǎng)絡(luò)在搜索過程中能夠“很快”的穿行于各極小點之間，但落于全局最小點的概率還是最大的。這一點保證網(wǎng)絡(luò)狀態(tài)落入全局最小點的可能性大。

機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc81（2）T很低時，情況正好相反。概率差距被加大，一旦網(wǎng)絡(luò)陷于某個極小點之后，雖然還有可能跳出該極小點，但是所需的搜索次數(shù)將是非常多的。這一點保證網(wǎng)絡(luò)狀態(tài)一旦達到全局最小點，跳出的可能性小（3）T→0（Hopfield網(wǎng)絡(luò))。差距被無限擴展，跳出局部最小點的概率趨于無窮小。這一點保證網(wǎng)絡(luò)狀態(tài)穩(wěn)定在全局最小點。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc8210.1.3Boltzmann機的運行步驟機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc設(shè)一個Boltzmann機具有n個隨機神經(jīng)元（p個顯見神經(jīng)元，q個隱見神經(jīng)元），第i個神經(jīng)元與第j個神經(jīng)元的連接權(quán)值為wij，i，j＝1,2,…,n。T0為初始溫度，m＝1,2,…,M為迭代次數(shù)。Boltzmann機的運行步驟為：第一步：對網(wǎng)絡(luò)進行初始化。設(shè)定初始溫度T0、終止溫度Tfinal和閾值ξ，以及網(wǎng)絡(luò)各神經(jīng)元的連接權(quán)值wij。83第二步：在溫度Tm條件下（初始溫度為T0）隨機選取網(wǎng)絡(luò)中的一個神經(jīng)元i，計算神經(jīng)元i的輸入信號總和ui：第三步：若ui>0，即能量差ΔEi>0，取vi=1為神經(jīng)元i的下一狀態(tài)值。若ui<0，計算概率：機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc84第四步：判斷網(wǎng)絡(luò)在溫度Tm下是否達到穩(wěn)定，若未達到穩(wěn)定，則繼續(xù)在網(wǎng)絡(luò)中隨機選取另一神經(jīng)元j，令j＝i，轉(zhuǎn)至第二步重復(fù)計算，直至網(wǎng)絡(luò)在Tm下達到穩(wěn)定。若網(wǎng)絡(luò)在Tm下已達到穩(wěn)定則轉(zhuǎn)至第五步計算。第五步：以一定規(guī)律降低溫度，使Tm+1<Tm，判斷Tm+1是否小于Tfinal，若Tm+1大于等于Tfinal，則Tm=Tm＋1，轉(zhuǎn)至第二步重復(fù)計算；若Tm+1小于Tfinal，則運行結(jié)束。此時在Tm下所求得的網(wǎng)絡(luò)穩(wěn)定狀態(tài)，即為網(wǎng)絡(luò)的輸出。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc85Boltzmann機學(xué)習(xí)需要注意幾點：（1）初始溫度T0的選擇方法。初始溫度T0的選取主要有以下方法：隨機選取網(wǎng)絡(luò)中k個神經(jīng)元，選取這k個神經(jīng)元能量的方差作為T0；在初始網(wǎng)絡(luò)中選取使ΔE最大的兩個神經(jīng)元，取T0為ΔEmax的若干倍；按經(jīng)驗值給出T0等。（2）確定終止溫度閾值Tfinal的方法。主要根據(jù)經(jīng)驗選取，若在連續(xù)若干溫度下網(wǎng)絡(luò)狀態(tài)保持不變，也可認為已達到終止溫度。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc86（3）概率閾值ξ的確定方法。ξ的選取方法主要有：在網(wǎng)絡(luò)初始化時按照經(jīng)驗確定或在網(wǎng)絡(luò)每次運行過程中選取一個[0,0.5]之間均勻分布的隨機數(shù)。（4）網(wǎng)絡(luò)權(quán)值wij的確定方法。將在下一章節(jié)討論。（5）在每一溫度下達到熱平衡的條件。通常在每一溫度下，實驗足夠多的次數(shù)，直至網(wǎng)絡(luò)狀態(tài)在此溫度下不再發(fā)生變化為止。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc87（6）降溫的方法。通常采用指數(shù)的方法進行降溫，即：為加快網(wǎng)絡(luò)收斂速度也可采用倍乘一個小于1的降溫系數(shù)的方法進行快速降溫。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc8810.1.4Boltzmann機的學(xué)習(xí)規(guī)則Boltzmann機是一種隨機神經(jīng)網(wǎng)絡(luò)，可使用概率中的似然函數(shù)量度其模擬外界環(huán)境概率分布的性能。因此，Boltzmann機的學(xué)習(xí)規(guī)則就是根據(jù)最大似然規(guī)則，通過調(diào)整權(quán)值wij，最小化似然函數(shù)或其對數(shù)。假設(shè)給定需要網(wǎng)絡(luò)模擬其概率分布的樣本集合，Vx是樣本集合中的一個狀態(tài)向量，Vx即可代表網(wǎng)絡(luò)中顯見神經(jīng)元的一個狀態(tài)，假設(shè)向量Vy表示網(wǎng)絡(luò)中隱見神經(jīng)元的一個可能狀態(tài)，則V=[VxVy]即可表示整個網(wǎng)絡(luò)所處的狀態(tài)。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc89由于網(wǎng)絡(luò)學(xué)習(xí)的最終目的是模擬外界給定樣本集合的概率分布，而Boltzmann機含有顯見神經(jīng)元和隱見神經(jīng)元，因此Boltzmann機的學(xué)習(xí)過程包括以下兩個階段：（1）主動階段：網(wǎng)絡(luò)在外界環(huán)境約束下運行，即由樣本集合中的狀態(tài)向量Vx控制顯見神經(jīng)元的狀態(tài)。定義神經(jīng)元i和j的狀態(tài)在主動階段的平均關(guān)聯(lián)為：

機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc90

其中概率P(Vy|Vx)表示網(wǎng)絡(luò)的顯見神經(jīng)元約束在Vx下隱見神經(jīng)元處于Vy的條件概率，它與網(wǎng)絡(luò)在主動階段的運行過程有關(guān)。2）被動階段：網(wǎng)絡(luò)不受外界環(huán)境約束，顯見神經(jīng)元和隱見神經(jīng)元自由運行，不受約束。被動階段的平均關(guān)聯(lián)為：定義神經(jīng)元i和j的狀態(tài)在機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc91

P(V)為網(wǎng)絡(luò)處于V狀態(tài)時的概率，vi和vj分別是神經(jīng)元i和j的輸出狀態(tài)。由于網(wǎng)絡(luò)在自由運行階段服從Boltzmann分布，因此:E(V)為網(wǎng)絡(luò)處于V狀態(tài)時的能量。網(wǎng)絡(luò)的權(quán)值wij需遵循下面的調(diào)整規(guī)則：機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc92wij(t)為在第t步時神經(jīng)元i，j之間的連接權(quán)值，η為學(xué)習(xí)速率，T是網(wǎng)絡(luò)溫度。Boltzmann機的優(yōu)點：（1）通過訓(xùn)練，神經(jīng)元體現(xiàn)了與周圍環(huán)境相匹配的概率分布；（2）網(wǎng)絡(luò)提供了一種可用于尋找、表示和訓(xùn)練的普遍方法；（3）若保證學(xué)習(xí)過程中溫度降低的足夠慢，根據(jù)狀態(tài)的演化，可以使網(wǎng)絡(luò)狀態(tài)的能量達到全局最小點。機器人智能與神經(jīng)計算實驗室(RINC.LAB)/rinc93但是在Boltzmann機的學(xué)習(xí)過程中被動階段的存在具有兩個很大的缺點：（1）增加計算時間。在外界環(huán)境約束條件下，一些神經(jīng)元由外部環(huán)境約束，而在自由運行條件下，所有的神經(jīng)元自由運行，這樣增加了Boltzmann機的隨機仿真時間。（