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

1、隨機網(wǎng)絡(luò)：學(xué)習(xí)運行引入隨機機制1.存在的問題：以目標(biāo)函數(shù)的極小值，作為學(xué)習(xí)或運行的目的 BP算法->誤差函數(shù)，梯度下降 Hop算法->Hebb規(guī)則->能量函數(shù)E 容易陷入局部極小點。,①無法避免，從②入手：將“總是沿梯度下降方向演變”改為”大部分沿梯度下降方向演變，但允許少數(shù)情況沿上升方向演變?！?目錄,引言模擬退火算法的模型模擬退火算法的簡單應(yīng)用模擬退火算法的參數(shù)控制問題Boltzm

2、ann機,4.1 引言,模擬退火(Simulated Annealing, SA)算法是近年來特別引入注目的一種適用于解大型組合優(yōu)化問題的優(yōu)化方法,算法來源于固體退火原理,其核心在于模仿熱力學(xué)中液體的凍結(jié)與結(jié)晶或金屬熔液的冷卻與退火過程--物理退火過程和Metropolis準(zhǔn)則. 下面分別介紹SA原理SA全局優(yōu)化的直觀解釋,4.1.1 模擬退火原理,簡單而言,在固體退火時,先將固體加熱使其溫度充分高,再讓其徐徐冷卻,其物理退火過

3、程由以下三部分組成：加溫過程等溫過程冷卻過程,4.1.1 模擬退火原理,加溫過程在固體退火時,先將固體加熱使其溫度充分高,其目的是增強粒子的熱運動,使其偏離平衡位置.當(dāng)溫度足夠高時,固體將溶解為液體,固體內(nèi)部粒子隨溫升變?yōu)闊o序狀, 彼此之間可以自由移動,從而消除系統(tǒng)原先可能存在的非均勻態(tài),使隨后進行的冷卻過程以某一平衡態(tài)為起點.熔解過程(加熱固體至高溫液態(tài))與系統(tǒng)的熵增過程聯(lián)系,系統(tǒng)內(nèi)部能量也隨溫度的升高而增大.,4.1.1

4、 模擬退火原理,等溫過程物理學(xué)的知識告訴我們,對于與周圍環(huán)境交換熱量而溫度不變的封閉系統(tǒng),系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進行,當(dāng)自由能達到最小時,系統(tǒng)達到平衡態(tài).冷卻過程目的是使粒子的熱運動減弱并漸趨有序,系統(tǒng)能量逐漸下降,從而得到低能的晶體結(jié)構(gòu). 徐徐冷卻時粒子就會喪失由干溫度而引起的流動性,漸趨有序,這時原子就會自己排列起來而形成一種純晶體,它們依次地朝各個方向排列成幾十億倍于單個原子大小的距離,這個純晶體狀態(tài)就是

5、該系統(tǒng)的平衡態(tài),亦為最小能量狀態(tài).,4.1.1 模擬退火原理,有趣的是:對一個徐徐冷卻的系統(tǒng),當(dāng)這些原子在逐漸失去活力的同時,它們自己就同時地排列而形成一個純晶體,使這個系統(tǒng)的能量達到其最小值.這里引起特別關(guān)注的是,在這個物理系統(tǒng)的冷卻過程中,這些原子是“同時地”把它們自己排列成一個純晶體的.如果一種金屬熔液是被快速冷卻或潑水使其冷卻的,則它不能達到純晶體狀態(tài),而是變成一種多晶體或非晶體狀態(tài),系統(tǒng)處在這種狀態(tài)時具有較高的能量.,4

6、.1.1 模擬退火原理,SA算法就是模仿上述物理系統(tǒng)徐徐退火過程的一種通用隨機搜索技術(shù),人們可用馬爾柯夫鏈的遍歷理論來給它以數(shù)學(xué)上的描述.在搜索最優(yōu)解的過程中,SA算法除了可以接受優(yōu)化解外,還基于隨機接受準(zhǔn)則(Metropolis準(zhǔn)則)有限度地接受惡化解,并且接受惡化解的概率慢慢趨向于0.這使得算法有可能從局部最優(yōu)中跳出,盡可能找到全局最優(yōu)解,并保證了算法的收斂.SA的思想最早是由Metropolis等(1953)提出的.Met

