第7章 群智能算法及其應用（AI應用3版）

1、第 7 章 群智能算法及其應用教材： 王萬良人工智能及其應用（第3版） 高等教育出版社，2016. 22第7章 群智能算法及其應用7.1 群智能算法產(chǎn)生的背景7.2 粒子群優(yōu)化算法 7.3 量子粒子群優(yōu)化算法 7.4 粒子群優(yōu)化算法的應用7.5 基本蟻群算法7.6 改進蟻群算法 7.7 蟻群算法的應用3 7.1 群智能算法產(chǎn)生的背景 群智能算法（swarm algorithms，SI）：受動物群體智能啟發(fā)的算法。 群體智能：由簡單個體組成的群落與環(huán)境以及個體之間的互動行為。 群智能算法包括：粒子群優(yōu)化算法、蟻群算法、蜂群算法、4 7.1 群智能算法產(chǎn)生的背景5第7章 群智能算法及其應用7.1

2、群智能算法產(chǎn)生的背景7.2 粒子群優(yōu)化算法 7.3 量子粒子群優(yōu)化算法 7.4 粒子群優(yōu)化算法的應用7.5 基本蟻群算法7.6 改進蟻群算法 7.7 蟻群算法的應用67.2 粒子群優(yōu)化算法產(chǎn)生背景粒子群優(yōu)化（Particle Swarm Optimization, PSO）算法是由美國普渡大學的Kennedy和Eberhart于1995年提出，它的基本概念源于對鳥群覓食行為的研究。設想這樣一個場景：一群鳥在隨機搜尋食物，在這個區(qū)域里只有一塊食物，所有的鳥都不知道食物在哪里，但是它們知道當前的位置離食物還有多遠。那么找到食物的最優(yōu)策略是什么呢?最簡單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域。7

3、7.2 粒子群優(yōu)化算法7.2.1 粒子群優(yōu)化算法的基本原理7.2.2 粒子群優(yōu)化算法的參數(shù)分析87.2.1 粒子群優(yōu)化算法的基本原理 基本思想將每個個體看作n維搜索空間中一個沒有體積質(zhì)量的粒子，在搜索空間中以一定的速度飛行，該速度決定粒子飛行的方向和距離。所有粒子還有一個由被優(yōu)化的函數(shù)決定的適應值?；驹鞵SO初始化為一群隨機粒子，然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個“極值”來更新自己。第一個就是粒子本身所找到的最優(yōu)解，這個解稱為個體極值。另個一是整個種群目前找到的最優(yōu)解，這個解稱為全局極值。97.2.1 粒子群優(yōu)化算法的基本原理 算法定義在n 維連續(xù)搜索空間中，對粒子群

4、中的第i (i=1, 2, , m)個粒子進行定義： ：表示搜索空間中粒子的當前位置。 ：表示該粒子至今所獲得的具有最優(yōu)適應度 的位置。 ：表示該粒子的搜索方向。10 7.2.1 粒子群優(yōu)化算法的基本原理 每個粒子經(jīng)歷過的最優(yōu)位置（pbest）記為 ，群體經(jīng)歷過的最優(yōu)位置(gbest)記為 ，則基本的PSO算法為：（7.1a）（7.1b）其中， 是慣性權重因子。1 ，2 是加速度常數(shù)，均為非負值。 和 為0, a1、0, a2范圍內(nèi)的具有均勻分布的隨機數(shù)，a1 與 a2 為相應的控制參數(shù)。11 7.2.1 粒子群優(yōu)化算法的基本原理 （7.1a）式(7.1a)右邊的第1部分是粒子在前一時刻的速度

5、；第2部分為個體“認知”分量，表示粒子本身的思考，將現(xiàn)有的位置和曾經(jīng)經(jīng)歷過的最優(yōu)位置相比。第3部分是群體“社會(social)”分量，表示粒子間的信息共享與相互合作。1 ，2分別控制個體認知分量和群體社會分量相對貢獻的學習率。隨機系數(shù)增加搜索方向的隨機性和算法多樣性。127.2.1 粒子群優(yōu)化算法的基本原理 基于學習率 ， ， Kennedy給出以下4種類型的PSO模型：若 1 0，2 0，則稱該算法為PSO全模型。若 1 0，2 = 0，則稱該算法為PSO認知模型。若 1 = 0，2 0，則稱該算法為PSO社會模型。若 1 = 0，2 0且g i，則稱該算法為PSO無私模型。137.2.1

