蟻群優(yōu)化算法PPTPPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)12去人工蜂群算法 細(xì)菌覓食算法 螢火蟲算法粒子群算法 人工魚群算法 鳥群算法第1頁/共59頁3 GambardellaMacro Dorigo第2頁/共59頁42001年至今1996年-2001年意大利學(xué)者Dorigo1991年Dorigo1991年 啟發(fā)各種改進(jìn)算法的提出，應(yīng)用領(lǐng)域更廣 引起學(xué)者關(guān)注，在應(yīng)用領(lǐng)域得到拓寬ACO首次被系統(tǒng)的提出自然界中真實(shí)蟻群集體行為第3頁/共59頁5F類比：大腸桿菌在人體腸道內(nèi)覓食的過程 信息素：信息素多的地方顯然經(jīng)過這里的螞蟻多，因而會(huì)有更多的螞蟻聚集過來。 正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。第4頁/共59頁6第5

2、頁/共59頁7第6頁/共59頁8相似之處在于：都是優(yōu)先選擇信息素濃度大的路徑。兩者的區(qū)別在于： （1）人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問過的節(jié)點(diǎn)。 （2）人工蟻群選擇路徑時(shí)不是盲目的，而是按一定規(guī)律有意識(shí)地尋找最短路徑。例如在TSP問題中，可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離。第7頁/共59頁9第8頁/共59頁10u 螞蟻k(k=1,2，,m)根據(jù)各個(gè)城市間連接路徑上的信息素濃度決定其下一個(gè)訪問城市，設(shè) 表示t時(shí)刻螞蟻k從城市i轉(zhuǎn)移到城市j的概率，其計(jì)算公式為： ( )( ),( )( )( )0,kisiskkisisijx allowkttsallowttPtsallow tP

3、kiju 信息更新公式為：1(1)(1)( ),01ijijijnkijiiktt 第9頁/共59頁11u 針對(duì)螞蟻釋放信息素問題，等人曾給出3中不同的模型，分別為蟻周系統(tǒng)、蟻量系統(tǒng)和蟻密系統(tǒng)，其計(jì)算公式如下： /kij0,kkiiQ L，第 只螞蟻從城市 訪問城市其他ij/kij0,kiiQ d，第 只螞蟻從城市 訪問城市其他kij0,kiiQ，第 只螞蟻從城市 訪問城市其他其中，Q為常數(shù)，表示螞蟻循環(huán)一次所釋放的信息素總量；L為第k只螞蟻經(jīng)過路徑的長(zhǎng)度；d為城市間的距離。第10頁/共59頁12u 采用分布式控制 u 每個(gè)個(gè)體只能感知局部的信息 u 個(gè)體可以改變環(huán)境 u 具有自組織性 u 是

4、一類概率型的全局搜索方法 u 優(yōu)化過程不依賴于優(yōu)化問題本身的嚴(yán)格數(shù)學(xué)性質(zhì) u 是一種基于多主體(Multi-Agent)的智能算法 u 具有潛在的并行性 第11頁/共59頁13u 子集越大信息正反饋的作用不明顯，搜索的隨機(jī)性增強(qiáng)，造成收斂速度變慢; u 反之，子集越小，搜索的隨機(jī)性減弱，雖然收斂速度較快，但是會(huì)使算法的全局性能降低，影響算法的穩(wěn)定性。信息素?fù)]發(fā)度 的選取 u 信息素?fù)]發(fā)度的大小對(duì)蟻群算法的收斂性能影響極大;u 當(dāng) 比較小時(shí)，搜索的全局性好，但收斂速度變慢; u 當(dāng) 比較大時(shí)，收斂速度比較快，但是容易陷入局部最優(yōu)。第12頁/共59頁14u 啟發(fā)式因子的大小則反映了在蟻群路徑搜索中

