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