6、粒子群優(yōu)化算法的基本原理 粒子群優(yōu)化算法的流程：（1）初始化每個粒子，即在允許范圍內(nèi)隨機設置每個粒 子的初始位置和速度。（2）評價每個粒子的適應度，計算每個粒子的目標函數(shù)。（3）設置每個粒子的 。對每個粒子，將其適應度與其經(jīng) 歷過的最好位置 進行比較，如果優(yōu)于 ，則將其作為該粒子的最好位置 。147.2.1 粒子群優(yōu)化算法的基本原理 粒子群優(yōu)化算法的流程：（4）設置全局最優(yōu)值 。對每個粒子，將其適應度與群體經(jīng)歷過的最好位置 進行比較，如果優(yōu)于 ，則將其作為當前群體的最好位置 。（5）根據(jù)式（7.1）更新粒子的速度和位置。（6）檢查終止條件。如果未達到設定條件（預設誤差或者迭代的次數(shù)），則返回第

7、（2）步。157.2.1 粒子群優(yōu)化算法流程圖167.2.2 粒子群優(yōu)化算法的參數(shù)分析 PSO算法的參數(shù)包括：群體規(guī)模m，慣性權重，加速度1，2，最大速度Vmax， 最大代數(shù)Gmax。對速度vi，算法中有最大速度Vmax作為限制，如果當前粒子的某維速度大于最大速度Vmax，則該維的速度就被限制為最大速度Vmax。（1）最大速度Vmax（2）權重因子3個權重因子：慣性權重，加速度1，2 。177.2.2 粒子群優(yōu)化算法的參數(shù)分析2. 位置更新方程中各部分的影響（1）只有第1部分，即 1=2=0 粒子將一直以當前的速度飛行，直到達邊界。由于它只能搜索有限的區(qū)域，所以很難找到好解。187.2.2 粒

8、子群優(yōu)化算法的參數(shù)分析2. 位置更新方程中各部分的影響（2）沒有第1部分，即 =0速度只取決于粒子當前位置和其歷史最好位置Pi 和 Pg，速度本身沒有記憶性。197.2.2 粒子群優(yōu)化算法的參數(shù)分析（3）沒有第2部分，即 1=0 粒子沒有認知能力，也就是“只有社會模型”。在粒子的相互作用下，有能力達到新的搜索空間。但對復雜問題，容易陷入局部最優(yōu)點。207.2.2 粒子群優(yōu)化算法的參數(shù)分析（4）沒有第3部分，即 2=0 粒子間沒有社會共享信息，也就是“只有認知”模型。因為個體間沒有交互，一個規(guī)模為M的群體等價于M個單個粒子的運行，因而得到最優(yōu)解的機率非常小。217.2.2 粒子群優(yōu)化算法的參數(shù)分

9、析3. 參數(shù)設置早期的實驗： 固定為1.0，1和2固定為2.0，因此Vmax成為唯一需要調(diào)節(jié)的參數(shù)，通常設為每維變化范圍1020%。Suganthan的實驗表明，1和2 為常數(shù)時可以得到較好的解，但不一定必須為2。這些參數(shù)也可以通過模糊系統(tǒng)進行調(diào)節(jié)。Shi和Eberhart提出一個模糊系統(tǒng)來調(diào)節(jié) 。22第7章 群智能算法及其應用7.1 群智能算法產(chǎn)生的背景7.2 粒子群優(yōu)化算法 7.3 量子粒子群優(yōu)化算法 7.4 粒子群優(yōu)化算法的應用7.5 基本蟻群算法7.6 改進蟻群算法 7.7 蟻群算法的應用237.3 量子粒子群優(yōu)化算法產(chǎn)生背景在量子力學中是沒有確定的軌跡的，因為根據(jù)不確定性原理，位置向

