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

智能優(yōu)化方法

AI-BasedOptimizationMethodsByProfessorDingweiWangNortheasternUniversityChina20041智能優(yōu)化方法

AI-BasedOptimizationM第六章最近發(fā)展起來的新算法一.蟻群優(yōu)化ACO二.粒子群優(yōu)化三.其它新方法四.我們的工作：群落選址算法2第六章最近發(fā)展起來的新算法一.蟻群優(yōu)化ACO2蟻群優(yōu)化的產(chǎn)生 蟻群優(yōu)化AntColonyOptimization在1995-1996年，Dorigo(Italy)提出ACO基本思想 模擬螞蟻選擇路線的能力。即：螞蟻以信息素的強度為概率來決定路線選擇。一.蟻群優(yōu)化（1）3蟻群優(yōu)化的產(chǎn)生一.蟻群優(yōu)化（1）3ACO整體往往大于部分的“簡單和”螞蟻的低智能——蟻群的高智慧螞蟻的簡單行為——蟻群的智能突現(xiàn)實際蟻群的覓食1、主體（agent)：螞蟻2、簡單的規(guī)則（rules）：分工、通訊3、相互作用（interaction）： 螞蟻<==觸角放電==>螞蟻螞蟻<==氣味積累==>環(huán)境4ACO整體往往大于部分的“簡單和”4ACO觀察實際蟻群的覓食1：5ACO觀察實際蟻群的覓食1：5ACO觀察實際蟻群的覓食2：

用障礙物切斷原來的通路6ACO觀察實際蟻群的覓食2：用障礙物切斷原來的通路6ACO觀察實際蟻群的覓食3：

搜索新路7ACO觀察實際蟻群的覓食3：搜索新路7ACO觀察實際蟻群的覓食4：最佳路徑形成8ACO觀察實際蟻群的覓食4：最佳路徑形成8ACO的基本計算公式 ACO最早用來解決TSP問題一.蟻群優(yōu)化（2）螞蟻標號迭代次數(shù)信息素的影響9ACO的基本計算公式一.蟻群優(yōu)化（2）螞蟻標號迭代次數(shù)信息素一.蟻群優(yōu)化（3）10一.蟻群優(yōu)化（3）10舉例說明一.蟻群優(yōu)化（4）1534211舉例說明一.蟻群優(yōu)化（4）1534211信息素強度的計算一.蟻群優(yōu)化（5）螞蟻k的巡回長度常量所有螞蟻留下的信息信息素增量遺忘因子12信息素強度的計算一.蟻群優(yōu)化（5）螞蟻k的巡回長度常量所有螞ACO的基本算法步驟初始化令S=1,(S是tabu表的指標，即走過的城市數(shù))將所有的初始城市記入一.蟻群優(yōu)化（6）13ACO的基本算法步驟一.蟻群優(yōu)化（6）13重復以下步驟，直到tabu表填滿（所有城市 走過）。令S=S+1,對k=1到m個城市，以選擇城市j移動，將j加入。對

