《[建筑土木]什么是人工智能算法》由會員分享，可在線閱讀，更多相關《[建筑土木]什么是人工智能算法（65頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、1什么是人工智能算法 n隨著計算機技術的飛速發(fā)展，智能計算方法的應用領域也越來越廣泛，當前存在的一些智能算法有人工神經(jīng)網(wǎng)絡 遺傳算法 模擬退火算法 群集智能 蟻群算法 粒子群算 等等。 蟻群算法只是其中的一種。人工智能計算也有人稱之為“軟計算”，是們受自然（生物界）規(guī)律的啟迪，根據(jù)其原理，模仿求解問題的算法。從自然界得到啟迪，模仿其結構進行發(fā)明創(chuàng)造，這就是仿生學。這是我們向自然界學習的一個方面。另一方面，我們還可以利用仿生原理進行設計(包括設計算法)，這就是智能計算的思想。2蟻群算法n起源n應用領域n研究背景n基本原理3蟻群優(yōu)化算法起源蟻群算法最開始的提出是在90年代有人受了螞蟻覓食時的通訊機

2、制的啟發(fā)用來解決計算機算法學中經(jīng)典的“旅行商問題（Traveling Salesman Problem, TSP）”。TSP問題屬于易于描述但難于解決的著名難題之一，至今世界上還有不少人在研究它。該問題的基本描述是：某售貨員要到若干個村莊售貨，各村莊之間的路程是已知的，為了提高效率，售貨員決定從所在商店出發(fā)，到每個村莊都售貨一次后再返回商店，問他應選擇一條什么路線才能使所走的總路程最短? 其實有很多實際問題可歸結為TSP問題。4蟻群優(yōu)化算法起源 例如郵路問題就是一個TSP問題。假定有一輛郵車要到n個不同的地點收集郵件，這種情況可以用n十1個結點的圖來表示。一個結點表示此郵車出發(fā)并要返回的那個郵

3、局，其余的n個結點表示要收集郵件的n個地點。郵車所行經(jīng)的路線是一條周游路線，希望求出具有最小長度的周游路線。再舉一個例子在一條裝配線上用一個機械手去緊固待裝配部件上的螺帽問題。機械手由其初始位置(該位置在第一個要緊固的螺帽的上方)開始，依次移動到其余的每一個螺帽，最后返回到初始位置。一條最小成本周游路線將使這機械手完成其工作所用的時間取最小值。所以TSP問題的研究也是具有很多實際價值。5蟻群算法應用領域 這種方法能夠被用于解決大多數(shù)優(yōu)化問題或者能夠轉化為優(yōu)化求解的問題?，F(xiàn)在其應用領域已擴展到多目標優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識別、電信QoS管理、生物系統(tǒng)建模、流程規(guī)劃、信號處理、機器人控制、

4、決策支持以及仿真和系統(tǒng)辯識等方面，群智能理論和方法為解決這類應用問題提供了新的途徑。6蟻群優(yōu)化算法研究背景 1/3 蟻群算法屬于群智理論。群智能理論研究領域有兩種主要的算法：蟻群算法(Ant Colony Optimization, ACO)和微粒群算法（Particle Swarm Optimization, PSO）。前者是對螞蟻群落食物采集過程的模擬，已成功應用于許多離散優(yōu)化問題。微粒群算法也是起源于對簡單社會系統(tǒng)的模擬，最初是模擬鳥群覓食的過程，但后來發(fā)現(xiàn)它是一種很好的優(yōu)化工具。 7蟻群優(yōu)化算法研究背景 2/3與大多數(shù)基于梯度的應用優(yōu)化算法不同，群智能依靠的是概率搜索算法。雖然概率搜索

5、算法通常要采用較多的評價函數(shù)，但是與梯度方法及傳統(tǒng)的演化算法相比，其優(yōu)點還是顯著的 ，主要表現(xiàn)在以下幾個方面：1 無集中控制約束，不會因個別個體的故障影響整個問題 的求解，確保了系統(tǒng)具備更強的可靠性 2 以非直接的信息交流方式確保了系統(tǒng)的擴展性 3 并行分布式算法模型，可充分利用多處理器 4 對問題定義的連續(xù)性無特殊要求 5 算法實現(xiàn)簡單 8蟻群優(yōu)化算法研究背景 3/3 群智能方法易于實現(xiàn)，算法中僅涉及各種基本的數(shù)學操作，其數(shù)據(jù)處理過程對CPU和內(nèi)存的要求也不高。而且，這種方法只需目標函數(shù)的輸出值，而無需其梯度信息。已完成的群智能理論和應用方法研究證明群智能方法是一種能夠有效解決大多數(shù)全局優(yōu)化

