現(xiàn)代優(yōu)化計(jì)算方法課件

什么是人工智能算法隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，智能計(jì)算方法的應(yīng)用領(lǐng)域也越來越廣泛，當(dāng)前存在的一些智能算法有人工神經(jīng)網(wǎng)絡(luò)

遺傳算法

模擬退火算法

群集智能

蟻群算法

粒子群算

等等。蟻群算法只是其中的一種。人工智能計(jì)算也有人稱之為“軟計(jì)算”，是們受自然（生物界）規(guī)律的啟迪，根據(jù)其原理，模仿求解問題的算法。從自然界得到啟迪，模仿其結(jié)構(gòu)進(jìn)行發(fā)明創(chuàng)造，這就是仿生學(xué)。這是我們向自然界學(xué)習(xí)的一個(gè)方面。另一方面，我們還可以利用仿生原理進(jìn)行設(shè)計(jì)(包括設(shè)計(jì)算法)，這就是智能計(jì)算的思想。1什么是人工智能算法隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，智能計(jì)算方法的蟻群算法起源應(yīng)用領(lǐng)域研究背景基本原理2蟻群算法起源2蟻群優(yōu)化算法起源蟻群算法最開始的提出是在90年代有人受了螞蟻覓食時(shí)的通訊機(jī)制的啟發(fā)用來解決計(jì)算機(jī)算法學(xué)中經(jīng)典的“旅行商問題（TravelingSalesmanProblem,TSP）”。TSP問題屬于易于描述但難于解決的著名難題之一，至今世界上還有不少人在研究它。該問題的基本描述是：某售貨員要到若干個(gè)村莊售貨，各村莊之間的路程是已知的，為了提高效率，售貨員決定從所在商店出發(fā)，到每個(gè)村莊都售貨一次后再返回商店，問他應(yīng)選擇一條什么路線才能使所走的總路程最短?其實(shí)有很多實(shí)際問題可歸結(jié)為TSP問題。3蟻群優(yōu)化算法起源蟻群算法最開始的提出是在90年代有人受了螞蟻蟻群優(yōu)化算法起源例如郵路問題就是一個(gè)TSP問題。假定有一輛郵車要到n個(gè)不同的地點(diǎn)收集郵件，這種情況可以用n十1個(gè)結(jié)點(diǎn)的圖來表示。一個(gè)結(jié)點(diǎn)表示此郵車出發(fā)并要返回的那個(gè)郵局，其余的n個(gè)結(jié)點(diǎn)表示要收集郵件的n個(gè)地點(diǎn)。郵車所行經(jīng)的路線是一條周游路線，希望求出具有最小長(zhǎng)度的周游路線。再舉一個(gè)例子在一條裝配線上用一個(gè)機(jī)械手去緊固待裝配部件上的螺帽問題。機(jī)械手由其初始位置(該位置在第一個(gè)要緊固的螺帽的上方)開始，依次移動(dòng)到其余的每一個(gè)螺帽，最后返回到初始位置。一條最小成本周游路線將使這機(jī)械手完成其工作所用的時(shí)間取最小值。所以TSP問題的研究也是具有很多實(shí)際價(jià)值。4蟻群優(yōu)化算法起源例如郵路問題就是一個(gè)TSP問蟻群算法應(yīng)用領(lǐng)域

