智能優(yōu)化算法_第1頁
智能優(yōu)化算法_第2頁
智能優(yōu)化算法_第3頁
智能優(yōu)化算法_第4頁
智能優(yōu)化算法_第5頁
已閱讀5頁,還剩5頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1、l 模擬退火算法模擬退火算法(SA)是一種啟發(fā)式算法,它是受加熱金屬的退火過程所啟發(fā)而提出的一種求解組合優(yōu)化問題的一種逼近算法.在某個溫度下,金屬分子停留在能量小的狀態(tài)的概率比停留在能量大的狀態(tài)的概率要大.SA在求復(fù)雜優(yōu)化問題最好解中已顯示出其非常的有效性自K i rkpatrick于1983將Metropolis在1953年提出的模擬退火思想應(yīng)用到組合優(yōu)化問題以來,受到大家的普遍關(guān)注.算法(模擬退火算法)Step 1.初始化可行解和溫度.Step 2.根據(jù)Boltzmann概率退火.Step 3.重復(fù)第二步直到穩(wěn)定狀態(tài).Step 4.降溫.Step 5.重復(fù)第二步至第四步直到滿足終止條件或直

2、到給定的步數(shù).Step 6.輸出最好的解作為最優(yōu)解.初始化過程1.隨機產(chǎn)生一個可行解S0.2.理論上,初始溫度應(yīng)保證平穩(wěn)分布中每一狀態(tài)的概率相等,即其中fij=f(sj)-f(si)如可取t0=K0(右下角),K為充分大的數(shù)而算法(初始溫度算法)Step 1.給定一個常數(shù)T;溫度to ;常數(shù)Xo(如0.9); Ro = 0.Step 2.在這個溫度退火L步.記接受狀態(tài)的個數(shù)為L',計算Rk= L'/L.Step 3.如果|Rk一X0|<,停止.否則,如果R(k-1),Rk<X0,則 k=k+l,to=to+T,返回step 2;如果R(k-1), Rk >=X

3、0,則k = k+l, to = to一T,返回step 2;如果R(k-1)>=X0,Rk<=X0,則k=k+l,to=to+T/2,返回step 2;如果R(k-1)<=X0,Rk>=X0,則k=k+l,to=to一T/2,返回step2 .退火退火過程就是在一給定溫度下,由一個狀態(tài)變到另一個狀態(tài),每一個狀態(tài)到達的次數(shù)服從一個概率分布,即基于Metropolis接受準則的過程,該過程達到平穩(wěn)時停止.在狀態(tài)sj時,產(chǎn)生的狀態(tài)sj被接受的概率為降溫:一種方法:另一種:其中M為溫度下降的總次數(shù).技術(shù)問題:解的表達形式和鄰域結(jié)構(gòu):要求解的表達形式簡潔明了易于操作;鄰域中每個

4、鄰居都是可行解,解空間中任何兩狀態(tài)可達.對TSP問題,解S可表示為城市的一個排序.解的鄰域可用不同的操作算子定義,如l 互換操作:即隨機交換解碼中兩不同的字符位置l 逆序操作:即將解碼中兩不同的隨機位置間的字符串逆序l 插入操作:即隨機選擇某個點插入到串中的不同隨機位置如果鄰域中有不是可行解的鄰居,可用罰值法,將其視為可行解,目標值為一個充分大的數(shù).但該法的缺陷是擴大了搜索區(qū)域,從而使計算時間增加.內(nèi)循環(huán)終止準則:常用的有l(wèi) 1.固定步數(shù)2.連續(xù)若干步的目標值變化較小3.由接受和拒絕的比率控制迭代步數(shù)外循環(huán)終止準則:常用的有1.設(shè)置終止溫度的i-值(比較小的正數(shù))2.設(shè)置循環(huán)總數(shù)3.連續(xù)若干步

5、搜索到的最優(yōu)解不再改進4.設(shè)置接受概率遺傳算法遺傳算法(GA)是一種解優(yōu)化問題的隨機搜索方法,它借助于生物進化中的自然選擇和遺傳(即適者生存)的規(guī)律.基本遺傳算法算法(基本遺傳算法)Step 1.隨機初始化pop_size個染色體.Step 2.用交叉算法更新染色體.Step 3.用變異算法更新染色體.Step 4.計算所有染色體的目標值.Step 5.根據(jù)目標值計算每個染色體的適應(yīng)度.Step 6.通過輪盤賭的方法選擇染色體.Step 7.重復(fù)第二至第六步直到終止條件滿足.Step 8.輸出最好的染色體作為最優(yōu)解.為利于遺傳算法的計算,首先要對解進行編碼,編碼后的解稱為染色體.對于約束優(yōu)化問