6、問題的新方法。更為重要是，群智能潛在的并行性和分布式特點為處理大量的以數(shù)據(jù)庫形式存在的數(shù)據(jù)提供了技術保證。無論是從理論研究還是應用研究的角度分析，群智能理論及其應用研究都是具有重要學術意義和現(xiàn)實價值的。 9蟻群算法原理 蟻群算法是對自然界螞蟻的尋徑方式進行模似而得出的一種仿生算法。螞蟻在運動過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為外激素(pheromone)的物質進行信息傳遞，而且螞蟻在運動過程中能夠感知這種物質，并以此指導自己的運動方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。 為了說明蟻群算法的原理，先簡要介

7、紹一下螞蟻搜尋食物的具體過程。在蟻群尋找食物時，它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。這是因為螞蟻在尋找路徑時會在路徑上釋放出一種特殊的信息素。當它們碰到一個還沒有走過的路口時就隨機地挑選一條路徑前行。與此同時釋放出與路徑長度有關的信息素。路徑越長，釋放的激素濃度會越低.當后來的螞蟻再次碰到這個路口的時候選擇激素濃度較高路徑概率就會相對較大。這樣形成一個正反饋。最優(yōu)路徑上的激索濃度越來越大而其它的路徑上激素濃度卻會隨著時間的流逝而消減。最終整個蟻群會找出最優(yōu)路徑。10簡化的螞蟻尋食過程 1/3螞蟻從A點出發(fā)，速度相同，食物在D點，可能隨機選擇路線ABD或ACD。假設初始時每條分配路線一只

8、螞蟻，每個時間單位行走一步，本圖為經(jīng)過9個時間單位時的情形：走ABD的螞蟻到達終點，而走ACD的螞蟻剛好走到C點，為一半路程。11簡化的螞蟻尋食過程 2/3本圖為從開始算起，經(jīng)過18個時間單位時的情形：走ABD的螞蟻到達終點后得到食物又返回了起點A，而走ACD的螞蟻剛好走到D點。12簡化的螞蟻尋食過程 3/3 假設螞蟻每經(jīng)過一處所留下的信息素為一個單位，則經(jīng)過36個時間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從D點取得了食物，此時ABD的路線往返了2趟，每一處的信息素為4個單位，而 ACD的路線往返了一趟，每一處的信息素為2個單位，其比值為2：1。 尋找食物的過程繼續(xù)進行，則按信息素的指導

9、，蟻群在ABD路線上增派一只螞蟻（共2只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個時間單位后，兩條線路上的信息素單位積累為12和4，比值為3：1。 若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個時間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。 若繼續(xù)進行，則按信息素的指導，最終所有的螞蟻會放棄ACD路線，而都選擇ABD路線。這也就是前面所提到的正反饋效應。13自然蟻群與人工蟻群算法 基于以上蟻群尋找食物時的最優(yōu)路徑選擇問題，可以構造人工蟻群，來解決最優(yōu)化問題，如TSP問題。 人工蟻群中把具有簡單功能的工作單元看作螞蟻

