【正文】 107 蟻群優(yōu)化算法 — 參考書 1n 智能蟻群算法及應(yīng)用 吳啟迪 上?？萍汲霭嫔鐝幕窘Y(jié)構(gòu)、算法特點、改進方法、突破途徑、實現(xiàn)模式及應(yīng)用模式等方面進行了論述。103 應(yīng)用 2/5 同時 ,分布式的計算方式則克服了傳統(tǒng)集中式算法可擴展性差的缺點 ,更適應(yīng)現(xiàn)代頻繁變化的大型光網(wǎng)絡(luò)。101 信息素的更改 6/6 蟻量算法（ antquantity algorithm）的信息素更新為 ,Q為常量， 表示 i到 j的距離，這樣信息濃度會隨城市距離的減小而加大。更新公式為 第 s+1只螞蟻根據(jù) 重新計算路由表。二、終止條件 1 給定一個外循環(huán)的最大數(shù)目，表明已經(jīng)有足夠的螞蟻工作； 2 當(dāng)前最優(yōu)解連續(xù) K次相同而停止，其中 K是一個給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)； 3 目標值控制規(guī)則，給定優(yōu)化問題（目標最小化）的一個下界和一個誤差值，當(dāng)算法得到的目標值同下界之差小于給定的誤差值時，算法終止。 92 每一節(jié)點的記憶信息和系數(shù)的確定 需要記憶的信息 1/3算法中需要記憶的信息有三部分。90 解的表達形式與算法的實現(xiàn) 3/4 算法的實現(xiàn)建立有向圖 ，其中 A中共有 條弧。 定義 ：若一個馬爾可夫過程 ，對任意給定的 滿足 則稱馬爾可夫過程 依概率 1收斂到 。第三次外循環(huán)后得到的信息素矩陣為：71 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 12/12 螞蟻以一定的概率從城市 i到城市 j進行轉(zhuǎn)移，信息素的更新在 STEP 3 完成，并隨 K而變化。 在 STEP 3中，蟻群永遠記憶到目前為止的最優(yōu)解。 得到新的 ，重復(fù)步驟 STEP 1。否則使螞蟻 s從起點 出發(fā)，用 表示螞蟻 s行走的城市集合，初始 為空集， 。 2 可見度，即先驗值。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。 尋找食物的過程繼續(xù)進行，則按信息素的指導(dǎo)，蟻群在 ABD路線上增派一只螞蟻（共 2只），而 ACD路線上仍然為一只螞蟻。路徑越長，釋放的激索濃度越低 .當(dāng)后來的螞蟻再次碰到這個路口的時候．選擇激素濃度較高路徑概率就會相對較大。 Costa和 Herz還提出了一種 AS在規(guī)劃問題方面的擴展應(yīng)用 —— 圖著色問題，并取得了可與其他啟發(fā)式算法相比的效果。其基本思想是將待聚類數(shù)據(jù)隨機地散布到一個二維平面內(nèi)，然后將虛擬螞蟻分布到這個空間內(nèi)，并以隨機方式移動，當(dāng)一只螞蟻遇到一個待聚類數(shù)據(jù)時即將之拾起并繼續(xù)隨機運動，若運動路徑附近的數(shù)據(jù)與背負的數(shù)據(jù)相似性高于設(shè)置的標準則將其放置在該位置，然后繼續(xù)移動，重復(fù)上述數(shù)據(jù)搬運過程。 HP公司和英國電信公司在 90年代中后期都開展了這方面的研究，設(shè)計了蟻群路由算法（ Ant Colony Routing, ACR）。 45 7/7 這種算法求解 TSP的能力與 AS、精英策略 AS、遺傳算法和模擬退火算法進行了比較。 ACS與 AS之間存在三方面的主要差異：首先， ACS采用了更為大膽的行為選擇規(guī)則；其次，只增強屬于全局最優(yōu)解的路徑上的信息素。通過與其它各種通用的啟發(fā)式算法相比，在不大于 75城市的 TSP中，這三種基本算法的求解能力還是比較理想的，但是當(dāng)問題規(guī)模擴展時， AS的解題能力大幅度下降。更為重要是，群智能潛在的并行性和分布式特點為處理大量的以數(shù)據(jù)庫形式存在的數(shù)據(jù)提供了技術(shù)保證?，F(xiàn)在其應(yīng)用領(lǐng)域已擴展到多目標優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識別、電信 QoS管理、生物系統(tǒng)建模、流程規(guī)劃、信號處理、機器人控制、決策支持以及仿真和系統(tǒng)辯識等方面，群智能理論和方法為解決這類應(yīng)用問題提供了新的途徑 。n 定義 多項式問題 給定一個組合優(yōu)化問題，若存在一個多項式算法，稱該問題為多項式時間可解問題，或簡稱 多項式問題 (或 P問題 ). 所有多項式問題的集合記為 P.n 例：線性規(guī)劃是否為多項式問題？25 計算復(fù)雜性參考書 11/11n 計算復(fù)雜性 , 作者： Christos， Papadimitriou清華大學(xué)出版社， 2022年 9月 第 1版n 計算復(fù)雜性導(dǎo)論， 作者：堵丁柱等， 高等教育出版社， 2022年 8月第 1版26 啟發(fā)式算法 _定義 1/6n 啟發(fā)式算法（ heuristic algorithm）n 定義 1. 基于 直觀或經(jīng)驗 構(gòu)造的算法，在可接受的花費（時間、空間）下，給出待解組合優(yōu)化問題的每個實例的一個 可行解 ，該可行解與最優(yōu)解偏差事先不一定可以預(yù)計 .n 定義 2. 啟發(fā)式算法是一種技術(shù)，在可接受的計算費用內(nèi)尋找最好解，但不保證該解的可行性與最優(yōu)性，無法描述該解與最優(yōu)解的近似程度。17 計算復(fù)雜性的概念 3/11n 問題 （ problem） ： 要回答的一般性提問，通常含有若干個滿足一定條件的參數(shù)（或自由變量）。 數(shù)學(xué)模型：8 組合優(yōu)化問題 2/8組合優(yōu)化問題的三參數(shù)表示： 9 組合優(yōu)化問題 3/8n 例 1 01背包問題（ 01 knapsack problem）10 組合優(yōu)化問題 4/811 組合優(yōu)化問題 5/8n 例 2 旅行商問題（ TSP,traveling salesman problem） 管梅谷教授 1960年首先提出，國際上稱之為中國郵遞員問題。 問題描述：一商人去 n個城市銷貨，所有城市走一遍再回到起點，使所走路程最短?？梢詮膬煞矫婷枋觯? （ 1）對所有參數(shù)的一般性描述； （ 2）答案（或解）必須滿足的性質(zhì)。n 特點（與傳統(tǒng)優(yōu)化方法不同）： 憑直觀和經(jīng)驗給出算法；不考慮所得解與最優(yōu)解的偏離程度 .27 啟發(fā)式算法 _優(yōu)點 2/6 優(yōu)點：（ 1）有可能比簡化數(shù)學(xué)模型解的誤差??；（ 2）對有些難題，計算時間可接受；（ 3）可用于某些最優(yōu)化算法（如分支定界算 法）之中的估界；（ 4）直觀易行；（ 5）速度較快；（ 6）程序簡單，易修改。36 蟻群優(yōu)化算法研究背景 1/3 群智能理論研究領(lǐng)域有兩種主要的算法：蟻群算法 (Ant Colony Optimization, ACO)和微粒群算法（ Particle Swarm Optimization, PSO）。無論是從理論研究還是應(yīng)用研究的角度分析，群智能理論及其應(yīng)用研究都是具有重要學(xué)術(shù)意義和現(xiàn)實價值的。 因此，其后的 ACO研究工作主要都集中于 AS性能的改進方面。其中， 0ρ1是信息素揮發(fā)參數(shù)， 是從尋路開始到當(dāng)前為止全局最優(yōu)的路徑長度。在大型TSP問題中（最多包含 132座城市），基于 AS的算法都顯示出了優(yōu)于 GA和 SA的特性。 每只螞蟻就像蟻群優(yōu)化算法中一樣，根據(jù)它在網(wǎng)絡(luò)上的經(jīng)驗與性能，動態(tài)更新路由表項。按照這樣的方法可實現(xiàn)對相似數(shù)據(jù)的聚類。51 蟻群優(yōu)化算法概念 蟻群算法原理 簡化的螞蟻尋食過程 自然蟻群與人工蟻群算法 蟻群算法與 TSP問題 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 一般蟻群算法的框架52 蟻群算法原理 蟻群算法是對自然界螞蟻的尋徑方式進行模似而得出的一種仿生算法。這樣形成一個正反饋。再經(jīng)過 36個時間單位后，兩條線路上的信息素單位積累為 12和 4，比值為 3： 1。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。 信息素的更新方式有 2種，一是揮發(fā)，也就是所有路徑上的信息素以一定的比率進行減少，模擬自然蟻群的信息素隨時間揮發(fā)的過程；二是增強，給評價值 “好 ”(有螞蟻走過 )的邊增加信息素。STEP 2 (內(nèi)循環(huán) ) 按螞蟻 的順序分別計算。63 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 4/12在 STEP 3 中，揮發(fā)因子 對于一個固定的 ，滿足并且 經(jīng)過 k次揮發(fā)，非最優(yōu)路徑的信息素逐漸減少至消失。65圖的蟻群系統(tǒng)（ GBAS） 6/12可以驗證，下式滿足：即 是一個隨機矩陣。假設(shè)第 K次外循環(huán)后得到信息素矩陣 ，得到當(dāng)前最優(yōu)解 。75 GBAS算法的收斂性分析 1/8 定理 滿足 指定條件 的馬爾可夫過程