7、ropolis等提出了重要性采樣法,即以概率接受新狀態(tài).,對于某一給定溫度，系統(tǒng)若達到熱平衡狀態(tài)(循環(huán)若干次)，則該狀態(tài)下的能量服從Bottzmann分布.,4.1.1 模擬退火原理,4.1.1 模擬退火原理,具體而言,在溫度t,由當(dāng)前狀態(tài)i產(chǎn)生新狀態(tài)j,兩者的能量分別為Ei和Ej,若Ej<Ei則接受新狀態(tài)j為當(dāng)前狀態(tài)；否則,若概率,大于[0,1)區(qū)間內(nèi)的隨機數(shù)則仍舊接受新狀態(tài)j為當(dāng)前狀態(tài),若不成立則保留i為當(dāng)前狀態(tài),其中k為Bo

8、ltzmann常數(shù).這種重要性采樣過程在高溫下可接受與當(dāng)前狀態(tài)能量差較大的新狀態(tài),而在低溫下基本只接受與當(dāng)前能量差較小的新狀態(tài),而且當(dāng)溫度趨于零時,就不能接受比當(dāng)前狀態(tài)能量高的新狀態(tài).這種接受準(zhǔn)則通常稱為Metropolis準(zhǔn)則.,4.1.1 模擬退火原理,1983年Kirkpatrick等人意識到組合優(yōu)化與物理退火的相似性,并受到Metropolis準(zhǔn)則的啟迪,首次把固體的退火過程與組合極小化聯(lián)系在一起,他們分別用目標(biāo)函數(shù)和組合極

9、小化問題的解替代物理系統(tǒng)的能量和狀態(tài),從而物理系統(tǒng)內(nèi)粒子的攝動等價于組合極小化問題的試探.SA是基于Monte Carlo迭代求解策略的一種隨機尋優(yōu)算法.極小化過程就是:首先在一個高溫(溫度現(xiàn)在就成為一個控制參數(shù))狀態(tài)下,利用具有概率突跳特性的Metropolis抽樣策略在解空間中進行隨機搜索,伴隨溫度的不斷下降,重復(fù)抽樣過程,將有效地“溶化”解空間;然后慢慢地降低溫度直到系統(tǒng)“結(jié)晶”到一個穩(wěn)定解,最終得到問題的全局最優(yōu)解.,4

10、.1.1 模擬退火原理,SA算法在組合最優(yōu)化中的成功應(yīng)用掀起了SA算法研究與應(yīng)用的高潮.1991年Dekkers和Aarts探討將SA算法應(yīng)用于求解連續(xù)優(yōu)化問題.20世紀(jì)90年代以來,SA算法在NN、GA、進化算法等優(yōu)化、學(xué)習(xí)領(lǐng)域得到極大的應(yīng)用.,4.1.1 模擬退火原理,SA算法的主要精髓是基于Metropolis準(zhǔn)則可接受求解過程的惡化解. Metropolis準(zhǔn)則為:粒子在溫度T時趨于平衡的概率為,其中E為溫度T時的內(nèi)能,

11、?E為其改變量,k為Boltzmann常數(shù).,4.1.1 模擬退火原理,利用上述固體退火原理來模擬求解組合優(yōu)化問題時,將內(nèi)能E模擬為目標(biāo)函數(shù)值f,溫度T演化成控制參數(shù)t,并以Metropolis準(zhǔn)則的概率,接受惡化解,按照上述方法即得到解組合優(yōu)化問題的SA算法.,4.1.1 模擬退火原理,SA算法的思想為:由初始解i和控制參數(shù)初值t開始,對當(dāng)前解重復(fù)產(chǎn)生新解 → 計算目標(biāo)函數(shù)差

12、 → 接受或舍棄的迭代,并逐步衰減t值,算法終止時的當(dāng)前解即為所得近似最優(yōu)解,這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程.,4.1.1 模擬退火原理,退火過程由冷卻進度表(Cooling Schedule)控制,包括控制參數(shù)的初值t及其衰減因子?t、每個t值時的迭代次數(shù)L和停止條件S.,4.1.2 SA全局優(yōu)化的直觀解釋,SA算法最重要的貢獻在于其能以較大的概率求取復(fù)雜優(yōu)化問題的全局解.下面通過連續(xù)函數(shù)優(yōu)