（計算信息素，理解為每個螞蟻在路徑(i,j)上留下的總氣味）一.蟻群優(yōu)化（7）14重復以下步驟，直到tabu表填滿（所有城市一.蟻群優(yōu)化（7）對若NC大于 停止，否則轉(zhuǎn)②，并清空tabu表一.蟻群優(yōu)化（8）15對一.蟻群優(yōu)化（8）15粒子群優(yōu)化（ParticleSwarmOptimization）PSO的產(chǎn)生1995年，Kennedy&Eberhart提出PSOPSO已經(jīng)成為當今的熱門2003年，《控制與決策》第二期刊登國內(nèi)第一篇PSO論文——綜述文章二.粒子群優(yōu)化（1）16粒子群優(yōu)化（ParticleSwarmOptimizatPSO的基本思想 模仿鳥群的飛行，覓食行為特征（用Swarm仿真軟件仿真）保持慣性按自身的最優(yōu)修正方向按群體的最優(yōu)修正方向二.粒子群優(yōu)化（2）17PSO的基本思想二.粒子群優(yōu)化（2）17PSO的特點 公式簡單，待定系數(shù)少，可用來解實優(yōu)化二.粒子群優(yōu)化（3）18PSO的特點二.粒子群優(yōu)化（3）18PSO的基本公式二.粒子群優(yōu)化（4）過去的方向個體最優(yōu)方向，第d個分量群體最優(yōu)方向19PSO的基本公式二.粒子群優(yōu)化（4）過去的方向個體最優(yōu)方向其中：二.粒子群優(yōu)化（5）20其中：二.粒子群優(yōu)化（5）20PSO的計算步驟初始化粒子群，給予隨機的位置和速度評估每個粒子的適應值 （目標函數(shù)值）對每個粒子，更新歷史最優(yōu)位置對群體更新歷史最好解二.粒子群優(yōu)化（6）21PSO的計算步驟二.粒子群優(yōu)化（6）21對所有粒子計算若達到最大迭代數(shù)停止，否則轉(zhuǎn)② 以上就是PSO最早最初始的經(jīng)典算法，以后有多種改進。二.粒子群優(yōu)化（7）22對所有粒子計算二.粒子群優(yōu)化（7）22文化算法（CultureAlgorithm）文化算法的基本思想： 借鑒不同文化的相互排斥的特性，用到進化算法中。三.其它新方法（1）23文化算法（CultureAlgorithm）三.其它新方掠奪搜索策略（PSS）掠奪搜索策略的基本思想： 模仿猛獸的捕食策略（廣域與鄰域有效結(jié)合起來）。三.其它新方法（2）24掠奪搜索策略（PSS）三.其它新方法（2）24人工生命算法人工生命算法的基本思想： 模仿生態(tài)環(huán)境中多種種群的相互作用。三.其它新方法（3）25人工生命算法三.其它新方法（3）25ALA食物鏈：（來自生物學的解釋）生產(chǎn)者所固有的能量和物質(zhì)，通過一系列取食和被食的關系在生態(tài)系統(tǒng)中傳遞，各種生物按其食物關系排列的鏈狀順序稱為食物鏈（foodchain)。簡單的生物鏈（下圖所示）26ALA食物鏈：（來自生物學的解釋）26食物鏈模式的人工生命算法思想定義食物鏈:Resource：Artificialorganism說明：1、定義了四種資源：ResourceB,W,R和G；2、定義四種生物：Blue,white，Red和Green；3、定義它們之間的取食關系：White生物吃藍色資源，白色廢物；White白色廢物，成為紅色生物的資源。其他，依次類推。Resource(B)Resource(G)Resource(R)Resource(W)WhiteRedGreenBlue

White生物吃藍色資源，產(chǎn)生白色廢物

White白色廢物，成為紅色生物的資源27食物鏈模式的人工生命算法思想:Resource：ArtifiALA算法描述：Step1:初始化（initalization）產(chǎn)生四種相等數(shù)量的人工生物，并隨機的布置在人工環(huán)境之中；每種人工生物的初始能量是Ie；產(chǎn)生四種相等數(shù)量的資源隨機的布置在人工環(huán)境之中；設定最大代數(shù)。Step2:尋找資源（searchresource)人工生物在它們的鄰域內(nèi)，從當前位置尋找離它最近的資源28ALA算法描述：28ALAStep3：移動時使用優(yōu)值保留策略（elitereservationstrategy）：首先，如果它們發(fā)現(xiàn)它們想吃的最近的資源在它們的鄰域內(nèi)，它們就移向它；其次，如果不是這樣，它們就隨機的在它們的鄰域內(nèi)移動；當隨機移動時，采用優(yōu)值保留策略即：如果人工生物有高的適值，那么它們移動最小的距離，以便僅輕微的改變適值，并甚至得到能量Ee。因此具有更高適值的生物有更多的機會生存。29ALAStep3：移動時使用優(yōu)值保留策略（eliteresALAStep4:新陳代謝（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)。30ALAStep4:新陳代謝（Metabolism）：30ALAStep7:減少能量（ReduceEnergy）：所有的生物將減少能量Le。如果某個人工生物的能量少有Ld，則它將死掉，同時從人工環(huán)境中移走。Step8:增長代數(shù)（Increasinggenernation）：代數(shù)增加1；如果代數(shù)小于結(jié)束的代數(shù)，返回Step2；否則結(jié)束計算。31ALAStep7:減少能量（ReduceEnergy）ALA韓國學者Bo-SukYang等人在《Optimumdesignofshortjournalbearingsbyartificiallifealgorithm》一文中，應用該算法進行短經(jīng)向軸承的優(yōu)化設計。32ALA韓國學者Bo-SukYang等人在《Optimum四.我們的工作：群落選址算法

