蟻群優(yōu)化算法起源20世紀90年代，意大利學者Dorigo等人從生物進化的機制中受到啟發(fā)，通過模擬自然界螞蟻搜索路徑的行為，提出一種新型的模擬進化算法——蟻群算法，它是群智能理論研究領(lǐng)域的一種主要算法。用該方法求解TSP問題、分配問題、job-shop調(diào)度問題取得了較好的試驗結(jié)果。雖然研究時間不長，但是目前的研究顯示出，蟻群算法在求解復(fù)雜優(yōu)化問題（特別是離散優(yōu)化問題）方面有一定優(yōu)勢，表明它是一種有發(fā)展前景的算法。ch2智能理論--蟻群算法蟻群優(yōu)化算法應(yīng)用領(lǐng)域蟻群算法能夠用于解決大多數(shù)優(yōu)化問題或者能夠被轉(zhuǎn)化為優(yōu)化求解的問題。目前，其應(yīng)用領(lǐng)域已擴展到多目標優(yōu)化數(shù)據(jù)分類數(shù)據(jù)聚類模式識別生物系統(tǒng)建模流程規(guī)劃信號處理機器人控制決策支持仿真和系統(tǒng)辯識ch2智能理論--蟻群算法蟻群優(yōu)化算法研究背景群智能理論研究領(lǐng)域有兩種主要的算法：蟻群算法(AntColonyOptimization,ACO)對螞蟻群落食物采集過程的模擬已成功應(yīng)用于許多離散優(yōu)化問題。微粒群算法(ParticleSwarmOptimization,PSO)起源于對簡單社會系統(tǒng)的模擬。最初模擬鳥群覓食的過程，后來發(fā)現(xiàn)它是一種很好的優(yōu)化工具。ch2智能理論--蟻群算法蟻群優(yōu)化算法研究背景群智能依靠的是概率搜索算法。雖然概率搜索算法通常要采用較多的評價函數(shù)，但與梯度法及傳統(tǒng)的演化算法相比，主要優(yōu)點為：