13、化的幾何直觀解釋來說明SA算法如何能以較大概率求得全局最優(yōu)解.考慮如下圖所示的全局優(yōu)化問題.,4.1.2 SA全局優(yōu)化的直觀解釋,4.1.2 SA全局優(yōu)化的直觀解釋,所謂SA優(yōu)化算法,其實質(zhì)上相當(dāng)于對該函數(shù)在水平方向上施以振動.若需逃離極值,則逃離出局部極值比全局極值需要更小的能量,即振動的幅度更小.,4.1.2 SA全局優(yōu)化的直觀解釋,4.1.2 SA全局優(yōu)化的直觀解釋,但實際上相反,SA的策略為函數(shù)值大,其能量大,即振動的幅度

14、大.,4.1.2 SA全局優(yōu)化的直觀解釋,因此,SA算法使得局部極值更容易被逃逸,全局極值更穩(wěn)定.故求得全局極值的概率較大.從上述直觀解釋,可以得出SA算法的全局優(yōu)化的原理：由于優(yōu)化過程中,拒絕惡化解的概率與函數(shù)值(能量)大小成正指數(shù)關(guān)系,而且局部極值本身更容易被逃逸,因此迭代變量落入函數(shù)值大的局部極值比落入函數(shù)值最小(能量最小)的全局極值更有可能產(chǎn)生逃逸.,4.2 SA算法的模型,SA算法可以分解為解空間、目標(biāo)函數(shù)和初始解三

15、部分.SA的基本思想:Step 1 初始化:初始溫度T(充分大),初始解狀態(tài)S(是算法迭代的起點),每個T值的迭代次數(shù)LStep 2 對k=1,……,L做第(3)至第6步:Step 3 產(chǎn)生新解S’Step 4 計算增量?t’=C(S’)-C(S),其中C(S)為評價函數(shù),4.2 SA算法的模型,Step 5 若?t’<0則接受S’作為新的當(dāng)前解,否則以概率exp(-?t’/T)接受S’作為新的當(dāng)前解.Step 6 如

16、果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解,結(jié)束程序.終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法.Step 7 T逐漸減少,且T?0,然后轉(zhuǎn)第2步.算法對應(yīng)流程圖如下所示.,4.2 SA算法的模型,4.2 SA算法的模型,SA算法新解的產(chǎn)生和接受可分為如下四個步驟:第一步是由一個產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個位于解空間的新解第二步是計算與新解所對應(yīng)的目標(biāo)函數(shù)差第三步是判斷新解是否被接受,判斷的依據(jù)是一個接受準(zhǔn)則第四步是當(dāng)新解

17、被確定接受時,用新解代替當(dāng)前解.,4.2 SA算法的模型,第一步是由一個產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個位于解空間的新解.為便于后續(xù)的計算和接受,減少算法耗時,通常選擇由當(dāng)前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法,如對構(gòu)成新解的全部或部分元素進行置換、互換等,注意到產(chǎn)生新解的變換方法決定了當(dāng)前新解的鄰域結(jié)構(gòu),因而對冷卻進度表的選取有一定的影響.,4.2 SA算法的模型,第二步是計算與新解所對應(yīng)的目標(biāo)函數(shù)差.第三步是判斷新解是否被接受,判斷的

18、依據(jù)是一個接受準(zhǔn)則.最常用的接受準(zhǔn)則是Metropo1is準(zhǔn)則:若?t’a，則接受x’為新狀態(tài)，否則仍停留來原狀態(tài)X）.,4.2 SA算法的模型,第四步是當(dāng)新解被確定接受時,用新解代替當(dāng)前解.這只需將當(dāng)前解中對應(yīng)于產(chǎn)生新解時的變換部分予以實現(xiàn),同時修正目標(biāo)函數(shù)值即可.此時,當(dāng)前解實現(xiàn)了一次迭代.可在此基礎(chǔ)上開始下一輪試驗.而當(dāng)新解被判定為舍棄時,則在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗.,4.2 SA算法的模型,從算法流程上看,模擬