ColonyLocationAlgorithm(CLA)基本思想模擬植物群落形成機制－－土地含有的適于植物生長營養(yǎng)成分；不同物種間對生存資源的競爭；人工干預手段——施肥策略。33四.我們的工作：群落選址算法

ColonyLocationCLA養(yǎng)分函數(shù)Nij(t):在t時刻，土地j對群落i的養(yǎng)分。加上時間t，是因為施肥可以改變肥力。對于指派問題，A為工作時間，（極小化）Nij(t)＝1／aij,即可。對于TSP，Nij(t)＝1／dij,即可。對于QAP，怎么設？34CLA養(yǎng)分函數(shù)34CLA生長率與衰亡率生長率：r是平均生長率，是所有土地對i的平均肥力。（行均值）35CLA生長率與衰亡率35衰亡率：是土地j對所有群落的肥力的均值。（列均值）CLA36衰亡率：CLA36CLA群落比例與歸一化設xij(t)是群落i在土地j上的比例；生長過程帶來比例的和不是1。行、列歸一化，反復進行。37CLA群落比例與歸一化37生長過程CLA38生長過程CLA38CLA解的構(gòu)成與評估xij(t)不是解。以xij(t)為概率，在每塊土地上產(chǎn)生一個群落，問題是要保證一個群落不能同時在兩塊土地上—解的合法性。其實很簡單，按隨機順序，在剩余群落中選。39CLA解的構(gòu)成與評估39CLA施肥過程若S(k*)是最好解；或者40CLA施肥過程或者40CLA解的信息熵的計算解的信息熵：41CLA解的信息熵的計算41CLA停止判據(jù)停止準則的計算：42CLA停止判據(jù)42指派問題的計算結(jié)果43指派問題的計算結(jié)果4344444545CLATSP的計算結(jié)果全國33城市的TSP計算結(jié)果好于文獻的結(jié)果，但TSP.Lab測試題的計算結(jié)果不好。工作還需要繼續(xù)進行。46CLATSP的計算結(jié)果46CLAQAP的計算結(jié)果自己編的題目計算結(jié)果不錯但對大規(guī)模問題計算效果不好，還需要做很多工作。包括養(yǎng)分函數(shù)的設置方法都還是問題。47CLAQAP的計算結(jié)果47歡迎提問，批評。謝謝大家！48歡迎提問，批評。謝謝大家！48課程全部結(jié)束

謝謝！49課程全部結(jié)束

謝謝！49演講完畢，謝謝觀看！演講完畢，謝謝觀看！智能優(yōu)化方法

AI-BasedOptimizationMethodsByProfessorDingweiWangNortheasternUniversityChina200451智能優(yōu)化方法

AI-BasedOptimizationM第六章最近發(fā)展起來的新算法一.蟻群優(yōu)化ACO二.粒子群優(yōu)化三.其它新方法四.我們的工作：群落選址算法52第六章最近發(fā)展起來的新算法一.蟻群優(yōu)化ACO2蟻群優(yōu)化的產(chǎn)生 蟻群優(yōu)化AntColonyOptimization在1995-1996年，Dorigo(Italy)提出ACO基本思想 模擬螞蟻選擇路線的能力。即：螞蟻以信息素的強度為概率來決定路線選擇。一.蟻群優(yōu)化（1）53蟻群優(yōu)化的產(chǎn)生一.蟻群優(yōu)化（1）3ACO整體往往大于部分的“簡單和”螞蟻的低智能——蟻群的高智慧螞蟻的簡單行為——蟻群的智能突現(xiàn)實際蟻群的覓食1、主體（agent)：螞蟻2、簡單的規(guī)則（rules）：分工、通訊3、相互作用（interaction）： 螞蟻<==觸角放電==>螞蟻螞蟻<==氣味積累==>環(huán)境54ACO整體往往大于部分的“簡單和”4ACO觀察實際蟻群的覓食1：55ACO觀察實際蟻群的覓食1：5ACO觀察實際蟻群的覓食2：