這種方法能夠被用于解決大多數(shù)優(yōu)化問題或者能夠轉(zhuǎn)化為優(yōu)化求解的問題?，F(xiàn)在其應(yīng)用領(lǐng)域已擴(kuò)展到多目標(biāo)優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識(shí)別、電信QoS管理、生物系統(tǒng)建模、流程規(guī)劃、信號(hào)處理、機(jī)器人控制、決策支持以及仿真和系統(tǒng)辯識(shí)等方面，群智能理論和方法為解決這類應(yīng)用問題提供了新的途徑。5蟻群算法應(yīng)用領(lǐng)域這種方法能夠被用于解決大多數(shù)優(yōu)化問題蟻群優(yōu)化算法研究背景1/3蟻群算法屬于群智理論。群智能理論研究領(lǐng)域有兩種主要的算法：蟻群算法(AntColonyOptimization,ACO)和微粒群算法（ParticleSwarmOptimization,PSO）。前者是對(duì)螞蟻群落食物采集過程的模擬，已成功應(yīng)用于許多離散優(yōu)化問題。微粒群算法也是起源于對(duì)簡(jiǎn)單社會(huì)系統(tǒng)的模擬，最初是模擬鳥群覓食的過程，但后來發(fā)現(xiàn)它是一種很好的優(yōu)化工具。

6蟻群優(yōu)化算法研究背景1/3蟻群算法屬于群智理論蟻群優(yōu)化算法研究背景2/3與大多數(shù)基于梯度的應(yīng)用優(yōu)化算法不同，群智能依靠的是概率搜索算法。雖然概率搜索算法通常要采用較多的評(píng)價(jià)函數(shù)，但是與梯度方法及傳統(tǒng)的演化算法相比，其優(yōu)點(diǎn)還是顯著的，主要表現(xiàn)在以下幾個(gè)方面：1無集中控制約束，不會(huì)因個(gè)別個(gè)體的故障影響整個(gè)問題的求解，確保了系統(tǒng)具備更強(qiáng)的可靠性

2以非直接的信息交流方式確保了系統(tǒng)的擴(kuò)展性

3并行分布式算法模型，可充分利用多處理器

4對(duì)問題定義的連續(xù)性無特殊要求

5算法實(shí)現(xiàn)簡(jiǎn)單

7蟻群優(yōu)化算法研究背景2/3與大多數(shù)基于梯度的應(yīng)用優(yōu)化算法不蟻群優(yōu)化算法研究背景3/3群智能方法易于實(shí)現(xiàn)，算法中僅涉及各種基本的數(shù)學(xué)操作，其數(shù)據(jù)處理過程對(duì)CPU和內(nèi)存的要求也不高。而且，這種方法只需目標(biāo)函數(shù)的輸出值，而無需其梯度信息。已完成的群智能理論和應(yīng)用方法研究證明群智能方法是一種能夠有效解決大多數(shù)全局優(yōu)化問題的新方法。更為重要是，群智能潛在的并行性和分布式特點(diǎn)為處理大量的以數(shù)據(jù)庫(kù)形式存在的數(shù)據(jù)提供了技術(shù)保證。無論是從理論研究還是應(yīng)用研究的角度分析，群智能理論及其應(yīng)用研究都是具有重要學(xué)術(shù)意義和現(xiàn)實(shí)價(jià)值的。

8蟻群優(yōu)化算法研究背景3/3群智能方法易于實(shí)現(xiàn)，算法中僅蟻群算法原理

