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

第10章非確定方法

10.1基本的非確定學(xué)習(xí)算法

10.2模擬退火算法

10.3Cauchy學(xué)習(xí)

10.4相關(guān)的幾個問題

第10章非確定方法確定的方法前幾章所給方法的共同特征非確定的方法生物神經(jīng)網(wǎng)絡(luò)按照概率運行別稱統(tǒng)計方法（StatisticalMethod）。既可以用于學(xué)習(xí)，又可以用于運行

10.1基本的非確定學(xué)習(xí)算法

基本思想從所給的網(wǎng)絡(luò)中“隨機地選取一個聯(lián)接權(quán)”，對該聯(lián)接權(quán)提出一個“偽隨機調(diào)整量”，當(dāng)用此調(diào)整量對所選的聯(lián)接權(quán)進行修改后，如果“被認(rèn)為”修改改進了網(wǎng)絡(luò)的性能，則保留此調(diào)整；否則放棄本次調(diào)整。

10.1基本的非確定學(xué)習(xí)算法基本數(shù)據(jù)結(jié)構(gòu)樣本集：S={(X1,Y1),(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輸出層隱藏層輸入層x2o2omxn…………………W(1)

W(L)W(2)算法10-1

基本統(tǒng)計學(xué)習(xí)算法

1從樣本集S中取一樣本（X,Y）；2將X輸入到網(wǎng)絡(luò)中，計算出實際輸出O；3求出網(wǎng)絡(luò)關(guān)于Y，O的誤差測度E；4隨機地從W(1)，W(2)，…，W(L)中選擇一個聯(lián)接權(quán)wij(p)；5生成一個小隨機數(shù)Δwij(p)；6用Δwij(p)修改wij(p)；算法10-1

基本統(tǒng)計學(xué)習(xí)算法7用修改后的W(1)，W(2)，…，W(L)重新計算X對應(yīng)的實際輸出O′；8求出網(wǎng)絡(luò)關(guān)于Y，O′的誤差測度E′；9如果E′<E，則保留本次對W(1)，W(2)，…，W(L)的修改，否則，根據(jù)概率判斷本次修改是否有用，如果認(rèn)為有用，則保留本次對W(1)，W(2)，…，W(L)的修改，如果認(rèn)為本次修改無用，則放棄它；10重復(fù)上述過程，直到網(wǎng)絡(luò)滿足要求。算法10-1

基本統(tǒng)計學(xué)習(xí)算法目標(biāo)函數(shù)（ObjectiveFunction）誤差測度函數(shù)：實際輸出與理想輸出方差和

計算量從W(1)，W(2)，…，W(L)中隨機地選擇wij

共有n×H1+H1×H2+H2×H3+…+HM-1×m個“變量”可供選擇偽隨機數(shù)偽隨機數(shù)發(fā)生器來產(chǎn)生Δwij(p)；按照所謂的“能量”函數(shù)的分布去計算它算法10-1

基本統(tǒng)計學(xué)習(xí)算法局部極小點當(dāng)E′<E不成立時，考慮使網(wǎng)絡(luò)從局部極小點中逃離出來，必須允許目標(biāo)函數(shù)暫時變壞

循環(huán)控制判斷標(biāo)準(zhǔn)用一個樣本對網(wǎng)絡(luò)的某一個聯(lián)接權(quán)進行修改后，是隨機地抽取另一個聯(lián)接權(quán)進行重復(fù)，還是再選擇下一個樣本進行重復(fù)對一個選定的樣本，每次是否可以選取若干個聯(lián)接權(quán)進行修改？如果可以，還應(yīng)做什么工作？

逃離局部極小點

聯(lián)接權(quán)修改量

太?。郝涞紸點后很難逃離

太大：導(dǎo)致在A、B兩點來回抖動

解決辦法

控制聯(lián)接權(quán)修改量的大?。簷?quán)修改量由大變小

允許暫時變壞

修改量的大小和網(wǎng)絡(luò)的“能量”相關(guān)

模擬退火

ABD逃離局部極小點DBA10.1模擬退火算法及模型

算法的提出

模擬退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等將其應(yīng)用于組合優(yōu)化。算法的目的

解決NP復(fù)雜性問題；克服優(yōu)化過程陷入局部極小；克服初值依賴性。10.1.1物理退火過程10.1模擬退火算法及模型

物理退火過程

什么是退火：退火是指將固體加熱到足夠高的溫度，使分子呈隨機排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列，固體達(dá)到某種穩(wěn)定狀態(tài)。

10.1.1物理退火過程10.1模擬退火算法及模型

物理學(xué)方面的模擬退火概念

固體物理中，金屬結(jié)構(gòu)的穩(wěn)定程度對應(yīng)著一個能量函數(shù)。

當(dāng)溫度高時，原子的運動不穩(wěn)定，能量函數(shù)較高。

如果用淬火的方式驟然降溫，能量函數(shù)就會進入一個局部極小。

10.1.1物理退火過程10.1模擬退火算法及模型

物理學(xué)方面的模擬退火概念

所謂退火，是近似一種雙極限過程：極限一：當(dāng)溫度有改變時，經(jīng)過無窮大時間后，系統(tǒng)可以進入穩(wěn)態(tài)；極限二：溫度以無窮小的速度趨進于絕對零度；

10.1.1物理退火過程10.1模擬退火算法及模型

物理學(xué)方面的模擬退火概念

在以上兩個極限的退火作用下，能量函數(shù)以概率收斂到全局極小。

所謂模擬退火算法，也就是近似構(gòu)造這種雙極限過程，從而獲得全局優(yōu)化的算法．

10.1.1物理退火過程10.1模擬退火算法及模型

物理退火過程

加溫過程——增強粒子的熱運動，消除系統(tǒng)原先可能存在的非均勻態(tài)；等溫過程——對于與環(huán)境換熱而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進行，當(dāng)自由能達(dá)到最小時，系統(tǒng)達(dá)到平衡態(tài)；冷卻過程——使粒子熱運動減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。

10.1.1物理退火過程10.1模擬退火算法及模型

數(shù)學(xué)表述

在溫度T，分子停留在狀態(tài)r滿足Boltzmann概率分布

10.1.1物理退火過程10.1模擬退火算法及模型

數(shù)學(xué)表述

在同一個溫度T，選定兩個能量E1<E2，有

在同一個溫度，分子停留在能量小的狀態(tài)的概率比停留在能量大的狀態(tài)的概率要大。

10.1.1物理退火過程<1>010.1模擬退火算法及模型

數(shù)學(xué)表述

若|D|為狀態(tài)空間D中狀態(tài)的個數(shù)，D0是具有最低能量的狀態(tài)集合：當(dāng)溫度很高時，每個狀態(tài)概率基本相同，接近平均值1/|D|；狀態(tài)空間存在超過兩個不同能量時，具有最低能量狀態(tài)的概率超出平均值1/|D|；當(dāng)溫度趨于0時，分子停留在最低能量狀態(tài)的概率趨于1。能量最低狀態(tài)10.1模擬退火算法及模型

Metropolis準(zhǔn)則（1953）——以概率接受新狀態(tài)

固體在恒定溫度下達(dá)到熱平衡的過程可以用MonteCarlo方法（計算機隨機模擬方法）加以模擬，雖然該方法簡單，但必須大量采樣才能得到比較精確的結(jié)果，計算量很大。

10.1.1物理退火過程10.1模擬退火算法及模型

Metropolis準(zhǔn)則（1953）——以概率接受新狀態(tài)

若在溫度T，當(dāng)前狀態(tài)i→新狀態(tài)j若Ej<Ei，則接受j為當(dāng)前狀態(tài)；否則，若概率p=exp[-(Ej-Ei)/kBT]大于[0,1)區(qū)間的隨機數(shù)，則仍接受狀態(tài)j為當(dāng)前狀態(tài)；若不成立則保留狀態(tài)i為當(dāng)前狀態(tài)。

10.1.1物理退火過程10.1模擬退火算法及模型

Metropolis準(zhǔn)則（1953）——以概率接受新狀態(tài)

p=exp[-(Ej-Ei)/kBT]

在高溫下，可接受與當(dāng)前狀態(tài)能量差較大的新狀態(tài)；在低溫下，只接受與當(dāng)前狀態(tài)能量差較小的新狀態(tài)。

10.1.1物理退火過程10.1模擬退火算法及模型

相似性比較

10.1.2組合優(yōu)化與物理退火的相似性10.1模擬退火算法及模型

基本步驟

給定初溫t=t0，隨機產(chǎn)生初始狀態(tài)s=s0，令k=0；RepeatRepeat產(chǎn)生新狀態(tài)sj=Genete(s)；ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽樣穩(wěn)定準(zhǔn)則滿足；退溫tk+1=update(tk)并令k=k+1；Until算法終止準(zhǔn)則滿足；輸出算法搜索結(jié)果。

10.1.3模擬退火算法的基本思想和步驟10.1模擬退火算法及模型

影響優(yōu)化結(jié)果的主要因素

給定初溫t=t0，隨機產(chǎn)生初始狀態(tài)s=s0，令k=0；RepeatRepeat產(chǎn)生新狀態(tài)sj=Genete(s)；ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽樣穩(wěn)定準(zhǔn)則滿足；退溫tk+1=update(tk)并令k=k+1；Until算法終止準(zhǔn)則滿足；輸出算法搜索結(jié)果。

10.1.3模擬退火算法的基本思想和步驟三函數(shù)兩準(zhǔn)則初始溫度10.1模擬退火算法及模型

定義馬爾科夫性（無后效性）：由時刻t0系統(tǒng)或過程所處的狀態(tài)，可以決定系統(tǒng)或過程在時刻t>0所處的狀態(tài)，而無需借助于t0以前系統(tǒng)或過程所處狀態(tài)的歷史資料。馬爾科夫性過程分布函數(shù)的描述：X(tn-1)=xn-1,即：P{X(tn)<=xn|x(t1=x1),X(t2)=x2,......,X(tn-1)=xn-1}=P{X(tn)<=xn|X(tn-1)<=xn-1},xn€R.

10.2.1馬爾科夫鏈10.2模擬退火算法的馬氏鏈描述

定義

10.2.1馬爾科夫鏈10.2模擬退火算法的馬氏鏈描述

定義

一步轉(zhuǎn)移概率：

n步轉(zhuǎn)移概率：若解空間有限，稱馬爾可夫鏈為有限狀態(tài)；若，稱馬爾可夫鏈為時齊的。

10.2.1馬爾科夫鏈10.2模擬退火算法的馬氏鏈描述

模擬退火算法對應(yīng)了一個馬爾可夫鏈

模擬退火算法：新狀態(tài)接受概率僅依賴于新狀態(tài)和當(dāng)前狀態(tài)，并由溫度加以控制。若固定每一溫度，算法均計算馬氏鏈的變化直至平穩(wěn)分布，然后下降溫度，則稱為時齊算法；若無需各溫度下算法均達(dá)到平穩(wěn)分布，但溫度需按一定速率下降，則稱為非時齊算法。分析收斂性

10.2.2模擬退火算法與馬爾科夫鏈10.3模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計原則

產(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è)計原則

(1)在固定溫度下，接受使目標(biāo)函數(shù)下降的候選解的概率要大于使目標(biāo)函數(shù)上升的候選解概率；(2)隨溫度的下降，接受使目標(biāo)函數(shù)上升的解的概率要逐漸減??；(3)當(dāng)溫度趨于零時，只能接受目標(biāo)函數(shù)下降的解。方法

具體形式對算法影響不大一般采用min[1,exp(-?C/t)]

10.10.2狀態(tài)接受函數(shù)10.3模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計收斂性分析

通過理論分析可以得到初溫的解析式，但解決實際問題時難以得到精確的參數(shù)；初溫應(yīng)充分大；實驗表明

初溫越大，獲得高質(zhì)量解的機率越大，但花費較多的計算時間；

10.10.3初溫10.3模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計方法

（1）均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值得方差為初溫；（2）隨機產(chǎn)生一組狀態(tài)，確定兩兩狀態(tài)間的最大目標(biāo)值差，根據(jù)差值，利用一定的函數(shù)確定初溫；（3）利用經(jīng)驗公式。

10.10.3初溫10.3模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計時齊算法的溫度下降函數(shù)

（1），α越接近1溫度下降越慢，且其大小可以不斷變化；（2），其中t0為起始溫度，K為算法溫度下降的總次數(shù)。

10.10.4溫度更新函數(shù)10.3模擬退火算法關(guān)鍵參數(shù)和操作的設(shè)計

時齊算法——常用的Metropolis抽樣穩(wěn)定準(zhǔn)則

（1）檢驗?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è)計常用方法

