我的人工神經(jīng)網(wǎng)絡(luò)-10 非確定方法課件

1、第10章 非確定方法 10.1 基本的非確定學(xué)習(xí)算法 10.2 模擬退火算法 10.3 Cauchy學(xué)習(xí) 10.4 相關(guān)的幾個(gè)問(wèn)題 第10章 非確定方法確定的方法前幾章所給方法的共同特征非確定的方法生物神經(jīng)網(wǎng)絡(luò)按照概率運(yùn)行別稱統(tǒng)計(jì)方法（Statistical Method）。既可以用于學(xué)習(xí)，又可以用于運(yùn)行 10.1 基本的非確定學(xué)習(xí)算法 基本思想從所給的網(wǎng)絡(luò)中“隨機(jī)地選取一個(gè)聯(lián)接權(quán)”，對(duì)該聯(lián)接權(quán)提出一個(gè)“偽隨機(jī)調(diào)整量”，當(dāng)用此調(diào)整量對(duì)所選的聯(lián)接權(quán)進(jìn)行修改后，如果“被認(rèn)為”修改改進(jìn)了網(wǎng)絡(luò)的性能，則保留此調(diào)整；否則放棄本次調(diào)整。 10.1 基本的非確定學(xué)習(xí)算法基本數(shù)據(jù)結(jié)構(gòu)樣本集：S= (X1,Y1

2、),(X2,Y2),(Xs,Ys)輸入向量：X=(x1，x2，xn)理想輸出向量：Y=(y1，y2，ym)L層： W(1) ，W(2) ，W(L) 10.1 基本的非確定學(xué)習(xí)算法拓?fù)浣Y(jié)構(gòu) x1o1輸出層隱藏層輸入層x2o2omxnW(1) W(L)W(2)算法10-1 基本統(tǒng)計(jì)學(xué)習(xí)算法7 用修改后的W(1) ，W(2) ，W(L)重新計(jì)算X對(duì)應(yīng)的實(shí)際輸出O；8 求出網(wǎng)絡(luò)關(guān)于Y，O的誤差測(cè)度E；9 如果EE，則保留本次對(duì)W(1) ，W(2) ，W(L)的修改， 否則，根據(jù)概率判斷本次修改是否有用，如果認(rèn)為有用，則保留本次對(duì)W(1) ，W(2) ，W(L)的修改，如果認(rèn)為本次修改無(wú)用，則放棄它；1

3、0 重復(fù)上述過(guò)程，直到網(wǎng)絡(luò)滿足要求。 算法10-1 基本統(tǒng)計(jì)學(xué)習(xí)算法目標(biāo)函數(shù)（Objective Function）誤差測(cè)度函數(shù)：實(shí)際輸出與理想輸出方差和 計(jì)算量 從W(1) ，W(2) ，W(L)中隨機(jī)地選擇wij 共有nH1+H1H2+H2H3+HM-1m個(gè)“變量”可供選擇偽隨機(jī)數(shù)偽隨機(jī)數(shù)發(fā)生器來(lái)產(chǎn)生wij(p)；按照所謂的“能量”函數(shù)的分布去計(jì)算它逃離局部極小點(diǎn) 聯(lián)接權(quán)修改量 太?。郝涞紸點(diǎn)后很難逃離 太大：導(dǎo)致在A、B兩點(diǎn)來(lái)回抖動(dòng) 解決辦法 控制聯(lián)接權(quán)修改量的大小：權(quán)修改量由大變小 允許暫時(shí)變壞 修改量的大小和網(wǎng)絡(luò)的“能量”相關(guān) 模擬退火 ABD逃離局部極小點(diǎn)DBA10.1 模擬退火算

