蟻群優(yōu)化算法PPT

1、 蟻群優(yōu)化算法蟻群優(yōu)化算法AntAnt Colony Optimization Colony Optimization 2算法介紹算法介紹 群智能算法群智能算法 群智能是一種由簡(jiǎn)單智能的個(gè)體通過某種形式的聚集協(xié)同而表現(xiàn)出智能行群智能是一種由簡(jiǎn)單智能的個(gè)體通過某種形式的聚集協(xié)同而表現(xiàn)出智能行為。它在沒有集中控制，不提供全局模型的前提下尋找復(fù)雜的分布式問題求解為。它在沒有集中控制，不提供全局模型的前提下尋找復(fù)雜的分布式問題求解方案提供了基礎(chǔ)。方案提供了基礎(chǔ)。群智能算法群智能算法通過模仿生物界的進(jìn)化機(jī)理和群體協(xié)作行為而提通過模仿生物界的進(jìn)化機(jī)理和群體協(xié)作行為而提出的仿生類隨機(jī)搜索算法。出的仿生類隨機(jī)

2、搜索算法。去去人工蜂群算法人工蜂群算法 細(xì)菌覓食算法細(xì)菌覓食算法 螢火蟲算法螢火蟲算法粒子群算法粒子群算法 人工魚群算法人工魚群算法 鳥群算法鳥群算法 3蟻群算法的提出蟻群算法的提出 GambardellaMacro Dorigo 4蟻群算法的發(fā)展蟻群算法的發(fā)展2001年至今年至今1996年年-2001年年意大利學(xué)者意大利學(xué)者Dorigo1991年年Dorigo1991年年 啟發(fā)啟發(fā)各種改進(jìn)算法的提出，應(yīng)用領(lǐng)域更廣各種改進(jìn)算法的提出，應(yīng)用領(lǐng)域更廣 引起學(xué)者關(guān)注，在應(yīng)用領(lǐng)域得到拓寬引起學(xué)者關(guān)注，在應(yīng)用領(lǐng)域得到拓寬ACO首次被系統(tǒng)的提出首次被系統(tǒng)的提出自然界中真實(shí)蟻群集體行為自然界中真實(shí)蟻群集體行

3、為 5蟻群算法原理蟻群算法原理如何找到最短路徑如何找到最短路徑 ？ F類比類比：大腸桿菌在人體腸道內(nèi)覓食的過程大腸桿菌在人體腸道內(nèi)覓食的過程 信息素：信息素多的地方顯然經(jīng)過這里的螞蟻多，信息素：信息素多的地方顯然經(jīng)過這里的螞蟻多，因而會(huì)有更多的螞蟻聚集過來。因而會(huì)有更多的螞蟻聚集過來。 正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。者選擇該路徑的概率就越大。 6蟻群算法原理蟻群算法原理自然螞蟻的智能特點(diǎn)自然螞蟻的智能特點(diǎn) 7蟻群算法原理蟻群算法原理人工螞蟻的模型人工螞蟻的模型 8蟻群算法原理蟻群算法原理自然蟻群與人工蟻群自然蟻

4、群與人工蟻群 相似之處相似之處在于：都是優(yōu)先選擇信息素濃度大的路徑。在于：都是優(yōu)先選擇信息素濃度大的路徑。兩者的區(qū)別兩者的區(qū)別在于：在于： （1）人工蟻群有一定的記憶能力，能夠記憶已經(jīng)）人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問過的節(jié)點(diǎn)。訪問過的節(jié)點(diǎn)。 （2）人工蟻群選擇路徑時(shí)不是盲目的，而是按一）人工蟻群選擇路徑時(shí)不是盲目的，而是按一定規(guī)律有意識(shí)地尋找最短路徑。例如在定規(guī)律有意識(shí)地尋找最短路徑。例如在TSP問題中，問題中，可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離。可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離。 9求解組合優(yōu)化問題的蟻群算法求解組合優(yōu)化問題的蟻群算法 10基本蟻群算法基本蟻群算法u

5、 螞蟻螞蟻k(k=1,2k(k=1,2，,m),m)根據(jù)各個(gè)城市間連接路徑上的信根據(jù)各個(gè)城市間連接路徑上的信息素濃度決定其下一個(gè)訪問城市，設(shè)息素濃度決定其下一個(gè)訪問城市，設(shè) 表示表示t t時(shí)刻螞蟻時(shí)刻螞蟻k k從城市從城市i i轉(zhuǎn)移到城市轉(zhuǎn)移到城市j j的概率，其計(jì)算公式為：的概率，其計(jì)算公式為： ( )( ),( )( )( )0,kisiskkisisijx allowkttsallowttP tsallow tPkiju 信息更新公式為：信息更新公式為：1(1)(1)( ),01ijijijnkijiiktt 11基本蟻群算法基本蟻群算法u 針對(duì)螞蟻釋放信息素問題，針對(duì)螞蟻釋放信息素問題