10、量xi和速度向量vi是不可能同時確定的。J. Sun受到量子物理學的啟發(fā)，于2004年提出了一種能夠保證全局收斂的具有量子行為的量子粒子群優(yōu)化 (Quantum-behaved particle swarm optimization，QPSO) 算法，并對算法的收斂性進行了分析。247.3 量子粒子群優(yōu)化算法7.3.1 基本量子粒子群優(yōu)化算法7.3.2 改進量子粒子群優(yōu)化算法25粒子不再被描述為位置向量 xi和速度向量vi ，而是采用波函數(shù)來表示。7.3.1 基本量子粒子群優(yōu)化算法 粒子的波函數(shù)為 （7.2） 其概率密度函數(shù)為 （7.3）其中，p為每個粒子歷史的最好位置。 參數(shù)L的取值定義為

11、（7.4）L指出了微粒的搜索空間范圍。 262. 引入了mbest為所有微粒的中心7.3.1 基本量子粒子群優(yōu)化算法 （7.5）其中，M是種群數(shù)目， pi 是第 i 個粒子的最好位置。通過將所有粒子的中心mbest取代每個粒子的最好位置p，可以有效提高算法的全局搜索能力。277.3.1 基本量子粒子群優(yōu)化算法參數(shù)L表示為 （7.6）其中， 為收斂系數(shù)，不同的 影響算法的收斂速度，一般取 的值為 （7.7）其中，MAXITER為最大迭代次數(shù)。 由概率密度函數(shù)通過Monte Carlo算法計算得到 （7.8）代入?yún)?shù)L，QPSO算法的進化方程為 （7.9）287.3.1 基本量子粒子群優(yōu)化算法量子

12、粒子群優(yōu)化算法的基本步驟：Step1：確定種群規(guī)模和粒子維數(shù)，初始化粒子群體；Step2：計算個體歷史最優(yōu)值(pbest)：計算每一個微粒的適應度值，通過和個體的歷史最優(yōu)值比較，如果當前值優(yōu)于個體歷史最優(yōu)值，則把當前值替換為個體最優(yōu)值(pbest)，否則不替換；Step3：計算所有微粒的適應值，與當前全局最優(yōu)值(gbest)比較，若當前值優(yōu)于全局最優(yōu)值，則把當前值替換為全局最優(yōu)值；Step4：計算所有粒子的重心（mbest）；根據(jù)公式(7.5)來更新所有粒子的重心（mbest）；Step5: 根據(jù)進化方程(7.9)更新每個粒子的位置，產(chǎn)生新種群；Step6：粒子適應度滿足收斂條件或者是達到最大

13、迭代次數(shù)，則算法結(jié)束，否則跳轉(zhuǎn)到步驟2繼續(xù)迭代執(zhí)行。29優(yōu)點：相對于粒子群優(yōu)化算法具有更好的收斂性和全局搜索能力。 缺點：求解約束優(yōu)化問題的時 會產(chǎn)生大量的不可行解 破壞種群的多樣性 導致算法陷入局部極值7.3.1 基本量子粒子群優(yōu)化算法30三種概率分布函數(shù)7.3.2 改進量子粒子群優(yōu)化算法（1）正態(tài)分布 正態(tài)分布是具有兩個參數(shù) 和 2 的連續(xù)型隨機變量的分布，正態(tài)分布記作 。正態(tài)分布的概率密度函數(shù)為 （7.10）其中， 是服從正態(tài)分布的隨機變量的均值，2是該隨機變量的方差。 31三種概率分布函數(shù)7.3.2 改進量子粒子群優(yōu)化算法（2）2 分布 設隨機變量 相互獨立，并且都服從標準正態(tài)分布 ，

14、則隨機變量 的概率密度為 （7.11）32三種概率分布函數(shù)7.3.2 改進量子粒子群優(yōu)化算法（3）t 分布 設隨機變量X與Y獨立，并且X服從標準正態(tài)分布 ，Y服從自由度為 k 的 2 分布，則隨機變量 的概率密度為 （7.12）337.3.2 改進量子粒子群優(yōu)化算法2. 變異操作（1）生成符合正態(tài)分布的隨機數(shù) 產(chǎn)生 均勻分布的隨機數(shù)30個，記為 ；由于 ， 。根據(jù)中心極限定理，可以認為近似服從均值為 ，方差為2.5的正態(tài)分布。計算 ，由中心極限定理，它可以看作是來自標準正態(tài)分布 的一個隨機數(shù)。347.3.2 改進量子粒子群優(yōu)化算法2. 變異操作（2）對個體的每個維度產(chǎn)生在可行域區(qū)間內(nèi)符合概率分