5、的隨機(jī)性因素作用的強(qiáng)度;u 啟發(fā)式因子的大小反映了在蟻群路徑搜索中確定性因素作用的強(qiáng)度?？傂畔⒘縌的選取 u 總信息量Q越大，可以加強(qiáng)蟻群搜索時(shí)的正反饋性能，有助于算法的快速收斂。螞蟻的初始分布 u 所有螞蟻初始時(shí)刻放在同一個(gè)城市;u 螞蟻分布在不同的城市中。第13頁/共59頁15u M.Dorigo曾經(jīng)對(duì)經(jīng)典的TSP問題求解復(fù)雜度進(jìn)行過深入的研究，所得到的經(jīng)驗(yàn)結(jié)果表明，算法的時(shí)間復(fù)雜度為O(NCn2m)，NC表示迭代次數(shù)，n表示城市數(shù)，m則表示參與搜索的螞蟻數(shù)量。當(dāng)參與搜索的螞蟻數(shù)量m大致與規(guī)模大小n相等時(shí)，算法的時(shí)間復(fù)雜度變?yōu)镺(NCn3)較強(qiáng)的魯棒性 分布式計(jì)算 易于與其他方法結(jié)合 u需

6、要較長(zhǎng)的搜索時(shí)間u容易出現(xiàn)停滯現(xiàn)第14頁/共59頁16 每次循環(huán)之后給予最優(yōu)解以額外的信息素量 這樣的解被稱為全局最優(yōu)解（global-best solution） 找出這個(gè)解的螞蟻被稱為精英螞蟻(elitist ants)帶精英策略的螞蟻系統(tǒng)（Ant System with elitist strategy, ASelite）是最早的改進(jìn)螞蟻系統(tǒng)。 遺傳算法中的精英策略 螞蟻系統(tǒng)中的精英策略 傳統(tǒng)的遺傳算法可能會(huì)導(dǎo)致最適應(yīng)個(gè)體的遺傳信息丟失 精英策略的思想是保留住一代中的最適應(yīng)個(gè)體第15頁/共59頁17信息素根據(jù)下式進(jìn)行更新 *(1)( )ijijijijtt其中1mkijijk,0,kki

7、jQkL如果螞蟻 在本次循環(huán)中經(jīng)過路徑(i,j)否則*,0,ijQL如果邊(i,j)是所找出的最優(yōu)解的一部分否則第16頁/共59頁18 表示精英螞蟻引起的路徑(i, j)上的信息素量的增加 是所找出的最優(yōu)解的路徑長(zhǎng)度 特點(diǎn)： 是精英螞蟻的個(gè)數(shù) Lu 可以使螞蟻系統(tǒng)找出更優(yōu)的解u 找到這些解的時(shí)間更短 u 精英螞蟻過多會(huì)導(dǎo)致搜索早熟收斂第17頁/共59頁19 蟻群系統(tǒng)的狀態(tài)轉(zhuǎn)移規(guī)則 0arg max ( , ) ( , ) ,ku allowedr ur uqqsS如果按先驗(yàn)知識(shí)選擇路徑否則其中，S根據(jù)下列公式得：到( )( ),( )( )( )0,kijijkkisisijs allowed

8、ttjallowedttPtotherwiseu 一只位于節(jié)點(diǎn)r的螞蟻通過應(yīng)用下式給出的規(guī)則選擇下一個(gè)將要移動(dòng)到的城市s： 第18頁/共59頁20 蟻群系統(tǒng)全局更新原則 1,( , )0,gbLr s如果(r,s) 全局最優(yōu)路徑否則( , )(1)( , )( , )r sr sr su 只有全局最優(yōu)的螞蟻才被允許釋放信息素。 u 目的：使螞蟻的搜索主要集中在當(dāng)前循環(huán)為止所找出的最好路徑領(lǐng)域內(nèi)。 u 全局更新在所有螞蟻都完成它們的路徑之后執(zhí)行，用下式對(duì)所建立的路徑進(jìn)行更新： 第19頁/共59頁21 蟻群系統(tǒng)局部更新原則 u 類似于蟻密和蟻量模型中的更新規(guī)則 u 螞蟻應(yīng)用下列局部更新規(guī)則對(duì)它們所

9、經(jīng)過的邊進(jìn)行信息素更新( , )(1)( , )( , )01r sr sr s其中，u 實(shí)驗(yàn)發(fā)現(xiàn)， 可以產(chǎn)生好的結(jié)果，其中n是城市的數(shù)量， 是由最近的鄰域啟發(fā)產(chǎn)生的一個(gè)路徑長(zhǎng)度nnLnn0Ln1u 局部更新規(guī)則可以有效地避免螞蟻收斂到同一路徑第20頁/共59頁22信息素軌跡更新原則 u在MMAS中，只有一只螞蟻用于在每次循環(huán)后更新信息軌跡。經(jīng)修改的軌跡更新原則如下：u 表示迭代最優(yōu)解或全局最優(yōu)解的值。u在蟻群算法中主要使用全局最優(yōu)解，而在MMAS中則主要使用迭代最優(yōu)解。(1)( )ijbestijijtt1()ijbestbestf s第21頁/共59頁23信息素軌跡的限制 uMMAS對(duì)信息