6、，M.DorigoM.Dorigo等人曾給出等人曾給出3 3中中不同的模型，分別為蟻周系統(tǒng)、蟻量系統(tǒng)和蟻密系統(tǒng)，不同的模型，分別為蟻周系統(tǒng)、蟻量系統(tǒng)和蟻密系統(tǒng)，其計(jì)算公式如下：其計(jì)算公式如下： 1.Ant-cycle/kij0,kkiiQ L，第 只螞蟻從城市 訪問城市其他2.Ant-quantityij/kij0,kiiQ d，第 只螞蟻從城市 訪問城市其他3.Ant-densitykij0,kiiQ，第 只螞蟻從城市 訪問城市其他其中，其中，Q Q為常數(shù)，表示螞蟻循環(huán)一次所釋放的信息素總量；為常數(shù)，表示螞蟻循環(huán)一次所釋放的信息素總量；L L為第為第k k只螞蟻經(jīng)只螞蟻經(jīng)過路徑的長(zhǎng)度；過路徑

7、的長(zhǎng)度；d d為城市間的距離。為城市間的距離。 12蟻群算法的主要特點(diǎn)蟻群算法的主要特點(diǎn)u 采用分布式控制采用分布式控制 u 每個(gè)個(gè)體只能感知局部的信息每個(gè)個(gè)體只能感知局部的信息 u 個(gè)體可以改變環(huán)境個(gè)體可以改變環(huán)境 u 具有自組織性具有自組織性 u 是一類概率型的全局搜索方法是一類概率型的全局搜索方法 u 優(yōu)化過程不依賴于優(yōu)化問題本身的嚴(yán)格數(shù)學(xué)性質(zhì)優(yōu)化過程不依賴于優(yōu)化問題本身的嚴(yán)格數(shù)學(xué)性質(zhì) u 是一種基于多主體是一種基于多主體(Multi-Agent)(Multi-Agent)的智能算法的智能算法 u 具有潛在的并行性具有潛在的并行性 13蟻群算法參數(shù)選擇蟻群算法參數(shù)選擇蟻群數(shù)量蟻群數(shù)量m的

8、選擇的選擇 u 子集越大信息正反饋的作用不明顯，搜索的隨機(jī)性增強(qiáng)，造成收子集越大信息正反饋的作用不明顯，搜索的隨機(jī)性增強(qiáng)，造成收斂速度變慢斂速度變慢; ; u 反之，子集越小，搜索的隨機(jī)性減弱，雖然收斂速度較快，但是反之，子集越小，搜索的隨機(jī)性減弱，雖然收斂速度較快，但是會(huì)使算法的全局性能降低，影響算法的穩(wěn)定性。會(huì)使算法的全局性能降低，影響算法的穩(wěn)定性。信息素?fù)]發(fā)度信息素?fù)]發(fā)度 的選取的選取 u 信息素?fù)]發(fā)度信息素?fù)]發(fā)度的大小對(duì)蟻群算法的收斂性能影響極大的大小對(duì)蟻群算法的收斂性能影響極大; ;u 當(dāng)當(dāng) 比較小時(shí)，搜索的全局性好，但收斂速度變慢比較小時(shí)，搜索的全局性好，但收斂速度變慢; ; u

9、當(dāng)當(dāng) 比較大時(shí)，收斂速度比較快，但是容易陷入局部最優(yōu)。比較大時(shí)，收斂速度比較快，但是容易陷入局部最優(yōu)。 14蟻群算法參數(shù)選擇蟻群算法參數(shù)選擇因子因子和和的選取的選取 u 啟發(fā)式因子啟發(fā)式因子的大小則反映了在蟻群路徑搜索中的隨機(jī)性因素作的大小則反映了在蟻群路徑搜索中的隨機(jī)性因素作用的強(qiáng)度用的強(qiáng)度; ;u 啟發(fā)式因子啟發(fā)式因子的大小反映了在蟻群路徑搜索中確定性因素作用的的大小反映了在蟻群路徑搜索中確定性因素作用的強(qiáng)度。強(qiáng)度。總信息量總信息量Q的選取的選取 u 總信息量總信息量Q Q越大，可以加強(qiáng)蟻群搜索時(shí)的正反饋性能，有助于算越大，可以加強(qiáng)蟻群搜索時(shí)的正反饋性能，有助于算法的快速收斂。法的快速收斂