6、題,遺傳算法是在染色體中進行操作,而把操作結(jié)果解碼后去檢驗其可行性.收斂性:模板理論l 設(shè)遺傳算法中群體和種群的維數(shù)相等,為一個偶數(shù) 維,且不隨代數(shù)的變化而變化;l 適應(yīng)函數(shù)直接選用目標函數(shù);l 種群中的個體通過輪盤賭的方式選取,即第i個染 色體被選中的概率為種群中的一對個體采用隨機交叉的方式產(chǎn)生下一代;每一個基因有相同的變異概率.模板定理我們有如果則從概率意義來說,每代中具有H模板的染色體個數(shù)將隨代數(shù)t的增加而增加.收斂定理l 若變異概率0<pm<1,交叉概率0<=Pc<=1,則 基本遺傳算法不收斂到全局最優(yōu)解.l 如果改進基本遺傳算法按交叉、變異、種群選取之后更新當(dāng)

7、前最優(yōu)染色體(解)的進化循環(huán)過程,則收斂于全局最優(yōu).l 如果改進基本遺傳算法按交叉、變異后就更新當(dāng)前最優(yōu)染色體之后進行種群選取的進化循環(huán)過程,則收斂于全局最優(yōu)。算法實現(xiàn):編碼和解碼-初始化-評價函數(shù)-選擇-交叉-變異編碼與解碼GA的關(guān)鍵問題之一是把解編碼為染色體,也要能把染色體解碼為解.常用的編碼方法有1.常規(guī)碼,即二進制碼2.實數(shù)碼3.根據(jù)問題確定的編碼二進制碼就是0一1編碼.采用0一1碼可以精確地表示整數(shù).用0一1編碼精確表示a到b所有整數(shù),只需編碼長度n初始化群體假設(shè)群體的規(guī)模為pop_size,隨機產(chǎn)生pop_size個染色體作為初始群體.初始化的方法根據(jù)問題的不同而設(shè)計.如對于連續(xù)優(yōu)

8、化問題,可預(yù)估一個含有最優(yōu)解的區(qū)域 (如超平面).在這個區(qū)域中隨機產(chǎn)生一個點,然后檢驗這個解的可行性.如是可行的,則接受為染色體;如不可行,則重新在那個區(qū)域中隨機產(chǎn)生一個點直到是可行點為止.重復(fù)剛才的過程pop_size次得到pop_size個初始染色體.群體的規(guī)模1. 群體的規(guī)模可以設(shè)定為個體編碼長度數(shù)的一個線性倍數(shù)2.群體的規(guī)??梢允且粋€給定數(shù)3.群體的規(guī)模也可以是變化的.當(dāng)連續(xù)多代沒能改變解的性能,則可擴大群體的規(guī)模;若解的改進非常好,則可以減少群體的規(guī)模.評價函數(shù)評價函數(shù)Eval ( V)是根據(jù)每個染色體V的適應(yīng)函數(shù)fitness( V)而得到與其他染色體的比例關(guān)系,可用它決定該染色體

9、被選為種群的概率.如選擇過程交叉運算1. 常用方法一一雙親雙子2.變化交叉位法3.多交叉位法4.雙親單子法5.顯性遺傳法6.單親遺傳法*對于根據(jù)問題確定的編碼,交叉運算可用如下之方法1.隨機選一個交叉位,父代交叉位前的基因分別繼承給兩個后代,兩后代之后的基因分別按對方基因順.序選取不重基因2.不變位法變異運算蟻群優(yōu)化算法Ant Colony OptimizationAlgorith ms(ACOA)是求解組合優(yōu)化問題的一種啟發(fā)式算法,它受螞蟻的社會行為而啟發(fā).在ACOA,計算信息是靠賦予一群人工螞蟻信息素而實現(xiàn)的.ACOA由orig。于1992年提出,在求解許多復(fù)雜優(yōu)化問題中宣示出良好的魯棒性