15、布的可行解 正態(tài)分布生成1個符合正態(tài)分布的隨機數(shù)v，變換x=+v由，正態(tài)分布的性質(zhì)可知，它可以看作是來自正態(tài)分布N(, 2)的一個隨機數(shù)。取 。為可變參數(shù)，用于控制解在可行域范圍內(nèi)的分布情況?？尚薪?。 2 分布生成k個滿足標準正態(tài)分布N(0,1)的隨機數(shù) ，取 。 k為可變參數(shù)，用于控制解在可行域范圍內(nèi)的分布情況?？尚薪?。 t 分布生成2個滿足標準正態(tài)分布N(0,1)的隨機數(shù) ，取 ，生成一個符合正態(tài)分布的隨機數(shù) X，取 。可行解 。357.3.2 改進量子粒子群優(yōu)化算法2. 變異操作（3）計算適應度由前面所生成的個體 在可行域區(qū)間內(nèi)，符合概率分布。根據(jù)適應度公式計算個體的適應度 。（4）

16、以一定的概率接受解計算動態(tài)變異率 (7.13)其中， 為原個體的適應度。 為變異操作后個體的適應度。依照概率 接受解，即將原個體X替換為變異后的解X。上式表明若pm1則表示X是個極好解，這個解必定被接受。36基于概率分布的量子粒子群優(yōu)化算法流程圖37第7章 群智能算法及其應用7.1 群智能算法產(chǎn)生的背景7.2 粒子群優(yōu)化算法 7.3 量子粒子群優(yōu)化算法 7.4 粒子群優(yōu)化算法的應用7.5 基本蟻群算法7.6 改進蟻群算法 7.7 蟻群算法的應用387.4 粒子群優(yōu)化算法的應用7.4.1 粒子群優(yōu)化算法應用領域7.4.2 粒子群優(yōu)化算法在PID參數(shù)整定中的應用7.4.3 粒子群優(yōu)化算法在車輛路徑

17、問題中的應用397.4.1 粒子群優(yōu)化算法應用領域（1）神經(jīng)網(wǎng)絡訓練 （7）經(jīng)濟領域（2）化工系統(tǒng)領域 （8）圖像處理領域（3）電力系統(tǒng)領域 （9）生物信息領域（4）機械設計領域 （10）醫(yī)學領域（5）通訊領域 （11）運籌學領域（6）機器人領域 .粒子群優(yōu)化算法已在諸多領域得到應用，歸納如下：40 7.4.2 粒子群優(yōu)化算法在PID參數(shù)整定中的應用典型的PID控制系統(tǒng)的控制量u與偏差e=(R-y)之間滿足以下差分方程 （7.14）PID控制器就是通過調(diào)整Kp，Ti，Td這3個參數(shù)來使系統(tǒng)的控制性能達到給定的要求。從最優(yōu)控制的角度，就是在Kp，Ti，Td這3個變量的參數(shù)空間中，尋找最優(yōu)的值使系

18、統(tǒng)的控制性能達到最優(yōu)。為優(yōu)化PID參數(shù)，可以選取如下函數(shù)作為評價控制性能的指標 （7.15）41編碼與初始種群 7.4.2 粒子群優(yōu)化算法在PID參數(shù)整定中的應用2. 適應度函數(shù) 實數(shù)編碼 在初始群體的生成上，首先根據(jù)經(jīng)驗估計出PID三個參數(shù)的取值范圍，在此范圍內(nèi)采用隨機生成的方式，使粒子群優(yōu)化算法在整個可行解空間中進行搜索。 由于PID參數(shù)優(yōu)化是求目標函數(shù)Q的極小值問題，因而需要將極小值問題轉(zhuǎn)換為極大值問題，適應度函數(shù)可以取為 （7.16）42舉例 7.4.2 粒子群優(yōu)化算法在PID參數(shù)整定中的應用采用PID控制器對被控對象進行控制，假定控制對象具有二階慣性加延遲的模型，其傳遞函數(shù)為: 。假

