【正文】 20 計(jì)算復(fù)雜性的概念 6/11n 算法計(jì)算量的度量之例 —— TSP枚舉法計(jì)算量的統(tǒng)計(jì)：21 計(jì)算復(fù)雜性的概念 7/11n 實(shí)例的輸入長(zhǎng)度：n 實(shí)例的輸入長(zhǎng)度是 n的多項(xiàng)式函數(shù)n 枚舉法的基本計(jì)算量是 n的階乘函數(shù)， 隨 n的增加，比指數(shù)函數(shù)增加得還快 .22 計(jì)算復(fù)雜性的概念 8/1123 計(jì)算復(fù)雜性的概念 9/11定義 多項(xiàng)式算法給定問(wèn)題 P， 算法 A， 對(duì)一個(gè)實(shí)例 I， 存在多項(xiàng)式函數(shù) g(x)， 使（ XX ）成立，稱 算法 A對(duì)實(shí)例 I是多項(xiàng)式算法 ；若存在多項(xiàng)式函數(shù) g(x)， 使（ XX ）對(duì)問(wèn)題 P的任意實(shí)例 I都成立，稱 算法 A為解決該問(wèn)題 P的多項(xiàng)式算法 .當(dāng) g(x)為指數(shù)函數(shù)時(shí)，稱 A為 P的指數(shù)時(shí)間算法。而且，這種方法只需目標(biāo)函數(shù)的輸出值，而無(wú)需其梯度信息。該系統(tǒng)的提出是以 AntQ算法為基礎(chǔ)的。比較典型的應(yīng)用研究包括：網(wǎng)絡(luò)路由優(yōu)化、數(shù)據(jù)挖掘以及一些經(jīng)典的組合優(yōu)化問(wèn)題。利用 ACO實(shí)現(xiàn)對(duì)生產(chǎn)流程和特料管理的綜合優(yōu)化，并通過(guò)與遺傳、模擬退火和禁忌搜索算法的比較證明了 ACO的工程應(yīng)用價(jià)值。54 簡(jiǎn)化的螞蟻尋食過(guò)程 2/3本圖為從開始算起，經(jīng)過(guò) 18個(gè)時(shí)間單位時(shí)的情形：走 ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn) A，而走 ACD的螞蟻剛好走到 D點(diǎn)。58 蟻群算法與 TSP問(wèn)題 2/3 TSP問(wèn)題的人工蟻群算法中，假設(shè) m只螞蟻在圖的相鄰節(jié)點(diǎn)間移動(dòng)，從而協(xié)作異步地得到問(wèn)題的解。若 ，則 。得到更新矩陣這是第一次外循環(huán)結(jié)束的狀態(tài)。89 解的表達(dá)形式與算法的實(shí)現(xiàn) 2/4 算法的實(shí)現(xiàn)例： 01背包問(wèn)題的解順序表達(dá)形式與算法實(shí)現(xiàn)。 Dorigo在求解 TSP問(wèn)題時(shí)，推薦參數(shù)的最佳設(shè)置為： 。實(shí)際上這種方式等價(jià)于蟻群離線方式中只有一只螞蟻。當(dāng)一只螞蟻遇到一個(gè)數(shù)據(jù)時(shí)即拾起并繼續(xù)行走，在行走過(guò)程中，如果遇到附近的數(shù)據(jù)與背負(fù)的數(shù)據(jù)相似性高于設(shè)置的標(biāo)準(zhǔn)時(shí)則將數(shù)據(jù)放置在該位置，繼續(xù)移動(dòng)?！? 用蟻群算法在分層圖模型的基礎(chǔ)上求解動(dòng)態(tài) RWA 問(wèn)題。 Q為一個(gè)常數(shù)，該算法名為蟻環(huán)算法（ antcycle algotithm） ,特點(diǎn)是行走的路徑越短對(duì)應(yīng)保存的信息素的值就越大。93 每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定 需要記憶的信息 2/3 第二部分需要記憶的信息是每個(gè)螞蟻的記憶表中存儲(chǔ)著的自身的歷史信息，這一部分主要由算法的中的 記憶，表示螞蟻已經(jīng)行走過(guò)的節(jié)點(diǎn)。而對(duì)于一般以順序作為解的優(yōu)化問(wèn)題，誰(shuí)在第一是很重要的。四個(gè)城市的非對(duì)稱 TSP問(wèn)題，距離矩陣和城市圖示如下：66 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 7/12假設(shè)共 4只螞蟻，所有螞蟻都從城市 A出發(fā)，揮發(fā)因子 。當(dāng)螞蟻在城市 i，若 完成第 s只螞蟻的計(jì)算。 兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)。最優(yōu)路徑上的激索濃度越來(lái)越大．而其它的路徑上激素濃度卻會(huì)隨著時(shí)間的流逝而消減。49 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 4/5 ACO還在許多經(jīng)典組合優(yōu)化問(wèn)題中獲得了成功的應(yīng)用，如二次規(guī)劃問(wèn)題（ QAP）、機(jī)器人路徑規(guī)劃、作業(yè)流程規(guī)劃、圖著色（ Graph Coloring）等問(wèn)題。而且在 Rankbased AS和精英策略 AS均優(yōu)于基本 AS的同時(shí)，前者還獲得了比精英策略 AS更好的解。較早的一種改進(jìn)方法是精英策略 (Elitist Strategy)，其思想是在算法開始后即對(duì)所有已發(fā)現(xiàn)的最好路徑給予額外的增強(qiáng)，并將隨后與之對(duì)應(yīng)的行程記為 Tgb(全局最優(yōu)行程 )，當(dāng)進(jìn)行信息素更新時(shí)，對(duì)這些行程予以加權(quán)，同時(shí)將經(jīng)過(guò)這些行程的螞蟻記為 “精英 ”，從而增大較好行程的選擇機(jī)會(huì)。前者是對(duì)螞蟻群落食物采集過(guò)程的模擬，已成功應(yīng)用于許多離散優(yōu)化問(wèn)題。n 實(shí)例 （ instance） :給問(wèn)題的所有參數(shù)指定具體值，得到問(wèn)題的一個(gè)實(shí)例。通過(guò)數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等，可以涉及信息技術(shù)、經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸和通信網(wǎng)絡(luò)等許多方面。24 計(jì)算復(fù)雜性的概念 10/11n 利用復(fù)雜性分析對(duì)組合優(yōu)化問(wèn)題歸類。已完成的群智能理論和應(yīng)用方法研究證明群智能方法是一種能夠有效解決大多數(shù)全局優(yōu)化問(wèn)題的新方法。 AntQ將螞蟻算法和一種增強(qiáng)型學(xué)習(xí)算法 Qlearning有機(jī)的結(jié)合了起來(lái)。 47 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 2/5 蟻群算法在電信路由優(yōu)化中已取得了一定的應(yīng)用成果。50 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 5/5 許多研究者將 ACO用于了武器攻擊目標(biāo)分配和優(yōu)化問(wèn)題、車輛運(yùn)行路徑規(guī)劃、區(qū)域性無(wú)線電頻率自動(dòng)分配、 Bayesian works的訓(xùn)練和集合覆蓋等應(yīng)用優(yōu)化問(wèn)題。55 簡(jiǎn)化的螞蟻尋食過(guò)程 3/3 假設(shè)螞蟻每經(jīng)過(guò)一處所留下的信息素為一個(gè)單位，則經(jīng)過(guò) 36個(gè)時(shí)間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過(guò)不同路徑從 D點(diǎn)取得了食物，此時(shí) ABD的路線往返了 2趟，每一處的信息素為 4個(gè)單位，而 ACD的路線往返了一趟，每一處的信息素為 2個(gè)單位，其比值為 2： 1。每只螞蟻的一步轉(zhuǎn)移概率由圖中的每條邊上的兩類參數(shù)決定： 1 信息素值 也稱信息素痕跡。用如下公式對(duì) W路徑上的信息素痕跡加強(qiáng)，對(duì)其他路徑上的信息素進(jìn)行揮發(fā)。70 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 11/12重復(fù)外循環(huán)，由于 W2全局最優(yōu)解， GBAS只記錄第一個(gè)最優(yōu)解，因此一但得到了全局最優(yōu)解，信息素的更新將不再依賴于以群的行走路線，而只是不斷增強(qiáng)最優(yōu)路線的信息素，同時(shí)進(jìn)行揮發(fā)。設(shè)有一個(gè)容積為 b的背包， n個(gè)尺寸分別為 ，價(jià)值分別為 的物品， 01背包問(wèn)題的數(shù)學(xué)模型為：假設(shè)其解的順序表達(dá)形式為　　　　　　　　，其中　　　為　　　　　　的一個(gè)排列。95 蟻群的規(guī)模和停止規(guī)則一、蟻群大小 一般情況下蟻群中螞蟻的個(gè)數(shù)不超過(guò) TSP圖中節(jié)點(diǎn)的個(gè)數(shù)。100 信息素的更改 5/6 與單螞蟻離線更新方式相比，信息量記憶更小的是信息素在線更新方式，即螞蟻每走一步，馬上回溯并且更新剛剛走過(guò)的路徑上的信息素，其規(guī)則為 其中， k為螞蟻行走的第 k步。重復(fù)以上過(guò)程即可實(shí)現(xiàn)數(shù)據(jù)聚類。因此 ,近年來(lái)國(guó)內(nèi)外對(duì)RWA 并行的分布式算法表現(xiàn)出極大的興趣 ,此類算法建立的基礎(chǔ)是分層圖模型 。 98 信息素的更改 3/6TSP問(wèn)題中，蟻群優(yōu)化算法根據(jù)信息素痕跡更新方式不同可以分為不同的算法，采用離線方式，并且時(shí)，其中 W為 t循環(huán)中 m只螞蟻所行走的最佳路線或第 t只螞蟻所行走的一條路徑。第一部分信息是存在每個(gè)節(jié)點(diǎn)的路由表數(shù)據(jù)結(jié)構(gòu) ，由此決定的的轉(zhuǎn)移概率為其中 T可以看成節(jié)點(diǎn) i的鄰域。75 GBAS算法的收斂性分析 1/8 定理 滿足 指定條件 的馬爾可夫過(guò)程 依概率 1收斂到 ,其中 為一條最優(yōu)路徑 , 定義為 : 證明分析 : 蟻群算法中 ,一但達(dá)到全局最優(yōu) ,由 只記錄第一個(gè)最優(yōu)解 .證明分三部分 :n 證明以概率 1達(dá)到一個(gè)最優(yōu)路徑n 證明 (1)上式成立n 證明以概率 1收斂到一個(gè)最優(yōu)路徑76 GBAS算法的收斂性分析 2/8證明以概率 1到達(dá)一個(gè)最優(yōu)路徑 對(duì)于最優(yōu)路徑 ,令 為蟻群中的一個(gè)螞蟻在第 k次外循環(huán)后第一次走到最優(yōu)路徑 的事件 . 表示僅第 k次外循環(huán)沒(méi)有走到 的事件 ,但前 k1次可能走到過(guò)這條最優(yōu)路徑 . 永遠(yuǎn)不會(huì)被走到的事件為 ,其概率為 :77 GBAS算法的收斂性分析 3/8 任意給定的固定弧 (i,j),在第 k次循環(huán)后 ,其信息素值的下界可以計(jì)算出 .78 GBAS算法的收斂性分析 4/8令 ,任何一個(gè)固定節(jié)點(diǎn)最多有 (n1)后續(xù)節(jié)點(diǎn) ,并且其弧上的信息素值都小于 1或者等于 :蟻群中的一只螞蟻在第 次循環(huán)走到路徑 W* 的概率為一個(gè)蟻群中至少有一只螞蟻，因此這是一個(gè)蟻群到達(dá)最優(yōu)路徑的一個(gè)下界 . 上式右側(cè)與 k無(wú)關(guān) ,79 GBAS算法的收斂性分析 5/8 則取對(duì)數(shù)有從而得到80 GBAS算法的收斂性分析 6/8 證明右式成立 隨機(jī)過(guò)程 以概率 1