10、。螞蟻的初始分布螞蟻的初始分布 u 所有螞蟻初始時(shí)刻放在同一個(gè)城市所有螞蟻初始時(shí)刻放在同一個(gè)城市; ;u 螞蟻分布在不同的城市中。螞蟻分布在不同的城市中。 15蟻群算法時(shí)間復(fù)雜度及蟻群算法時(shí)間復(fù)雜度及優(yōu)缺點(diǎn)優(yōu)缺點(diǎn)u M.Dorigo M.Dorigo曾經(jīng)對(duì)經(jīng)典的曾經(jīng)對(duì)經(jīng)典的TSPTSP問題求解復(fù)雜度進(jìn)問題求解復(fù)雜度進(jìn)行過深入的研究，所得到的經(jīng)驗(yàn)結(jié)果表明，算法行過深入的研究，所得到的經(jīng)驗(yàn)結(jié)果表明，算法的時(shí)間復(fù)雜度為的時(shí)間復(fù)雜度為O(NCn2m)O(NCn2m)，NCNC表示迭代次數(shù)，表示迭代次數(shù)，n n表示城市數(shù)，表示城市數(shù)，m m則表示參與搜索的螞蟻數(shù)量。當(dāng)則表示參與搜索的螞蟻數(shù)量。當(dāng)參與搜索

11、的螞蟻數(shù)量參與搜索的螞蟻數(shù)量m m大致與規(guī)模大小大致與規(guī)模大小n n相等時(shí)，相等時(shí)，算法的時(shí)間復(fù)雜度變?yōu)樗惴ǖ臅r(shí)間復(fù)雜度變?yōu)镺(NCn3)O(NCn3)較強(qiáng)的魯棒性較強(qiáng)的魯棒性 分布式計(jì)算分布式計(jì)算 易于與其他方法結(jié)合易于與其他方法結(jié)合 u需要較長(zhǎng)的搜索時(shí)間需要較長(zhǎng)的搜索時(shí)間u容易出現(xiàn)停滯現(xiàn)容易出現(xiàn)停滯現(xiàn) 16帶精英策略的螞蟻系統(tǒng)帶精英策略的螞蟻系統(tǒng) 每次循環(huán)之后給予最優(yōu)解以額外的信息素量每次循環(huán)之后給予最優(yōu)解以額外的信息素量 這樣的解被稱為這樣的解被稱為全局最優(yōu)解全局最優(yōu)解（global-best solution） 找出這個(gè)解的螞蟻被稱為找出這個(gè)解的螞蟻被稱為精英螞蟻精英螞蟻(elitis

12、t ants)帶精英策略的螞蟻系統(tǒng)（帶精英策略的螞蟻系統(tǒng)（Ant System with elitist strategy, ASelite）是最早的改進(jìn)螞蟻系統(tǒng)。）是最早的改進(jìn)螞蟻系統(tǒng)。 遺傳算法中的精英策略遺傳算法中的精英策略 螞蟻系統(tǒng)中的精英策略螞蟻系統(tǒng)中的精英策略 傳統(tǒng)的遺傳算法可能會(huì)導(dǎo)致最適應(yīng)個(gè)體的遺傳信息丟失傳統(tǒng)的遺傳算法可能會(huì)導(dǎo)致最適應(yīng)個(gè)體的遺傳信息丟失 精英策略的思想是保留住一代中的最適應(yīng)個(gè)體精英策略的思想是保留住一代中的最適應(yīng)個(gè)體 17帶精英策略的螞蟻系統(tǒng)帶精英策略的螞蟻系統(tǒng)信息素根據(jù)下式進(jìn)行更新信息素根據(jù)下式進(jìn)行更新 *(1)( )ijijijijtt其中其中1mkijij

13、k,0,kkijQkL如果螞蟻 在本次循環(huán)中經(jīng)過路徑(i,j)否則*,0,ijQL如果邊(i,j)是所找出的最優(yōu)解的一部分否則 18帶精英策略的螞蟻系統(tǒng)帶精英策略的螞蟻系統(tǒng) 表示精英螞蟻引起的路徑表示精英螞蟻引起的路徑(i, j)上的信息素量的增加上的信息素量的增加 是所找出的最優(yōu)解的路徑長(zhǎng)度是所找出的最優(yōu)解的路徑長(zhǎng)度 特點(diǎn)：特點(diǎn)： 是精英螞蟻的個(gè)數(shù)是精英螞蟻的個(gè)數(shù) Lu 可以使螞蟻系統(tǒng)找出更優(yōu)的解可以使螞蟻系統(tǒng)找出更優(yōu)的解u 找到這些解的時(shí)間更短找到這些解的時(shí)間更短 u 精英螞蟻過多會(huì)導(dǎo)致搜索早熟收斂精英螞蟻過多會(huì)導(dǎo)致搜索早熟收斂 19蟻群系統(tǒng)蟻群系統(tǒng) 蟻群系統(tǒng)的狀態(tài)轉(zhuǎn)移規(guī)則蟻群系統(tǒng)的狀態(tài)轉(zhuǎn)