蟻群算法是對(duì)自然界螞蟻的尋徑方式進(jìn)行模似而得出的一種仿生算法。螞蟻在運(yùn)動(dòng)過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為外激素(pheromone)的物質(zhì)進(jìn)行信息傳遞，而且螞蟻在運(yùn)動(dòng)過程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。為了說明蟻群算法的原理，先簡(jiǎn)要介紹一下螞蟻搜尋食物的具體過程。在蟻群尋找食物時(shí)，它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。這是因?yàn)槲浵佋趯ふ衣窂綍r(shí)會(huì)在路徑上釋放出一種特殊的信息素。當(dāng)它們碰到一個(gè)還沒有走過的路口時(shí)．就隨機(jī)地挑選一條路徑前行。與此同時(shí)釋放出與路徑長(zhǎng)度有關(guān)的信息素。路徑越長(zhǎng)，釋放的激素濃度會(huì)越低.當(dāng)后來的螞蟻再次碰到這個(gè)路口的時(shí)候．選擇激素濃度較高路徑概率就會(huì)相對(duì)較大。這樣形成一個(gè)正反饋。最優(yōu)路徑上的激索濃度越來越大．而其它的路徑上激素濃度卻會(huì)隨著時(shí)間的流逝而消減。最終整個(gè)蟻群會(huì)找出最優(yōu)路徑。9蟻群算法原理蟻群算法是對(duì)自然界螞蟻的尋徑簡(jiǎn)化的螞蟻尋食過程1/3螞蟻從A點(diǎn)出發(fā)，速度相同，食物在D點(diǎn)，可能隨機(jī)選擇路線ABD或ACD。假設(shè)初始時(shí)每條分配路線一只螞蟻，每個(gè)時(shí)間單位行走一步，本圖為經(jīng)過9個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)，而走ACD的螞蟻剛好走到C點(diǎn)，為一半路程。10簡(jiǎn)化的螞蟻尋食過程1/3螞蟻從A點(diǎn)出發(fā)，速度相同，食物在D簡(jiǎn)化的螞蟻尋食過程2/3本圖為從開始算起，經(jīng)過18個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A，而走ACD的螞蟻剛好走到D點(diǎn)。11簡(jiǎn)化的螞蟻尋食過程2/3本圖為從開始算起，經(jīng)過18個(gè)時(shí)間單簡(jiǎn)化的螞蟻尋食過程3/3

假設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個(gè)單位，則經(jīng)過36個(gè)時(shí)間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從D點(diǎn)取得了食物，此時(shí)ABD的路線往返了2趟，每一處的信息素為4個(gè)單位，而ACD的路線往返了一趟，每一處的信息素為2個(gè)單位，其比值為2：1。尋找食物的過程繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，蟻群在ABD路線上增派一只螞蟻（共2只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為12和4，比值為3：1。若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。若繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，最終所有的螞蟻會(huì)放棄ACD路線，而都選擇ABD路線。這也就是前面所提到的正反饋效應(yīng)。12簡(jiǎn)化的螞蟻尋食過程3/3假設(shè)螞蟻每經(jīng)過自然蟻群與人工蟻群算法基于以上蟻群尋找食物時(shí)的最優(yōu)路徑選擇問題，可以構(gòu)造人工蟻群，來解決最優(yōu)化問題，如TSP問題。人工蟻群中把具有簡(jiǎn)單功能的工作單元看作螞蟻。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問過的節(jié)點(diǎn)。同時(shí)，人工蟻群再選擇下一條路徑的時(shí)候是按一定算法規(guī)律有意識(shí)地尋找最短路徑，而不是盲目的。例如在TSP問題中，可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離。13自然蟻群與人工蟻群算法基于以上蟻群尋找食物時(shí)的最蟻群算法與TSP問題1/3TSP問題表示為一個(gè)N個(gè)城市的有向圖G=（N，A），其中 城市之間距離目標(biāo)函數(shù)為，其中為城市1,2，…n的一個(gè)排列，。14蟻群算法與TSP問題1/3TSP問題表示為一個(gè)N個(gè)城市的有蟻群算法與TSP問題2/3