無集中控制約束，不會因個別個體的故障影響整個問題的求解，確保了系統(tǒng)具備更強的魯棒性以非直接的信息交流方式確保了系統(tǒng)的擴展性并行分布式算法模型，可充分利用多處理器對問題定義的連續(xù)性無特殊要求算法實現(xiàn)簡單ch2智能理論--蟻群算法蟻群優(yōu)化算法研究背景群智能方法的易于實現(xiàn)體現(xiàn)在：算法中僅涉及各種基本的數(shù)學操作數(shù)據(jù)處理過程對CPU和內(nèi)存的要求不高只需要目標函數(shù)的輸出值，不需要它的梯度信息。ch2智能理論--蟻群算法蟻群優(yōu)化算法研究背景已完成的群智能理論和應(yīng)用方法研究證明群智能方法能夠有效解決大多數(shù)全局優(yōu)化問題群智能潛在的并行性和分布式特點為處理大量的、以數(shù)據(jù)庫形式存在的數(shù)據(jù)提供了技術(shù)保證。無論從理論研究還是應(yīng)用研究的角度分析，群智能理論及其應(yīng)用研究都是有重要學術(shù)意義和現(xiàn)實價值。ch2智能理論--蟻群算法蟻群優(yōu)化算法研究現(xiàn)狀從Dorigo在90年代最早提出蟻群算法—-螞蟻系統(tǒng)(AntSystem,AS)，并將其應(yīng)用于解決TSP問題開始，基本的蟻群算法得到了不斷的發(fā)展和完善，并在其他許多實際優(yōu)化問題求解中進一步得到了驗證。AS改進版共同點：增強螞蟻搜索過程中對最優(yōu)解的探索能力差異：搜索控制策略ch2智能理論--蟻群算法蟻群優(yōu)化算法研究現(xiàn)狀最初提出的AS有三種版本：Ant-density、Ant-quantity、Ant-cycle前兩種算法中，螞蟻在兩個位置節(jié)點間每移動一次后即更新信息素。Ant-cycle中，所有螞蟻都完成了自己的行程后，才對信息素進行更新，而且每個螞蟻所釋放的信息素被表達為反映相應(yīng)行程質(zhì)量的函數(shù)。與其它各種通用的啟發(fā)式算法相比，在不大于75城市的TSP中，它們的求解能力比較理想。但是當問題規(guī)模擴展時，AS的解題能力大幅度下降。ch2智能理論--蟻群算法蟻群優(yōu)化算法研究現(xiàn)狀其后的ACO研究工作主要都集中在AS性能的改進方面。較早的一種改進是精英策略(ElitistStrategy)，其思想是：在算法開始后，對所有已發(fā)現(xiàn)的最好路徑給予額外增強，并將隨后與之對應(yīng)的行程記為Tgb(全局最優(yōu)行程)，當進行信息素更新時，對這些行程予以加權(quán)，同時將經(jīng)過這些行程的螞蟻記為“精英”，從而增大較好行程的選擇機會。這種改進型算法能以更快的速度獲得更好的解。但是若選擇的精英過多，則算法會由于較早收斂于局部次優(yōu)解，而導致搜索的過早停滯。ch2智能理論--蟻群算法螞蟻尋食過程尋找路徑時，在路徑上釋放出一種特殊的信息素。碰到?jīng)]有走過的路口，隨機挑選一條路徑，并釋放出與路徑長度有關(guān)的信息素。路徑越長，釋放的激素濃度越低。后來的螞蟻再次碰到這個路口的時候，選擇激素濃度較高路徑概率相對較大。正反饋：最優(yōu)路徑上激素濃度越來越大，其它路徑上激素濃度隨時間的流逝而消減。最終整個蟻群找出最優(yōu)路徑。ch2智能理論--蟻群算法簡化的螞蟻尋食過程螞蟻從A點出發(fā)，速度相同，食物在D點。可隨機選擇的路線：ABD或ACD。設(shè)初始時每條路線分配一只螞蟻，每單位時間行走一步上圖為經(jīng)過9個時間單位時的情形：走ABD的螞蟻到達終點，而走ACD的螞蟻剛好走到C點，為一半路程。ch2智能理論--蟻群算法簡化的螞蟻尋食過程本圖為從開始算起，經(jīng)過18個時間單位時的情形：走ABD的螞蟻到達終點后得到食物又返回了起點A走ACD的螞蟻剛好走到D點。ch2智能理論--蟻群算法簡化的螞蟻尋食過程設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個單位。36個時間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從D點取得了食物。ABD的路線往返了2趟，每一處的信息素為4個單位ACD的路線往返了1趟，每一處的信息素為2個單位信息素比值為2:1按信息素指導，蟻群在ABD路線上增派一只螞蟻(共2只)，ACD路線上仍然是一只螞蟻。ch2智能理論--蟻群算法簡化的螞蟻尋食過程72個時間單位后，兩條線路上的信息素單位積累為12和4，比值為3:1。若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻(共3只)，ACD路線上仍然是一只螞蟻。再36個時間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。若繼續(xù)進行，按信息素指導，最終所有螞蟻會放棄ACD路線，都選擇ABD路線，這就是正反饋效應(yīng)。ch2智能理論--蟻群算法自然蟻群與人工蟻群算法人工蟻群中把具有簡單功能的工作單元看作螞蟻。相似處：優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。區(qū)別：人工蟻群能記憶已訪問過的節(jié)點，在選擇下條路徑時是按一定算法規(guī)律有意識地尋找最短路徑。如，TSP問題中可預(yù)先知道當前城市到下一個目的地的距離。ch2智能理論--蟻群算法蟻群算法與TSP問題初始的蟻群算法是基于圖的蟻群算法(graph-basedantsystem，GBAS)，2000年由Gutjahr在FutureGenerationComputingSystems提出。TSP問題表示為N個城市的有向圖：G=(N,A)目標函數(shù)w=(i1,i2,…,in)為城市1,2,…,n的一個排列(dij)nn為城市間距離矩陣ch2智能理論--蟻群算法蟻群算法與TSP問題設(shè)m只螞蟻在圖的相鄰節(jié)點間移動，協(xié)作異步地得到解。螞蟻計算出下一步所有可達節(jié)點的一步轉(zhuǎn)移概率，并按此概率實現(xiàn)一步移動，依此往復(fù)。一步轉(zhuǎn)移概率由圖中每條邊上的兩類參數(shù)決定：信息素值、可見度(即先驗值)。信息素的更新有2種方式：揮發(fā)——所有路徑上信息素以一定比率減少增強——給評價值“好”(有螞蟻走過)的邊增加信息素ch2智能理論--蟻群算法基于圖的蟻群系統(tǒng)(GBAS)STEP0