用障礙物切斷原來的通路56ACO觀察實際蟻群的覓食2：用障礙物切斷原來的通路6ACO觀察實際蟻群的覓食3：

搜索新路57ACO觀察實際蟻群的覓食3：搜索新路7ACO觀察實際蟻群的覓食4：最佳路徑形成58ACO觀察實際蟻群的覓食4：最佳路徑形成8ACO的基本計算公式 ACO最早用來解決TSP問題一.蟻群優(yōu)化（2）螞蟻標號迭代次數(shù)信息素的影響59ACO的基本計算公式一.蟻群優(yōu)化（2）螞蟻標號迭代次數(shù)信息素一.蟻群優(yōu)化（3）60一.蟻群優(yōu)化（3）10舉例說明一.蟻群優(yōu)化（4）1534261舉例說明一.蟻群優(yōu)化（4）1534211信息素強度的計算一.蟻群優(yōu)化（5）螞蟻k的巡回長度常量所有螞蟻留下的信息信息素增量遺忘因子62信息素強度的計算一.蟻群優(yōu)化（5）螞蟻k的巡回長度常量所有螞ACO的基本算法步驟初始化令S=1,(S是tabu表的指標，即走過的城市數(shù))將所有的初始城市記入一.蟻群優(yōu)化（6）63ACO的基本算法步驟一.蟻群優(yōu)化（6）13重復以下步驟，直到tabu表填滿（所有城市 走過）。令S=S+1,對k=1到m個城市，以選擇城市j移動，將j加入。對

（計算信息素，理解為每個螞蟻在路徑(i,j)上留下的總氣味）一.蟻群優(yōu)化（7）64重復以下步驟，直到tabu表填滿（所有城市一.蟻群優(yōu)化（7）對若NC大于 停止，否則轉(zhuǎn)②，并清空tabu表一.蟻群優(yōu)化（8）65對一.蟻群優(yōu)化（8）15粒子群優(yōu)化（ParticleSwarmOptimization）PSO的產(chǎn)生1995年，Kennedy&Eberhart提出PSOPSO已經(jīng)成為當今的熱門2003年，《控制與決策》第二期刊登國內(nèi)第一篇PSO論文——綜述文章二.粒子群優(yōu)化（1）66粒子群優(yōu)化（ParticleSwarmOptimizatPSO的基本思想 模仿鳥群的飛行，覓食行為特征（用Swarm仿真軟件仿真）保持慣性按自身的最優(yōu)修正方向按群體的最優(yōu)修正方向二.粒子群優(yōu)化（2）67PSO的基本思想二.粒子群優(yōu)化（2）17PSO的特點 公式簡單，待定系數(shù)少，可用來解實優(yōu)化二.粒子群優(yōu)化（3）68PSO的特點二.粒子群優(yōu)化（3）18PSO的基本公式二.粒子群優(yōu)化（4）過去的方向個體最優(yōu)方向，第d個分量群體最優(yōu)方向69PSO的基本公式二.粒子群優(yōu)化（4）過去的方向個體最優(yōu)方向其中：二.粒子群優(yōu)化（5）70其中：二.粒子群優(yōu)化（5）20PSO的計算步驟初始化粒子群，給予隨機的位置和速度評估每個粒子的適應值 （目標函數(shù)值）對每個粒子，更新歷史最優(yōu)位置對群體更新歷史最好解二.粒子群優(yōu)化（6）71PSO的計算步驟二.粒子群優(yōu)化（6）21對所有粒子計算若達到最大迭代數(shù)停止，否則轉(zhuǎn)② 以上就是PSO最早最初始的經(jīng)典算法，以后有多種改進。二.粒子群優(yōu)化（7）72對所有粒子計算二.粒子群優(yōu)化（7）22文化算法（CultureAlgorithm）文化算法的基本思想： 借鑒不同文化的相互排斥的特性，用到進化算法中。三.其它新方法（1）73文化算法（CultureAlgorithm）三.其它新方掠奪搜索策略（PSS）掠奪搜索策略的基本思想： 模仿猛獸的捕食策略（廣域與鄰域有效結(jié)合起來）。三.其它新方法（2）74掠奪搜索策略（PSS）三.其它新方法（2）24人工生命算法人工生命算法的基本思想： 模仿生態(tài)環(huán)境中多種種群的相互作用。三.其它新方法（3）75人工生命算法三.其它新方法（3）25ALA食物鏈：（來自生物學的解釋）生產(chǎn)者所固有的能量和物質(zhì)，通過一系列取食和被食的關系在生態(tài)系統(tǒng)中傳遞，各種生物按其食物關系排列的鏈狀順序稱為食物鏈（foodchain)。簡單的生物鏈（下圖所示）76ALA食物鏈：（來自生物學的解釋）26食物鏈模式的人工生命算法思想定義食物鏈:Resource：Artificialorganism說明：1、定義了四種資源：ResourceB,W,R和G；2、定義四種生物：Blue,white，Red和Green；3、定義它們之間的取食關系：White生物吃藍色資源，白色廢物；White白色廢物，成為紅色生物的資源。其他，依次類推。Resource(B)Resource(G)Resource(R)Resource(W)WhiteRedGreenBlue