TSP問題的人工蟻群算法中，假設(shè)m只螞蟻在圖的相鄰節(jié)點(diǎn)間移動(dòng)，從而協(xié)作異步地得到問題的解。每只螞蟻的一步轉(zhuǎn)移概率由圖中的每條邊上的兩類參數(shù)決定：1信息素值也稱信息素痕跡。2可見度，即先驗(yàn)值。信息素的更新方式有2種，一是揮發(fā)，也就是所有路徑上的信息素以一定的比率進(jìn)行減少，模擬自然蟻群的信息素隨時(shí)間揮發(fā)的過程；二是增強(qiáng)，給評(píng)價(jià)值“好”(有螞蟻?zhàn)哌^)的邊增加信息素。15蟻群算法與TSP問題2/3TSP問題蟻群算法與TSP問題3/3螞蟻向下一個(gè)目標(biāo)的運(yùn)動(dòng)是通過一個(gè)隨機(jī)原則來實(shí)現(xiàn)的，也就是運(yùn)用當(dāng)前所在節(jié)點(diǎn)存儲(chǔ)的信息，計(jì)算出下一步可達(dá)節(jié)點(diǎn)的概率，并按此概率實(shí)現(xiàn)一步移動(dòng)，逐此往復(fù)，越來越接近最優(yōu)解。螞蟻在尋找過程中，或者找到一個(gè)解后，會(huì)評(píng)估該解或解的一部分的優(yōu)化程度，并把評(píng)價(jià)信息保存在相關(guān)連接的信息素中。16蟻群算法與TSP問題3/3螞蟻向下一初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）1/12初始的蟻群算法是基于圖的蟻群算法，graph-basedantsystem,簡(jiǎn)稱為GBAS，是由GutjahrWJ在2000年的FutureGenerationComputingSystems提出的，算法步驟如下：STEP0

對(duì)n個(gè)城市的TSP問題，城市間的距離矩陣為，給TSP圖中的每一條弧賦信息素初值，假設(shè)m只螞蟻在工作，所有螞蟻都從同一城市出發(fā)。當(dāng)前最好解是 。17初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）1/12初初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）2/12STEP1

（外循環(huán)）如果滿足算法的停止規(guī)則，則停止計(jì)算并輸出計(jì)算得到的最好解。否則使螞蟻s從起點(diǎn)出發(fā)，用表示螞蟻s行走的城市集合，初始為空集，。STEP2(內(nèi)循環(huán))按螞蟻的順序分別計(jì)算。當(dāng)螞蟻在城市i，若 完成第s只螞蟻的計(jì)算。否則，若，則以概率 ， 到達(dá)j， ；若則到達(dá) 重復(fù)STEP2。18初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）2/12S初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）3/12STRP3

對(duì) ，若，按中城市的順序計(jì)算路徑程度；若，路徑長(zhǎng)度置為一個(gè)無窮大值（即不可達(dá)）。比較m只螞蟻中的路徑長(zhǎng)度，記走最短路徑的螞蟻為t。若，則。用如下公式對(duì)W路徑上的信息素痕跡加強(qiáng)，對(duì)其他路徑上的信息素進(jìn)行揮發(fā)。得到新的，重復(fù)步驟STEP1。19初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）3/12S初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）4/12在STEP3

中，揮發(fā)因子對(duì)于一個(gè)固定的，滿足并且

經(jīng)過k次揮發(fā)，非最優(yōu)路徑的信息素逐漸減少至消失。20初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）4/12在初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）5/12以上算法中，在螞蟻的搜尋過程中，以信息素的概率分布來決定從城市i到城市j的轉(zhuǎn)移。算法中包括信息素更新的過程

1信息素?fù)]發(fā)（evaporation）信息素痕跡的揮發(fā)過程是每個(gè)連接上的信息素痕跡的濃度自動(dòng)逐漸減弱的過程，由表示，這個(gè)揮發(fā)過程主要用于避免算法過快地向局部最優(yōu)區(qū)域集中，有助于搜索區(qū)域的擴(kuò)展。