14、移規(guī)則 0arg max ( , ) ( , ) ,ku allowedr ur uqqsS如果按先驗(yàn)知識(shí)選擇路徑否則其中，其中，S S根據(jù)下列公式得：根據(jù)下列公式得：到到( )( ),( )( )( )0,kijijkkisisijs allowedttjallowedttPtotherwiseu 一只位于節(jié)點(diǎn)一只位于節(jié)點(diǎn)r r的螞蟻通過應(yīng)用下式給出的規(guī)則選擇下的螞蟻通過應(yīng)用下式給出的規(guī)則選擇下一個(gè)將要移動(dòng)到的城市一個(gè)將要移動(dòng)到的城市s s： 20蟻群系統(tǒng)蟻群系統(tǒng) 蟻群系統(tǒng)全局更新原則蟻群系統(tǒng)全局更新原則 1,( , )0,gbLr s如果(r,s) 全局最優(yōu)路徑否則( , )(1)( ,

15、)( , )r sr sr su 只有全局最優(yōu)的螞蟻才被允許釋放信息素。只有全局最優(yōu)的螞蟻才被允許釋放信息素。 u 目的：使螞蟻的搜索主要集中在當(dāng)前循環(huán)為止所找出目的：使螞蟻的搜索主要集中在當(dāng)前循環(huán)為止所找出的最好路徑領(lǐng)域內(nèi)。的最好路徑領(lǐng)域內(nèi)。 u 全局更新在所有螞蟻都完成它們的路徑之后執(zhí)行，用全局更新在所有螞蟻都完成它們的路徑之后執(zhí)行，用下式對(duì)所建立的路徑進(jìn)行更新：下式對(duì)所建立的路徑進(jìn)行更新： 21蟻群系統(tǒng)蟻群系統(tǒng) 蟻群系統(tǒng)局部更新原則蟻群系統(tǒng)局部更新原則 u 類似于蟻密和蟻量模型中的更新規(guī)則類似于蟻密和蟻量模型中的更新規(guī)則 u 螞蟻應(yīng)用下列局部更新規(guī)則對(duì)它們所經(jīng)過的邊進(jìn)行信螞蟻應(yīng)用下列局部

16、更新規(guī)則對(duì)它們所經(jīng)過的邊進(jìn)行信息素更新息素更新( , )(1)( , )( , )01r sr sr s其中，u 實(shí)驗(yàn)發(fā)現(xiàn)，實(shí)驗(yàn)發(fā)現(xiàn)， 可以產(chǎn)生好的結(jié)果，其中可以產(chǎn)生好的結(jié)果，其中n n是城是城市的數(shù)量，市的數(shù)量， 是由最近的鄰域啟發(fā)產(chǎn)生的一個(gè)路徑長(zhǎng)度是由最近的鄰域啟發(fā)產(chǎn)生的一個(gè)路徑長(zhǎng)度nnLnn0Ln1u 局部更新規(guī)則可以有效地避免螞蟻收斂到同一路徑局部更新規(guī)則可以有效地避免螞蟻收斂到同一路徑 22Max-Min Ant SystemMax-Min Ant System（MMASMMAS）信息素軌跡更新原則信息素軌跡更新原則 u在在MMASMMAS中，只有一只螞蟻用于在每次循環(huán)后更新信息中，

17、只有一只螞蟻用于在每次循環(huán)后更新信息軌跡。經(jīng)修改的軌跡更新原則如下：軌跡。經(jīng)修改的軌跡更新原則如下：u 表示迭代最優(yōu)解或全局最優(yōu)解的值。表示迭代最優(yōu)解或全局最優(yōu)解的值。u在蟻群算法中主要使用全局最優(yōu)解，而在在蟻群算法中主要使用全局最優(yōu)解，而在MMASMMAS中則主中則主要使用迭代最優(yōu)解。要使用迭代最優(yōu)解。(1)( )ijbestijijtt1()ijbestbestf s 23Max-Min Ant SystemMax-Min Ant System（MMASMMAS）信息素軌跡的限制信息素軌跡的限制 uMMASMMAS對(duì)信息素軌跡的最小值和最大值分別施加了對(duì)信息素軌跡的最小值和最大值分別施加了

