蟻群算法--李燕

1、物流工程李燕蟻群算法蟻群算法蟻群算法的提出蟻群算法的提出 一二 算法的數(shù)學(xué)模型算法的數(shù)學(xué)模型三蟻群算法的應(yīng)用蟻群算法的應(yīng)用 蟻群算法（Ant Colony Optimization, ACO），又稱螞蟻算法一種用來在圖中尋找優(yōu)化路徑的機(jī)率型算法。 它由Marco Dorigo于1992年在他的博士論文“Ant system: optimization by a colony of cooperating agents”中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。最早用于解決著名的旅行商問題(TSP , traveling salesman problem)。蟻群算法的提出蟻群算法的

2、提出 一Macro Dorigoo螞蟻在覓食的過程中會釋放特有的分泌物信息素，這種信息素能被同伴識別。當(dāng)螞蟻沿著一條路找到食物后會馬上返回來，這樣，路程短的螞蟻來回一次的時間就短，這也意味著重復(fù)的頻率就快，因而在單位時間里走過的螞蟻數(shù)目就多，灑下的信息素自然也會多，自然會有更多的螞蟻被吸引過來，從而灑下更多的信息素；而長的路正相反，因此，越來越多地螞蟻聚集到較短的路徑上來，最短的路徑就近似找到了。概念原型 螞蟻從A點(diǎn)出發(fā)，速度相同，食物在D點(diǎn)，可能隨機(jī)選擇路線ABD或ACD。假設(shè)初始時每條分配路線一只螞蟻，每個時間單位行走一步，本圖為經(jīng)過9個時間單位時的情形：走ABD的螞蟻到達(dá)終點(diǎn)，而走ACD

3、的螞蟻剛好走到C點(diǎn)，為一半路程。簡化的螞蟻尋食過程 本圖為從開始算起，經(jīng)過18個時間單位時的情形：走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A，而走ACD的螞蟻剛好走到D點(diǎn)。假設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個單位，則經(jīng)過36個時間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從D點(diǎn)取得了食物，此時ABD的路線往返了2趟，每一處的信息素為4個單位，而 ACD的路線往返了一趟，每一處的信息素為2個單位，其比值為2：1。 尋找食物的過程繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，蟻群在ABD路線上增派一只螞蟻（共2只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個時間單位后，兩條線路上的信息素單位積累為12和4，

4、比值為3：1。 若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個時間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。 若繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，最終所有的螞蟻會放棄ACD路線，而都選擇ABD路線。這也就是正反饋效應(yīng)。人工蟻群算法 基于以上蟻群尋找食物時的最優(yōu)路徑選擇問題，可以構(gòu)造人工蟻群，來解決最優(yōu)化問題，如TSP問題。 人工蟻群中把具有簡單功能的工作單元看作螞蟻。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。 兩者的區(qū)別在于人工蟻群有一定的記憶

5、能力，能夠記憶已經(jīng)訪問過的節(jié)點(diǎn)。同時，人工蟻群在選擇下一條路徑的時候是按一定算法規(guī)律有意識地尋找最短路徑，而不是盲目的。例如在TSP問題中，可以預(yù)先知道當(dāng)前城市到下一個目的地的距離。o 螞蟻k(k=1,2，,m)根據(jù)各個城市間連接路徑上的信息素濃度決定其下一個訪問城市，設(shè)Pijk(t)表示t時刻螞蟻k從城市i轉(zhuǎn)移到城市j的概率，其計(jì)算公式為： ( ) ( , ) ( , ),( ) ( , ) ( , )( , )(1)0,kkks Jii ji jif jJii si sPi jotherwise二 算法的數(shù)學(xué)模型算法的數(shù)學(xué)模型o 其中， 表示從城市i可以直接到達(dá)的且又不在螞蟻訪問過的城市序