2信息素增強(qiáng)（reinforcement）增強(qiáng)過程是蟻群優(yōu)化算法中可選的部分，稱為離線更新方式（還有在線更新方式）。這種方式可以實(shí)現(xiàn)由單個(gè)螞蟻無法實(shí)現(xiàn)的集中行動(dòng)。也就是說，增強(qiáng)過程體現(xiàn)在觀察蟻群（m只螞蟻）中每只螞蟻所找到的路徑，并選擇其中最優(yōu)路徑上的弧進(jìn)行信息素的增強(qiáng)，揮發(fā)過程是所有弧都進(jìn)行的，不于螞蟻數(shù)量相關(guān)。這種增強(qiáng)過程中進(jìn)行的信息素更新稱為離線的信息素更新。在STEP3中，蟻群永遠(yuǎn)記憶到目前為止的最優(yōu)解。21初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）5/12圖的蟻群系統(tǒng)（GBAS）6/12可以驗(yàn)證，下式滿足：即是一個(gè)隨機(jī)矩陣。四個(gè)城市的非對(duì)稱TSP問題，距離矩陣和城市圖示如下：22圖的蟻群系統(tǒng)（GBAS）6/12可以驗(yàn)證，下式滿足：四個(gè)城初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）7/12假設(shè)共4只螞蟻，所有螞蟻都從城市A出發(fā)，揮發(fā)因子。此時(shí)，觀察GBAS的計(jì)算過程。矩陣共有12條弧，初始信息素記憶矩陣為：23初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）7/12假初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）8/12執(zhí)行GBAS算法的步驟2，假設(shè)螞蟻的行走路線分別為：當(dāng)前最優(yōu)解為，這個(gè)解是截止到當(dāng)前的最優(yōu)解，碰巧是實(shí)際最優(yōu)解24初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）8/12執(zhí)初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）9/12按算法步驟3的信息素更新規(guī)則，得到更新矩陣這是第一次外循環(huán)結(jié)束的狀態(tài)。25初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）9/12按初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）10/12重復(fù)外循環(huán)，由于上一次得到的W2已經(jīng)是全局最優(yōu)解，因此按算法步驟3的信息素更新規(guī)則，無論螞蟻如何行走，都只是對(duì)W2路線上的城市信息素進(jìn)行增強(qiáng)，其他的城市信息素進(jìn)行揮發(fā)。得到更新矩陣這是第一次外循環(huán)結(jié)束的狀態(tài)。26初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）10/12初始的蟻群優(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ā)。第三次外循環(huán)后得到的信息素矩陣為：27初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）11/12初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）12/12螞蟻以一定的概率從城市i到城市j進(jìn)行轉(zhuǎn)移，信息素的更新在STEP3完成，并隨K而變化。假設(shè)第K次外循環(huán)后得到信息素矩陣，得到當(dāng)前最優(yōu)解。第K次循環(huán)前的信息素和最優(yōu)解為，經(jīng)過第K次外循環(huán)后，得到。由于螞蟻的一步轉(zhuǎn)移概率是隨機(jī)的，從到也是隨機(jī)的，是一個(gè)馬爾可夫過程。28初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）12/12一般蟻群算法的框架一般蟻群算法的框架和GBAS基本相同，有三個(gè)組成部分：蟻群的活動(dòng)；信息素的揮發(fā)；信息素的增強(qiáng)；主要體現(xiàn)在前面的算法中步驟2和步驟3中的轉(zhuǎn)移概率公式和信息素更新公式。29一般蟻群算法的框架一般蟻群算法的框架和GBAS基本相同，有三蟻群優(yōu)化算法—算法模型和收斂性分析馬氏過程的收斂定義GBAS算法的收斂性分析其他算法及收斂性分析30蟻群優(yōu)化算法—算法模型和收斂性分析馬氏過程的收斂定義30馬氏過程的收斂定義蟻群優(yōu)化算法的每步迭代對(duì)應(yīng)隨機(jī)變量其中為信息素痕跡；為n城市的一個(gè)排列，最多有個(gè)狀態(tài)。第s只螞蟻在第k輪轉(zhuǎn)移只由決定，這個(gè)螞蟻行走的路徑和一起，共同決定了，再通過信息素的更新原則可以進(jìn)一步得到。的變化僅由決定，而與先前的狀態(tài)無關(guān)，這是一個(gè)典型的馬爾可夫過程。

定義：若一個(gè)馬爾可夫過程，對(duì)任意給定的滿足

