【正文】 的順序分別計算。算法步驟如下：STEP 0 對 n個城市的 TSP問題，城市間的距離矩陣為 ，給 TSP圖中的每一條弧 賦信息素初值 ，假設(shè) m只螞蟻在工作，所有螞蟻都從同一城市 出發(fā)。 信息素的更新方式有 2種，一是揮發(fā)，也就是所有路徑上的信息素以一定的比率進(jìn)行減少，模擬自然蟻群的信息素隨時間揮發(fā)的過程；二是增強(qiáng)，給評價值 “好 ”(有螞蟻走過 )的邊增加信息素。57 蟻群算法與 TSP問題 1/3TSP問題表示為一個 N個城市的有向圖 G=（ N， A），其中 城市之間距離目標(biāo)函數(shù)為 ，其中 為城市 1,2， …n 的一個排列， 。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。這也就是前面所提到的正反饋效應(yīng)。再經(jīng)過 36個時間單位后，兩條線路上的信息素單位積累為 12和 4，比值為 3： 1。假設(shè)初始時每條分配路線一只螞蟻，每個時間單位行走一步，本圖為經(jīng)過 9個時間單位時的情形：走 ABD的螞蟻到達(dá)終點，而走 ACD的螞蟻剛好走到 C點，為一半路程。這樣形成一個正反饋。這是因為螞蟻在尋找路徑時會在路徑上釋放出一種特殊的信息素。51 蟻群優(yōu)化算法概念 蟻群算法原理 簡化的螞蟻尋食過程 自然蟻群與人工蟻群算法 蟻群算法與 TSP問題 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 一般蟻群算法的框架52 蟻群算法原理 蟻群算法是對自然界螞蟻的尋徑方式進(jìn)行模似而得出的一種仿生算法。利用 MAXMIN AS解決 PAQ也取得了比較理想的效果，并通過實驗中的計算數(shù)據(jù)證明采用該方法處理 PAQ比較早的 SA算法更好，且與禁忌搜索算法性能相當(dāng)。按照這樣的方法可實現(xiàn)對相似數(shù)據(jù)的聚類。目前這方面的應(yīng)用研究仍在升溫，因為通信網(wǎng)絡(luò)的分布式信息結(jié)構(gòu)、非穩(wěn)定隨機(jī)動態(tài)特性以及網(wǎng)絡(luò)狀態(tài)的異步演化與 ACO的算法本質(zhì)和特性非常相似。 每只螞蟻就像蟻群優(yōu)化算法中一樣，根據(jù)它在網(wǎng)絡(luò)上的經(jīng)驗與性能，動態(tài)更新路由表項。 蟻群優(yōu)化算法并不是旅行商問題的最佳解決方法，但是它卻為解決組合優(yōu)化問題提供了新思路，并很快被應(yīng)用到其它組合優(yōu)化問題中。在大型TSP問題中（最多包含 132座城市），基于 AS的算法都顯示出了優(yōu)于 GA和 SA的特性。為了避免搜索停滯，路徑上的信息素濃度被限制在 [MAX， MIN ]范圍內(nèi)，另外，信息素的初始值被設(shè)為其取值上限，這樣有助于增加算法初始階段的搜索能力。其中， 0ρ1是信息素?fù)]發(fā)參數(shù)， 是從尋路開始到當(dāng)前為止全局最優(yōu)的路徑長度。 41 3/7 為了進(jìn)一步克服 AS中暴露出的問題，提出了蟻群系統(tǒng) (Ant Colony System, ACS)。 因此，其后的 ACO研究工作主要都集中于 AS性能的改進(jìn)方面。而且，取得了最佳結(jié)果的 ACO是通過引入局部搜索算法實現(xiàn)的，這實際上是一些結(jié)合了標(biāo)準(zhǔn)局域搜索算法的混合型概率搜索算法，有利于提高蟻群各級系統(tǒng)在優(yōu)化問題中的求解質(zhì)量。無論是從理論研究還是應(yīng)用研究的角度分析，群智能理論及其應(yīng)用研究都是具有重要學(xué)術(shù)意義和現(xiàn)實價值的。雖然概率搜索算法通常要采用較多的評價函數(shù)，但是與梯度方法及傳統(tǒng)的演化算法相比，其優(yōu)點還是顯著的 ，主要表現(xiàn)在以下幾個方面：1 無集中控制 約 束，不會因個 別 個體的故障影響整個 問題 的求解，確保了系 統(tǒng) 具 備 更 強(qiáng) 的 魯 棒性 2 以非直接的信息交流方式確保了系 統(tǒng) 的 擴(kuò) 展性 3 并行分布式算法模型，可充分利用多 處 理器 4 對問題 定 義 的 連續(xù) 性無特殊要求 5 算法 實現(xiàn)簡單 38 蟻群優(yōu)化算法研究背景 3/3 群智能方法易于實現(xiàn)，算法中僅涉及各種基本的數(shù)學(xué)操作，其數(shù)據(jù)處理過程對 CPU和內(nèi)存的要求也不高。36 蟻群優(yōu)化算法研究背景 1/3 群智能理論研究領(lǐng)域有兩種主要的算法：蟻群算法 (Ant Colony Optimization, ACO)和微粒群算法（ Particle Swarm Optimization, PSO）。提出了許多用以解決復(fù)雜優(yōu)化問題的新方法，如進(jìn)化規(guī)劃、進(jìn)化策略、遺傳算法等，這些算法成功地解決了一些實際問題。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）程序簡單，易修改。問題是在 F中找到一個點 f*，使對 F中任意的 f，有 C(f*) C(f),稱 f*為這一具體問題的最優(yōu)解（或全局最優(yōu)解） .19 計算復(fù)雜性的概念 5/11n 算法計算量的度量： 加、減、乘、除、比較的總運算次數(shù)與實例的計算機(jī)計算時的二進(jìn)制輸入數(shù)據(jù)的大小關(guān)系?？梢詮膬煞矫婷枋觯? （ 1）對所有參數(shù)的一般性描述； （ 2）答案（或解）必須滿足的性質(zhì)。到 31個城市時，要計算 325年。 問題描述：一商人去 n個城市銷貨，所有城市走一遍再回到起點，使所走路程最短。1算法設(shè)計與分析 第七章補(bǔ)充材料 蟻群算法介紹山東師范大學(xué)計算機(jī)系授課：徐連誠， 3432， 2022年 9月 5日 — 2022年 1月 20日2內(nèi) 容一、啟發(fā)式方法概述二、蟻群優(yōu)化算法3背 景n 傳統(tǒng)實際問題的特點 連續(xù)性問題 —— 主要以微積分為基礎(chǔ)，且問題規(guī)模較小n 傳統(tǒng)的優(yōu)化方法 追求準(zhǔn)確 —— 精確解 理論的完美 —— 結(jié)果漂亮 主要方法：線性與非線性規(guī)劃、動態(tài)規(guī)劃、多目標(biāo)規(guī)劃、整數(shù)規(guī)劃等；排隊論、庫存論、對策論、決策論等。 數(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個為起終點需要 (n1)!個枚舉，設(shè)計算機(jī) 1秒能完成 24個城市的枚舉，則城市數(shù)與計算時間的關(guān)系如下表：16 計算復(fù)雜性的概念 2/11城市數(shù)24 25 26 27 28 29 30 31計算時間1sec24sec10minhourdaydayyear325year隨城市增多，計算時間增加很快。17 計算復(fù)雜性的概念 3/11n 問題 （ problem） ： 要回答的一般性提問，通常含有若干個滿足一定條件的參數(shù)（或自由變量）。C是費用函數(shù)，是由 F到 R（ 實數(shù)集）的映像。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)解的近似程度。 (2）概率分析 （ probability analysis） 用最壞情況分析，會因一個最壞實例影響總體評價 . 在實例數(shù)據(jù)服從一定概率分布情形下，研究算法復(fù)雜性和解的效果 . (3)大規(guī)模計算分析 通過大量實例計算，評價算法效果 .n 注意數(shù)據(jù)的隨機(jī)性和代表性 .322 蟻群優(yōu)化算法1. 蟻群優(yōu)化算法概述2. 蟻群優(yōu)化算法概念3. 算法模型和收