6、列 中的城市集合， 是一個啟發(fā)式信息，通常由 直接計(jì)算， 表示邊(i,j)上的信息素量。 由公式（1）可知，長度越短、信息素濃度越大的路徑被螞蟻選擇的概率越大。 和 是兩個預(yù)先設(shè)置的參數(shù)，用來控制啟發(fā)式信息（路徑的能見度）與信息濃度（路徑的軌跡）作用的權(quán)重關(guān)系。當(dāng) 時，算法演變成傳統(tǒng)的隨機(jī)貪婪算法，最鄰近城市被選種的概率最大，當(dāng) 時，螞蟻完全只根據(jù)信息度濃度確定路徑，算法將快速收斂，這樣構(gòu)建出的最優(yōu)路徑往往與實(shí)際目標(biāo)有著較大的差異，算法的性能比較糟糕，實(shí)驗(yàn)表明，在AS中設(shè)置 比較合適。( )kJikR( , )i j( , )1 /iji jd( , )i j001 2,a 2 5o信息更新公

7、式為：1(1)(1)( ) ijijijnkijijktto信息素更新的每一輪中，問題空間中的所有路徑上的信息素都會發(fā)生蒸發(fā)，信息素蒸發(fā)是自然界本身固有的特征，在算法中能避免信息素的無限積累，使得算法可以快速丟棄之前構(gòu)建過的較差路徑。隨后所有的螞蟻根據(jù)自己構(gòu)建路徑長度在它們本輪經(jīng)過的邊釋放信息素。螞蟻構(gòu)建的路徑越短、釋放的信息素就越多；一條被螞蟻爬過的邊的次數(shù)越多、它所獲得的信息素也越多。on表示螞蟻的個數(shù), 是信息素的蒸發(fā)率，規(guī)定 ，一般設(shè)置為0.5. 是本次循環(huán)中路徑（i,j）上信息素的增量。01ij根據(jù)信息素更新策略的不同, M. Dorigo 曾提出3 種不同的基本蟻群算法模型,其差別

8、在于 求法的不同,即:Ant - Cycle 模型Ant - Quantity 模型Ant - Density 模型其中Ant - antity 模型和Ant - Density 模型利用的是局部信息; 而Ant- Cycle 模型利用的是整體信息, 在求解TSP 時性能較好, 因此通常采用Ant - Cycle 模型模型作為蟻群算法的基本模型。Ant-Cycle模型蟻周模型式中，Q表示信息素強(qiáng)度，表示螞蟻循環(huán)一次所釋放的信息素總量，它在一定程度上影響算法的收斂速度；Lk表示第k只螞蟻在本次循環(huán)中所走路徑的總長度。Ant-Quantity模型蟻量模型Ant-Density模型蟻密模型 kij三

9、蟻群算法的應(yīng)用蟻群算法的應(yīng)用TSP問題o 旅行商問題旅行商問題（TSP,traveling salesman problem）1960年首先提出。o 問題描述問題描述：一商人去n個城市銷貨，所有城市走一遍再回到起點(diǎn)，使所走路程最短。蟻群系統(tǒng)在TSP問題中的應(yīng)用10城市TSP問題20城市TSP問題蟻群系統(tǒng)在TSP問題中的應(yīng)用30城市TSP問題48城市TSP問題TSP問題的數(shù)學(xué)描述TSP問題表示為一個N個城市的有向圖G=（N，A），其中城市之間距離目標(biāo)函數(shù)為其中， ，為城市1,2，n的一個排列， 。nnijd)(nliilldwf11min)(),(21niiiw11iinN1,2,.,n A(i ,j)| ,i jNo下面以TSP為例說明基本蟻群算法模型。o首先將m只螞蟻隨機(jī)放置在n個城市，位于城市i的第k只螞蟻選擇下一個城市j的概率為: 蟻群算法求解TSP問題) 1 (,0,),(),(),(),(),(otherwisetabujifsisijijijiPktabuskko其中： 表示邊（i，j）上的信息素濃度； 是啟發(fā)信息，dij是城市i和j之間的距離； 和反映了信息素與啟發(fā)信息的相對重要性； 表示螞蟻k已經(jīng)訪問過的城市列表。),(ji),(/1),(jidjiktabuo當(dāng)所有螞蟻完成周游后，按以下公式進(jìn)行信