則稱馬爾可夫過程依概率1收斂到。31馬氏過程的收斂定義蟻群優(yōu)化算法的每步迭代對(duì)應(yīng)隨機(jī)變量3GBAS算法的收斂性分析1/8

定理

滿足指定條件的馬爾可夫過程依概率1收斂到,其中為一條最優(yōu)路徑,定義為:

證明分析:蟻群算法中,一但達(dá)到全局最優(yōu),由只記錄第一個(gè)最優(yōu)解.證明分三部分:

證明以概率1達(dá)到一個(gè)最優(yōu)路徑證明(1)上式成立證明以概率1收斂到一個(gè)最優(yōu)路徑32GBAS算法的收斂性分析1/8定理滿足指定條件的GBAS算法的收斂性分析2/8證明以概率1到達(dá)一個(gè)最優(yōu)路徑對(duì)于最優(yōu)路徑,令為蟻群中的一個(gè)螞蟻在第k次外循環(huán)后第一次走到最優(yōu)路徑的事件.表示僅第k次外循環(huán)沒有走到的事件,但前k-1次可能走到過這條最優(yōu)路徑.永遠(yuǎn)不會(huì)被走到的事件為,其概率為:33GBAS算法的收斂性分析2/8證明以概率1到達(dá)一個(gè)最優(yōu)路徑GBAS算法的收斂性分析3/8任意給定的固定弧(i,j),在第k次循環(huán)后,其信息素值的下界可以計(jì)算出.34GBAS算法的收斂性分析3/8任意給定的固定弧(iGBAS算法的收斂性分析4/8令 ,任何一個(gè)固定節(jié)點(diǎn)最多有(n-1)后續(xù)節(jié)點(diǎn),并且其弧上的信息素值都小于1或者等于1.得:蟻群中的一只螞蟻在第次循環(huán)走到路徑W*的概率為一個(gè)蟻群中至少有一只螞蟻，因此這是一個(gè)蟻群到達(dá)最優(yōu)路徑的一個(gè)下界.上式右側(cè)與k無關(guān),35GBAS算法的收斂性分析4/8令 ,任何一個(gè)固定節(jié)點(diǎn)GBAS算法的收斂性分析5/8

則取對(duì)數(shù)有從而得到36GBAS算法的收斂性分析5/836GBAS算法的收斂性分析6/8證明右式成立隨機(jī)過程以概率1達(dá)到一條最優(yōu)路徑.當(dāng)某條最優(yōu)路徑Z在第k次循環(huán)被首次走到后,在第k+1輪循環(huán)按信息素的更新原則,可以用歸納法證明,對(duì)于任意37GBAS算法的收斂性分析6/8證明右式成立37GBAS算法的收斂性分析7/8由于級(jí)數(shù)是發(fā)散的,可知.因此,當(dāng)時(shí),在第K輪迭代之后,該弧永遠(yuǎn)不再被加強(qiáng),從而有也既弧上的信息素之和將趨于0.對(duì)于信息素的更新公式(2),可以歸納證明(6)式的第二項(xiàng)與(i,j)弧無關(guān),結(jié)合(7)式可得的極限存在,且所有的極限之和為1.對(duì)于所有的38GBAS算法的收斂性分析7/8由于級(jí)數(shù)是發(fā)散的,GBAS算法的收斂性分析8/8結(jié)合前兩部分討論,當(dāng)Xn首次到達(dá)最優(yōu)路徑后,對(duì)于任何最優(yōu)路徑上的弧,(1)式的轉(zhuǎn)移概率

,即依概率1收斂到

.39GBAS算法的收斂性分析8/8結(jié)合前兩部分討論,當(dāng)X其他算法及收斂性分析1/4

MAX-MIN蟻群優(yōu)化算法指定揮發(fā)系數(shù)不隨時(shí)間變化,這是和GBAS算法不同的一點(diǎn),改變了信息素?fù)]發(fā)和增強(qiáng)的規(guī)則(9式)，同時(shí)給出一個(gè)下界控制信息素的揮發(fā).

