智能優(yōu)化算法

1、l 模擬退火算法模擬退火算法(SA)是一種啟發(fā)式算法，它是受加熱金屬的退火過程所啟發(fā)而提出的一種求解組合優(yōu)化問題的一種逼近算法.在某個(gè)溫度下，金屬分子停留在能量小的狀態(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.隨機(jī)產(chǎn)生一個(gè)可行解S0.2.理論上，初始溫度應(yīng)保證平穩(wěn)分布中每一狀態(tài)的概率相等，即其中fij=f(sj)-f(si)如可取t0=K0(右下角),K為充分大的數(shù)而算法(初始溫度算法)Step 1.給定一個(gè)常數(shù)T;溫度to ;常數(shù)Xo(如0.9); Ro = 0.Step 2.在這個(gè)溫度退火L步.記接受狀態(tài)的個(gè)數(shù)為L'，計(jì)算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 .退火退火過程就是在一給定溫度下，由一個(gè)狀態(tài)變到另一個(gè)狀態(tài)，每一個(gè)狀態(tài)到達(dá)的次數(shù)服從一個(gè)概率分布，即基于Metropolis接受準(zhǔn)則的過程，該過程達(dá)到平穩(wěn)時(shí)停止.在狀態(tài)sj時(shí)，產(chǎn)生的狀態(tài)sj被接受的概率為降溫：一種方法：另一種：其中M為溫度下降的總次數(shù).技術(shù)問題：解的表達(dá)形式和鄰域結(jié)構(gòu):要求解的表達(dá)形式簡潔明了易于操作;鄰域中每個(gè)

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

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

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

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

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

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

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

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

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

13、)是一個(gè)連續(xù)函數(shù).我們希望訓(xùn)練一個(gè)NN去逼近函數(shù)f (x).對于一個(gè)固定神經(jīng)元和網(wǎng)絡(luò)結(jié)構(gòu)的NN，網(wǎng)絡(luò)權(quán)可作成一個(gè)向量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ù)的確定因?yàn)楹瘮?shù)f從Rn(右上角)映入Rm，輸入神經(jīng)元的數(shù)目是n，而輸出神經(jīng)元的數(shù)目是m.因此主要問題是確定隱層神經(jīng)元的數(shù)目.雖然連續(xù)函數(shù)可用在隱層具有無窮多神經(jīng)元的NN任意逼近，但在實(shí)際應(yīng)用中不可能用無窮多神經(jīng)元的隱層.一方面，太少的隱層神經(jīng)元會(huì)使NN缺乏一般能力.另一方面，太多的隱層神經(jīng)元會(huì)增加訓(xùn)練NN的時(shí)間以及增加NN的反應(yīng)時(shí)間.在實(shí)際應(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.計(jì)算誤差Ek.-Step 5