19、定采樣周期選擇為0.1s，根據(jù)經(jīng)驗Kp參數(shù)范圍為（0，4），Ti參數(shù)范圍為（0，1），Td參數(shù)范圍為（0，1）。取粒子群種群規(guī)模為20，迭代次數(shù)為50，c1的取值根據(jù)迭代的次數(shù)線性減小，初始值為1.5，最終值0.4。 1= 2=2。43舉例 7.4.2 粒子群優(yōu)化算法在PID參數(shù)整定中的應用PID參數(shù)粒子群優(yōu)化算法尋優(yōu)結(jié)果見表7.1所示。為了說明粒子群優(yōu)化算法的有效性，表中同時也給出了用單純形法的尋優(yōu)結(jié)果。算法KpTiTdQ粒子群優(yōu)化算法0.629320.593490.237154.84232單純形法0.630570.594810.237034.86818表7.1 優(yōu)化結(jié)果及比較 44車輛路徑

20、問題（VRP）的模型 7.4.3 粒子群優(yōu)化算法在車輛路徑問題中的應用車輛路徑問題：假定配送中心最多可以用 輛車對 個客戶進行運輸配送， 表示倉庫。每個車輛載重為 ，每個客戶的需求為 ，客戶i到客戶 j 的運輸成本為 cij（可以是距離，時間，費用等）。定義如下變量：45車輛路徑問題（VRP）的模型 7.4.3 粒子群優(yōu)化算法在車輛路徑問題中的應用則車輛路徑問題的數(shù)學模型如下表示： (7.17a) (7.17b) 每輛車的能力約束 (7.17c) 保證每個客戶都被服務 (7.17d) 保證客戶是僅被一輛車訪問 (7.17e) 保證客戶是僅被一輛車訪問 (7.17f) 消除子回路 (7.17g)

21、 表示變量的取值范圍 (7.17h) 表示變量的取值范圍46 7.4.2 粒子群優(yōu)化算法在車輛路徑問題中的應用2. 編碼與初始種群 對這類組合優(yōu)化問題，編碼方式、初始解的設置對問題的求解都有很大的影響。采用常用的自然數(shù)編碼方式。 對于K輛車和L個客戶的問題，用從1到L的自然數(shù)隨機排列來產(chǎn)生一組解 。然后分別用節(jié)約法或者最近插入法構(gòu)造初始解。47 7.4.2 粒子群優(yōu)化算法在PID參數(shù)整定中的應用粒子群優(yōu)化算法的各個參數(shù)設置如下：種群規(guī)模p=50 ，迭代次數(shù)N=1000 ， c1的初始值為1，隨著迭代的進行，線性減小到0，c2=c3=1.4 ， 。表7.2 優(yōu)化結(jié)果及其比較3. 實驗結(jié)果實例PS

22、OGAbestdev(%)bestdev(%)A-n32-k58295.738184.34A-n33-k57056.656741.97A-n34-k58326.948215.52A-n39-k68726.088665.35A-n44-k610168.499915.76A-n46-k79776.899574.7A-n54-k712053.2612033.08A-n60-k914769.0114104.13A-n69-k912751012437.24A-n80-k10199212.9818716.1248第7章 群智能算法及其應用7.1 群智能算法產(chǎn)生的背景7.2 粒子群優(yōu)化算法 7.3 量子粒子

23、群優(yōu)化算法 7.4 粒子群優(yōu)化算法的應用7.5 基本蟻群算法7.6 改進蟻群算法 7.7 蟻群算法的應用49 20世紀90年代初，意大利科學家Marco Dorigo等受螞蟻覓食行為的啟發(fā)，提出蟻群算法(Ant Colony Optimization，ACO)。 7.5 基本蟻群算法 一種應用于組合優(yōu)化問題的啟發(fā)式搜索算法。 在解決離散組合優(yōu)化方面具有良好的性能。 產(chǎn)生背景50 基本思想7.5 基本蟻群算法 信息素跟蹤：按照一定的概率沿著信息素較強的路徑覓食。 信息素遺留：會在走過的路上會釋放信息素，使得在一定的范圍內(nèi)的其他螞蟻能夠覺察到并由此影響它們的行為。51 7.5 基本蟻群算法 （1）