18、 和和 的限制，從而使得對(duì)所有信息素軌跡的限制，從而使得對(duì)所有信息素軌跡 ，有，有u 的選取要基于兩點(diǎn)假設(shè)：的選取要基于兩點(diǎn)假設(shè)：1.1.最優(yōu)解在搜索停滯發(fā)最優(yōu)解在搜索停滯發(fā)生之前不久被找出。生之前不久被找出。2.2.對(duì)解構(gòu)造的主要影響是由信息素對(duì)解構(gòu)造的主要影響是由信息素軌跡的上限與下限之間的相對(duì)差異決定軌跡的上限與下限之間的相對(duì)差異決定minmaxm inm ax( )ijtm ax11( )()ijttio p titfsmin 24Max-Min Ant SystemMax-Min Ant System（MMASMMAS）信息素軌跡的平滑化信息素軌跡的平滑化u基本思想：通過增加選擇有著

19、低強(qiáng)度信息素軌跡量解基本思想：通過增加選擇有著低強(qiáng)度信息素軌跡量解元素的概率以提高探索新解的能力元素的概率以提高探索新解的能力u平滑機(jī)制有助于對(duì)搜索空間進(jìn)行更有效的探索平滑機(jī)制有助于對(duì)搜索空間進(jìn)行更有效的探索*max( )( )( )( )ijijijtttt *( )( )ijijtt其中,01,和分別為平滑化之前和之后的信息素軌跡量 25Max-Min Ant SystemMax-Min Ant System（MMASMMAS） 26蟻群算法的應(yīng)用蟻群算法的應(yīng)用 27蟻群算法的應(yīng)用蟻群算法的應(yīng)用TSP問題問題u問題描述：旅行商按一定的順序訪問問題描述：旅行商按一定的順序訪問n n個(gè)城市，使

20、得每個(gè)城市，使得每個(gè)城市都被訪問且僅能被訪問一次而使花費(fèi)代價(jià)最小，個(gè)城市都被訪問且僅能被訪問一次而使花費(fèi)代價(jià)最小，從圖論的觀點(diǎn)來看，就是找出一個(gè)最短的封閉回路。從圖論的觀點(diǎn)來看，就是找出一個(gè)最短的封閉回路。uTSPTSP的求解是的求解是NP-hardNP-hard問題。隨著城市數(shù)目的增多問題。隨著城市數(shù)目的增多, ,問題問題空間將呈指數(shù)級(jí)增長(zhǎng)空間將呈指數(shù)級(jí)增長(zhǎng)uTSPTSP在許多工程領(lǐng)域具有廣泛的應(yīng)用價(jià)值，例如電路板在許多工程領(lǐng)域具有廣泛的應(yīng)用價(jià)值，例如電路板布線、機(jī)器人控制、交通路由等。布線、機(jī)器人控制、交通路由等。 28蟻群系統(tǒng)在蟻群系統(tǒng)在TSPTSP問題中的應(yīng)用問題中的應(yīng)用 29蟻群算法