10、和通用性.問題描述螞蟻在尋找食物過程中,會在他們經(jīng)過的地方留下信息素.這些物質(zhì)能影響后來螞蟻的行動,后到的螞蟻選擇有較多這些物質(zhì)的路徑的可能性比有較少這些物質(zhì)的路徑的可能性大得多.后到的螞蟻留下的信息素會對原有的信息素進行加強.考慮極小化問題(s, f, 偶米噶),其中s是定義域,f是目標函數(shù),而(偶米噶)約束集.組合優(yōu)化問題(S, f,偶米噶)也可描述為一個有向圖問題G=(C,L,T),其中C為頂點集,L為連接頂點C的邊集,而T是一個稱為信息素(淘)的向量.基本蟻群算法算法(蟻群優(yōu)化算法)Step 1.初始化所有的信息素具有同樣的量.Step 2.根據(jù)信息素構(gòu)造人工螞蟻行動路線(解)Step

11、 3.重復(fù)第二步直至所有螞蟻完成一次行動.Step 4.根據(jù)當(dāng)前最好解更新路徑上的信息素.Step 5.重復(fù)第二至第四步直至終止條件滿足.Step 6.輸出最好解作為最優(yōu)解.信息素更新在t時刻,設(shè)S是目前為止的最好可行解,而St是當(dāng)前t時刻的最好可行解.設(shè)f(s)和f (st)是對應(yīng)的目標函數(shù)值.如果,f (St)<f(s),則sßSt,在s的弧上增強信息素,而在其它弧上揮發(fā)信息素.信息素增強和揮發(fā)的方法一:信息素增強和揮發(fā)的方法二(MAX-MIN方法):信息素增強和揮發(fā)的方法三:l 收斂性神經(jīng)網(wǎng)絡(luò)James在1890年描述了神經(jīng)網(wǎng)絡(luò)的基本原理:大腦皮層每一點的活力是由其他點勢

12、能釋放的綜合效能產(chǎn)生的.這一勢能同下面的因素有關(guān):相關(guān)其他點的興奮次數(shù);興奮的強度;與其他不相連的其他點所接受的能量.人工神經(jīng)元人工神經(jīng)元模擬生物神經(jīng)元的行為對輸入信號作權(quán)和運算Y=wo+w1X1+w2X2+wnXn其中X1 , X2 , ,Xn是輸入,w0,wl,w2,wn是權(quán)重,而y是輸出.Sigmoid函數(shù)定義一個沒記憶的非線性函數(shù)(fai)作為激勵函數(shù)來改變輸出值激勵函數(shù)的選取依賴于應(yīng)用問題.如可用sigmoid函數(shù)它的導(dǎo)數(shù)為我們考慮一個單隱層的NN,其中輸入層有n個神經(jīng)元,輸出層有m個神經(jīng)元,而隱含層有p個神經(jīng)元.那么在隱層神經(jīng)元的輸出為因此輸出層神經(jīng)元的輸出為函數(shù)逼近假設(shè),f (x

13、)是一個連續(xù)函數(shù).我們希望訓(xùn)練一個NN去逼近函數(shù)f (x).對于一個固定神經(jīng)元和網(wǎng)絡(luò)結(jié)構(gòu)的NN,網(wǎng)絡(luò)權(quán)可作成一個向量w.設(shè)F (x, w)是由NN所得出的輸出訓(xùn)練過程是尋找權(quán)向量w以最好地逼近函數(shù)f(x).設(shè)是訓(xùn)練數(shù)據(jù)集.我們希望選擇權(quán)向量w使得F(x*, w)對于輸入x*i(小寫)來說最接近要求的輸出y*i.即,訓(xùn)練過程是找權(quán)向量w以極小化以下的誤差函數(shù)神經(jīng)元數(shù)的確定因為函數(shù)f從Rn(右上角)映入Rm,輸入神經(jīng)元的數(shù)目是n,而輸出神經(jīng)元的數(shù)目是m.因此主要問題是確定隱層神經(jīng)元的數(shù)目.雖然連續(xù)函數(shù)可用在隱層具有無窮多神經(jīng)元的NN任意逼近,但在實際應(yīng)用中不可能用無窮多神經(jīng)元的隱層.一方面,太少的隱層神經(jīng)元會使NN缺乏一般能力.另一方面,太多的隱層神經(jīng)元會增加訓(xùn)練NN的時間以及增加NN的反應(yīng)時間.在實際應(yīng)用中,可根據(jù)具體問題通過適當(dāng)增加或減少神經(jīng)元數(shù)目來確定隱層神經(jīng)元數(shù).反向傳播算法算法(反向傳播算法)Step 1.初始化權(quán)向量w,Step 2. k<-k+1.-Step 3.調(diào)整權(quán)重w.-Step 4.計算誤差Ek.-Step 5

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論