24、環(huán)境：有障礙物、有其他螞蟻、有信息素。 （2）覓食規(guī)則：范圍內(nèi)尋找是否有食物，否則看是否有信息素，每只螞蟻都會以小概率犯錯。 （3）移動規(guī)則：都朝信息素最多的方向移動，無信息素則繼續(xù)朝原方向移動，且有隨機的小的擾動，有記憶性。 （4）避障規(guī)則：移動的方向如有障礙物擋住，螞蟻會隨機選擇另一個方向。（5）信息素規(guī)則：越靠近食物播撒的信息素越多，越離開食物播撒的信息素越少。527.5 基本蟻群算法7.5.1 基本蟻群算法模型7.5.2 蟻群算法的參數(shù)選擇537.5.1 基本蟻群算法模型蟻群優(yōu)化算法的第一個應用是著名的旅行商問題。旅行商問題闡明 蟻群系統(tǒng)模型旅行商問題（Traveling Salesm

25、an Problem，TSP）：在尋求單一旅行者由起點出發(fā)，通過所有給定的需求點之后，最后再回到原點的最小路徑成本。螞蟻搜索食物的過程 ：通過個體之間的信息交流與相互協(xié)作最終找到從蟻穴到食物源的最短路徑。54蟻群系統(tǒng)的模型 7.5.1 基本蟻群算法模型 m 是蟻群中螞蟻的數(shù)量 表示元素(城市) 和元素(城市) 之間的距離 表示能見度，稱為啟發(fā)信息函數(shù)，等于距離 的倒數(shù)，即 表示t時刻位于城市x的螞蟻的個數(shù)， 表示t時刻在xy連線上殘留的信息素，初始時 刻，各條路徑上的信息素相等即 螞蟻k在運動過程中，根據(jù)各條路徑上的信息素決定轉(zhuǎn)移方向。55 7.5.1 基本蟻群算法模型 表示在t時刻螞蟻 k

26、選擇從元素(城市) x 轉(zhuǎn)移到元素(城市) y 的概率，也稱為隨機比例規(guī)則。信息素 共同決定局部啟發(fā)信息蟻群系統(tǒng)的模型56 7.5.1 基本蟻群算法模型 表示如下： （7.18） 其中： 表示螞蟻k下一步允許選擇的城市 記錄螞蟻k當前所走過的城市 是信息素啟發(fā)式因子，表示軌跡的相對重要性57 7.5.1 基本蟻群算法模型 表示如下： （7.18） 其中： 值越大該螞蟻越傾向于選擇其它螞蟻經(jīng)過的路徑，該狀態(tài)轉(zhuǎn)移概率越接近于貪婪規(guī)則。當 = 0時不再考慮信息素水平，算法就成為有多重起點的隨機貪婪算法。當 = 0時算法就成為純粹的正反饋的啟發(fā)式算法。58 7.5.1 基本蟻群算法模型用參數(shù)1-表示信

27、息素消逝程度，螞蟻完成一次循環(huán)，各路徑上信息素濃度消散規(guī)則為： （7.19）蟻群的信息素濃度更新規(guī)則為： （7.20）M. Dorigo給出 的三種不同模型59螞蟻圈系統(tǒng)（Ant-cycle System） 7.5.1 基本蟻群算法模型單只螞蟻所訪問路徑上的信息素濃度更新規(guī)則為： （7.21）其中： 為當前路徑上的信息素 為路徑（x, y）上信息素的增量 第k只螞蟻留在路徑（x, y）上的信息素的增量 Q 為常數(shù) Lk 為優(yōu)化問題的目標函數(shù)值，表示第k只螞蟻在本次循環(huán) 中所走路徑的長度602. 螞蟻數(shù)量系統(tǒng)（Ant-quantity System） 7.5.1 基本蟻群算法模型 （7.22）3

28、. 螞蟻密度系統(tǒng)（Ant-density System） （7.23）61 7.5.1 基本蟻群算法模型螞蟻圈系統(tǒng)利用的是全局信息 ，即螞蟻完成一個循環(huán)后，更新所有路徑上的信息。螞蟻數(shù)量系統(tǒng)利用的是局部信息 ，即螞蟻每走一步都要更新殘留信息素的濃度。螞蟻密度系統(tǒng)利用的是局部信息 ，即螞蟻每走一步都要更新殘留信息素的濃度。三種模型比較效果最好，通常作為蟻群優(yōu)化算法的基本模型。627.5.1 基本蟻群算法模型全局信息更新方法優(yōu)點： 保證了殘留信息素不至于無限累積； 如果路徑?jīng)]有被選中，那么上面的殘留信息素會隨時間的 推移而逐漸減弱，這使算法能“忘記”不好的路徑； 即使路徑經(jīng)常被訪問也不至于因為 的