（1）設(shè)置終止溫度的閾值；（2）設(shè)置外循環(huán)迭代次數(shù)；（3）算法搜索到的最優(yōu)值連續(xù)若干步保持不變；（4）概率分析方法。

10.10.6外循環(huán)終止準(zhǔn)則模擬退火組合優(yōu)化法

目標(biāo)函數(shù)——能量函數(shù)人工溫度T——一個初值較大的數(shù)依據(jù)網(wǎng)絡(luò)的能量和溫度來決定聯(lián)接權(quán)的調(diào)整量（稱為步長）。與金屬的退火過程（Annealing）非常相似模擬退火組合優(yōu)化法基本思想隨機地為系統(tǒng)選擇一個初始狀態(tài){wij(p)}，在此初始狀態(tài)下，給系統(tǒng)一個小的隨機擾動Δwij(p)，計算系統(tǒng)的能量變化ΔE=E({wij(p)+Δwij(p)})-E({wij(p)})

若ΔE<0則接受若ΔE≥0則依據(jù)概率判斷是否被接受若接受，則系統(tǒng)從狀態(tài){wij(p)}變換到狀態(tài){wij(p)+Δwij(p)}；否則，系統(tǒng)保持不變

模擬退火組合優(yōu)化法在這個過程中，逐漸地降低溫度T。所得的系統(tǒng)狀態(tài)序列{wij(p)