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

智能優(yōu)化方法

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

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