29、累積，而產(chǎn)生 使期望值的作用無法體現(xiàn)； 充分體現(xiàn)了算法中全局范圍內(nèi)較短路徑(較好解)的生存能力； 加強了信息正反饋性能； 提高了系統(tǒng)搜索收斂的速度。63信息素啟發(fā)因子 7.5.2 蟻群算法的參數(shù)選擇反映了蟻群在路徑搜索中隨機性因素作用的強度； 值越大，螞蟻選擇以前走過的路徑的可能性越大，搜索的隨機性減弱；當 過大時會使蟻群的搜索過早陷于局部最優(yōu)。期望值啟發(fā)式因子反映了蟻群在路徑搜索中先驗性、確定性因素作用的強度； 值越大，螞蟻在某個局部點上選擇局部最短路徑的可能性越大；雖然搜索的收斂速度得以加快，但蟻群在最優(yōu)路徑的搜索過程中隨機性 減弱，易于陷入局部最優(yōu)。64信息素揮發(fā)度1- 7.5.2 蟻群

30、算法的參數(shù)選擇當要處理的問題規(guī)模比較大時，會使那些從來未被搜索到的路徑(可行解)上的信息量減小到接近于0，因而降低了算法的全局搜索能力；而且當1- 過大時，以前搜索過的路徑被再次選擇的可能性過大，也會影響到算法的隨機性能和全局搜索能力；反之，通過減小信息素揮發(fā)度 1- 雖然可以提高算法的隨機性能和全局搜索能力，但又會使算法的收斂速度降低。信息素啟發(fā)因子期望值啟發(fā)式因子信息素揮發(fā)度1-65第7章 群智能算法及其應用7.1 群智能算法產(chǎn)生的背景7.2 粒子群優(yōu)化算法 7.3 量子粒子群優(yōu)化算法 7.4 粒子群優(yōu)化算法的應用7.5 基本蟻群算法7.6 改進蟻群算法 7.7 蟻群算法的應用667.6

31、改進蟻群算法7.6.1 螞蟻-Q系統(tǒng)7.6.2 蟻群系統(tǒng)7.6.2 最大-最小螞蟻系統(tǒng)7.6.2 自適應蟻群算法67 1995年，意大利學者M.Luca，M.Gambardella, M.Dorigo提出了螞蟻Q 系統(tǒng)（Ant-Q System）。7.6.1 螞蟻-Q系統(tǒng) 在解構(gòu)造過程中提出了偽隨機比例狀態(tài)遷移規(guī)則；信息素局部更新規(guī)則引入強化學習中的Q學習機制；在ACA算法的基礎上，進行了以下創(chuàng)新： 在信息素的全局更新中采用了精英策略。68 7.6.1 螞蟻-Q系統(tǒng)（7.24）根據(jù)式（7.25）計算概率分布：（7.25）AQ值按照如下規(guī)則進行更新：（7.26）（7.27）69 1996年，Ga