21、求解蟻群算法求解TSPTSP問題問題下面以下面以TSP為例說明基本蟻群算法模型。為例說明基本蟻群算法模型。u首先將首先將m m只螞蟻隨機(jī)放置在只螞蟻隨機(jī)放置在n n個(gè)城市，位于城市個(gè)城市，位于城市i i的第的第k k只螞蟻選擇下一個(gè)城市只螞蟻選擇下一個(gè)城市j j的概率為的概率為: : u 表示邊（表示邊（i i，j j）上的信息素濃度；）上的信息素濃度； 是是啟發(fā)信息，啟發(fā)信息，d d是城市是城市i i和和j j之間的距離；之間的距離；和和反映了信息反映了信息素與啟發(fā)信息的相對(duì)重要性；素與啟發(fā)信息的相對(duì)重要性； 表示螞蟻表示螞蟻k k已經(jīng)訪問過已經(jīng)訪問過的城市列表。的城市列表。) 1 (,0,

22、),(),(),(),(),(otherwisetabujifsisijijijiPktabuskk),(ji),(/1),(jidjiktabu 30蟻群算法求解蟻群算法求解TSPTSP問題問題u當(dāng)所有螞蟻完成周游后，按以下公式進(jìn)行信息素更新。當(dāng)所有螞蟻完成周游后，按以下公式進(jìn)行信息素更新。u其中，其中，為小于為小于1 1的常數(shù)，表示信息的持久性。的常數(shù)，表示信息的持久性。)2()()(1mkkijijijijijtnt) 3(0otherwiselijLQkkkiju其中，其中，Q Q為常數(shù)；為常數(shù)； 表示第表示第k k只螞蟻在本次迭代中走過只螞蟻在本次迭代中走過的路徑長(zhǎng)度。的路徑長(zhǎng)度。k

23、L 31InitializationDistribute the ants, Modify the tabu Calculate the probability of moving between citiesi+Update pheromone between cities i=city.NMeet the requirement of the solution Number of traverse city i=1outputMove to j and modify the tabuNYCalculate the distance each ant walks the loopYNEach

24、 ant choose the next city 32實(shí)現(xiàn)過程實(shí)現(xiàn)過程 33實(shí)現(xiàn)過程實(shí)現(xiàn)過程 34實(shí)現(xiàn)過程實(shí)現(xiàn)過程 35實(shí)現(xiàn)過程實(shí)現(xiàn)過程 36中國旅行商問題中國旅行商問題1.5602e+04ACATSP(C,100,10,1,5,0.1,100) 37遺傳算法和蟻群算法在遺傳算法和蟻群算法在求解求解TSPTSP問題上的對(duì)比分析問題上的對(duì)比分析 38細(xì)菌覓食機(jī)理細(xì)菌覓食機(jī)理 趨向性操作趨向性操作設(shè)細(xì)菌種群大小為設(shè)細(xì)菌種群大小為S，一個(gè)細(xì)菌所處的位，一個(gè)細(xì)菌所處的位置表示一個(gè)問題的候選解，置表示一個(gè)問題的候選解，細(xì)菌細(xì)菌i的信息的信息用用D維向量表示為維向量表示為12,1,2,iiiiDiS 細(xì)

25、菌細(xì)菌i在第在第j次趨向性操作、第次趨向性操作、第k次復(fù)制操作次復(fù)制操作和第和第l次遷徙操作之后的位置表示為次遷徙操作之后的位置表示為細(xì)菌細(xì)菌i的的每一步趨向性操作每一步趨向性操作表示如下：表示如下：(1, , )( , , )( ) ( )iijk lj k lC ijC(i)0 表示向前游動(dòng)的步長(zhǎng)單位表示向前游動(dòng)的步長(zhǎng)單位 表示旋轉(zhuǎn)后選擇的一個(gè)隨機(jī)前進(jìn)方向表示旋轉(zhuǎn)后選擇的一個(gè)隨機(jī)前進(jìn)方向( ) j 39細(xì)菌覓食機(jī)理細(xì)菌覓食機(jī)理 聚群行為聚群行為 “抱團(tuán)抱團(tuán)” 在細(xì)菌趨向最佳生存環(huán)境的過程中，菌落的個(gè)體根據(jù)自身當(dāng)前的適應(yīng)度值對(duì)在細(xì)菌趨向最佳生存環(huán)境的過程中，菌落的個(gè)體根據(jù)自身當(dāng)前的適應(yīng)度值對(duì)

26、其他所有細(xì)菌釋放信息，吸引素和排斥素，即信息素。同時(shí)，此細(xì)菌接受其其他所有細(xì)菌釋放信息，吸引素和排斥素，即信息素。同時(shí)，此細(xì)菌接受其他所有細(xì)菌的釋放的吸引素和排斥素，在其所有信息素的作用下修改自己的他所有細(xì)菌的釋放的吸引素和排斥素，在其所有信息素的作用下修改自己的適應(yīng)值。保證向局部環(huán)境變好的位置移動(dòng)。在一個(gè)菌落中，上述個(gè)體間的信適應(yīng)值。保證向局部環(huán)境變好的位置移動(dòng)。在一個(gè)菌落中，上述個(gè)體間的信息素濃度計(jì)算方法可表示為：息素濃度計(jì)算方法可表示為： 40算法簡(jiǎn)介算法簡(jiǎn)介 41細(xì)菌覓食機(jī)理細(xì)菌覓食機(jī)理 聚群行為聚群行為 “抱團(tuán)抱團(tuán)” 其中，其中，Jcc(,P(j,k,l)是一種隨種群分布狀態(tài)變化的目

27、標(biāo)函數(shù)，當(dāng)它被是一種隨種群分布狀態(tài)變化的目標(biāo)函數(shù)，當(dāng)它被疊加到問題的實(shí)際目標(biāo)函數(shù)時(shí)，就表示了細(xì)菌與最佳個(gè)體的相對(duì)距疊加到問題的實(shí)際目標(biāo)函數(shù)時(shí)，就表示了細(xì)菌與最佳個(gè)體的相對(duì)距離變化趨勢(shì)；離變化趨勢(shì)；S 表示種群的大??；表示種群的大小；p指明了優(yōu)化問題的維度。指明了優(yōu)化問題的維度。F類比類比：其他群智能算法的聚群行為：其他群智能算法的聚群行為：l花蜜源比較差的偵查蜂轉(zhuǎn)向花蜜源比較好的偵查蜂，變成花蜜源比較差的偵查蜂轉(zhuǎn)向花蜜源比較好的偵查蜂，變成跟隨蜂跟隨蜂 -舞蹈舞蹈l 亮度比較弱的螢火蟲轉(zhuǎn)向亮度比較好的螢火蟲亮度比較弱的螢火蟲轉(zhuǎn)向亮度比較好的螢火蟲-熒光素?zé)晒馑?42細(xì)菌覓食機(jī)理細(xì)菌覓食機(jī)理 復(fù)

28、制（優(yōu)勝劣汰）復(fù)制（優(yōu)勝劣汰） 經(jīng)過一個(gè)周期的趨向操作后，菌落進(jìn)行復(fù)制操作。該操作遵循達(dá)爾文經(jīng)過一個(gè)周期的趨向操作后，菌落進(jìn)行復(fù)制操作。該操作遵循達(dá)爾文的的優(yōu)勝劣汰原理。首先，菌落依據(jù)優(yōu)勝劣汰原理。首先，菌落依據(jù)適應(yīng)度值適應(yīng)度值排序，獲得足夠多食物（適排序，獲得足夠多食物（適應(yīng)應(yīng)度函數(shù)較優(yōu)）的個(gè)體進(jìn)行分裂，而能量不足的個(gè)體將會(huì)死去。同時(shí)，度函數(shù)較優(yōu)）的個(gè)體進(jìn)行分裂，而能量不足的個(gè)體將會(huì)死去。同時(shí)，分裂的個(gè)體和死去的個(gè)體數(shù)量相等，這保證了種群數(shù)量的穩(wěn)定。產(chǎn)生分裂的個(gè)體和死去的個(gè)體數(shù)量相等，這保證了種群數(shù)量的穩(wěn)定。產(chǎn)生的的新一代個(gè)體進(jìn)入下一個(gè)趨向操作周期。新一代個(gè)體進(jìn)入下一個(gè)趨向操作周期。F其他群

29、智能算法的淘汰機(jī)制：其他群智能算法的淘汰機(jī)制：l花蜜源比較差的偵查蜂轉(zhuǎn)向花蜜源比較好的偵查蜂過程花蜜源比較差的偵查蜂轉(zhuǎn)向花蜜源比較好的偵查蜂過程 淘汰花蜜源淘汰花蜜源比較差的蜜蜂比較差的蜜蜂l螢火蟲亮度比較弱的淘汰螢火蟲亮度比較弱的淘汰 43細(xì)菌覓食機(jī)理細(xì)菌覓食機(jī)理 前前提提經(jīng)過復(fù)制操作后經(jīng)過復(fù)制操作后算法的種群大小不變算法的種群大小不變 44細(xì)菌覓食機(jī)理細(xì)菌覓食機(jī)理 驅(qū)散行為驅(qū)散行為 幾次復(fù)制操作后，菌落將呈現(xiàn)幾個(gè)幾次復(fù)制操作后，菌落將呈現(xiàn)幾個(gè)聚集簇，種群多樣性退化，聚集簇，種群多樣性退化，“早熟早熟”。為了避免這種現(xiàn)。為了避免這種現(xiàn)象，象，BFO 算法引算法引入了變異操作入了變異操作驅(qū)散行

30、為。該操驅(qū)散行為。該操作模擬了細(xì)菌隨水流或其他生物遷作模擬了細(xì)菌隨水流或其他生物遷徙到新環(huán)境的生物現(xiàn)象，其運(yùn)行模徙到新環(huán)境的生物現(xiàn)象，其運(yùn)行模式是菌落中的一些個(gè)體以小概率（式是菌落中的一些個(gè)體以小概率（通常選擇通常選擇 25%）重新在搜索空間中）重新在搜索空間中隨機(jī)選擇一個(gè)位置。經(jīng)過驅(qū)散操作隨機(jī)選擇一個(gè)位置。經(jīng)過驅(qū)散操作后新一代個(gè)體進(jìn)入新的趨向操作周期后新一代個(gè)體進(jìn)入新的趨向操作周期。 45聚群與驅(qū)散聚群與驅(qū)散 46輸入：輸入：運(yùn)行相關(guān)的參數(shù)組運(yùn)行相關(guān)的參數(shù)組初始化初始化（菌落在搜索環(huán)境中隨機(jī)散開，并初始化每一個(gè)（菌落在搜索環(huán)境中隨機(jī)散開，并初始化每一個(gè)個(gè)體的健康指標(biāo)向量，三層循環(huán)的個(gè)體的健康

31、指標(biāo)向量，三層循環(huán)的l,j,kl,j,k索引均為索引均為0 0）驅(qū)散索引：驅(qū)散索引：l=l+1jNc?復(fù)制復(fù)制（依據(jù)（依據(jù)health進(jìn)行排序，淘汰后進(jìn)行排序，淘汰后一半，復(fù)制前一半）一半，復(fù)制前一半）驅(qū)散驅(qū)散（對(duì)每一個(gè)細(xì)菌：取一隨機(jī)數(shù)，若?。▽?duì)每一個(gè)細(xì)菌：取一隨機(jī)數(shù)，若小于驅(qū)散概率，則重新初始化）于驅(qū)散概率，則重新初始化）kNre?lNed?復(fù)制索引復(fù)制索引:k=k+1尋優(yōu)終止尋優(yōu)終止輸出環(huán)境最好的位置和相應(yīng)值輸出環(huán)境最好的位置和相應(yīng)值趨向索引趨向索引:j=j+1種群趨向種群趨向是是重初始趨向索引重初始趨向索引重初始化趨向，復(fù)制索引重初始化趨向，復(fù)制索引j=0,k=0 47細(xì)菌覓食算法參數(shù)問