4、法及模型 算法的提出 模擬退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等將其應(yīng)用于組合優(yōu)化。算法的目的 解決NP復(fù)雜性問(wèn)題； 克服優(yōu)化過(guò)程陷入局部極?。?克服初值依賴性。 10.1.1 物理退火過(guò)程10.1 模擬退火算法及模型 物理學(xué)方面的模擬退火概念 固體物理中，金屬結(jié)構(gòu)的穩(wěn)定程度對(duì)應(yīng)著一個(gè)能量函數(shù)。 當(dāng)溫度高時(shí)，原子的運(yùn)動(dòng)不穩(wěn)定，能量函數(shù)較高。 如果用淬火的方式驟然降溫，能量函數(shù)就會(huì)進(jìn)入一個(gè)局部極小。 10.1.1 物理退火過(guò)程10.1 模擬退火算法及模型 物理學(xué)方面的模擬退火概念 所謂退火，是近似一種雙極限過(guò)程：極限一：當(dāng)溫度有改變時(shí)，經(jīng)過(guò)

5、無(wú)窮大時(shí)間后，系統(tǒng)可以進(jìn)入穩(wěn)態(tài)；極限二：溫度以無(wú)窮小的速度趨進(jìn)于絕對(duì)零度； 10.1.1 物理退火過(guò)程10.1 模擬退火算法及模型 物理退火過(guò)程 加溫過(guò)程增強(qiáng)粒子的熱運(yùn)動(dòng)，消除系統(tǒng)原先可能存在的非均勻態(tài)； 等溫過(guò)程對(duì)于與環(huán)境換熱而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時(shí)，系統(tǒng)達(dá)到平衡態(tài)； 冷卻過(guò)程使粒子熱運(yùn)動(dòng)減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。 10.1.1 物理退火過(guò)程10.1 模擬退火算法及模型 數(shù)學(xué)表述 在溫度T，分子停留在狀態(tài)r滿足Boltzmann概率分布 10.1.1 物理退火過(guò)程10.1 模擬退火算法及模型 數(shù)學(xué)表

6、述 在同一個(gè)溫度T，選定兩個(gè)能量E1E2，有 在同一個(gè)溫度，分子停留在能量小的狀態(tài)的概率比停留在能量大的狀態(tài)的概率要大。 10.1.1 物理退火過(guò)程010.1 模擬退火算法及模型 數(shù)學(xué)表述 若|D|為狀態(tài)空間D中狀態(tài)的個(gè)數(shù)，D0是具有最低能量的狀態(tài)集合： 當(dāng)溫度很高時(shí)，每個(gè)狀態(tài)概率基本相同，接近平均值1/|D|； 狀態(tài)空間存在超過(guò)兩個(gè)不同能量時(shí)，具有最低能量狀態(tài)的概率超出平均值1/|D| ； 當(dāng)溫度趨于0時(shí)，分子停留在最低能量狀態(tài)的概率趨于1。能量最低狀態(tài) 10.1 模擬退火算法及模型 Metropolis準(zhǔn)則（1953）以概率接受新?tīng)顟B(tài) 固體在恒定溫度下達(dá)到熱平衡的過(guò)程可以用Monte Ca

7、rlo方法（計(jì)算機(jī)隨機(jī)模擬方法）加以模擬，雖然該方法簡(jiǎn)單，但必須大量采樣才能得到比較精確的結(jié)果，計(jì)算量很大。 10.1.1 物理退火過(guò)程10.1 模擬退火算法及模型 Metropolis準(zhǔn)則（1953）以概率接受新?tīng)顟B(tài) 若在溫度T，當(dāng)前狀態(tài)i 新?tīng)顟B(tài)j 若Ej=randrom0,1 s=sj; Until 抽樣穩(wěn)定準(zhǔn)則滿足； 退溫tk+1=update(tk)并令k=k+1； Until 算法終止準(zhǔn)則滿足； 輸出算法搜索結(jié)果。 10.1.3 模擬退火算法的基本思想和步驟10.1 模擬退火算法及模型 定義馬爾科夫性（無(wú)后效性）：由時(shí)刻t0系統(tǒng)或過(guò)程所處的狀態(tài)，可以決定系統(tǒng)或過(guò)程在時(shí)刻t0所處的狀

