【正文】 智能優(yōu)化計(jì)算 2022/8/27 77 蟻群優(yōu)化算法 — 參考書(shū) 1 ? 智能蟻群算法及應(yīng)用 吳啟迪 上?？萍汲霭嫔? 從基本結(jié)構(gòu)、算法特點(diǎn)、改進(jìn)方法、突破途徑、實(shí)現(xiàn)模式及應(yīng)用模式等方面進(jìn)行了論述。 智能優(yōu)化計(jì)算 2022/8/27 73 應(yīng)用 2/5 同時(shí) ,分布式的計(jì)算方式則克服了傳統(tǒng)集中式算法可擴(kuò)展性差的缺點(diǎn) ,更適應(yīng)現(xiàn)代頻繁變化的大型光網(wǎng)絡(luò)。 ( 1 ) ( ) ( )ij ij ijk k k? ? ?? ? ? ?智能優(yōu)化計(jì)算 2022/8/27 71 信息素的更改 6/6 蟻量算法（ antquantity algorithm）的信息素更新 為 ,Q為常量， 表示 i到 j的距離，這樣信息 濃度會(huì)隨城市距離的減小而加大。更新公式為 第 s+1只螞蟻根據(jù) 重新計(jì)算路由表。 二、終止條件 1 給定一個(gè)外循環(huán)的最大數(shù)目，表明已經(jīng)有足夠的螞蟻工作； 2 當(dāng)前最優(yōu)解連續(xù) K次相同而停止，其中 K是一個(gè)給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)； 3 目標(biāo)值控制規(guī)則，給定優(yōu)化問(wèn)題（目標(biāo)最小化）的一個(gè)下界和一個(gè)誤差值，當(dāng)算法得到的目標(biāo)值同下界之差小于給定的誤差值時(shí)，算法終止。 ()0, 1 , 2 , .. .,ii L sic s m????( ( )) ( )f L t f w?( ( )) ( )f L t f w? : ( )W L t?ij?1 2 1( ) ( 0 , , , .. .. , , )kkL s i i i i ?? 11 jkijab????1ki ?智能優(yōu)化計(jì)算 2022/8/27 62 每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定 需要記憶的信息 1/3 算法中需要記憶的信息有三部分。 ( 1, 2 , ..., )ia i n? ( 1, 2 , ..., )ic i n?? ?11m a x..0 , 1 , 1 , ....,niiiniiiicxs t a x bx j n???????? ?120 , , , ..., ni i i ? ?12, , .. ., ni i i? ?1, 2 , 3, ..., n智能優(yōu)化計(jì)算 2022/8/27 60 解的表達(dá)形式與算法的實(shí)現(xiàn) 3/4 算法的實(shí)現(xiàn) 建立有向圖 ，其中 A中共有 條弧。和 體現(xiàn)了相關(guān)信息痕跡和預(yù)見(jiàn)度對(duì)螞蟻決策的相對(duì)影響。 智能優(yōu)化計(jì)算 2022/8/27 43 蟻群優(yōu)化算法 — 算法模型和收斂性分析 馬氏過(guò)程的收斂定義 GBAS算法的收斂性分析 智能優(yōu)化計(jì)算 2022/8/27 44 馬氏過(guò)程的收斂定義 蟻群優(yōu)化算法的每步迭代對(duì)應(yīng)隨機(jī)變量 其中 為信息素痕跡； 為 n城市的一個(gè)排列，最多有 個(gè)狀態(tài)。 0 1 24 1 6 1 241 6 0 1 24 1 24( 1 ) ( ( 1 ) )1 24 1 12 0 1 61 24 1 6 1 24 0ij????????????智能優(yōu)化計(jì)算 2022/8/27 39 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 10/12 重復(fù)外循環(huán)，由于上一次得到的 W2已經(jīng)是全局最優(yōu)解，因此按算法步驟 3的信息素更新規(guī)則，無(wú)論螞蟻如何行走，都只是對(duì) W2路線上的城市信息素進(jìn)行增強(qiáng)，其他的城市信息素進(jìn)行揮發(fā)。 (1 ) ( )k ij k???智能優(yōu)化計(jì)算 2022/8/27 35 圖的蟻群系統(tǒng)（ GBAS） 6/12 可以驗(yàn)證，下式滿足： 即 是一個(gè)隨機(jī)矩陣。 1 sm?? ()L s N? ()Ls()L s N?( ( ) ) ( ( ) )f L t f L W? ()W L t?( ) , : 1ij k k k? ??111( ) ( 1 ) ( 1 ) ( , )( ) ( 1 ) ( 1 ) ( , )kij k ijij k ijk k i j WWk k i j W?? ? ?? ? ??????? ? ? ???? ? ???為 上的一條弧不是 上的一條弧智能優(yōu)化計(jì)算 2022/8/27 33 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 4/12 在 STEP 3 中，揮發(fā)因子 對(duì)于一個(gè)固定的 ，滿足 并且 經(jīng)過(guò) k次揮發(fā)，非最優(yōu)路徑的信息素逐漸減少至消失。當(dāng)螞蟻在城市 i，若 完成第 s只螞蟻的計(jì)算。 信息素的更新方式有 2種，一是揮發(fā)，也就是所有路徑上的信息素以一定的比率進(jìn)行減少，模擬自然蟻群的信息素隨時(shí)間揮發(fā)的過(guò)程；二是增強(qiáng)，給評(píng)價(jià)值“好” (有螞蟻?zhàn)哌^(guò) )的邊增加信息素。較短路徑的 信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的 優(yōu)化結(jié)果。再經(jīng)過(guò) 36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為 12和 4，比值為 3： 1。這樣形成一個(gè)正反饋。 智能優(yōu)化計(jì)算 2022/8/27 21 蟻群優(yōu)化算法概念 蟻群算法原理 簡(jiǎn)化的螞蟻尋食過(guò)程 自然蟻群與人工蟻群算法 蟻群算法與 TSP問(wèn)題 初始的蟻群優(yōu)化算法 —基于圖的蟻群系統(tǒng)（ GBAS） 一般蟻群算法的框架 智能優(yōu)化計(jì)算 2022/8/27 22 蟻群算法原理 蟻群算法是對(duì)自然界螞蟻的尋徑方式進(jìn)行模似而得出的一種仿生算法。按照這樣的方法可實(shí)現(xiàn)對(duì)相似數(shù)據(jù)的聚類(lèi)。 每只螞蟻就像蟻群優(yōu)化算法中一樣，根據(jù)它在網(wǎng)絡(luò)上的經(jīng)驗(yàn)與性能，動(dòng)態(tài)更新路由表項(xiàng)。在大型TSP問(wèn)題中（最多包含 132座城市），基于 AS的算法都顯示出了優(yōu)于 GA和 SA的特性。其中， 0ρ1是信息素?fù)]發(fā)參數(shù)， 是從尋路開(kāi)始到當(dāng)前為止全局最優(yōu)的路徑長(zhǎng)度。 因此，其后的 ACO研究工作主要都集中于 AS性能的改進(jìn)方面。無(wú)論是從理論研究還是應(yīng)用研究的角度分析，群智能理論及其應(yīng)用研究都是具有重要學(xué)術(shù)意義和現(xiàn)實(shí)價(jià)值的。 智能優(yōu)化計(jì)算 2022/8/27 6 蟻群優(yōu)化算法研究背景 1/3 群智能理論研究領(lǐng)域有兩種主要的算法：蟻群算法 (Ant Colony Optimization, ACO)和微粒群算法（ Particle Swarm Optimization, PSO）。 20世紀(jì) 90年代意大利學(xué)者 M． Dorigo， V． Maniezzo，A． Colorni等從生物進(jìn)化的機(jī)制中受到啟發(fā)，通過(guò)模擬自然界螞蟻搜索路徑的行為，提出來(lái)一種新型的模擬進(jìn)化算法 —— 蟻群算法，是群智能理論研究領(lǐng)域的一種主要算法。而且，這種方法只需目標(biāo)函數(shù)的輸出值，而無(wú)需其梯度信息。 智能優(yōu)化計(jì)算 2022/8/27 10 2/7 最初提出的 AS有三種版本： Antdensity、 Antquantity和 Antcycle。該系統(tǒng)的提出是以 AntQ算法為基礎(chǔ)的。 智能優(yōu)化計(jì)算 2022/8/27 14 6/7 另一種對(duì) AS改進(jìn)的算法是 Rankbased Version AS。比較典型的應(yīng)用研究包括：網(wǎng)絡(luò)路由優(yōu)化、數(shù)據(jù)挖掘以及一些經(jīng)典的組合優(yōu)化問(wèn)題。 智能優(yōu)化計(jì)算 2022/8/27 18 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 3/5 基于群智能的聚類(lèi)算法起源于對(duì)蟻群蟻卵的分類(lèi)研究。利用 ACO實(shí)現(xiàn)對(duì)生產(chǎn)流程和特料管理的綜合優(yōu)化，并通過(guò)與遺傳、模擬退火和禁忌搜索算法的比較證明了 ACO的工程應(yīng)用價(jià)值。當(dāng)它們碰到一個(gè)還沒(méi)有走過(guò)的路口時(shí)．就隨機(jī)地挑選一條路徑前行。 智能優(yōu)化計(jì)算 2022/8/27 24 簡(jiǎn)化的螞蟻尋食過(guò)程 2/3 本圖為從開(kāi)始算起，經(jīng)過(guò) 18個(gè)時(shí)間單位時(shí)的情形：走 ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn) A，而走 ACD的螞蟻剛好走到 D點(diǎn)。 智能優(yōu)化計(jì)算 2022/8/27 26 自然蟻群與人工蟻群算法 基于以上蟻群尋找食物時(shí)的最優(yōu)路徑選擇問(wèn)題，可以構(gòu)造 人工蟻群，來(lái)解決最優(yōu)化問(wèn)題，如 TSP問(wèn)題。 }, |j), { ( iA n}{ 1 , 2 , . . . ,N Nji ???nnijd ?)(?? ??nlii lldwf1 1)(),( 21 niiiw ??11 iin ??智能優(yōu)化計(jì)算 2022/8/27 28 蟻群算法與 TSP問(wèn)題 2/3 TSP問(wèn)題的人工蟻群算法中，假設(shè) m只螞蟻在圖的相鄰節(jié)點(diǎn)間移動(dòng)，從而協(xié)作異步地得到問(wèn)題的解。 }, |j), { ( iA n}{ 1 , 2 , . . . ,N Nji ???nnijd ?)(),( ji ||1)0( Aij ??0i),2,1( nw ?? 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 2/12 STEP 1 （外循環(huán)）如果滿足算法的停止規(guī)則，則停止計(jì)算并輸出計(jì)算得到的最好解。 若 ，則 。也就是說(shuō)，增強(qiáng)過(guò)程體現(xiàn)在觀察蟻群（ m只螞蟻） 中每只螞蟻所找到的路徑，并選擇其中最優(yōu)路徑上的弧進(jìn)行信息素的增強(qiáng)， 揮發(fā)過(guò)程是所有弧都進(jìn)行的，不于螞蟻數(shù)量相關(guān)。3 : , ( 3 ) 8 。 第 K次循環(huán)前的信息素和最優(yōu)解為 ，經(jīng)過(guò) 第 K次外循環(huán)后，得到 。 （9）m in( ) , 1l n( 1 )l im 0kkkckkkc???????令：其中 ，則定理5. 2. 1的 結(jié)論也成立。 TSP問(wèn)題尋找的是最短回路，而一般優(yōu)化問(wèn)題中， STEP 3 中的判斷條件 需要根據(jù)實(shí)際問(wèn)題進(jìn)行修改。 ( , )G V A? ? ?0 , 1 , 2 , .. .. , , {( , ) | , }V n A i j i j V? ? ? ?( 1)nn? 1 ( 1 )ij nn? ??12( ) ( 0 , , , ...., )kL s i i i