32、題細(xì)菌覓食算法參數(shù)問題F種群大小S：S小，算法的計(jì)算速度快，但種群的多樣性降低，影響算法的優(yōu)化性能；小，算法的計(jì)算速度快，但種群的多樣性降低，影響算法的優(yōu)化性能；S大，避免算法陷入局部極小值，但計(jì)算量增加，收斂速度變慢。大，避免算法陷入局部極小值，但計(jì)算量增加，收斂速度變慢。F游動(dòng)步長(zhǎng)C：C不小于某一特定值，能有效避免算法過早收斂；不小于某一特定值，能有效避免算法過早收斂； C太大，降低算法的收斂速度太大，降低算法的收斂速度。F趨向性操作次數(shù)Nc:Nc越大，搜索更細(xì)致，但復(fù)雜度增加；越大，搜索更細(xì)致，但復(fù)雜度增加；Nc越小，算法容易陷入局部最小值。越小，算法容易陷入局部最小值。F復(fù)制操作次數(shù)N

33、re：Nre太大，會(huì)增加算法的復(fù)雜度；太大，會(huì)增加算法的復(fù)雜度；Nre太小，算法容易早熟收斂。太小，算法容易早熟收斂。F遷徙（驅(qū)散）操作Ned:Ned 越大，避免算法陷入早熟，但復(fù)雜度隨之增加；越大，避免算法陷入早熟，但復(fù)雜度隨之增加；Ned越小，算法沒有發(fā)揮遷徙操作的隨機(jī)搜索作用。越小，算法沒有發(fā)揮遷徙操作的隨機(jī)搜索作用。 48細(xì)菌覓食算法的改進(jìn)細(xì)菌覓食算法的改進(jìn)自適應(yīng)步長(zhǎng)調(diào)整策略自適應(yīng)步長(zhǎng)調(diào)整策略 在趨向行為中，原始在趨向行為中，原始BFOBFO使用固定步長(zhǎng)求解問題不利于算法的收使用固定步長(zhǎng)求解問題不利于算法的收斂。因此提出了一種基于細(xì)菌擁擠度的自適應(yīng)步長(zhǎng)調(diào)整策略。斂。因此提出了一種基于細(xì)