19、退火算法包括三過程(函數(shù))兩準(zhǔn)則,即狀態(tài)產(chǎn)生過程、狀態(tài)接受過程、溫度更新過程、內(nèi)循環(huán)終止準(zhǔn)則和外循環(huán)終止準(zhǔn)則,這些環(huán)節(jié)的設(shè)計將決定SA算法的優(yōu)化性能.其中狀態(tài)產(chǎn)生過程和外循環(huán)終止準(zhǔn)則根據(jù)SA算法應(yīng)用于不同的領(lǐng)域的不同優(yōu)化問題,其具體過程不同.其它過程和準(zhǔn)則則是SA算法的基本要素,基本不變.,4.2 SA算法的模型,A. 狀態(tài)產(chǎn)生函數(shù)設(shè)計狀態(tài)產(chǎn)生函數(shù)(鄰域函數(shù))的出發(fā)點應(yīng)該是盡可能保證產(chǎn)生的候選解遍布全部的解空間.通常

20、,狀態(tài)產(chǎn)生函數(shù)由兩部分組成,即產(chǎn)生候選解的方式和候選解產(chǎn)生的概率分布. B. 狀態(tài)接受函數(shù)狀態(tài)接受函數(shù)一般以概率的方式給出,不同接受函數(shù)的差別主要在于接受概率的形式不同.設(shè)計狀態(tài)接受概率,應(yīng)該遵循以下原則：① 在固定溫度下,接受使目標(biāo)函數(shù)值下降的候選解的概率要大于使目標(biāo)值上升的候選解的概率；,4.2 SA算法的模型,② 隨溫度的下降,接受使目標(biāo)函數(shù)值上升的解的概率要逐漸減小；③ 當(dāng)溫度趨于零時,只能接受目標(biāo)函數(shù)值下降的解.狀

21、態(tài)接受函數(shù)的引入是SA算法實現(xiàn)全局搜索的最關(guān)鍵的因素.,C. 溫度更新函數(shù)溫度更新函數(shù),即溫度的下降方式,用于在外循環(huán)中修改溫度值.目前,最常用的溫度更新函數(shù)為指數(shù)退溫函數(shù),當(dāng)然還有其它不同的降溫策略.,4.2 SA算法的模型,4.2 SA算法的模型,D. 內(nèi)循環(huán)終止準(zhǔn)則內(nèi)循環(huán)終止準(zhǔn)則,或稱Metropolis抽樣穩(wěn)定準(zhǔn)則,用于決定在各溫度下產(chǎn)生候選解的數(shù)目.常用的抽樣準(zhǔn)則包括：① 檢驗?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定；② 連續(xù)若干步

22、的目標(biāo)值變化較??；③ 按一定的步數(shù)抽樣.,4.2 SA算法的模型,E. 外循環(huán)終止準(zhǔn)則外循環(huán)終止準(zhǔn)則,即算法終止準(zhǔn)則,用于決定算法何時結(jié)束.設(shè)置溫度終值是一種簡單的方法.SA算法的收斂性理論中要求溫度終值趨于零,這顯然不合實際.通常的做法是：① 設(shè)置終止溫度的閾值；② 設(shè)置外循環(huán)迭代次數(shù)；③ 算法收斂到的最優(yōu)值連續(xù)若干步保持不變；④ 檢驗系統(tǒng)熵是否穩(wěn)定.,4.3 SA算法的簡單應(yīng)用,作為SA算法應(yīng)用,討論貨郎擔(dān)問題(TSP

23、):設(shè)有n個城市,用數(shù)碼1,…,n代表.城市i和城市j之間的距離為d(i,j), i, j=1,…,nTSP問題是要找遍訪每個域市恰好一次的一條回路,且其路徑總長度為最短.,4.3 SA算法的簡單應(yīng)用,求解TSP的SA算法模型可描述如下:解空間 解空間S是遍訪每個城市恰好一次的所有回路,是{1,……,n}的所有循環(huán)排列的集合,S中的成員記為(w1,w2 ,……,wn),并記wn+1= w1.初始解可選為(1,……,n)目

