《《蟻群優(yōu)化算法》PPT課件》由會員分享，可在線閱讀，更多相關(guān)《《蟻群優(yōu)化算法》PPT課件（29頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、螞蟻的生活習性,蟻群優(yōu)化的起源,蟻群優(yōu)化 (ant colony optimization, ACO)，又名蟻群算法。 1991年意大利學者M.Dorigo在其博士學位論文中首先提出。 通過模擬自然界中螞蟻集體尋徑的行為而提出的一種基于種群的啟發(fā)式仿生進化算法。,蟻群優(yōu)化的特征,一種典型的群體智能模式。 充分利用蟻群能通過個體間簡單的信息傳遞來進行尋優(yōu)。 通過正反饋、分布式協(xié)作進行路徑尋優(yōu)。,正反饋原理：螞蟻釋放信息素(pheromone)。,蟻群優(yōu)化的正反饋機制,旅行商問題（TSP）,旅行商問題（traveling salesman problem, TSP）。 一名商人要遍歷多個城市，各個

2、城市之間可達且距離已知，如何找到在訪問每個城市一次后再回到起點的最短路徑。,TSP問題舉例,TSP問題的解,,蟻群優(yōu)化描述,,蟻群優(yōu)化描述,蟻群優(yōu)化描述,概率分配的實現(xiàn)方法,蟻群優(yōu)化的流程,,帶精英策略的螞蟻系統(tǒng),帶精英策略的螞蟻系統(tǒng),帶精英策略的螞蟻系統(tǒng)（Ant System with elitist strategy）是最早的改進螞蟻系統(tǒng)。 精英策略的思想是保留住一代中的最適應個體。 螞蟻系統(tǒng)中的精英策略： 每次循環(huán)之后給予最優(yōu)解以額外的信息素量。 這樣的解被稱為全局最優(yōu)解（global-best solution）。 找出這個解的螞蟻被稱為精英螞蟻(elitist ants)。,帶精英策

3、略的螞蟻系統(tǒng),信息素根據(jù)下式進行更新,其中,帶精英策略的螞蟻系統(tǒng),表示精英螞蟻引起的路徑(i, j)上的信息素量的增加。,是精英螞蟻的個數(shù)。,是所找出的最優(yōu)解的路徑長度。,帶精英策略的螞蟻系統(tǒng)的特征,可以使螞蟻系統(tǒng)找出更優(yōu)的解。 找到這些解的時間更短。 精英螞蟻過多會導致搜索早熟收斂。,,比較兩組概率,第一組概率： 0.02 0.10 0.02 0.70 0.03 0.03 0.08 0.02 A B C D E F G H 第二組概率： 0.15 0.13 0.10 0.12 0.10 0.15 0.11 0.14 A B C D E F G H,較優(yōu)

4、的解，取不到怎么辦？,蟻群系統(tǒng),蟻群系統(tǒng)(Ant Colony System, ACS)是由Dorigo和Gambardella在1996年提出的。 蟻群系統(tǒng)做了三個方面的改進： 狀態(tài)轉(zhuǎn)移規(guī)則為更好更合理地利用新路徑和利用關(guān)于問題的先驗知識提供了方法。 全局更新規(guī)則只應用于最優(yōu)的螞蟻路徑上。 在建立問題解決方案的過程中，應用局部信息素更新規(guī)則。,蟻群系統(tǒng)狀態(tài)轉(zhuǎn)移規(guī)則,一只位于節(jié)點r的螞蟻通過應用下式給出的規(guī)則選擇下一個將要移動到的城市s,其中，S根據(jù)下列公式得到,,蟻群系統(tǒng)狀態(tài)轉(zhuǎn)移規(guī)則,q是在0,1區(qū)間均勻分布的隨機數(shù)。 q0的大小決定了利用先驗知識與探索新路徑之間的相對重要性。 上述狀態(tài)轉(zhuǎn)移

5、規(guī)則被稱為偽隨機比例規(guī)則。 特點是算法傾向于選擇短的且有著大量信息素的邊作為移動方向。,比較兩組概率,第一組概率： 0.02 0.10 0.02 0.70 0.03 0.03 0.08 0.02 A B C D E F G H 第二組概率： 0.15 0.13 0.10 0.12 0.10 0.15 0.11 0.14 A B C D E F G H,總是取到該較優(yōu)的解，怎么辦？,局部最優(yōu)與全局最優(yōu),最大-最小螞蟻系統(tǒng),蟻群算法將螞蟻的搜索行為集中到最優(yōu)解的附近可以提高解的質(zhì)量和收斂速度，從而改進算法的性能。但這種搜索方式會使早熟收斂行為更容易發(fā)生。 最

6、大-最小螞蟻系統(tǒng)(Max-Min Ant System, MMAS)能將這種搜索方式和一種能夠有效避免早熟收斂的機制結(jié)合在一起，從而使算法獲得最優(yōu)的性能。,最大-最小螞蟻系統(tǒng),為了充分利用循環(huán)最優(yōu)解和到目前為止找出的最優(yōu)解，在每次循環(huán)之后，只有一只螞蟻進行信息素更新。 這只螞蟻可能是找出當前循環(huán)中最優(yōu)解的螞蟻，也可能是找出從實驗開始以來最優(yōu)解的螞蟻。 為避免搜索的停滯，在每個解的元素上的的信息素軌跡量的值域范圍被限制在 區(qū)間內(nèi)。,信息素軌跡更新,在MMAS中，只有一只螞蟻用于在每次循環(huán)后更新信息軌跡。 經(jīng)修改的軌跡更新規(guī)則如下：,表示迭代最優(yōu)解或全局最優(yōu)解的值。,信息素軌跡的限制的原因,不管是選擇迭代最優(yōu)還是全局最優(yōu)螞蟻來進行信息素更新，都可能導致搜索的停滯。 停滯現(xiàn)象發(fā)生的原因：在每個選擇點上一個選擇的信息素軌跡量明顯高于其他的選擇。 避免停滯狀態(tài)發(fā)生的方法：影響用來選擇下一解元素的概率，它直接依賴于信息素軌跡和啟發(fā)信息。 MMAS通過限制信息素軌跡的影響，可以避免各信息素軌跡之間的差異過大。,Thank You !,