8、態(tài)，而無(wú)需借助于t0以前系統(tǒng)或過(guò)程所處狀態(tài)的歷史資料。馬爾科夫性過(guò)程分布函數(shù)的描述：X(tn-1)=xn-1,即：PX(tn)=xn|x(t1=x1),X(t2)=x2,.,X(tn-1)=xn-1=PX(tn)=xn|X(tn-1)=xn-1, xnR. 10.2.1 馬爾科夫鏈10.2 模擬退火算法的馬氏鏈描述 定義 10.2.1 馬爾科夫鏈10.2 模擬退火算法的馬氏鏈描述 定義 一步轉(zhuǎn)移概率： n步轉(zhuǎn)移概率： 若解空間有限，稱馬爾可夫鏈為有限狀態(tài)； 若 ，稱馬爾可夫鏈為時(shí)齊的。 10.2.1 馬爾科夫鏈10.2 模擬退火算法的馬氏鏈描述 模擬退火算法對(duì)應(yīng)了一個(gè)馬爾可夫鏈 模擬退火算法：

9、新?tīng)顟B(tài)接受概率僅依賴于新?tīng)顟B(tài)和當(dāng)前狀態(tài)，并由溫度加以控制。 若固定每一溫度，算法均計(jì)算馬氏鏈的變化直至平穩(wěn)分布，然后下降溫度，則稱為時(shí)齊算法； 若無(wú)需各溫度下算法均達(dá)到平穩(wěn)分布，但溫度需按一定速率下降，則稱為非時(shí)齊算法。分析收斂性 10.2.2 模擬退火算法與馬爾科夫鏈10.3 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)原則 產(chǎn)生的候選解應(yīng)遍布全部解空間方法 在當(dāng)前狀態(tài)的鄰域結(jié)構(gòu)內(nèi)以一定概率方式（均勻分布、正態(tài)分布、指數(shù)分布等）產(chǎn)生 10.10.1 狀態(tài)產(chǎn)生函數(shù)10.3 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)原則 (1)在固定溫度下，接受使目標(biāo)函數(shù)下降的候選解的概率要大于使目標(biāo)函數(shù)上升的候選解概率； (2)隨

10、溫度的下降，接受使目標(biāo)函數(shù)上升的解的概率要逐漸減??； (3)當(dāng)溫度趨于零時(shí)，只能接受目標(biāo)函數(shù)下降的解。方法 具體形式對(duì)算法影響不大 一般采用min1,exp(-C/t) 10.10.2 狀態(tài)接受函數(shù)10.3 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)收斂性分析 通過(guò)理論分析可以得到初溫的解析式，但解決實(shí)際問(wèn)題時(shí)難以得到精確的參數(shù)； 初溫應(yīng)充分大；實(shí)驗(yàn)表明 初溫越大，獲得高質(zhì)量解的機(jī)率越大，但花費(fèi)較多的計(jì)算時(shí)間； 10.10.3 初溫10.3 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)方法 （1）均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值得方差為初溫； （2）隨機(jī)產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差，根據(jù)差值，利用一定

11、的函數(shù)確定初溫； （3）利用經(jīng)驗(yàn)公式。 10.10.3 初溫10.3 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)時(shí)齊算法的溫度下降函數(shù) （1） ，越接近1溫度下降越慢，且其大小可以不斷變化； （2） ，其中t0為起始溫度，K為算法溫度下降的總次數(shù)。 10.10.4 溫度更新函數(shù)10.3 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì) 時(shí)齊算法常用的Metropolis抽樣穩(wěn)定準(zhǔn)則 （1）檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定； （2）連續(xù)若干步的目標(biāo)值變化較小； （3）按一定的步數(shù)抽樣。 10.10.5 內(nèi)循環(huán)終止準(zhǔn)則10.3 模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計(jì)常用方法 （1）設(shè)置終止溫度的閾值； （2）設(shè)置外循環(huán)迭代次數(shù)； （3