10、素軌跡的最小值和最大值分別施加了 和 的限制，從而使得對(duì)所有信息素軌跡 ，有u 的選取要基于兩點(diǎn)假設(shè)：1.最優(yōu)解在搜索停滯發(fā)生之前不久被找出。2.對(duì)解構(gòu)造的主要影響是由信息素軌跡的上限與下限之間的相對(duì)差異決定minmaxm inm ax( )ijtm ax11( )()ijttio p titfsmin第22頁/共59頁24信息素軌跡的平滑化u基本思想：通過增加選擇有著低強(qiáng)度信息素軌跡量解元素的概率以提高探索新解的能力u平滑機(jī)制有助于對(duì)搜索空間進(jìn)行更有效的探索*max( )( )( )( )ijijijtttt *( )( )ijijtt其中,01,和分別為平滑化之前和之后的信息素軌跡量第23

11、頁/共59頁25第24頁/共59頁26第25頁/共59頁27TSP問題u問題描述：旅行商按一定的順序訪問n個(gè)城市，使得每個(gè)城市都被訪問且僅能被訪問一次而使花費(fèi)代價(jià)最小，從圖論的觀點(diǎn)來看，就是找出一個(gè)最短的封閉回路。uTSP的求解是NP-hard問題。隨著城市數(shù)目的增多,問題空間將呈指數(shù)級(jí)增長(zhǎng)uTSP在許多工程領(lǐng)域具有廣泛的應(yīng)用價(jià)值，例如電路板布線、機(jī)器人控制、交通路由等。第26頁/共59頁28第27頁/共59頁29下面以TSP為例說明基本蟻群算法模型。u首先將m只螞蟻隨機(jī)放置在n個(gè)城市，位于城市i的第k只螞蟻選擇下一個(gè)城市j的概率為: u 表示邊（i，j）上的信息素濃度； 是啟發(fā)信息，d是城市