10、。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結果。 兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問過的節(jié)點。同時，人工蟻群再選擇下一條路徑的時候是按一定算法規(guī)律有意識地尋找最短路徑，而不是盲目的。例如在TSP問題中，可以預先知道當前城市到下一個目的地的距離。14蟻群算法與TSP問題 1/3TSP問題表示為一個N個城市的有向圖G=（N，A），其中城市之間距離目標函數(shù)為 ，其中 為城市1,2，n的一個排列， 。, |j), (iA n1,2,.,NNjinnijd)(nliilldwf11)(),(21niiiw

11、11iin15蟻群算法與TSP問題 2/3 TSP問題的人工蟻群算法中，假設m只螞蟻在圖的相鄰節(jié)點間移動，從而協(xié)作異步地得到問題的解。每只螞蟻的一步轉移概率由圖中的每條邊上的兩類參數(shù)決定：1 信息素值 也稱信息素痕跡。2 可見度，即先驗值。 信息素的更新方式有2種，一是揮發(fā)，也就是所有路徑上的信息素以一定的比率進行減少，模擬自然蟻群的信息素隨時間揮發(fā)的過程；二是增強，給評價值“好”(有螞蟻走過)的邊增加信息素。16蟻群算法與TSP問題 3/3 螞蟻向下一個目標的運動是通過一個隨機原則來實現(xiàn)的，也就是運用當前所在節(jié)點存儲的信息，計算出下一步可達節(jié)點的概率，并按此概率實現(xiàn)一步移動，逐此往復，越來越

12、接近最優(yōu)解。 螞蟻在尋找過程中，或者找到一個解后，會評估該解或解的一部分的優(yōu)化程度，并把評價信息保存在相關連接的信息素中。17初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 1/12初始的蟻群算法是基于圖的蟻群算法，graph-based ant system,簡稱為GBAS，是由Gutjahr W J在2000年的Future Generation Computing Systems提出的，算法步驟如下：STEP 0 對n個城市的TSP問題，城市間的距離矩陣為 ，給TSP圖中的每一條弧 賦信息素初值 ，假設m只螞蟻在工作，所有螞蟻都從同一城市 出發(fā)。當前最好解是。, |j), (iA n1,

13、2,.,NNjinnijd)(),(ji|1)0(Aij0i),2,1(nw18初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 2/12STEP 1 （外循環(huán)）如果滿足算法的停止規(guī)則，則停止計算并輸出計算得到的最好解。否則使螞蟻s從起點 出發(fā)，用 表示螞蟻s行走的城市集合，初始 為空集， 。STEP 2 (內(nèi)循環(huán)) 按螞蟻 的順序分別計算。當螞蟻在城市i，若 完成第s只螞蟻的計算。否則，若，則以概率，到達j， ；若則到達重復STEP 2。0i)(sL)(sLms 11sm( ) |( , ),( )L sNli lA lL s 或0( ) |( , ),( ) L sNTli lA lL si

14、 且(1),(1)ijijijl TkpjTk0,ijpjT( )( ) , :L sL sjij0( ) |( , ),( ) L sNTli lA lL si 且000, ( )( ) , :;i L sL siii19初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 3/12STRP 3 對 ，若 ，按 中城市的順序計算路徑程度；若 ，路徑長度置為一個無窮大值（即不可達）。比較m只螞蟻中的路徑長度，記走最短路徑的螞蟻為t。若 ，則 。用如下公式對W路徑上的信息素痕跡加強，對其他路徑上的信息素進行揮發(fā)。 得到新的 ，重復步驟STEP 1。1sm( )L sN( )L s( )L sN( (

15、)( ()f L tf L W( )WL t( ), :1ijk kk111( )(1)(1)( , )( )(1)(1)( , )kijkijijkijkki jWWkki jW為上的一條弧不是上的一條弧20初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 4/12在STEP 3 中，揮發(fā)因子 對于一個固定的 ，滿足并且 經(jīng)過k次揮發(fā)，非最優(yōu)路徑的信息素逐漸減少至消失。kln1,ln(1)kkkKk 1K 1kk 21初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 5/12 以上算法中，在螞蟻的搜尋過程中，以信息素的概率分布來決定從城市i到城市j的轉移。 算法中包括信息素更新的過程 1 信息素

16、揮發(fā)（evaporation） 信息素痕跡的揮發(fā)過程是每個連接上的信息素痕跡的濃度自動逐漸減弱的過程，由 表示，這個揮發(fā)過程主要用于避免算法過快地向局部最優(yōu)區(qū)域集中，有助于搜索區(qū)域的擴展。 2 信息素增強（reinforcement）增強過程是蟻群優(yōu)化算法中可選的部分，稱為離線更新方式（還有在線更新方式）。這種方式可以實現(xiàn)由單個螞蟻無法實現(xiàn)的集中行動。也就是說，增強過程體現(xiàn)在觀察蟻群（m只螞蟻）中每只螞蟻所找到的路徑，并選擇其中最優(yōu)路徑上的弧進行信息素的增強，揮發(fā)過程是所有弧都進行的，不于螞蟻數(shù)量相關。這種增強過程中進行的信息素更新稱為離線的信息素更新。 在STEP 3中，蟻群永遠記憶到目前為

17、止的最優(yōu)解。(1)( )kijk 22圖的蟻群系統(tǒng)（GBAS） 6/12可以驗證，下式滿足：即 是一個隨機矩陣。( )k( , )( )1,0iji jAkk 四個城市的非對稱TSP問題，距離矩陣和城市圖示如下：010.511011()1.55011110ijDd23初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 7/12假設共4只螞蟻，所有螞蟻都從城市A出發(fā)，揮發(fā)因子 。此時，觀察GBAS的計算過程。 矩陣共有12條弧，初始信息素記憶矩陣為：1,1,2,32kk01 121 121 121 1201 121 12(0)(0)1 121 1201 121 121 121 120ij24初始的蟻

18、群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 8/12執(zhí)行GBAS算法的步驟2，假設螞蟻的行走路線分別為：當前最優(yōu)解為，這個解是截止到當前的最優(yōu)解，碰巧是實際最優(yōu)解1:,(1)4;2:,(2)3.5;3:,(3)8;4:,(4)4.5;WABCDA f WWACDBA f WWADCBA f WWABDCA f W第一只第二只第三只第四只25初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 9/12按算法步驟3的信息素更新規(guī)則，得到更新矩陣這是第一次外循環(huán)結束的狀態(tài)。01 241 61 241 601 241 24(1)(1)1 241 1201 61 241 61 240ij26初始的蟻群優(yōu)化算法基

19、于圖的蟻群系統(tǒng)（GBAS） 10/12重復外循環(huán)，由于上一次得到的W2已經(jīng)是全局最優(yōu)解，因此按算法步驟3的信息素更新規(guī)則，無論螞蟻如何行走，都只是對W2路線上的城市信息素進行增強，其他的城市信息素進行揮發(fā)。得到更新矩陣這是第一次外循環(huán)結束的狀態(tài)。01 485 241 485 2401 481 48(2)(2)1 481 4805 241 485 241 480ij27初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 11/12重復外循環(huán)，由于W2全局最優(yōu)解，GBAS只記錄第一個最優(yōu)解，因此一但得到了全局最優(yōu)解，信息素的更新將不再依賴于以群的行走路線，而只是不斷增強最優(yōu)路線的信息素，同時進行揮發(fā)。

20、第三次外循環(huán)后得到的信息素矩陣為：01 9611 481 9611 4801 961 96(3)(3)1 961 96011 481 9611 481 960ij28初始的蟻群優(yōu)化算法基于圖的蟻群系統(tǒng)（GBAS） 12/12 螞蟻以一定的概率從城市i到城市j進行轉移，信息素的更新在STEP 3 完成，并隨K而變化。假設第K次外循環(huán)后得到信息素矩陣 ，得到當前最優(yōu)解 。第K次循環(huán)前的信息素和最優(yōu)解為 ，經(jīng)過第K次外循環(huán)后，得到 。由于螞蟻的一步轉移概率是隨機的，從 到 也是隨機的，是一個馬爾可夫過程。( )( )|( , )ijkki jA( )W k(1),(1)kW k( ),( )k W

21、k(1),(1)kW k( ),( )k W k29一般蟻群算法的框架一般蟻群算法的框架和GBAS基本相同，有三個組成部分： 蟻群的活動； 信息素的揮發(fā)； 信息素的增強；主要體現(xiàn)在前面的算法中步驟2和步驟3中的轉移概率公式和信息素更新公式。30蟻群優(yōu)化算法算法模型和收斂性分析馬氏過程的收斂定義GBAS算法的收斂性分析其他算法及收斂性分析31馬氏過程的收斂定義 蟻群優(yōu)化算法的每步迭代對應隨機變量 其中 為信息素痕跡； 為n城市的一個排列，最多有 個狀態(tài)。第s只螞蟻在第k輪轉移只由 決定，這個螞蟻行走的路徑和 一起，共同決定了 ，再通過信息素的更新原則可以進一步得到 。 的變化僅由 決定，而與先前

22、的狀態(tài)無關，這是一個典型的馬爾可夫過程。 定義定義：若一個馬爾可夫過程 ，對任意給定的 滿足 則稱馬爾可夫過程 依概率1收斂到 。( ( ),( ),0,1,.,kXk W kk( )k( )W k!n(1)k(1)W k ( )W k( )k1kXkX,0,1,.kXk 0*X,0,1,2,.kXk *lim1kkp XX32GBAS算法的收斂性分析 1/8 定理 滿足指定條件的馬爾可夫過程 依概率1收斂到 ,其中 為一條最優(yōu)路徑, 定義為: 證明分析: 蟻群算法中,一但達到全局最優(yōu),由 只記錄第一個最優(yōu)解.證明分三部分:n 證明以概率1達到一個最優(yōu)路徑n 證明(1)上式成立n 證明以概率1

23、收斂到一個最優(yōu)路徑( ( ),( ),0,1,.,kXk W kk*(,)XW*W*1,( ,)0(1)ijWi jW為的一條弧其他f(L(t)f(w)33GBAS算法的收斂性分析 2/8證明以概率1到達一個最優(yōu)路徑 對于最優(yōu)路徑 ,令 為蟻群中的一個螞蟻在第k次外循環(huán)后第一次走到最優(yōu)路徑 的事件. 表示僅第k次外循環(huán)沒有走到 的事件,但前k-1次可能走到過這條最優(yōu)路徑. 永遠不會被走到的事件為 ,其概率為:*WkF*WkF*W*W12FF12*1*1()|)(2kkP FFPkWPkW*第 次循環(huán)蟻群沒有走到第ik次循環(huán)蟻群沒有走到W前 次循環(huán)蟻群沒有走到34GBAS算法的收斂性分析 3/8

24、 任意給定的固定弧(i,j),在第k次循環(huán)后,其信息素值的下界可以計算出.111111111()(1)(1)ln(1)(1)ln (1)ln(1)(1)ln1(1) ln(1)(3 )lni jkijllKklijllKKlijlKlijlkllKkKk 35GBAS算法的收斂性分析 4/8令,任何一個固定節(jié)點最多有(n-1)后續(xù)節(jié)點,并且其弧上的信息素值都小于1或者等于1.得:蟻群中的一只螞蟻在第 次循環(huán)走到路徑 W* 的概率為一個蟻群中至少有一只螞蟻，因此這是一個蟻群到達最優(yōu)路徑的一個下界. 上式右側與k無關,11(1)ln(1)KlijlK ,(1)lnijpkKnkk(kK)*( ,

25、)*( ) ()(4)1)lnWiji jWpknk36GBAS算法的收斂性分析 5/8 則取對數(shù)有從而得到*( ,*)1( )1 ()(1)lnwiji j WPkWpknk 前 次循環(huán)蟻群沒有走到*1*(1 ()(1)ln(2)(5)kwk KPkWnk前 次循環(huán)蟻群沒有走到*ln(1 () )()(1)ln(1)lnwwk Kk Knknk12()1P FF37GBAS算法的收斂性分析 6/8 證明右式成立 隨機過程 以概率1達到一條最優(yōu)路徑.當某條最優(yōu)路徑Z在第k次循環(huán)被首次走到后,在第k+1輪循環(huán)按信息素的更新原則,可以用歸納法證明,對于任意*1,( , )0ijWi jW為的一條弧

26、其他(i,j)W*,r=1,2,.111011()(1) ( )(1)*(6)K rrrijlijK lll Kq lK rKK qW 38GBAS算法的收斂性分析 7/8由于級數(shù) 是發(fā)散的,可知 .因此,當 時,在第K輪迭代之后,該弧永遠不再被加強,從而有 也既 弧上的信息素之和將趨于0.對于信息素的更新公式(2),可以歸納證明(6)式的第二項與(i,j)弧無關,結合(7)式可得 的極限存在,且所有的極限之和為1.對于所有的l1(1)0ll1()(1)(07)(KrijlijlKKrK ( , )*i jW( , )*i jW( , )( )1,iji jAkk成立( , )*i jW1li

27、m()lim( *(8,*)*)ijlrlKrXWW ,即 可 得39GBAS算法的收斂性分析 8/8 結合前兩部分討論,當Xn首次到達最優(yōu)路徑后,對于任何最優(yōu)路徑上的弧,(1)式的轉移概率 ,即 依概率1收斂到 .( )1ijp l ( ( ),( ),0,1,.,kXk W kk*(,)XW40其他算法及收斂性分析 1/4 MAX-MIN蟻群優(yōu)化算法指定揮發(fā)系數(shù)不隨時間變化,這是和GBAS算法不同的一點,改變了信息素揮發(fā)和增強的規(guī)則(9式)，同時給出一個下界 控制信息素的揮發(fā). 定理 在MAX-MIN算法中,min(1)kminmax(1)(1),(1)( , )( )max(1)(1),

28、(1),01,(1)ijijijijijkWki jWkkkk 其他其中為實數(shù)。 （9）min( ),1ln(1)lim0kkkckkkc令：其中，則定理5.2.1的結論也成立。41其他算法及收斂性分析 2/4ij(1)(1)p0(1)(1) | ( , )(1)(1)1.ijill TiijijijakjTakjTAkaki jAkkiij式螞蟻轉移概率更一般的規(guī)則由存儲在每個節(jié)點的路由表數(shù)據(jù)結構A =a |(i,j)A決定，即轉移概率為其中，取決于三部分因素，T是從i可以直接到達的節(jié)點結合。第一部分為每個節(jié)點的信息素痕跡和預見度第二部分為每（ ）個螞蟻自身的記憶表中存儲的歷史信息.第三部分

29、為問題的約束條件.42其他算法及收斂性分析 3/4(1)(1)(1)(1)(1)01(1),.ijijilill Tijijkkj Tkkkj TTSPkd ij常見的路由表信息由下式求得：a其中， 為殘留信息的相對重要程度， 為預見值的相對重要程度。和 體現(xiàn)了相關信息痕跡和預見度對螞蟻決策的相對影響。問題中為先驗知識 43其他算法及收斂性分析 4/4(1)1.,( )(1)( ):(1) ( ),(0,1)ijijijijijkki jkkkk ij信息素痕跡為時刻連接城市和的路徑上的信息殘留濃度為避免過多的殘留信息會淹沒全局最優(yōu)解需要在每只螞蟻完成一次循環(huán)后對殘留信息進行更新,削弱舊信息,

30、增強新信息.記(i,j)弧上的信息素在第k-1個循環(huán)的變化為(k-1),則保留的信息素為然后進行信息素的揮發(fā)其中為信息素的衰退系數(shù).44蟻群優(yōu)化算法技術問題解的表達形式與算法的實現(xiàn)每一節(jié)點的記憶信息和系數(shù)的確定蟻群的規(guī)模和停止規(guī)則信息素的更改45解的表達形式與算法的實現(xiàn) 1/4 -解的表達形式 解的表達形式 基于TSP問題的蟻群優(yōu)化算法，其解的形式是所有城市的一個排列（閉圈，這種情況下誰在第一并不重要），信息素痕跡按每個弧記錄。而對于一般以順序作為解的優(yōu)化問題，誰在第一是很重要的。蟻群算法在解決這類問題時，只需要建立一個虛擬的始終點，就可以把TSP問題的解法推廣，用于諸多的優(yōu)化問題。 諸如車間

31、作業(yè)及下料等問題，他們的共同特點是解以一個順序表示。TSP問題尋找的是最短回路，而一般優(yōu)化問題中，STEP 3 中的判斷條件 需要根據(jù)實際問題進行修改。( )L sN46解的表達形式與算法的實現(xiàn) 2/4 -算法的實現(xiàn)例：0-1背包問題的解順序表達形式與算法實現(xiàn)。設有一個容積為b的背包，n個尺寸分別為 ，價值分別為 的物品，0-1背包問題的數(shù)學模型為：假設其解的順序表達形式為，其中為的一個排列。(1,2,., )ia in(1,2,., )ic in11m a x. .0 ,1,1, .,niiiniiiic xs ta xbxjn120,.,niii12, ,.,ni ii1,2,3,.,n4

32、7解的表達形式與算法的實現(xiàn) 3/4 -算法的實現(xiàn)建立有向圖 ，其中 A中共有 條弧。初始信息素痕跡定義為 。設第s只螞蟻第k步所走的路線為 ，表示螞蟻從0點出發(fā)，順序到達 。第 步按TSP算法的轉移概率公式行走選擇 。若 則 ，否則，此螞蟻不再繼續(xù)行走，退回起點。( ,)GV A0,1,2,.,( ,) |,VnAi ji jV(1)n n1(1)ijn n12( )(0,.,)kL siii12,.,kiii1k 1ki11jkijab121( )(0, ,.,)kkL si iii48解的表達形式與算法的實現(xiàn)4/4 -算法的實現(xiàn) 對蟻群重復以上過程，比較m只螞蟻的裝包值 并記憶具有最大裝包

33、值的螞蟻為t。把GBAS算法中步驟3中的改為 ，若滿足此條件則替換當前最好解為 ，對W上的弧進行信息素的加強，其他弧進行信息素的揮發(fā)。 算法中記錄了三個信息：信息素痕跡 ；行走路線 ；和問題的約束條件，以確定是否將 加入。 ( )0,1,2,.,ii L sic sm( ( )( )f L tf w( ( )( )f L tf w:( )WL tij121( )(0, ,.,)kkL si iii11jkijab1ki49每一節(jié)點的記憶信息和系數(shù)的確定-需要記憶的信息 1/3算法中需要記憶的信息有三部分。第一部分信息是存在每個節(jié)點的路由表數(shù)據(jù)結構 ，由此決定的的轉移概率為其中T可以看成節(jié)點i的

34、鄰域。|( , )iijAai jA(1)(1)|( , )iijA kaki jA(1)(1),0ijili jlTakjTakPjT(1)(1)(1)(1)(1),0ijijililijl TkkkkakjTjT50每一節(jié)點的記憶信息和系數(shù)的確定-需要記憶的信息 2/3 第二部分需要記憶的信息是每個螞蟻的記憶表中存儲著的自身的歷史信息，這一部分主要由算法的中的 記憶，表示螞蟻已經(jīng)行走過的節(jié)點。 第三部分為問題的約束條件。在GBAS中，T集合表示滿足約束條件的候選集，在背包問題的蟻群算法中由判別條件 ，來實現(xiàn)記 憶功能。( )L s11jkijab121( )(0, ,.,)kkL si i

35、ii51每一節(jié)點的記憶信息和系數(shù)的確定-系數(shù)的確定 3/3 殘留信息的相對重要程度 和預見值的相對重要程度 體現(xiàn)了相關信息痕跡和預見度對螞蟻決策的相對影響。Dorigo在求解TSP問題時，推薦參數(shù)的最佳設置為： 。1,5,0.552蟻群的規(guī)模和停止規(guī)則一、蟻群大小 一般情況下蟻群中螞蟻的個數(shù)不超過TSP圖中節(jié)點的個數(shù)。二、終止條件 1 給定一個外循環(huán)的最大數(shù)目，表明已經(jīng)有足夠的螞蟻工作； 2 當前最優(yōu)解連續(xù)K次相同而停止，其中K是一個給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)； 3 目標值控制規(guī)則，給定優(yōu)化問題（目標最小化）的一個下界和一個誤差值，當算法得到的目標值同下界之差小于給定的誤差值時

36、，算法終止。53信息素的更改 1/6 信息素的更新分為離線和在線兩種方式。離線方式（同步更新方式）的主要思想是在若干只螞蟻完成n個城市的訪問后，統(tǒng)一對殘留信息進行更新處理。 信息素的在線更新（異步更新方式）即螞蟻每行走一步，立即回溯并且更新行走路徑上的信息素。54信息素的更改 2/6 離線方式的信息素更新可以進一步分為單螞蟻離線更新和蟻群離線更新。 蟻群離線更新方式是在蟻群中的m只螞蟻全部完成n城市的訪問（第k-1次蟻群循環(huán)）后，統(tǒng)一對殘留信息進行更新處理。 其中， 為第k-1次循環(huán)后的的信息素的痕跡值。 單螞蟻離線更新是在第s只螞蟻完成對所有n個城市的訪問后，進行路徑回溯，更新行走路徑上的信

37、息素，同時釋放分配給它的資源。更新公式為 第s+1只螞蟻根據(jù) 重新計算路由表。 ( )(1)(1)ijijijkkk( )ijk(1)( )( )ijijijsss(1)ijs55信息素的更改 3/6TSP問題中，蟻群優(yōu)化算法根據(jù)信息素痕跡更新方式不同可以分為不同的算法，采用離線方式，并且時，其中W為t循環(huán)中m只螞蟻所行走的最佳路線或第t只螞蟻所行走的一條路徑。Q為一個常數(shù)，該算法名為蟻環(huán)算法（ant-cycle algotithm）,特點是行走的路徑越短對應保存的信息素的值就越大。(1)( )i ji jks或為( ),( , )( , )0i jQWti jWi jW56信息素的更改 4/

38、6 GBAS算法是典型的離線信息素更新方式。該算法中，蟻群中螞蟻的先后出行順序沒有相關性，但是每次循環(huán)需要記憶m只螞蟻的行走路徑，以進行比較選擇最優(yōu)路徑。相對而言，單螞蟻離線更新方式記憶信息少，只需要記憶第s只螞蟻的路徑，并通過信息素更新后，釋放該螞蟻的所有記錄信息。實際上這種方式等價于蟻群離線方式中只有一只螞蟻。57信息素的更改 5/6 與單螞蟻離線更新方式相比，信息量記憶更小的是信息素在線更新方式，即螞蟻每走一步，馬上回溯并且更新剛剛走過的路徑上的信息素，其規(guī)則為 其中，k為螞蟻行走的第k步。(1)( )( )ijijijkkk58信息素的更改 6/6 蟻量算法（ant-quantity

39、algorithm）的信息素更新為 ,Q為常量， 表示i到j的距離，這樣信息濃度會隨城市距離的減小而加大。蟻密算法（ ant-density algorithm ）信息素更新為 。 以上三種算法中，蟻環(huán)算法效果最好，因為他用的是全局信息，而其余兩種算法用的是局部信息。蟻環(huán)離線更新方法很好地保證了殘留信息不至于無限積累，非最優(yōu)路徑會逐漸隨時間推移被忘記。( )iji jQkdijd( )ijkQ59應用 1/5光網(wǎng)絡的智能管理 分布式動態(tài)選路及波長分配( RWA , Routing and Wavelength Assignment ) 是指在實時業(yè)務情況下光通路的路由選擇和波長分配的優(yōu)化問題,

40、是實現(xiàn)自動交換光網(wǎng)絡(ASON ,Automatically Switched Optical Network) 的關鍵技術之一。研究RWA 問題的目的是盡可能減少所需要的波長數(shù)和降低光路連接請求的阻塞率。由于RWA 問題是NP-C 問題,文獻中大多將RWA 問題拆分成路由和波長分配兩個子問題分別加以解決。但是,由于RWA 問題本身是一個不可分割的整體,把RWA 分開考慮必然造成難以得到全局最優(yōu)解的后果。60應用 2/5 同時,分布式的計算方式則克服了傳統(tǒng)集中式算法可擴展性差的缺點,更適應現(xiàn)代頻繁變化的大型光網(wǎng)絡。因此,近年來國內(nèi)外對RWA 并行的分布式算法表現(xiàn)出極大的興趣,此類算法建立的基礎

41、是分層圖模型 。 用蟻群算法在分層圖模型的基礎上求解動態(tài)RWA 問題?；谖浵仭靶畔⑺乇怼眮硗瓿删植啃畔⒌乃⑿掠嬎?。以分布的形式做少量的計算來刷新全局路由選擇信息。 參考文獻： 基于蟻群系統(tǒng)的分布式RWA 算法研究 孫海金, 朱娜, 周乃富 2005 年第2 期 光通信研究61應用 3/5蟻群算法用于計算機網(wǎng)絡路由參考文獻：計算機網(wǎng)絡中的組播路由算法 謝銀祥 62應用 4/563應用 5/5蟻群算法用于聚類（蟻群蟻卵分類） 思想：把待聚類的數(shù)據(jù)隨機散布在一個平面上，放置若干只虛擬螞蟻使其在平面上隨機運動。當一只螞蟻遇到一個數(shù)據(jù)時即拾起并繼續(xù)行走，在行走過程中，如果遇到附近的數(shù)據(jù)與背負的數(shù)據(jù)相似性高于設置的標準時則將數(shù)據(jù)放置在該位置，繼續(xù)移動。重復以上過程即可實現(xiàn)數(shù)據(jù)聚類。64智能算法前景n目前的智能計算研究水平暫時還很難使“智能機器”真正具備人類的常識，但智能計算將在21世紀蓬勃發(fā)展。不僅僅只是功能模仿要持有信息機理一致的觀點。即人工腦與生物腦將不只是功能模仿，而是具有相同的特性。這兩者的結合將開辟一個全新的領域，開辟很多新的研究方向。智能計算將探索智能的新概念，新理論，新方法和新技術，而這一切將在以后的發(fā)展中取得重大成就。65ENDThanks