24、標(biāo)函數(shù) 此時的目標(biāo)函數(shù)即為訪問所有城市的路徑總長度或稱為代價函數(shù):f(w1, w2 ,…,wn)=sum(d(wj, wj+1))我們要求此代價函數(shù)的最小值.,4.3 SA算法的簡單應(yīng)用,新解的產(chǎn)生隨機產(chǎn)生1和n之間的兩相異數(shù)k和m,若km,則將(w1, w2 ,…,wk , wk+1 ,…,wm ,…,wn)變?yōu)?(wm, wm-1 ,…,w1 , wm+1 ,…,wk-1 ,wn , wn-1 ,…,wk).上述變換

25、方法可簡單說成是“逆轉(zhuǎn)中間或者逆轉(zhuǎn)兩端”.,4.3 SA算法的簡單應(yīng)用,也可以采用其他的變換方法,有些變換有獨特的優(yōu)越性,有時也將它們交替使用,得到一種更好方法.代價函數(shù)差設(shè)將(w1, w2 ,……,wn)變換為(u1, u2 ,……,un), 則代價函數(shù)差為,4.3 SA算法的簡單應(yīng)用,根據(jù)上述分析,可寫出用SA算法求解TSP問題的偽程序:Procedure TSPSA:　begin　　init-of-T; { T為初始溫度

26、}　　S={1,……,n}; {S為初始值}　　termination=false;　　while termination=false　　　begin　　　　for i=1 to L do　　　　　begin　　　　　　generate(S’ from S); { 從當(dāng)前回路S產(chǎn)生新回

27、 路S’},4.3 SA算法的簡單應(yīng)用,?t:=f(S’)-f(S);{f(S)為路徑總長}　　　　　　IF(?tRandom-of-[0,1])　　　　　　　S=S’;　　　　　　IF the-halt-condition-is-TRUE THEN　　　　　　　termination=true;　　　　　End;　　　　T_lower;　　　End;　End,4.3 SA算法的簡單應(yīng)用,SA

28、算法的應(yīng)用很廣泛,可以以較高的效率求解最大截問題(Max Cut Problem)、0-1背包問題(Zero One Knapsack Problem)、圖著色問題(Graph Colouring Problem)、調(diào)度問題(Scheduling Problem)等等.,4.4 SA算法的參數(shù)控制問題,SA算法是一種非常良好的,具有普適性的迭代優(yōu)化算法.其主要性質(zhì)有：與初始值無關(guān),算法求得的解與初始解狀態(tài)S(是算法迭代的起點)

29、無關(guān);SA算法具有漸近收斂性,已在理論上被證明是一種以概率1收斂于全局最優(yōu)解的全局優(yōu)化算法;SA算法具有并行性.,4.4 SA算法的參數(shù)控制問題,SA算法的應(yīng)用很廣泛,可以求解NP完全問題,但其參數(shù)難以控制,其主要問題有以下三點:溫度T的初始值設(shè)置問題.退火速度問題溫度管理問題.,4.4 SA算法的參數(shù)控制問題,A. 溫度T的初始值設(shè)置問題.初始溫度、溫度更新函數(shù)、內(nèi)循環(huán)終止準(zhǔn)則和外循環(huán)終止準(zhǔn)則通常被稱為退火歷程(annea

30、ling schedule).實驗表明,初溫越大,獲得高質(zhì)量解的幾率越大,但花費的計算時間將增加.初始溫度高,則搜索到全局最優(yōu)解的可能性大,但因此要花費大量的計算時間;反之,則可節(jié)約計算時間,但全局搜索性能可能受到影響.,4.4 SA算法的參數(shù)控制問題,因此,初溫的確定是影響SA算法全局搜索性能的重要因素之一,應(yīng)折衷考慮優(yōu)化質(zhì)量和優(yōu)化效率,實際應(yīng)用過程中,初始溫度一般需要依據(jù)實驗結(jié)果進行若干次調(diào)整.,4.4 SA算法的參數(shù)控制問