32、mbardella和Dorigo又在Ant-Q算法的基礎上，提出一種修正的蟻群算法，稱之為蟻群系統(tǒng)(ant colony system, ACS)，該算法可以看成是Ant-Q算法的特例。7.6.2 蟻群系統(tǒng) 螞蟻選擇城市時遵循的規(guī)則不同，這里使用的是所謂的狀態(tài)轉(zhuǎn)移規(guī)則:與ACA算法的不同之處：（7.28）其中：Sk是序號為k的螞蟻所選中的下一個節(jié)點; q表示一個隨機變量，q0是一個適當選定的閾值。707.6.2 蟻群系統(tǒng) 主要不同在于螞蟻選擇下一城市之前，多進行了一次隨機試 驗，將選擇情況分成“利用已知信息”和“探索”兩類。相比ACA算法，進行了以下創(chuàng)新： 還提出了所謂的精英策略(elitis

33、t strategy) 。 結(jié)果發(fā)現(xiàn)，對精英螞蟻數(shù)而言有一個最優(yōu)的范圍：低于此范 圍，增加精英螞蟻數(shù)可較早地發(fā)現(xiàn)更好的路徑，高于此范圍， 精英螞蟻會在搜索早期迫使尋優(yōu)過程始終在次優(yōu)解附近，導致 性能變差。71 最大-最小螞蟻系統(tǒng)(Max-Min Ant System，MMAS)是德國學者Thomas Stutzle等在1997年提出的。7.6.3 最大-最小螞蟻系統(tǒng) 該算法在啟動時將所有支路上的信息素濃度初始化為最大值 max；為了更好地利用歷史信息，每次迭代后按揮發(fā)系數(shù)降低信息素濃度，只有最佳路徑上的支路才允許增加其信息素濃度并保持在高水平上，也就是用當前找到的最好解更新信息素來指引螞蟻向更

34、高質(zhì)量的解空間搜索的貪婪策略。MMAS算法思想：72 7.6.3 最大-最小螞蟻系統(tǒng)（7.29）為了避免算法過早收斂于局部最優(yōu)解，將各條路徑可能的信息素濃度限制于min, max。采用了讓軌跡上信息素濃度的增加正比于max和當前濃度(x, y)之差的平滑機制，如式（7.30）所示，其中0 n0+1 時 開始減小 n 越大 越小。算法具體實現(xiàn)時，0 、n0 可以根據(jù)需要進行調(diào)節(jié)。787.6.4 自適應蟻群算法784.自適應信息素強度Q(n)當算法陷入局部收斂時采用時變函數(shù)Q(n)來代替基本蟻群算法中調(diào)整信息素 中為常數(shù)項的信息素強度Q，即選擇 ，隨著人工螞蟻搜索過程動態(tài)的調(diào)整，Q(n)如下所示：

35、 （7.34）其中，Q0為初始信息素強度，可以根據(jù)需要調(diào)整。 797.6.4 自適應蟻群算法795. 改進的信息素更新策略信息素更新策略存在多種方式：走過的全部路徑上的信息素進行更新，導致算法獲得的結(jié)果振蕩, 不易收斂更新搜索到最優(yōu)邊上的信息素，則進一步加強了蟻群算法的正反饋作用，導致搜索過程迅速陷入局部最優(yōu)解807.6.4 自適應蟻群算法805. 改進的信息素更新策略記l為每代最優(yōu)解對應的螞蟻，螞蟻總數(shù)為m。 （1） 當算法未陷入局部最優(yōu)時，采用全局更新和局部更新結(jié)合的策略，其中和Q均為初始值： Step1：全局更新，計算所有螞蟻經(jīng)過路徑上的信息素增量： （7.35） Step2：局部更新，

36、如果該代最優(yōu)解為歷代最優(yōu)解，則調(diào)整螞蟻l經(jīng)過路徑上的信息素增量： （7.36） Step3：更新所有螞蟻經(jīng)過路徑上的信息素： （7.37） 817.6.4 自適應蟻群算法815. 改進的信息素更新策略記l為每代最優(yōu)解對應的螞蟻，螞蟻總數(shù)為m。 （2）當算法陷入局部最優(yōu)時,僅采用全局更新策略： Step1：計算除最優(yōu)螞蟻l外所有其他螞蟻經(jīng)過路徑上的信息素增量： （7.38） Step2：計算螞蟻l經(jīng)過的路徑上的信息素增量： （7.39） Step3：更新除螞蟻l外所有其他螞蟻經(jīng)過路徑上的信息素： （7.40） Step4：更新螞蟻l經(jīng)過路徑上的信息素： （7.41） 827.6.4 自適應蟻群算法826. 限定信息素的范圍通過縮小各路徑信息素的差距，可以使算法有更好的全局收斂性。對各路徑上的信息素進行限定，以防止某些路徑上的信息素過大或過小而影響算法的全局收斂性。837.6.4 自適應蟻群算法83圖7.5 自適應蟻群算法流程圖84第7章 群智能算法及其應用7.1 群智能算法產(chǎn)生的背景7.2 粒子群優(yōu)化算