【正文】 依概率 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達(dá)到一條最優(yōu)路徑 .當(dāng)某條最優(yōu)路徑 Z在第 k次循環(huán)被首次走到后 ,在第 k+1輪循環(huán)按信息素的更新原則 ,可以用歸納法證明 ,對(duì)于任意81 GBAS算法的收斂性分析 7/8由于級(jí)數(shù) 是發(fā)散的 ,可知 .因此 ,當(dāng) 時(shí) ,在第 K輪迭代之后 ,該弧永遠(yuǎn)不再被加強(qiáng) ,從而有 也既 弧上的信息素之和將趨于 0.對(duì)于信息素的更新公式 (2),可以歸納證明(6)式的第二項(xiàng)與 (i,j)弧無(wú)關(guān) ,結(jié)合 (7)式可得 的極限存在 ,且所有的極限之和為 82 GBAS算法的收斂性分析 8/8 結(jié)合前兩部分討論 ,當(dāng) Xn首次到達(dá)最優(yōu)路徑后 ,對(duì)于任何最優(yōu)路徑上的弧 ,(1)式的轉(zhuǎn)移概率 ,即 依概率 1收斂到 .83 其他算法及收斂性分析 1/4 MAXMIN蟻群優(yōu)化算法指定揮發(fā)系數(shù)不隨時(shí)間變化 ,這是和 GBAS算法不同的一點(diǎn) ,改變了信息素?fù)]發(fā)和增強(qiáng)的規(guī)則 (9式 )，同時(shí)給出一個(gè)下界 控制信息素的揮發(fā) . 定理 在 MAXMIN算法中 ,84 其他算法及收斂性分析 2/485 其他算法及收斂性分析 3/486 其他算法及收斂性分析 4/487 蟻群優(yōu)化算法 — 技術(shù)問(wèn)題 解的表達(dá)形式與算法的實(shí)現(xiàn) 每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定 蟻群的規(guī)模和停止規(guī)則 信息素的更改88 解的表達(dá)形式與算法的實(shí)現(xiàn) 1/4 解的表達(dá)形式 解的表達(dá)形式 基于 TSP問(wèn)題的蟻群優(yōu)化算法，其解的形式是所有城市的一個(gè)排列（閉圈，這種情況下誰(shuí)在第一并不重要），信息素痕跡按每個(gè)弧記錄。初始信息素痕跡定義為 。第一部分信息是存在每個(gè)節(jié)點(diǎn)的路由表數(shù)據(jù)結(jié)構(gòu) ，由此決定的的轉(zhuǎn)移概率為其中 T可以看成節(jié)點(diǎn) i的鄰域。96 信息素的更改 1/6 信息素的更新分為離線和在線兩種方式。 98 信息素的更改 3/6TSP問(wèn)題中，蟻群優(yōu)化算法根據(jù)信息素痕跡更新方式不同可以分為不同的算法，采用離線方式，并且時(shí)，其中 W為 t循環(huán)中 m只螞蟻所行走的最佳路線或第 t只螞蟻所行走的一條路徑。蟻密算法（ antdensity algorithm ）信息素更新為 。因此 ,近年來(lái)國(guó)內(nèi)外對(duì)RWA 并行的分布式算法表現(xiàn)出極大的興趣 ,此類算法建立的基礎(chǔ)是分層圖模型 。主要內(nèi)容有蟻群算法的由來(lái)、研究成果、應(yīng)用綜述、算法的具體描述及改進(jìn)、算法的典型優(yōu)化問(wèn)題求解模式、算法的典型應(yīng)用及拓展應(yīng)用。重復(fù)以上過(guò)程即可實(shí)現(xiàn)數(shù)據(jù)聚類。但是 ,由于 RWA 問(wèn)題本身是一個(gè)不可分割的整體 ,把 RWA 分開考慮必然造成難以得到全局最優(yōu)解的后果。100 信息素的更改 5/6 與單螞蟻離線更新方式相比，信息量記憶更小的是信息素在線更新方式，即螞蟻每走一步，馬上回溯并且更新剛剛走過(guò)的路徑上的信息素，其規(guī)則為 其中， k為螞蟻行走的第 k步。 單螞蟻離線更新是在第 s只螞蟻完成對(duì)所有 n個(gè)城市的訪問(wèn)后，進(jìn)行路徑回溯，更新行走路徑上的信息素，同時(shí)釋放分配給它的資源。95 蟻群的規(guī)模和停止規(guī)則一、蟻群大小 一般情況下蟻群中螞蟻的個(gè)數(shù)不超過(guò) TSP圖中節(jié)點(diǎn)的個(gè)數(shù)。 算法中記錄了三個(gè)信息：信息素痕跡 ；行走路線 ；和問(wèn)題的約束條件 ，以確定是否將 加入。設(shè)有一個(gè)容積為 b的背包， n個(gè)尺寸分別為 ，價(jià)值分別為 的物品， 01背包問(wèn)題的數(shù)學(xué)模型為：假設(shè)其解的順序表達(dá)形式為　　　　　　　　，其中　　　為　　　　　　的一個(gè)排列。 的變化僅由 決定，而與先前的狀態(tài)無(wú)關(guān)，這是一個(gè)典型的馬爾可夫過(guò)程。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ā)。這種增強(qiáng)過(guò)程中進(jìn)行的信息素更新稱為離線的信息素更新。用如下公式對(duì) W路徑上的信息素痕跡加強(qiáng)，對(duì)其他路徑上的信息素進(jìn)行揮發(fā)。61 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 2/12STEP 1 （外循環(huán)）如果滿足算法的停止規(guī)則，則停止計(jì)算并輸出計(jì)算得到的最好解。每只螞蟻的一步轉(zhuǎn)移概率由圖中的每條邊上的兩類參數(shù)決定： 1 信息素值 也稱信息素痕跡。 人工蟻群中把具有簡(jiǎ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。與此同時(shí)釋放出與路徑長(zhǎng)度有關(guān)的信息素。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)題。 Lumer和 Faieta將 Deneubourg提出將蟻巢分類模型應(yīng)用于數(shù)據(jù)聚類分析。 47 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 2/5 蟻群算法在電信路由優(yōu)化中已取得了一定的應(yīng)用成果。與 “精英策略 ”相似，在此算法中總是更新更好進(jìn)程上的信息素，選擇的標(biāo)準(zhǔn)是其行程長(zhǎng)度 決定的排序，且每個(gè)螞蟻放置信息素的強(qiáng)度通過(guò)下式中的排序加權(quán)處理確定，其中，ｗ為每次迭代后放置信息素的螞蟻總數(shù)。 AntQ將螞蟻算法和一種增強(qiáng)型學(xué)習(xí)算法 Qlearning有機(jī)的結(jié)合了起來(lái)。在 Antdensity和 Antquantity中螞蟻在兩個(gè)位置節(jié)點(diǎn)間每移動(dòng)一次后即更新信息素，而在 Antcycle中當(dāng)所有的螞蟻都完成了自己的行程后才對(duì)信息素進(jìn)行更新，而且每個(gè)螞蟻所釋放的信息素被表達(dá)為反映相應(yīng)行程質(zhì)量的函數(shù)。已完成的群智能理論和應(yīng)用方法研究證明群智能方法是一種能夠有效解決大多數(shù)全局優(yōu)化問(wèn)題的新方法。用該方法求解 TSP問(wèn)題、分配問(wèn)題、 jobshop調(diào)度問(wèn)題，取得了較好的試驗(yàn)結(jié)果．雖然研究時(shí)間不長(zhǎng)，但是現(xiàn)在的研究顯示出，蟻群算法在求解復(fù)雜優(yōu)化問(wèn)題（特別是離散優(yōu)化問(wèn)題）方面有一定優(yōu)勢(shì)，表明它是一種有發(fā)展前景的算法．35 蟻群優(yōu)化算法應(yīng)用領(lǐng)域 這種方法能夠被用于解決大多數(shù)優(yōu)化問(wèn)題或者能夠轉(zhuǎn)化為優(yōu)化求解的問(wèn)題。24 計(jì)算復(fù)雜性的概念 10/11n 利用復(fù)雜性分析對(duì)組合優(yōu)化問(wèn)題歸類。以目前二進(jìn)制計(jì)算機(jī)中的存儲(chǔ)和計(jì)算為基礎(chǔ)，以理論的形式系統(tǒng)描述，是評(píng)估算法性能的基礎(chǔ)。通過(guò)數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)編排、分組、次序或篩選等，