【正文】 Date108。Date107 蟻群優(yōu)化算法 — 參考書 2? 蟻群算法及其應(yīng)用 李士勇 哈工大出版社 國內(nèi)首部 蟻 群算法的 專 著，系 統(tǒng) 地 闡 述 蟻 群算法的基本原理、基本 蟻 群算法及改 進 算法， 蟻 群算法與 遺傳 、免疫算法的融合，自適 應(yīng)蟻 群算法，并行 蟻 群算法， 蟻 群算法的收 斂 性與理 論 模型及其在 優(yōu) 化 問題 中的 應(yīng) 用。Date106 蟻群優(yōu)化算法 — 參考書 1? 智能蟻群算法及應(yīng)用 吳啟迪 上?？萍汲霭嫔鐝幕窘Y(jié)構(gòu)、算法特點、改進方法、突破途徑、實現(xiàn)模式及應(yīng)用模式等方面進行了論述。當(dāng)一只螞蟻遇到一個數(shù)據(jù)時即拾起并繼續(xù)行走，在行走過程中，如果遇到附近的數(shù)據(jù)與背負的數(shù)據(jù)相似性高于設(shè)置的標(biāo)準(zhǔn)時則將數(shù)據(jù)放置在該位置，繼續(xù)移動。以分布的形式做少量的計算來刷新全局路由選擇信息?！? 用蟻群算法在分層圖模型的基礎(chǔ)上求解動態(tài) RWA 問題。Date102 應(yīng)用 同時 ,分布式的計算方式則克服了傳統(tǒng)集中式算法可擴展性差的缺點 ,更適應(yīng)現(xiàn)代頻繁變化的大型光網(wǎng)絡(luò)。由于 RWA 問題是 NPC 問題 ,文獻中大多將 RWA 問題拆分成路由和波長分配兩個子問題分別加以解決。Date101 應(yīng)用 光 網(wǎng)絡(luò)的智能管理 分布式動態(tài)選路及波長分配 ( RWA , Routing and Wavelength Assignment ) 是指在實時業(yè)務(wù)情況下光通路的路由選擇和波長分配的優(yōu)化問題 ,是實現(xiàn)自動交換光網(wǎng)絡(luò) (ASON ,Automatically Switched Optical Network) 的關(guān)鍵技術(shù)之一。 以上三種算法中，蟻環(huán)算法效果最好，因為他用的是全局信息，而其余兩種算法用的是局部信息。Date100 信息素的更改 蟻量算法（ antquantity algorithm）的信息素更新為 ,Q為常量， 表示 i到 j的距離，這樣信息濃度會隨城市距離的減小而加大。實際上這種方式等價于蟻群離線方式中只有一只螞蟻。該算法中，蟻群中螞蟻的先后出行順序沒有相關(guān)性，但是每次循環(huán)需要記憶 m只螞蟻的行走路徑，以進行比較選擇最優(yōu)路徑。 Q為一個常數(shù)，該算法名為蟻環(huán)算法（ antcycle algotithm） ,特點是行走的路徑越短對應(yīng)保存的信息素的值就越大。更新公式為 第 s+1只螞蟻根據(jù) 重新計算路由表。 其中， 為第 k1次循環(huán)后的的信息素的痕跡值。Date96 信息素的更改 離線方式的信息素更新可以進一步分為單螞蟻離線更新和蟻群離線更新。離線方式（同步更新方式）的主要思想是在若干只螞蟻完成 n個城市的訪問后，統(tǒng)一對殘留信息進行更新處理。二、終止條件 1 給定一個外循環(huán)的最大數(shù)目，表明已經(jīng)有足夠的螞蟻工作； 2 當(dāng)前最優(yōu)解連續(xù) K次相同而停止，其中 K是一個給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)； 3 目標(biāo)值控制規(guī)則，給定優(yōu)化問題（目標(biāo)最小化）的一個下界和一個誤差值，當(dāng)算法得到的目標(biāo)值同下界之差小于給定的誤差值時，算法終止。 Dorigo在求解 TSP問題時，推薦參數(shù)的最佳設(shè)置為： 。在 GBAS中， T集合表示滿足約束條件的候選集，在背包問題的蟻群算法中由判別條件 ， 來實現(xiàn)記 憶功能。Date92 每一節(jié)點的記憶信息和系數(shù)的確定 需要記憶的信息 第二部分需要記憶的信息是每個螞蟻的記憶表中存儲著的自身的歷史信息，這一部分主要由算法的中的 記憶，表示螞蟻已經(jīng)行走過的節(jié)點。 Date91 每一節(jié)點的記憶信息和系數(shù)的確定 需要記憶的信息算法中需要記憶的信息有三部分。把 GBAS算法中步驟 3中的改為 ，若滿足此條件則替換當(dāng)前最好解為 ，對 W上的弧進行信息素的加強，其他弧進行信息素的揮發(fā)。若 則 ，否則，此螞蟻不再繼續(xù)行走，退回起點。設(shè)第 s只螞蟻第 k步所走的路線為 ，表示螞蟻從 0點出發(fā)，順序到達 。Date89 解的表達形式與算法的實現(xiàn) 算法的實現(xiàn)建立有向圖 ，其中 A中共有 條弧。Date88 解的表達形式與算法的實現(xiàn) 算法的實現(xiàn)例： 01背包問題的解順序表達形式與算法實現(xiàn)。 諸如車間作業(yè)及下料等問題，他們的共同特點是解以一個順序表示。而對于一般以順序作為解的優(yōu)化問題，誰在第一是很重要的。 定義 ：若一個馬爾可夫過程 ，對任意給定的 滿足 則稱馬爾可夫過程 依概率 1收斂到 。第 s只螞蟻在第 k輪轉(zhuǎn)移只由 決定，這個螞蟻行走的路徑和 一起，共同決定了 ，再通過信息素的更新原則可以進一步得到 。Date71 一般蟻群算法的框架一般蟻群算法的框架和 GBAS基本相同，有三個組成部分： 蟻群的活動； 信息素的揮發(fā)； 信息素的增強；主要體現(xiàn)在前面的算法中步驟 2和步驟 3中的轉(zhuǎn)移概率公式和信息素更新公式。第 K次循環(huán)前的信息素和最優(yōu)解為 ，經(jīng)過第 K次外循環(huán)后，得到 。第三次外循環(huán)后得到的信息素矩陣為：Date70 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 螞蟻以一定的概率從城市 i到城市 j進行轉(zhuǎn)移，信息素的更新在 STEP 3 完成，并隨 K而 變化。得到更新矩陣這是第一次外循環(huán)結(jié)束的狀態(tài)。 矩陣共有 12條弧，初始信息素記憶矩陣為：Date66 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS）執(zhí)行 GBAS算法的步驟 2，假設(shè)螞蟻的行走路線分別為：當(dāng)前最優(yōu)解為，這個解是截止到當(dāng)前的最優(yōu)解，碰巧是實際最優(yōu)解Date67 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS）按算法步驟 3的信息素更新規(guī)則，得到更新矩陣這是第一次外循環(huán)結(jié)束的狀態(tài)。四個城市的非對稱 TSP問題，距離矩陣和城市圖示如下：Date65 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng) （ GBAS）假設(shè)共 4只螞蟻，所有螞蟻都從城市 A出發(fā)，揮發(fā)因子 。 在 STEP 3中，蟻群永遠記憶到目前為止的最優(yōu)解。也就是說，增強過程體現(xiàn)在觀察蟻群（ m只螞蟻）中每只螞蟻所找到的路徑，并選擇其中最優(yōu)路徑上的弧進行信息素的增強，揮發(fā)過程是所有弧都進行的，不于螞蟻數(shù)量相關(guān)。 2 信息素增強（ reinforcement） 增強過程是蟻群優(yōu)化算法中可選的部分，稱為離線更新方式（還有在線更新方式）。Date63 — 基于圖的蟻群系統(tǒng) （ GBAS） 以上算法中，在螞蟻的搜尋過程中，以信息素的概率分布來決定從城市i到城市 j的轉(zhuǎn)移。 得到新的 ，重復(fù)步驟 STEP 1。若 ，則 。Date61 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS）STRP 3 對 ，若 ，按 中城市的順序計算路徑程度；若 ，路徑長度置為一個無窮大值（即不可達）。當(dāng)螞蟻在城市 i， 若 完成第 s只螞蟻的計算。否則使螞蟻 s從起點 出發(fā)，用 表示螞蟻 s行走的城市集合，初始 為空集， 。當(dāng)前最好解是 。 螞蟻在尋找過程中，或者找到一個解后，會評估該解或解的一部分的優(yōu)化程度，并把評價信息保存在相關(guān)連接的信息素中。 信息素的更新方式有 2種，一是揮發(fā)，也就是所有路徑上的信息素以一定的比