31、題,B. 退火速度問題.SA算法的全局搜索性能也與退火速度密切相關(guān).一般來說,同一溫度下的“充分”搜索(退火)是相當(dāng)必要的,但這需要計算時間.實際應(yīng)用中,要針對具體問題的性質(zhì)和特征設(shè)置合理的退火平衡條件.C. 溫度管理問題.溫度管理問題也是SA算法難以處理的問題之一.實際應(yīng)用中,由于必須考慮計算復(fù)雜度的切實可行性等問題,常采用如下所示的降溫方式:T(t+1)＝k?T(t)式中k為正的略小于1.00的常數(shù),t為降溫的次數(shù).

32、,4.5 Boltzmann機,前面介紹的NN模型都為確定性的NN,組成它們的神經(jīng)元進行信息處理時均為確定的.但在生物神經(jīng)元中,由于有各種各樣的干擾,以及神經(jīng)元本身所具有的一定程度的不確定性.同時基于硬件實現(xiàn)的ANN本身也會受到各種擾動,其特性也呈現(xiàn)一定的不確定性.因此,研究具有不確定性特征、隨機特征的ANN是非常必要的.Boltzmann機是基于退火原理來決定神經(jīng)元狀態(tài)演變的,正是具有隨機性特征的互聯(lián)型網(wǎng)絡(luò).,4.5 Bolt

33、zmann機,Boltzmann機是由Hinton等人于1984年提出的,其一般拓撲結(jié)構(gòu)為具有輸入層、隱單元層、輸出層的3層前向NN.下面將主要介紹Boltzmann機的網(wǎng)絡(luò)結(jié)構(gòu)網(wǎng)絡(luò)能量Boltzmann機網(wǎng)絡(luò)狀態(tài)變化規(guī)則,4.5.1 網(wǎng)絡(luò)結(jié)構(gòu),Boltzmann機是一種有反饋的互聯(lián)型網(wǎng)絡(luò).假定網(wǎng)絡(luò)由n個節(jié)點構(gòu)成,任意一個節(jié)點i的輸出為:vi(t)∈{0,1}.節(jié)點之間的連接權(quán)植矩陣是對稱的,即:wij=wji ,wii=0

34、.當(dāng)節(jié)點i的輸入:,發(fā)生變化時,將引起輸出vi(t+1)的更新.這種更新在各節(jié)點之間是以異步方式進行的,并且以概率Pi值來決定vi(t+1).,4.5.1 網(wǎng)絡(luò)結(jié)構(gòu),在此規(guī)定vi(t+1)為1的概率Pi為：,由上式可得到： (4.1),4.5.1 網(wǎng)絡(luò)結(jié)構(gòu),圖4.2 節(jié)點的輸出受溫度

35、T的影響,4.5.1 網(wǎng)絡(luò)結(jié)構(gòu),由以上分析可知，任意節(jié)點i當(dāng)被選擇狀態(tài)更新時，下一狀態(tài)為1的概率為： (4.2),T為網(wǎng)絡(luò)的溫度參數(shù)，ui為i節(jié)點的激活函數(shù)。,則下一狀態(tài)為0的概率為,4.5.1 網(wǎng)絡(luò)結(jié)構(gòu),一般情況下，當(dāng)激活函數(shù)ui>0時，下一狀態(tài)為1的概率pi(1)將大于下一

36、狀態(tài)為0的概率pi(0)，且隨著ui值的增加， pi(1)也越大。同理，當(dāng)uipi(1), 且隨著ui值的減小， pi(0)也越大。,T趨于0時，概率分布曲線近似于單位階躍函數(shù)(等價于離散HNN網(wǎng)絡(luò)，只是描述網(wǎng)絡(luò)單元狀態(tài)“思想”的出發(fā)點不同)。T趨于無窮大時，概率分布曲線近似于一條直線。,4.5.2 網(wǎng)絡(luò)能量,網(wǎng)絡(luò)的能量函數(shù)定義為：,根據(jù)式(4.1)給定的概率,考查vi(t+1)更新為1時,網(wǎng)絡(luò)能量的變化為：,4.5.2 網(wǎng)絡(luò)能量,由

