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