1、第10章 非確定方法 10.1 基本的非確定學習算法 10.2 模擬退火算法 10.3 Cauchy學習 10.4 相關的幾個問題 第10章 非確定方法確定的方法前幾章所給方法的共同特征非確定的方法生物神經網絡按照概率運行別稱統計方法（Statistical Method）。既可以用于學習，又可以用于運行 10.1 基本的非確定學習算法 基本思想從所給的網絡中“隨機地選取一個聯接權”，對該聯接權提出一個“偽隨機調整量”，當用此調整量對所選的聯接權進行修改后，如果“被認為”修改改進了網絡的性能，則保留此調整；否則放棄本次調整。 10.1 基本的非確定學習算法基本數據結構樣本集：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 基本的非確定學習算法拓撲結構 x1o1輸出層隱藏層輸入層x2o2omxnW(1) W(L)W(2)算法10-1 基本統計學習算法7 用修改后的W(1) ，W(2) ，W(L)重新計算X對應的實際輸出O；8 求出網絡關于Y，O的誤差測度E；9 如果EE，則保留本次對W(1) ，W(2) ，W(L)的修改， 否則，根據概率判斷本次修改是否有用，如果認為有用，則保留本次對W(1) ，W(2) ，W(L)的修改，如果認為本次修改無用，則放棄它；1

3、0 重復上述過程，直到網絡滿足要求。 算法10-1 基本統計學習算法目標函數（Objective Function）誤差測度函數：實際輸出與理想輸出方差和 計算量 從W(1) ，W(2) ，W(L)中隨機地選擇wij 共有nH1+H1H2+H2H3+HM-1m個“變量”可供選擇偽隨機數偽隨機數發生器來產生wij(p)；按照所謂的“能量”函數的分布去計算它逃離局部極小點 聯接權修改量 太小：落到A點后很難逃離 太大：導致在A、B兩點來回抖動 解決辦法 控制聯接權修改量的大小：權修改量由大變小 允許暫時變壞 修改量的大小和網絡的“能量”相關 模擬退火 ABD逃離局部極小點DBA10.1 模擬退火算

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

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

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

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

8、態，而無需借助于t0以前系統或過程所處狀態的歷史資料。馬爾科夫性過程分布函數的描述：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 模擬退火算法的馬氏鏈描述 定義 一步轉移概率： n步轉移概率： 若解空間有限，稱馬爾可夫鏈為有限狀態； 若 ，稱馬爾可夫鏈為時齊的。 10.2.1 馬爾科夫鏈10.2 模擬退火算法的馬氏鏈描述 模擬退火算法對應了一個馬爾可夫鏈 模擬退火算法：

9、新狀態接受概率僅依賴于新狀態和當前狀態，并由溫度加以控制。 若固定每一溫度，算法均計算馬氏鏈的變化直至平穩分布，然后下降溫度，則稱為時齊算法； 若無需各溫度下算法均達到平穩分布，但溫度需按一定速率下降，則稱為非時齊算法。分析收斂性 10.2.2 模擬退火算法與馬爾科夫鏈10.3 模擬退火算法關鍵參數和操作的設計原則 產生的候選解應遍布全部解空間方法 在當前狀態的鄰域結構內以一定概率方式（均勻分布、正態分布、指數分布等）產生 10.10.1 狀態產生函數10.3 模擬退火算法關鍵參數和操作的設計原則 (1)在固定溫度下，接受使目標函數下降的候選解的概率要大于使目標函數上升的候選解概率； (2)隨

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

11、的函數確定初溫； （3）利用經驗公式。 10.10.3 初溫10.3 模擬退火算法關鍵參數和操作的設計時齊算法的溫度下降函數 （1） ，越接近1溫度下降越慢，且其大小可以不斷變化； （2） ，其中t0為起始溫度，K為算法溫度下降的總次數。 10.10.4 溫度更新函數10.3 模擬退火算法關鍵參數和操作的設計 時齊算法常用的Metropolis抽樣穩定準則 （1）檢驗目標函數的均值是否穩定； （2）連續若干步的目標值變化較小； （3）按一定的步數抽樣。 10.10.5 內循環終止準則10.3 模擬退火算法關鍵參數和操作的設計常用方法 （1）設置終止溫度的閾值； （2）設置外循環迭代次數； （3

12、）算法搜索到的最優值連續若干步保持不變； （4）概率分析方法。 10.10.6 外循環終止準則模擬退火組合優化法 目標函數能量函數人工溫度T一個初值較大的數依據網絡的能量和溫度來決定聯接權的調整量（稱為步長）。與金屬的退火過程（Annealing）非常相似模擬退火組合優化法基本思想 隨機地為系統選擇一個初始狀態wij(p)，在此初始狀態下，給系統一個小的隨機擾動wij(p)，計算系統的能量變化E=E(wij(p)+wij(p)-E(wij(p) 若 E0 then2.10.1 按均勻分布在0,1區間取一隨機數r；2.10.2 按Boltzmann分布計算接受本次調整的概率：P(E( wij(p

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

14、溫度下降必須與時間的對數成反比，網絡最終才能收斂到全局極小點 算法10-2 模擬退火算法T的初值T0 T0= E(w (h) )；即：取初始系統目標函數（能量）的值 T0=z E(w (h) )。即：取初始系統目標函數（能量）值的若干倍 按照經驗給出 算法10-2 模擬退火算法調整量wij(p)的計算 可以根據Boltzmann分布或者Gaussian分布來計算。也可以用其它的方法。下面討論按Gaussian分布進行計算的方法。我們取如下形式的Gaussian分布函數。簡潔起見，用符號w代替符號wij(p)： p(w)= 10.5 模擬退火算法的實現與應用 10.5.1 30城市TSP問題（d

15、*=4210.741 by D B Fogel） TSP Benchmark 問題 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 模擬退火算法的實現與應用算法流程 10.5.1 30城市TSP問題（d*=4210.741 by D B Fogel） 10.4 模擬退火算法的改進模擬

16、退火算法的優點 質量高； 初值魯棒性強； 簡單、通用、易實現。模擬退火算法的缺點 由于要求較高的初始溫度、較慢的降溫速率、較低的終止溫度，以及各溫度下足夠多次的抽樣，因此優化過程較長。 10.4.1 模擬退火算法的優缺點10.4 模擬退火算法的改進改進的可行方案 （1）設計合適的狀態產生函數； （2）設計高效的退火歷程； （3）避免狀態的迂回搜索； （4）采用并行搜索結構； （5）避免陷入局部極小，改進對溫度的控制方式； （6）選擇合適的初始狀態； （7）設計合適的算法終止準則。 10.4.2 改進內容10.4 模擬退火算法的改進改進的方式 （1）增加升溫或重升溫過程，避免陷入局部極小； （2

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

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

19、若CC(s)? 若是，則令s*=s，q=0；否則，令q=q+1。若C0，則以概率exp(-C/t)接受s作為下一當前狀態； （4）令k=k+1，判斷qm1? 若是，則轉第(5)步；否則，返回第(2)步； （5）將當前最優解s*和當前狀態s(k)返回改進退火過程。 10.4.3 一種改進的模擬退火算法10.5 模擬退火算法的實現與應用初始溫度的計算 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問題（d*=4210.741 by D B Fogel） 10.5 模擬退火算法的實現與應用狀態產生函數的設計 （1）互換操作，隨機交換兩個城市的順序； （2）逆序操