34、菌擁擠度的自適應(yīng)步長(zhǎng)調(diào)整策略。當(dāng)當(dāng) crowd較小時(shí)，細(xì)菌以較大的步長(zhǎng)尋優(yōu)較小時(shí)，細(xì)菌以較大的步長(zhǎng)尋優(yōu); 當(dāng)當(dāng)crowd 較大時(shí)，細(xì)較大時(shí)，細(xì)菌以較小的步長(zhǎng)尋優(yōu)。這樣能夠保證算法在優(yōu)化初期有很強(qiáng)的全菌以較小的步長(zhǎng)尋優(yōu)。這樣能夠保證算法在優(yōu)化初期有很強(qiáng)的全局搜索能力，在優(yōu)化后期有很強(qiáng)的局部開采能力。局搜索能力，在優(yōu)化后期有很強(qiáng)的局部開采能力。 49細(xì)菌覓食算法的改進(jìn)細(xì)菌覓食算法的改進(jìn)基于環(huán)境感知的細(xì)菌覓食優(yōu)化算法基于環(huán)境感知的細(xì)菌覓食優(yōu)化算法 在趨向行為中，賦予細(xì)菌對(duì)周圍細(xì)菌狀態(tài)進(jìn)行感知。在執(zhí)行中，在趨向行為中，賦予細(xì)菌對(duì)周圍細(xì)菌狀態(tài)進(jìn)行感知。在執(zhí)行中，所有細(xì)菌按照適應(yīng)度分成兩類：所有細(xì)菌按照適應(yīng)度分成兩類：l優(yōu)于適應(yīng)度平均值的，通過追蹤最優(yōu)細(xì)菌進(jìn)行搜索；優(yōu)于適應(yīng)度平均值的，通過追蹤最優(yōu)細(xì)菌進(jìn)行搜索；l劣于適應(yīng)度平均值的，通過追蹤細(xì)菌群體中心位置進(jìn)行劣于適應(yīng)度平均值的，通過追蹤細(xì)菌群體中心位置進(jìn)行搜索。搜索。第一種情