對n個城市的TSP問題，城市間的距離矩陣為：(dij)nn給TSP圖中的每一條弧(i,j)賦信息素初值：ij(0)=1/|A||A|：表示圖中弧(i,j)的數(shù)目，即矩陣(dij)nn中不為零的數(shù)；設(shè)有m只螞蟻工作，都從同一城市i0出發(fā)當前最好解是：w*=(1,2,…,n)目標函數(shù)：ch2智能理論--蟻群算法基于圖的蟻群系統(tǒng)(GBAS)STEP1(外循環(huán))

若滿足算法停止規(guī)則，停止計算，輸出計算得到的最好解給定外循環(huán)的最大數(shù)目，表明有足夠的螞蟻工作；當前最優(yōu)解連續(xù)K次相同而停止，K是給定的整數(shù)，表示算法已收斂；給定優(yōu)化問題的下界和誤差值，當算法得到的目標值同下界之差小于給定的誤差值時，算法終止。否則使螞蟻s(1sm)從起點i0出發(fā)，用L(s)表示螞蟻s行走的城市集合，初始L(s)為空集。ch2智能理論--蟻群算法基于圖的蟻群系統(tǒng)(GBAS)STEP2(內(nèi)循環(huán))

按螞蟻1sm的順序分別計算在城市i，若L(s)=N或{l|(i,l)A,lL(s)}=，完成螞蟻s的計算。否則，若T={l|(i,l)A,lL(s)}-{i0}，以概率 到達j，L(s)=L(s){j}，il=j若L(s)N且T=，則到達i0， L(s)=L(s){i0}，il=i0 重復(fù)STEP2ch2智能理論--蟻群算法基于圖的蟻群系統(tǒng)(GBAS)STEP3

對螞蟻1sm，若L(s)=N，按L(s)中城市的順序計算路徑長度；若L(s)N，路徑長度置為無窮大(即不可達)。比較m只螞蟻的路徑長度，記走最短路徑的螞蟻為t。若f(L(t))<f(w*)，則w*=L(t)ch2智能理論--蟻群算法修改信息素值對固定的K1，揮發(fā)因子k滿足：加強w*路徑上的信息素揮發(fā)其他路徑上的信息素，經(jīng)過k次揮發(fā)，非最優(yōu)路徑的信息素逐漸減少至消失。k=k+1，重復(fù)STEP1ch2智能理論--蟻群算法關(guān)于信息素螞蟻以信息素的概率分布來決定從城市i到j(luò)的轉(zhuǎn)移，信息素更新過程由兩部分組成揮發(fā)——每個連接上信息素逐漸減弱的過程由(1-k-1)ij(k-1)表示，該過程主要用于避免算法過快地向局部最優(yōu)區(qū)域集中，有助于搜索區(qū)域的擴展。揮發(fā)過程是所有弧都進行的，與螞蟻數(shù)量無關(guān)。增強——觀察蟻群中每只螞蟻找到的路徑，選擇最優(yōu)路徑上的弧進行信息素增強，實現(xiàn)單個螞蟻無法實現(xiàn)的集中行動。增強過程是蟻群優(yōu)化算法中可選的部分。ch2智能理論--蟻群算法關(guān)于信息素信息素的更新分為離線和在線兩種方式。離線方式（同步更新方式） 主要思想是在若干只螞蟻完成n個城市的訪問后，統(tǒng)一對殘留信息進行更新處理。在線更新（異步更新方式） 螞蟻每走一步，立即回溯并且更新行走路徑上的信息素。ch2智能理論--蟻群算法基于圖的蟻群系統(tǒng)(GBAS)四個城市的非對稱TSP問題ch2智能理論--蟻群算法基于圖的蟻群系統(tǒng)（GBAS）設(shè)共有4只螞蟻，都從城市A出發(fā)揮發(fā)因子初始信息素記憶矩陣為：ch2智能理論--蟻群算法基于圖的蟻群系統(tǒng)（GBAS）執(zhí)行GBAS算法的步驟2，設(shè)螞蟻的行走路線分別為： 第一只w1：ABCDA

f(w1)=4 第二只w2：ACDBA

f(w1)=3.5 第三只w3：ADCBA

f(w1)=8 第四只w4：A