12、i和j之間的距離；和反映了信息素與啟發(fā)信息的相對(duì)重要性； 表示螞蟻k已經(jīng)訪問過的城市列表。) 1 (,0,),(),(),(),(),(otherwisetabujifsisijijijiPktabuskk),(ji),(/1),(jidjiktabu第28頁/共59頁30u當(dāng)所有螞蟻完成周游后，按以下公式進(jìn)行信息素更新。u其中，為小于1的常數(shù)，表示信息的持久性。)2()()(1mkkijijijijijtnt)3(0otherwiselijLQkkkiju其中，Q為常數(shù)； 表示第k只螞蟻在本次迭代中走過的路徑長(zhǎng)度。kL第29頁/共59頁31InitializationDistribute t

13、he ants, Modify the tabu Calculate the probability of moving between citiesi+Update pheromone between cities Meet the requirement of the solution Number of traverse city i=1outputMove to j and modify the tabuNYCalculate the distance each ant walks the loopYNEach ant choose the next city 第30頁/共59頁32第

14、31頁/共59頁33第32頁/共59頁34第33頁/共59頁35第34頁/共59頁361.5602e+04ACATSP(C,100,10,1,5,0.1,100)第35頁/共59頁37第36頁/共59頁38趨向性操作設(shè)細(xì)菌種群大小為S，一個(gè)細(xì)菌所處的位置表示一個(gè)問題的候選解，細(xì)菌i的信息用D維向量表示為12,1,2,iiiiDiS 細(xì)菌i在第j次趨向性操作、第k次復(fù)制操作和第l次遷徙操作之后的位置表示為細(xì)菌i的每一步趨向性操作表示如下：(1, , )( , , )( ) ( )iijk lj k lC ijC(i)0 表示向前游動(dòng)的步長(zhǎng)單位 表示旋轉(zhuǎn)后選擇的一個(gè)隨機(jī)前進(jìn)方向( ) j第37頁/

15、共59頁39第38頁/共59頁40第39頁/共59頁41F類比：其他群智能算法的聚群行為：l花蜜源比較差的偵查蜂轉(zhuǎn)向花蜜源比較好的偵查蜂，變成跟隨蜂 -舞蹈l 亮度比較弱的螢火蟲轉(zhuǎn)向亮度比較好的螢火蟲-熒光素第40頁/共59頁42F其他群智能算法的淘汰機(jī)制：l花蜜源比較差的偵查蜂轉(zhuǎn)向花蜜源比較好的偵查蜂過程 淘汰花蜜源比較差的蜜蜂l螢火蟲亮度比較弱的淘汰第41頁/共59頁43前提經(jīng)過復(fù)制操作后算法的種群大小不變第42頁/共59頁44第43頁/共59頁45第44頁/共59頁46輸入：運(yùn)行相關(guān)的參數(shù)組初始化（菌落在搜索環(huán)境中隨機(jī)散開，并初始化每一個(gè)個(gè)體的健康指標(biāo)向量，三層循環(huán)的l,j,k索引均為0

16、）驅(qū)散索引：l=l+1jNc?復(fù)制（依據(jù)health進(jìn)行排序，淘汰后一半，復(fù)制前一半）驅(qū)散（對(duì)每一個(gè)細(xì)菌：取一隨機(jī)數(shù)，若小于驅(qū)散概率，則重新初始化）kNre?lNed?復(fù)制索引:k=k+1尋優(yōu)終止輸出環(huán)境最好的位置和相應(yīng)值趨向索引:j=j+1種群趨向是重初始趨向索引重初始化趨向，復(fù)制索引j=0,k=0第45頁/共59頁47第46頁/共59頁48自適應(yīng)步長(zhǎng)調(diào)整策略 在趨向行為中，原始BFO使用固定步長(zhǎng)求解問題不利于算法的收斂。因此提出了一種基于細(xì)菌擁擠度的自適應(yīng)步長(zhǎng)調(diào)整策略。當(dāng) crowd較小時(shí)，細(xì)菌以較大的步長(zhǎng)尋優(yōu); 當(dāng)crowd 較大時(shí)，細(xì)菌以較小的步長(zhǎng)尋優(yōu)。這樣能夠保證算法在優(yōu)化初期有很強(qiáng)

17、的全局搜索能力，在優(yōu)化后期有很強(qiáng)的局部開采能力。第47頁/共59頁49基于環(huán)境感知的細(xì)菌覓食優(yōu)化算法 在趨向行為中，賦予細(xì)菌對(duì)周圍細(xì)菌狀態(tài)進(jìn)行感知。在執(zhí)行中，所有細(xì)菌按照適應(yīng)度分成兩類：l優(yōu)于適應(yīng)度平均值的，通過追蹤最優(yōu)細(xì)菌進(jìn)行搜索；l劣于適應(yīng)度平均值的，通過追蹤細(xì)菌群體中心位置進(jìn)行搜索。第一種情況：相當(dāng)于細(xì)菌位置的精細(xì)搜索。第二種情況：有助于全局最優(yōu)和快速收斂。第48頁/共59頁50具有協(xié)同思想的細(xì)菌覓食優(yōu)化算法 針對(duì)細(xì)菌趨向行為中隨機(jī)翻轉(zhuǎn)和游動(dòng)環(huán)節(jié)，引入PSO算法粒子向個(gè)體和社會(huì)學(xué)習(xí)的思想，賦予細(xì)菌能夠記憶當(dāng)前細(xì)菌群體的最優(yōu)位置和最優(yōu)解。l在翻轉(zhuǎn)過程中適應(yīng)度變差，則向群體最優(yōu)學(xué)習(xí)。l若隨機(jī)轉(zhuǎn)向失效，則反方向?qū)W習(xí)。除此之外：F基于免疫進(jìn)化的細(xì)菌覓食優(yōu)化算法F基于高斯分布的細(xì)菌覓食算法第49頁/共59頁51車間調(diào)度問題（Job-Scheduling Problem，簡(jiǎn)稱JSP），指車間有一些機(jī)器和一些工件，每個(gè)工件都有其特定的加工順序，現(xiàn)用m臺(tái)機(jī)器加工n