第六章 最近發(fā)展起來的新算法

智能優(yōu)化方法

AI-BasedOptimizationMethodsByProfessorDingweiWangNortheasternUniversityChina20041第六章最近開展起來的新算法一.蟻群優(yōu)化ACO二.粒子群優(yōu)化三.其它新方法四.我們的任務(wù)：群落選址算法2蟻群優(yōu)化的產(chǎn)生 蟻群優(yōu)化AntColonyOptimization在1995-1996年，Dorigo(Italy)提出ACO根本思想 模擬螞蟻選擇道路的才干。即：螞蟻以信息素的強(qiáng)度為概率來決議道路選擇。一.蟻群優(yōu)化〔1〕3ACO整體往往大于部分的“簡單和〞螞蟻的低智能——蟻群的高智慧螞蟻的簡單行為——蟻群的智能突現(xiàn)實(shí)踐蟻群的尋食1、主體〔agent)：螞蟻2、簡單的規(guī)那么〔rules〕：分工、通訊3、相互作用〔interaction〕： 螞蟻<==觸角放電==>螞蟻螞蟻<==氣味積累==>環(huán)境4ACO察看實(shí)踐蟻群的尋食1：5ACO察看實(shí)踐蟻群的尋食2：用妨礙物切斷原來的通路6ACO察看實(shí)踐蟻群的尋食3：搜索新路7ACO察看實(shí)踐蟻群的尋食4：最正確途徑構(gòu)成8ACO的根本計(jì)算公式 ACO最早用來處理TSP問題一.蟻群優(yōu)化〔2〕螞蟻標(biāo)號迭代次數(shù)信息素的影響9一.蟻群優(yōu)化〔3〕10舉例闡明一.蟻群優(yōu)化〔4〕1534211信息素強(qiáng)度的計(jì)算一.蟻群優(yōu)化〔5〕螞蟻k的巡回長度常量一切螞蟻留下的信息信息素增量遺忘因子12ACO的根本算法步驟初始化令S=1,(S是tabu表的目的，即走過的城市數(shù))將一切的初始城市記入一.蟻群優(yōu)化〔6〕13反復(fù)以下步驟，直到tabu表填滿〔一切城市 走過〕。令S=S+1,對k=1到m個(gè)城市，以選擇城市j挪動，將j參與。對 〔計(jì)算信息素，了解為每個(gè)螞蟻在途徑(i,j)上留下的總氣味〕一.蟻群優(yōu)化〔7〕14對假設(shè)NC大于 停頓，否那么轉(zhuǎn)②，并清空tabu表一.蟻群優(yōu)化〔8〕15粒子群優(yōu)化〔ParticleSwarmOptimization〕PSO的產(chǎn)生1995年，Kennedy&Eberhart提出PSOPSO曾經(jīng)成為當(dāng)今的搶手2003年，<控制與決策>第二期刊登國內(nèi)第一篇PSO論文——綜述文章二.粒子群優(yōu)化〔1〕16PSO的根本思想 模擬鳥群的飛行，尋食行為特征〔用Swarm仿真軟件仿真〕堅(jiān)持慣性按本身的最優(yōu)修正方向按群體的最優(yōu)修正方向二.粒子群優(yōu)化〔2〕17PSO的特點(diǎn) 公式簡單，待定系數(shù)少，可用來解實(shí)優(yōu)化二.粒子群優(yōu)化〔3〕18PSO的根本公式二.粒子群優(yōu)化〔4〕過去的方向個(gè)體最優(yōu)方向，第d個(gè)分量群體最優(yōu)方向19其中：二.粒子群優(yōu)化〔5〕20PSO的計(jì)算步驟初始化粒子群，給予隨機(jī)的位置和速度評價(jià)每個(gè)粒子的順應(yīng)值 〔目的函數(shù)值〕對每個(gè)粒子，更新歷史最優(yōu)位置對群體更新歷史最好解二.粒子群優(yōu)化〔6〕21對一切粒子計(jì)算假設(shè)到達(dá)最大迭代數(shù)停頓，否那么轉(zhuǎn)② 以上就是PSO最早最初始的經(jīng)典算法，以后有多種改良。二.粒子群優(yōu)化〔7〕22文化算法〔CultureAlgorithm〕文化算法的根本思想： 自創(chuàng)不同文化的相互排斥的特性，用到進(jìn)化算法中。三.其它新方法〔1〕23掠奪搜索戰(zhàn)略〔PSS〕掠奪搜索戰(zhàn)略的根本思想： 模擬猛獸的捕食戰(zhàn)略〔廣域與鄰域有效結(jié)合起來〕。三.其它新方法〔2〕24人工生命算法人工生命算法的根本思想： 模擬生態(tài)環(huán)境中多種種群的相互作用。三.其它新方法〔3〕25ALA食物鏈：〔來自生物學(xué)的解釋〕消費(fèi)者所固有的能量和物質(zhì)，經(jīng)過一系列取食和被食的關(guān)系在生態(tài)系統(tǒng)中傳送，各種生物按其食物關(guān)系陳列的鏈狀順序稱為食物鏈〔foodchain)。簡單的生物鏈〔以下圖所示〕26食物鏈方式的人工生命算法思想定義食物鏈:Resource：Artificialorganism闡明：1、定義了四種資源：ResourceB,W,R和G；2、定義四種生物：Blue,white，Red和Green；3、定義它們之間的取食關(guān)系：White生物吃藍(lán)色資源，白色廢物；White白色廢物，成為紅色生物的資源。其他，依次類推。Resource(B)Resource(G)Resource(R)Resource(W)WhiteRedGreenBlueWhite生物吃藍(lán)色資源，產(chǎn)生白色廢物White白色廢物，成為紅色生物的資源27ALA算法描畫：Step1:初始化〔initalization〕產(chǎn)生四種相等數(shù)量的人工生物，并隨機(jī)的布置在人工環(huán)境之中；每種人工生物的初始能量是Ie；產(chǎn)生四種相等數(shù)量的資源隨機(jī)的布置在人工環(huán)境之中；設(shè)定最大代數(shù)。Step2:尋覓資源〔searchresource)人工生物在它們的鄰域內(nèi)，從當(dāng)前位置尋覓離它最近的資源28ALAStep3：挪動時(shí)運(yùn)用優(yōu)值保管戰(zhàn)略〔elitereservationstrategy〕：首先，假設(shè)它們發(fā)現(xiàn)它們想吃的最近的資源在它們的鄰域內(nèi)，它們就移向它；其次，假設(shè)不是這樣，它們就隨機(jī)的在它們的鄰域內(nèi)挪動；當(dāng)隨機(jī)挪動時(shí)，采用優(yōu)值保管戰(zhàn)略即：假設(shè)人工生物有高的適值，那么它們挪動最小的間隔，以便僅細(xì)微的改動適值，并甚至得到能量Ee。因此具有更高適值的生物有更多的時(shí)機(jī)生存。29ALAStep4:新陳代謝〔Metabolism〕：假設(shè)人工生物發(fā)現(xiàn)最近的資源正是它們想要的吃的〔Metabolism〕，它們就吃了它，并得到能量Ge，并隨機(jī)的產(chǎn)生廢物在鄰域內(nèi)。Step5:年齡增長〔aging〕在這個(gè)過程中，每個(gè)生物的年齡添加1。Step6：復(fù)制〔reproduction〕假設(shè)生物年齡到達(dá)了Ra，并且能量>=Re，它將和最近的同種的同樣滿足上述條件的生物交配。規(guī)那么如下：例如：A，B都滿足年齡到達(dá)了Ra，并且能量>=Re，它們根據(jù)概率Rp來決議是復(fù)制它們本人(clone)還是交配(mate)。30ALAStep7:減少能量〔ReduceEnergy〕：一切的生物將減少能量Le。假設(shè)某個(gè)人工生物的能量少有Ld，那么它將死掉，同時(shí)從人工環(huán)境中移走。Step8:增長代數(shù)〔Increasinggenernation〕：代數(shù)添加1；假設(shè)代數(shù)小于終了的代數(shù)，前往Step2；否那么終了計(jì)算。31ALA韓國學(xué)者Bo-SukYang等人在<Optimumdesignofshortjournalbearingsbyartificiallifealgorithm>一文中，運(yùn)用該算法進(jìn)展短經(jīng)向軸承的優(yōu)化設(shè)計(jì)。32四.我們的任務(wù)：群落選址算法