White生物吃藍色資源，產(chǎn)生白色廢物

White白色廢物，成為紅色生物的資源77食物鏈模式的人工生命算法思想:Resource：ArtifiALA算法描述：Step1:初始化（initalization）產(chǎn)生四種相等數(shù)量的人工生物，并隨機的布置在人工環(huán)境之中；每種人工生物的初始能量是Ie；產(chǎn)生四種相等數(shù)量的資源隨機的布置在人工環(huán)境之中；設定最大代數(shù)。Step2:尋找資源（searchresource)人工生物在它們的鄰域內(nèi)，從當前位置尋找離它最近的資源78ALA算法描述：28ALAStep3：移動時使用優(yōu)值保留策略（elitereservationstrategy）：首先，如果它們發(fā)現(xiàn)它們想吃的最近的資源在它們的鄰域內(nèi)，它們就移向它；其次，如果不是這樣，它們就隨機的在它們的鄰域內(nèi)移動；當隨機移動時，采用優(yōu)值保留策略即：如果人工生物有高的適值，那么它們移動最小的距離，以便僅輕微的改變適值，并甚至得到能量Ee。因此具有更高適值的生物有更多的機會生存。79ALAStep3：移動時使用優(yōu)值保留策略（eliteresALAStep4:新陳代謝（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)。80ALAStep4:新陳代謝（Metabolism）：30ALAStep7:減少能量（ReduceEnergy）：所有的生物將減少能量Le。如果某個人工生物的能量少有Ld，則它將死掉，同時從人工環(huán)境中移走。Step8:增長代數(shù)（Increasinggenernation）：代數(shù)增加1；如果代數(shù)小于結(jié)束的代數(shù)，返回Step2；否則結(jié)束計算。81ALAStep7:減少能量（ReduceEnergy）ALA韓國學者Bo-SukYang等人在《Optimumdesignofshortjournalbearingsbyartificiallifealgorithm》一文中，應用該算法進行短經(jīng)向軸承的優(yōu)化設計。82ALA韓國學者Bo-SukYang等人在《Optimum四.我們的工作：群落選址算法

ColonyLocationAlgorithm(CLA)基本思想模擬植物群落形成機制－－土地含有的適于植物生長營養(yǎng)成分；不同物種間對生存資源的競爭；人工干預手段——施肥策略。83四.我們的工作：群落選址算法

ColonyLoc