定理

在MAX-MIN算法中,40其他算法及收斂性分析1/4MAX-MIN蟻群優(yōu)化算其他算法及收斂性分析2/441其他算法及收斂性分析2/441其他算法及收斂性分析3/442其他算法及收斂性分析3/442其他算法及收斂性分析4/443其他算法及收斂性分析4/443蟻群優(yōu)化算法—技術(shù)問題解的表達(dá)形式與算法的實(shí)現(xiàn)每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定蟻群的規(guī)模和停止規(guī)則信息素的更改44蟻群優(yōu)化算法—技術(shù)問題解的表達(dá)形式與算法的實(shí)現(xiàn)44解的表達(dá)形式與算法的實(shí)現(xiàn)1/4

----解的表達(dá)形式解的表達(dá)形式基于TSP問題的蟻群優(yōu)化算法，其解的形式是所有城市的一個(gè)排列（閉圈，這種情況下誰在第一并不重要），信息素痕跡按每個(gè)弧記錄。而對(duì)于一般以順序作為解的優(yōu)化問題，誰在第一是很重要的。蟻群算法在解決這類問題時(shí)，只需要建立一個(gè)虛擬的始終點(diǎn)，就可以把TSP問題的解法推廣，用于諸多的優(yōu)化問題。諸如車間作業(yè)及下料等問題，他們的共同特點(diǎn)是解以一個(gè)順序表示。TSP問題尋找的是最短回路，而一般優(yōu)化問題中，STEP3中的判斷條件需要根據(jù)實(shí)際問題進(jìn)行修改。45解的表達(dá)形式與算法的實(shí)現(xiàn)1/4

----解的表達(dá)形式解的表達(dá)形式與算法的實(shí)現(xiàn)2/4

----算法的實(shí)現(xiàn)例：0-1背包問題的解順序表達(dá)形式與算法實(shí)現(xiàn)。設(shè)有一個(gè)容積為b的背包，n個(gè)尺寸分別為，價(jià)值分別為的物品，0-1背包問題的數(shù)學(xué)模型為：假設(shè)其解的順序表達(dá)形式為，其中為的一個(gè)排列。46解的表達(dá)形式與算法的實(shí)現(xiàn)2/4

----算法的實(shí)現(xiàn)例：0解的表達(dá)形式與算法的實(shí)現(xiàn)3/4

----算法的實(shí)現(xiàn)建立有向圖，其中A中共有條弧。初始信息素痕跡定義為。設(shè)第s只螞蟻第k步所走的路線為，表示螞蟻從0點(diǎn)出發(fā)，順序到達(dá)。第步按TSP算法的轉(zhuǎn)移概率公式行走選擇。若則，否則，此螞蟻不再繼續(xù)行走，退回起點(diǎn)。47解的表達(dá)形式與算法的實(shí)現(xiàn)3/4

----算法的實(shí)現(xiàn)建立有解的表達(dá)形式與算法的實(shí)現(xiàn)4/4----算法的實(shí)現(xiàn)對(duì)蟻群重復(fù)以上過程，比較m只螞蟻的裝包值 并記憶具有最大裝包值的螞蟻為t。把GBAS算法中步驟3中的改為，若滿足此條件則替換當(dāng)前最好解為，對(duì)W上的弧進(jìn)行信息素的加強(qiáng)，其他弧進(jìn)行信息素的揮發(fā)。算法中記錄了三個(gè)信息：信息素痕跡；行走路線；和問題的約束條件 ，以確定是否將加入。48解的表達(dá)形式與算法的實(shí)現(xiàn)4/4----算法的實(shí)現(xiàn)每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定----需要記憶的信息1/3算法中需要記憶的信息有三部分。第一部分信息是存在每個(gè)節(jié)點(diǎn)的路由表數(shù)據(jù)結(jié)構(gòu)，由此決定的的轉(zhuǎn)移概率為其中T可以看成節(jié)點(diǎn)i的鄰域。49每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定----需要記憶的信息1/3每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定----需要記憶的信息2/3第二部分需要記憶的信息是每個(gè)螞蟻的記憶表中存儲(chǔ)著的自身的歷史信息，這一部分主要由算法的中的記憶，表示螞蟻已經(jīng)行走過的節(jié)點(diǎn)。第三部分為問題的約束條件。在GBAS中，T集合表示滿足約束條件的候選集，在背包問題的蟻群算法中由判別條件， 來實(shí)現(xiàn)記