ColonyLocationAlgorithm(CLA)根本思想模擬植物群落構(gòu)成機(jī)制－－土地含有的適于植物生長營養(yǎng)成分；不同物種間對生存資源的競爭；人工干涉手段——施肥戰(zhàn)略。33CLA營養(yǎng)函數(shù)Nij(t):在t時(shí)辰，土地j對群落i的營養(yǎng)。加上時(shí)間t，是由于施肥可以改動肥力。對于指派問題，A為任務(wù)時(shí)間，〔極小化〕Nij(t)＝1／aij,即可。對于TSP，Nij(t)＝1／dij,即可。對于QAP，怎樣設(shè)？34CLA生長率與衰亡率生長率：r是平均生長率，是一切土地對i的平均肥力?！残芯怠?5衰亡率：是土地j對一切群落的肥力的均值?！擦芯怠矯LA36CLA群落比例與歸一化設(shè)xij(t)是群落i在土地j上的比例；生長過程帶來比例的和不是1。行、列歸一化，反復(fù)進(jìn)展。37生長過程CLA38CLA解的構(gòu)成與評價(jià)xij(t)不是解。以xij(t)為概率，在每塊土地上產(chǎn)生一個(gè)群落，問題是要保證一個(gè)群落不能同時(shí)在兩塊土地上—解的合法性。其實(shí)很簡單，按隨機(jī)順序，在剩余群落中選。39CLA施肥過程假設(shè)S(k*)是最好解；或者40CLA解的信息熵的計(jì)算解的信息熵：41CLA停頓判據(jù)停頓準(zhǔn)那么的計(jì)算：42