《隨機神經網絡ppt課件》由會員分享，可在線閱讀，更多相關《隨機神經網絡ppt課件（49頁珍藏版）》請在裝配圖網上搜索。

第六章 隨機神經網絡,1,隨機網絡：學習運行引入隨機機制 1.存在的問題：以目標函數的極小值，作為學習或運行的目的 BP算法-誤差函數，梯度下降 Hop算法-Hebb規(guī)則-能量函數E 容易陷入局部極小點.,2,①無法避免; 從②入手：將“總是沿梯度下降方向演變”改為”大部分沿梯度下降方向演變，但允許少數情況沿上升方向演變.”,3,目 錄,引言 模擬退火算法的模型 模擬退火算法的簡單應用 模擬退火算法的參數控制問題 Boltzmann機,4,6.1 引言,模擬退火(Simulated Annealing, SA)算法是近年來特別引入注目的一種適用于解大型組合優(yōu)化問題的優(yōu)化方法,算法來源于固體退火原理,其核心在于 模仿熱力學中液體的凍結與結晶或金屬熔液的冷卻與退火過程--物理退火過程和Metropolis準則. 下面分別介紹 SA原理 SA全局優(yōu)化的直觀解釋,5,6.1.1 模擬退火原理,簡單而言,在固體退火時,先將固體加熱使其溫度充分高,再讓其徐徐冷卻,其物理退火過程由以下三部分組成： 加溫過程 等溫過程 冷卻過程,6,6.1.1 模擬退火原理,加溫過程 在固體退火時,先將固體加熱使其溫度充分高,其目的是增強粒子的熱運動,使其偏離平衡位置. 當溫度足夠高時,固體將溶解為液體,固體內部粒子隨溫升變?yōu)闊o序狀, 彼此之間可以自由移動,從而消除系統原先可能存在的非均勻態(tài),使隨后進行的冷卻過程以某一平衡態(tài)為起點. 熔解過程(加熱固體至高溫液態(tài))與系統的熵增過程聯系,系統內部能量也隨溫度的升高而增大.,7,6.1.1 模擬退火原理,等溫過程 物理學的知識告訴我們,對于與周圍環(huán)境交換熱量而溫度不變的封閉系統,系統狀態(tài)的自發(fā)變化總是朝自由能減少的方向進行,當自由能達到最小時,系統達到平衡態(tài). 冷卻過程 目的是使粒子的熱運動減弱并漸趨有序,系統能量逐漸下降,從而得到低能的晶體結構. 徐徐冷卻時粒子就會喪失由于溫度而引起的流動性,漸趨有序,這時原子就會自己排列起來而形成一種純晶體,它們依次地朝各個方向排列成幾十億倍于單個原子大小的距離,這個純晶體狀態(tài)就是該系統的平衡態(tài),亦為最小能量狀態(tài).,8,6.1.1 模擬退火原理,有趣的是: 對一個徐徐冷卻的系統,當這些原子在逐漸失去活力的同時,它們自己就同時地排列而形成一個純晶體,使這個系統的能量達到其最小值. 這里引起特別關注的是,在這個物理系統的冷卻過程中,這些原子是“同時地”把它們自己排列成一個純晶體的. 如果一種金屬熔液是被快速冷卻或潑水使其冷卻的,則它不能達到純晶體狀態(tài),而是變成一種多晶體或非晶體狀態(tài),系統處在這種狀態(tài)時具有較高的能量.,9,6.1.1 模擬退火原理,SA算法就是模仿上述物理系統徐徐退火過程的一種通用隨機搜索技術,人們可用馬爾柯夫鏈的遍歷理論來給它以數學上的描述. 在搜索最優(yōu)解的過程中,SA算法除了可以接受優(yōu)化解外,還基于隨機接受準則(Metropolis準則)有限度地接受惡化解,并且接受惡化解的概率慢慢趨向于0. 這使得算法有可能從局部最優(yōu)中跳出,盡可能找到全局最優(yōu)解,并保證了算法的收斂. SA的思想最早是由Metropolis等(1953)提出的. Metropolis等提出了重要性采樣法,即以概率接受新狀態(tài).,10,對于某一給定溫度，系統若達到熱平衡狀態(tài)(循環(huán)若干次)，則該狀態(tài)下的能量服從Bottzmann分布.,6.1.1 模擬退火原理,11,6.1.1 模擬退火原理,具體而言,在溫度t,由當前狀態(tài)i產生新狀態(tài)j,兩者的能量分別為Ei和Ej,若EjEi則接受新狀態(tài)j為當前狀態(tài)；否則,若概率,大于[0,1)區(qū)間內的隨機數則仍舊接受新狀態(tài)j為當前狀態(tài),若不成立則保留i為當前狀態(tài),其中k為Boltzmann常數. 這種重要性采樣過程在高溫下可接受與當前狀態(tài)能量差較大的新狀態(tài),而在低溫下基本只接受與當前能量差較小的新狀態(tài),而且當溫度趨于零時,就不能接受比當前狀態(tài)能量高的新狀態(tài). 這種接受準則通常稱為Metropolis準則.,12,6.1.1 模擬退火原理,1983年Kirkpatrick等人意識到組合優(yōu)化與物理退火的相似性,并受到Metropolis準則的啟迪,首次把固體的退火過程與組合極小化聯系在一起,他們分別用目標函數和組合極小化問題的解替代物理系統的能量和狀態(tài),從而物理系統內粒子的攝動等價于組合極小化問題的試探. SA是基于Monte Carlo迭代求解策略的一種隨機尋優(yōu)算法. 極小化過程就是: 首先在一個高溫(溫度現在就成為一個控制參數)狀態(tài)下,利用具有概率突跳特性的Metropolis抽樣策略在解空間中進行隨機搜索,伴隨溫度的不斷下降,重復抽樣過程,將有效地“溶化”解空間; 然后慢慢地降低溫度直到系統“結晶”到一個穩(wěn)定解,最終得到問題的全局最優(yōu)解.,13,6.1.1 模擬退火原理,SA算法在組合最優(yōu)化中的成功應用掀起了SA算法研究與應用的高潮. 1991年Dekkers和Aarts探討將SA算法應用于求解連續(xù)優(yōu)化問題. 20世紀90年代以來,SA算法在NN、GA、進化算法等優(yōu)化、學習領域得到極大的應用.,14,6.1.1 模擬退火原理,SA算法的主要精髓是基于Metropolis準則可接受求解過程的惡化解. Metropolis準則為: 粒子在溫度T時趨于平衡的概率為,其中E為溫度T時的內能, ?E為其改變量, k為Boltzmann常數.,15,6.1.1 模擬退火原理,利用上述固體退火原理來模擬求解組合優(yōu)化問題時, 將內能E模擬為目標函數值f,溫度T演化成控制參數t, 并以Metropolis準則的概率,接受惡化解, 按照上述方法即得到解組合優(yōu)化問題的SA算法.,16,6.1.1 模擬退火原理,SA算法的思想為: 由初始解i和控制參數初值t開始,對當前解重復 產生新解 → 計算目標函數差 → 接受或舍棄 的迭代, 并逐步衰減t值, 算法終止時的當前解即為所得近似最優(yōu)解, 這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程.,17,6.1.1 模擬退火原理,退火過程由冷卻進度表(Cooling Schedule)控制,包括控制參數的初值t及其衰減因子?t、每個t值時的迭代次數L和停止條件S.,18,6.1.2 SA全局優(yōu)化的直觀解釋,SA算法最重要的貢獻在于其能以較大的概率求取復雜優(yōu)化問題的全局解. 下面通過連續(xù)函數優(yōu)化的幾何直觀解釋來說明SA算法如何能以較大概率求得全局最優(yōu)解. 考慮如下圖所示的全局優(yōu)化問題.,19,6.1.2 SA全局優(yōu)化的直觀解釋,20,6.1.2 SA全局優(yōu)化的直觀解釋,所謂SA優(yōu)化算法,其實質上相當于對該函數在水平方向上施以振動. 若需逃離極值,則 逃離出局部極值比全局極值需要更小的能量,即振動的幅度更小.,21,6.1.2 SA全局優(yōu)化的直觀解釋,22,6.1.2 SA全局優(yōu)化的直觀解釋,但實際上相反,SA的策略為函數值大,其能量大,即振動的幅度大.,23,6.1.2 SA全局優(yōu)化的直觀解釋,因此,SA算法使得局部極值更容易被逃逸,全局極值更穩(wěn)定. 故求得全局極值的概率較大. 從上述直觀解釋,可以得出SA算法的全局優(yōu)化的原理： 由于優(yōu)化過程中,拒絕惡化解的概率與函數值(能量)大小成正指數關系, 而且局部極值本身更容易被逃逸, 因此迭代變量落入函數值大的局部極值比落入函數值最小(能量最小)的全局極值更有可能產生逃逸.,24,6.2 SA算法的模型,SA算法可以分解為解空間、目標函數和初始解三部分. SA的基本思想: Step 1 初始化:初始溫度T(充分大),初始解狀態(tài)S(是算法迭代的起點),每個T值的迭代次數L Step 2 對k=1,……,L做第(3)至第6步: Step 3 產生新解S’ Step 4 計算增量?t’=C(S’)-C(S),其中C(S)為評價函數,25,6.2 SA算法的模型,Step 5 若?t’0則接受S’作為新的當前解,否則以概率exp(-?t’/T)接受S’作為新的當前解. Step 6 如果滿足終止條件則輸出當前解作為最優(yōu)解,結束程序. 終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法. Step 7 T逐漸減少,且T?0,然后轉第2步. 算法對應流程圖如下所示.,26,6.2 SA算法的模型,27,6.2 SA算法的模型,SA算法新解的產生和接受可分為如下四個步驟: 第一步是由一個產生函數從當前解產生一個位于解空間的新解 第二步是計算與新解所對應的目標函數差 第三步是判斷新解是否被接受,判斷的依據是一個接受準則 第四步是當新解被確定接受時,用新解代替當前解.,28,6.2 SA算法的模型,第一步是由一個產生函數從當前解產生一個位于解空間的新解. 為便于后續(xù)的計算和接受,減少算法耗時,通常選擇由當前新解經過簡單地變換即可產生新解的方法, 如對構成新解的全部或部分元素進行置換、互換等,注意到產生新解的變換方法決定了當前新解的鄰域結構,因而對冷卻進度表的選取有一定的影響.,29,6.2 SA算法的模型,第二步是計算與新解所對應的目標函數差. 第三步是判斷新解是否被接受,判斷的依據是一個接受準則. 最常用的接受準則是Metropo1is準則: 若?t’a，則接受x’為新狀態(tài)，否則仍停留來原狀態(tài)X）.,30,6.2 SA算法的模型,第四步是當新解被確定接受時,用新解代替當前解. 這只需將當前解中對應于產生新解時的變換部分予以實現,同時修正目標函數值即可. 此時,當前解實現了一次迭代.可在此基礎上開始下一輪試驗. 而當新解被判定為舍棄時,則在原當前解的基礎上繼續(xù)下一輪試驗.,31,6.2 SA算法的模型,從算法流程上看,模擬退火算法包括三過程(函數)兩準則,即 狀態(tài)產生過程、 狀態(tài)接受過程、 溫度更新過程、 內循環(huán)終止準則和 外循環(huán)終止準則, 這些環(huán)節(jié)的設計將決定SA算法的優(yōu)化性能. 其中狀態(tài)產生過程和外循環(huán)終止準則根據SA算法應用于不同的領域的不同優(yōu)化問題,其具體過程不同. 其它過程和準則則是SA算法的基本要素,基本不變.,32,6.2 SA算法的模型,A. 狀態(tài)產生函數 設計狀態(tài)產生函數(鄰域函數)的出發(fā)點應該是盡可能保證產生的候選解遍布全部的解空間. 通常,狀態(tài)產生函數由兩部分組成,即產生候選解的方式和候選解產生的概率分布. B. 狀態(tài)接受函數 狀態(tài)接受函數一般以概率的方式給出,不同接受函數的差別主要在于接受概率的形式不同. 設計狀態(tài)接受概率,應該遵循以下原則： ① 在固定溫度下,接受使目標函數值下降的候選解的概率要大于使目標值上升的候選解的概率；,33,6.2 SA算法的模型,② 隨溫度的下降,接受使目標函數值上升的解的概率要逐漸減??； ③ 當溫度趨于零時,只能接受目標函數值下降的解. 狀態(tài)接受函數的引入是SA算法實現全局搜索的最關鍵的因素.,34,C.溫度更新函數 溫度更新函數,即溫度的下降方式,用于在外循環(huán)中修改溫度值. 目前,最常用的溫度更新函數為指數退溫函數,當然還有其它不同的降溫策略.,6.2 SA算法的模型,35,6.2 SA算法的模型,D.內循環(huán)終止準則 內循環(huán)終止準則,或稱Metropolis抽樣穩(wěn)定準則,用于決定在各溫度下產生候選解的數目. 常用的抽樣準則包括： ① 檢驗目標函數的均值是否穩(wěn)定； ② 連續(xù)若干步的目標值變化較?。?③ 按一定的步數抽樣.,36,6.2 SA算法的模型,E.外循環(huán)終止準則 外循環(huán)終止準則,即算法終止準則,用于決定算法何時結束.設置溫度終值是一種簡單的方法. SA算法的收斂性理論中要求溫度終值趨于零,這顯然不合實際.通常的做法是： ① 設置終止溫度的閾值； ② 設置外循環(huán)迭代次數； ③ 算法收斂到的最優(yōu)值連續(xù)若干步保持不變； ④ 檢驗系統熵是否穩(wěn)定.,37,6.3 SA算法的簡單應用,作為SA算法應用,討論貨郎擔問題(TSP): 設有n個城市,用數碼1,…,n代表. 城市i和城市j之間的距離為d(i,j), i, j=1,…,n TSP問題是要找遍訪每個域市恰好一次的一條回路,且其路徑總長度為最短.,38,6.3 SA算法的簡單應用,求解TSP的SA算法模型可描述如下: 解空間 解空間S是遍訪每個城市恰好一次的所有回路,是{1,……,n}的所有循環(huán)排列的集合, S中的成員記為(w1,w2 ,……,wn), 并記wn+1= w1.初始解可選為(1,……,n) 目標函數 此時的目標函數即為訪問所有城市的路徑總長度或稱為代價函數: f(w1, w2 ,…,wn)=sum(d(wj, wj+1)) 我們要求此代價函數的最小值.,39,6.3 SA算法的簡單應用,新解的產生 隨機產生1和n之間的兩相異數k和m,若km,則將 (w1, w2 ,…,wk , wk+1 ,…,wm ,…,wn) 變?yōu)? (wm, wm-1 ,…,w1 , wm+1 ,…,wk-1 ,wn , wn-1 ,…,wk). 上述變換方法可簡單說成是“逆轉中間或者逆轉兩端”.,40,6.3 SA算法的簡單應用,也可以采用其他的變換方法,有些變換有獨特的優(yōu)越性,有時也將它們交替使用,得到一種更好方法. 代價函數差 設將(w1, w2 ,……,wn)變換為(u1, u2 ,……,un), 則代價函數差為,41,6.3 SA算法的簡單應用,根據上述分析,可寫出用SA算法求解TSP問題的偽程序: Procedure TSPSA: begin init-of-T; { T為初始溫度} S={1,……,n}; {S為初始值} termination=false; while termination=false begin for i=1 to L do begin generate(S’ from S); { 從當前回路S產生新回 路S’},42,6.3 SA算法的簡單應用,?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,43,6.3 SA算法的簡單應用,SA算法的應用很廣泛,可以以較高的效率 求解最大截問題(Max Cut Problem)、 0-1背包問題(Zero One Knapsack Problem)、 圖著色問題(Graph Colouring Problem)、 調度問題(Scheduling Problem)等等.,44,6.4 SA算法的參數控制問題,SA算法是一種非常良好的,具有普適性的迭代優(yōu)化算法.其主要性質有： 與初始值無關,算法求得的解與初始解狀態(tài)S(是算法迭代的起點)無關; SA算法具有漸近收斂性,已在理論上被證明是一種以概率1收斂于全局最優(yōu)解的全局優(yōu)化算法; SA算法具有并行性.,45,6.4 SA算法的參數控制問題,SA算法的應用很廣泛,可以求解NP完全問題,但其參數難以控制,其主要問題有以下三點: 溫度T的初始值設置問題. 退火速度問題. 溫度管理問題.,46,6.4 SA算法的參數控制問題,A. 溫度T的初始值設置問題. 初始溫度、溫度更新函數、內循環(huán)終止準則和外循環(huán)終止準則通常被稱為退火歷程(annealing schedule). 實驗表明,初溫越大,獲得高質量解的幾率越大,但花費的計算時間將增加. 初始溫度高,則搜索到全局最優(yōu)解的可能性大,但因此要花費大量的計算時間; 反之,則可節(jié)約計算時間,但全局搜索性能可能受到影響.,47,6.4 SA算法的參數控制問題,因此,初溫的確定是影響SA算法全局搜索性能的重要因素之一,應折衷考慮優(yōu)化質量和優(yōu)化效率, 實際應用過程中,初始溫度一般需要依據實驗結果進行若干次調整.,48,6.4 SA算法的參數控制問題,B. 退火速度問題. SA算法的全局搜索性能也與退火速度密切相關. 一般來說,同一溫度下的“充分”搜索(退火)是相當必要的,但這需要計算時間. 實際應用中,要針對具體問題的性質和特征設置合理的退火平衡條件. C. 溫度管理問題. 溫度管理問題也是SA算法難以處理的問題之一. 實際應用中,由于必須考慮計算復雜度的切實可行性等問題,常采用如下所示的降溫方式: T(t+1)＝k?T(t) 式中k為正的略小于1.00的常數,t為降溫的次數.,49,