憶功能。50每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定----需要記憶的信息2/3每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定----系數(shù)的確定3/3

殘留信息的相對(duì)重要程度和預(yù)見值的相對(duì)重要程度體現(xiàn)了相關(guān)信息痕跡和預(yù)見度對(duì)螞蟻決策的相對(duì)影響。Dorigo在求解TSP問題時(shí)，推薦參數(shù)的最佳設(shè)置為：。51每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定----系數(shù)的確定3/3蟻群的規(guī)模和停止規(guī)則一、蟻群大小一般情況下蟻群中螞蟻的個(gè)數(shù)不超過TSP圖中節(jié)點(diǎn)的個(gè)數(shù)。二、終止條件

1給定一個(gè)外循環(huán)的最大數(shù)目，表明已經(jīng)有足夠的螞蟻工作；

2當(dāng)前最優(yōu)解連續(xù)K次相同而停止，其中K是一個(gè)給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)；

3目標(biāo)值控制規(guī)則，給定優(yōu)化問題（目標(biāo)最小化）的一個(gè)下界和一個(gè)誤差值，當(dāng)算法得到的目標(biāo)值同下界之差小于給定的誤差值時(shí)，算法終止。52蟻群的規(guī)模和停止規(guī)則一、蟻群大小一般情況下蟻群中螞蟻的個(gè)信息素的更改1/6信息素的更新分為離線和在線兩種方式。離線方式（同步更新方式）的主要思想是在若干只螞蟻完成n個(gè)城市的訪問后，統(tǒng)一對(duì)殘留信息進(jìn)行更新處理。信息素的在線更新（異步更新方式）即螞蟻每行走一步，立即回溯并且更新行走路徑上的信息素。53信息素的更改1/6信息素的更新分為離線和在線兩種方式信息素的更改2/6離線方式的信息素更新可以進(jìn)一步分為單螞蟻離線更新和蟻群離線更新。蟻群離線更新方式是在蟻群中的m只螞蟻全部完成n城市的訪問（第k-1次蟻群循環(huán)）后，統(tǒng)一對(duì)殘留信息進(jìn)行更新處理。其中，為第k-1次循環(huán)后的的信息素的痕跡值。單螞蟻離線更新是在第s只螞蟻完成對(duì)所有n個(gè)城市的訪問后，進(jìn)行路徑回溯，更新行走路徑上的信息素，同時(shí)釋放分配給它的資源。更新公式為第s+1只螞蟻根據(jù)重新計(jì)算路由表。

54信息素的更改2/6離線方式的信息素更新可以進(jìn)一步分信息素的更改3/6TSP問題中，蟻群優(yōu)化算法根據(jù)信息素痕跡更新方式不同可以分為不同的算法，采用離線方式，并且時(shí)，其中W為t循環(huán)中m只螞蟻所行走的最佳路線或第t只螞蟻所行走的一條路徑。Q為一個(gè)常數(shù)，該算法名為蟻環(huán)算法（ant-cyclealgotithm）,特點(diǎn)是行走的路徑越短對(duì)應(yīng)保存的信息素的值就越大。55信息素的更改3/6TSP問題中，蟻群優(yōu)化算法根據(jù)信息素痕跡信息素的更改4/6

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

蟻量算法（ant-quantitya