12、）算法搜索到的最優(yōu)值連續(xù)若干步保持不變； （4）概率分析方法。 10.10.6 外循環(huán)終止準(zhǔn)則模擬退火組合優(yōu)化法 目標(biāo)函數(shù)能量函數(shù)人工溫度T一個(gè)初值較大的數(shù)依據(jù)網(wǎng)絡(luò)的能量和溫度來(lái)決定聯(lián)接權(quán)的調(diào)整量（稱為步長(zhǎng)）。與金屬的退火過(guò)程（Annealing）非常相似模擬退火組合優(yōu)化法基本思想 隨機(jī)地為系統(tǒng)選擇一個(gè)初始狀態(tài)wij(p)，在此初始狀態(tài)下，給系統(tǒng)一個(gè)小的隨機(jī)擾動(dòng)wij(p)，計(jì)算系統(tǒng)的能量變化E=E(wij(p)+wij(p)-E(wij(p) 若 E0 then2.10.1 按均勻分布在0,1區(qū)間取一隨機(jī)數(shù)r；2.10.2 按Boltzmann分布計(jì)算接受本次調(diào)整的概率：P(E( wij(p

13、) +wij(p) ) = 2.10.3 if P(E( wij(p) +wij(p) )r then 轉(zhuǎn)2.2； 算法10-2 模擬退火算法2.7 用 wij(p) +wij(p) 代替 wij(p) ；2.8 if 樣本集中還有未被選用的樣本 then 轉(zhuǎn) 2.1；3 判斷在此溫度下，檢驗(yàn)Metropolis抽樣是否穩(wěn)定。如不穩(wěn)定，則直接轉(zhuǎn)2；4 降低溫度T；5 如果T足夠小，則結(jié)束，否則，轉(zhuǎn)2。 算法10-2 模擬退火算法算法的第2步原則上應(yīng)該對(duì)每一個(gè)樣本調(diào)整每一個(gè)權(quán)，調(diào)整的順序是隨機(jī)的；溫度T的降低 T=T 叫做冷卻率，一般情況下可以在0.8，0.9之間取值 Geman(1984年)：

14、溫度下降必須與時(shí)間的對(duì)數(shù)成反比，網(wǎng)絡(luò)最終才能收斂到全局極小點(diǎn) 算法10-2 模擬退火算法T的初值T0 T0= E(w (h) )；即：取初始系統(tǒng)目標(biāo)函數(shù)（能量）的值 T0=z E(w (h) )。即：取初始系統(tǒng)目標(biāo)函數(shù)（能量）值的若干倍 按照經(jīng)驗(yàn)給出 算法10-2 模擬退火算法調(diào)整量wij(p)的計(jì)算 可以根據(jù)Boltzmann分布或者Gaussian分布來(lái)計(jì)算。也可以用其它的方法。下面討論按Gaussian分布進(jìn)行計(jì)算的方法。我們?nèi)∪缦滦问降腉aussian分布函數(shù)。簡(jiǎn)潔起見(jiàn)，用符號(hào)w代替符號(hào)wij(p)： p(w)= 10.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用 10.5.1 30城市TSP問(wèn)題（d

15、*=4210.741 by D B Fogel） TSP Benchmark 問(wèn)題 41 94;37 84;54 67;25 62; 7 64;2 99;68 58;71 44;54 62;83 69;64 60;18 54;22 60;83 46;91 38;25 38;24 42;58 69;71 71;74 78;87 76;18 40;13 40;82 7;62 32; 58 35;45 21;41 26;44 35;4 5010.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用算法流程 10.5.1 30城市TSP問(wèn)題（d*=4210.741 by D B Fogel） 10.4 模擬退火算法的改進(jìn)模擬

16、退火算法的優(yōu)點(diǎn) 質(zhì)量高； 初值魯棒性強(qiáng)； 簡(jiǎn)單、通用、易實(shí)現(xiàn)。模擬退火算法的缺點(diǎn) 由于要求較高的初始溫度、較慢的降溫速率、較低的終止溫度，以及各溫度下足夠多次的抽樣，因此優(yōu)化過(guò)程較長(zhǎng)。 10.4.1 模擬退火算法的優(yōu)缺點(diǎn)10.4 模擬退火算法的改進(jìn)改進(jìn)的可行方案 （1）設(shè)計(jì)合適的狀態(tài)產(chǎn)生函數(shù)； （2）設(shè)計(jì)高效的退火歷程； （3）避免狀態(tài)的迂回搜索； （4）采用并行搜索結(jié)構(gòu)； （5）避免陷入局部極小，改進(jìn)對(duì)溫度的控制方式； （6）選擇合適的初始狀態(tài)； （7）設(shè)計(jì)合適的算法終止準(zhǔn)則。 10.4.2 改進(jìn)內(nèi)容10.4 模擬退火算法的改進(jìn)改進(jìn)的方式 （1）增加升溫或重升溫過(guò)程，避免陷入局部極?。?（2

17、）增加記憶功能（記憶“Best so far”狀態(tài)）； （3）增加補(bǔ)充搜索過(guò)程（以最優(yōu)結(jié)果為初始解）； （4）對(duì)每一當(dāng)前狀態(tài)，采用多次搜索策略，以概率接受區(qū)域內(nèi)的最優(yōu)狀態(tài)； （5）結(jié)合其它搜索機(jī)制的算法； （6）上述各方法的綜合。 10.4.2 改進(jìn)內(nèi)容10.4 模擬退火算法的改進(jìn)改進(jìn)的思路 （1）記錄“Best so far”狀態(tài)，并即時(shí)更新； （2）設(shè)置雙閾值，使得在盡量保持最優(yōu)性的前提下減少計(jì)算量，即在各溫度下當(dāng)前狀態(tài)連續(xù) m1 步保持不變則認(rèn)為Metropolis抽樣穩(wěn)定，若連續(xù) m2 次退溫過(guò)程中所得最優(yōu)解不變則認(rèn)為算法收斂。 10.4.3 一種改進(jìn)的模擬退火算法10.4 模擬退火算

18、法的改進(jìn)改進(jìn)的退火過(guò)程 （1）給定初溫t0，隨機(jī)產(chǎn)生初始狀態(tài)s，令初始最優(yōu)解s*=s，當(dāng)前狀態(tài)為s(0)=s，i=p=0； （2）令t=ti，以t，s*和s(i)調(diào)用改進(jìn)的抽樣過(guò)程，返回其所得最優(yōu)解s*和當(dāng)前狀態(tài)s(k)，令當(dāng)前狀態(tài)s(i)=s(k)； （3）判斷C(s*)m2? 若是，則轉(zhuǎn)第(6)步；否則，返回第(2)步； （6）以最優(yōu)解s*作為最終解輸出，停止算法。 10.4.3 一種改進(jìn)的模擬退火算法10.4 模擬退火算法的改進(jìn)改進(jìn)的抽樣過(guò)程 （1）令k=0時(shí)的初始當(dāng)前狀態(tài)為s(0)=s(i)，q=0； （2）由狀態(tài)s通過(guò)狀態(tài)產(chǎn)生函數(shù)產(chǎn)生新?tīng)顟B(tài)s，計(jì)算增量C=C(s)-C(s)； （3）

19、若CC(s)? 若是，則令s*=s，q=0；否則，令q=q+1。若C0，則以概率exp(-C/t)接受s作為下一當(dāng)前狀態(tài)； （4）令k=k+1，判斷qm1? 若是，則轉(zhuǎn)第(5)步；否則，返回第(2)步； （5）將當(dāng)前最優(yōu)解s*和當(dāng)前狀態(tài)s(k)返回改進(jìn)退火過(guò)程。 10.4.3 一種改進(jìn)的模擬退火算法10.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用初始溫度的計(jì)算 for i=1:100 route=randperm(CityNum); fval0(i)=CalDist(dislist,route); end t0=-(max(fval0)-min(fval0)/log(0.9); 10.5.1 30城市TSP問(wèn)題（d*=4210.741 by D B Fogel） 10.5 模擬退火算法的實(shí)現(xiàn)與應(yīng)用狀態(tài)產(chǎn)生函數(shù)的設(shè)計(jì) （1）互換操作，隨機(jī)交換兩個(gè)城市的順序； （2）逆序操