37、上式可知,當(dāng)ui(t)≥0時,網(wǎng)絡(luò)能量將減少或不變,且ui(t)≥0時,概率Pi大；相反,ui(t)＜0時,網(wǎng)絡(luò)的能量增加或不變,且ui(t)＜0時,概率Pi小.,4.5.2 網(wǎng)絡(luò)能量,穩(wěn)定性分析由于有,若ui>0，pi(1)>0.5，即有較大的概率取vi=1，若原來vi=1，則△vi=0， △Ei=0；若原來vi=0，則△vi>0，所以△Ei<0。若ui<0， pi(1)<0.5，即有較大的概

38、率取vi=0，若原來vi=0，則△vi=0， △Ei=0；若原來vi=1，則△vi<0，所以△Ei<0。,4.5.2 網(wǎng)絡(luò)能量,可見，隨著系統(tǒng)狀態(tài)的演變，從概率意義上，系統(tǒng)的能量總是朝小的方向變化，所以系統(tǒng)最后總能穩(wěn)定到能量的極小點附近。但由于是隨機網(wǎng)絡(luò)，在能量極小點附近，系統(tǒng)也不會停止在某一個固定的狀態(tài)。總之,Boltzmann機允許網(wǎng)絡(luò)狀態(tài)以小的概率往能量大的方向遷移,這樣做的目的是使網(wǎng)絡(luò)能量函數(shù)能夠收斂于全局最小點.

39、,4.5.3 Boltzmann機網(wǎng)絡(luò)狀態(tài)變化規(guī)則,Boltzmann機網(wǎng)絡(luò)狀態(tài)變化規(guī)則Step 1 從n個節(jié)點中隨機地選取節(jié)點i； Step 2 計算節(jié)點i(1≤i≤n)的輸入ui(t),Step 3 以概率Pi來決定i的輸出vi(t+1) ：,4.5.3 Boltzmann機網(wǎng)絡(luò)狀態(tài)變化規(guī)則,Step 4 其它節(jié)點不變化；,Step 5 返回Step 1,4.5.3 Boltzmann機網(wǎng)絡(luò)狀態(tài)變化規(guī)則,例4.1： 假設(shè)一個3節(jié)

40、點的Boltzmann機。設(shè)網(wǎng)絡(luò)參數(shù)為,4.5.3 Boltzmann機網(wǎng)絡(luò)狀態(tài)變化規(guī)則,試確定溫度T=0.5和T=1時的網(wǎng)絡(luò)狀態(tài)轉(zhuǎn)移函數(shù)。首先計算某一狀態(tài)下各節(jié)點單元的激活函數(shù)值。以狀態(tài)v1v2v3=(111)為例：,應(yīng)用狀態(tài)轉(zhuǎn)移公式，依次計算溫度T=0.5和T=1時各個狀態(tài)相應(yīng)各節(jié)點的狀態(tài)更新概率，如表4.1。這樣就可以計算出各個狀態(tài)的轉(zhuǎn)移概率。,4.5.3 Boltzmann機網(wǎng)絡(luò)狀態(tài)變化規(guī)則,表4.1 3節(jié)點Boltzman

41、n機各個狀態(tài)的節(jié)點的激發(fā)概率,4.5.3 Boltzmann機網(wǎng)絡(luò)狀態(tài)變化規(guī)則,狀態(tài)轉(zhuǎn)移概率可用一個統(tǒng)一式子表達為：,應(yīng)用上面兩個公式，可以方便的確定在不同溫度下，各狀態(tài)轉(zhuǎn)移到其他狀態(tài)的概率。狀態(tài)轉(zhuǎn)移情況可以和HNN的情況進行比較后，可以得出結(jié)論：溫度的引入，使原有HNN中的狀態(tài)轉(zhuǎn)移概率分布發(fā)生了一定的變化，不僅可以向低能轉(zhuǎn)移，而且有機會由低能向高能態(tài)轉(zhuǎn)移。當(dāng)溫度較高時，轉(zhuǎn)移到其它狀態(tài)的概率分別接近1/n。,,狀態(tài)保持不變的概率可按下式

42、求得：,4.5.3 Boltzmann機網(wǎng)絡(luò)狀態(tài)變化規(guī)則,用圖示的方法來描述狀態(tài)轉(zhuǎn)移關(guān)系是復(fù)雜的，不實用的，我們可以用隨機過程中的馬爾可夫鏈的一些知識清晰的表達這一關(guān)系。馬爾可夫鏈?zhǔn)菚r間和狀態(tài)都離散的馬爾可夫過程。考慮給定一組狀態(tài)S0,---Sm-1，這些狀態(tài)以已知轉(zhuǎn)移概率pij（表示在狀態(tài)Si后出現(xiàn)Sj的概率）一個接一個的出現(xiàn)。該系統(tǒng)的狀態(tài)變化可用pij構(gòu)成的m*m 矩陣表示。,,其中，,,,,4.5.3 Boltzmann機網(wǎng)絡(luò)狀

43、態(tài)變化規(guī)則,例4.1中3節(jié)點Boltzmann機在T=1.0時的狀態(tài)轉(zhuǎn)移圖可用下表表示：,4.5.3 Boltzmann機網(wǎng)絡(luò)狀態(tài)變化規(guī)則,假設(shè)在t時刻出現(xiàn)Si的概率為Pi(t)，那么在t+1時刻狀態(tài)為Sj的概率Pj(t+1)可以由所有進入該狀態(tài)的概率求和得到，即,4.5.3 Boltzmann機網(wǎng)絡(luò)狀態(tài)變化規(guī)則,例4.2 對于例4.1所給的系統(tǒng)，假設(shè)在t=0時刻處，任何狀態(tài)的概率均為0.125，試確定下時刻狀態(tài)S2的概率。,同理，可計

44、算出到達其它各個狀態(tài)的概率，如表4.2所示。,隨著時間t的增加，在給定的溫度下，到達各個狀態(tài)的概率將趨于一個平衡狀態(tài)。,4.5.3 Boltzmann機網(wǎng)絡(luò)狀態(tài)變化規(guī)則,利用馬爾可夫鏈預(yù)測將來某一時刻的狀態(tài)概率分布，是隨機NN中非常有用的一個技術(shù)。例4.3 分析例4.1所示Boltzmann機，當(dāng)溫度由1.0按0.005的速率降到0.01時，狀態(tài)概率的分布變化如下表所示。,4.5.3 Boltzmann機網(wǎng)絡(luò)狀態(tài)變化規(guī)則,4.5.3

45、Boltzmann機網(wǎng)絡(luò)狀態(tài)變化規(guī)則,假定系統(tǒng)初始時刻t＝0時處于任意一個狀態(tài)的概率Pi(0)為0.125，起始溫度T0=1。利用馬爾可夫鏈的一步轉(zhuǎn)移概率矩陣所建立的馬爾可夫鏈，可以計算出當(dāng)t=13時刻狀態(tài)分布概率不再發(fā)生變化，我們稱此狀態(tài)為網(wǎng)絡(luò)的一個熱平衡態(tài)，如上表所示。此時，若將溫度降到0.995，則打破了T=1.0時的熱平衡，狀態(tài)轉(zhuǎn)移概率重新分布。利用新建立的馬爾可夫鏈，可以計算出下一時刻的狀態(tài)概率分布，當(dāng)t=15時系統(tǒng)達到一個新

46、的熱平衡。同理，若將溫度再降到0.01時，則當(dāng)t=473時，系統(tǒng)便可進入全局最小能量的穩(wěn)態(tài)S6。,4.5.3 Boltzmann機網(wǎng)絡(luò)狀態(tài)變化規(guī)則,事實上，S對應(yīng)的各個狀態(tài)的能量如下表示：,參考文獻,[1] Kirkpatrick, S , Gelatt, C.D., Vecchi, M.P. 1983. Optimization by Simulated Annealing. Science, vol 220, No. 4598, p

47、p 671-680 [2] P.J.M. van Laarhoven, E.H.L. Aarts, Simulated Annealing: Theory and Applications, Kluwer Academic Publisher, 1987. [3] A. A. Zhigljavsky, Theory of Global Random Search, Kluwer Academic Publishers, 1991.,