蟻群算法及其應(yīng)用實(shí)例

1、蟻群算法及其應(yīng)用實(shí)例、,、刖百：本文章相關(guān)內(nèi)容參考自包子陽(yáng)等編著智能優(yōu)化算法及其MATLAB實(shí)例(第2版)，將自己的理解寫(xiě)出來(lái)供讀者參考，筆者將算法Matlab實(shí)例用Python改寫(xiě)，如存在不合理的地方評(píng)論指正。主要內(nèi)容有：1.蟻群算法理論2.基本蟻群算法描述3蟻群算法TSP問(wèn)題中的應(yīng)用實(shí)例(Pyhton)、蟻群算法理論蟻群算法(antcolonyoptimization,ACO),又稱(chēng)螞蟻算法，是一種對(duì)自然界螞蟻的尋徑方式進(jìn)行模擬而得到的一種仿生算在圖中尋找優(yōu)化路徑的機(jī)率型算法。螞蟻在運(yùn)動(dòng)過(guò)程中，可以在行走的路徑上留下信息素，后來(lái)的螞蟻可以感知到信息素的存在，信息素濃度越高的路徑越容易被后來(lái)

2、的螞蟻選擇，從而形成一種正反饋現(xiàn)象。它能夠求出從原點(diǎn)出發(fā)，經(jīng)過(guò)若干個(gè)給定的需求點(diǎn)，最終返回原點(diǎn)的最短路徑。這也就是著名的旅行商問(wèn)題(TravelingSalemanProblem，TSP)。1真實(shí)蟻群若螞蟻從A點(diǎn)出發(fā)到D點(diǎn)覓食，它可以隨機(jī)從ABD或ACD中選擇一條路。假設(shè)初始時(shí)為每條路分配一只螞蟻，每個(gè)時(shí)間單位行走一步，則經(jīng)過(guò)8個(gè)時(shí)間單位后，情形如下圖所示：ABD路線的螞蟻到達(dá)D點(diǎn)，ACD路線的螞蟻到達(dá)C點(diǎn)。螞蟻出發(fā)后8個(gè)時(shí)間單位情形.png那么，再過(guò)8個(gè)時(shí)間單位，很容易可以得到下列情形：ABD路線的螞蟻回到A點(diǎn)，ACD路線的螞蟻到達(dá)D點(diǎn)。螞蟻出發(fā)后16個(gè)時(shí)間單位情形.png經(jīng)過(guò)32個(gè)單位時(shí)間

3、后，ABD路徑上的螞蟻往返兩趟，ACD往返一趟，那么ABD與ACD路徑上的信息素濃度比值為2:1。根據(jù)信息素的指導(dǎo)，接下來(lái)ABD路徑就有2只螞蟻選擇，ACD路徑仍然為1只，經(jīng)過(guò)32個(gè)單位時(shí)間后信息素就會(huì)達(dá)到3:1。因此會(huì)有越來(lái)越多的螞蟻選擇ABD,ACD逐漸被放棄，這就形成了正反饋。2人工蟻群基于以上真實(shí)蟻群尋及食物時(shí)的鼓優(yōu)路徑選擇問(wèn)題，可以構(gòu)造人工蟻聲，來(lái)解扶最優(yōu)化問(wèn)題，如TEP問(wèn)題人工蟻群中把具有簡(jiǎn)單功能的工作單元看作蝦蟻二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短轉(zhuǎn)徑的信息高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果兩者貳區(qū)別在于人工蟻群有一-定貳記憶能力，能夠記憶已經(jīng)

4、訪問(wèn)過(guò)的節(jié)點(diǎn).同時(shí)，人工蟻群再選擇F條路徑的時(shí)喉是按定算法規(guī)律有意識(shí)地尋找最短路徑.而不是盲目的a倒如在TEP問(wèn)題中，可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離，在TSP問(wèn)題的人工蟻群算假設(shè)閃只螞蛻在圖的相鄰節(jié)點(diǎn)同移動(dòng)，從而協(xié)乍異芳地得到問(wèn)題的解。每只螞蟻抽一步轉(zhuǎn)移概率由閣中的每條邊上的兩類(lèi)蔘數(shù)決定：一是信息素（5,也稱(chēng)信息素痕跡：二是可見(jiàn)度*即先驗(yàn)殖。信息素的更新方式有兩種：-是揮發(fā).也就是所有路徑上的信息素以定的比率減少，模擬自然蟻群的信息素隨時(shí)用揮發(fā)的過(guò)程：-是塩強(qiáng)，給評(píng)價(jià)價(jià)計(jì)（有螞蟻?zhàn)哌^(guò)）的邊堪加信息素.螞蟻向下一個(gè)目標(biāo)的運(yùn)動(dòng)是通過(guò)一個(gè)隨機(jī)原則來(lái)實(shí)現(xiàn)的.也就是運(yùn)月當(dāng)前所在節(jié)心存儲(chǔ)的莖息，

5、計(jì)算出下“步可達(dá)節(jié)點(diǎn)的橇率，井按此槪率實(shí)現(xiàn)歩移動(dòng)，如此往復(fù)，越來(lái)越接近最優(yōu)認(rèn)。螞蟻在尋找過(guò)程中.或在找到個(gè)解后，會(huì)評(píng)怙該解或解的一部3蟻群算法特點(diǎn)-.蟻群算法是一種本質(zhì)上的并行算法，每只螞蟻獨(dú)立運(yùn)行，僅通過(guò)信息素通信。蟻群算法是一種自組織算法，自組織就是系統(tǒng)從無(wú)序到有序的變化過(guò)程蟻群算法具有較強(qiáng)的魯棒性，求解結(jié)果不依賴(lài)于初始路線的選擇，求解過(guò)程不需要人工調(diào)整，參數(shù)少，設(shè)置簡(jiǎn)單，易于應(yīng)用到組合優(yōu)化問(wèn)題。蟻群算法是一種正反饋算法。二、基本蟻群算法1基本蟻群算法表述基本蟻群算法表述：在算法的初始時(shí)刻，將m只螞蟻隨機(jī)分配到n座城市，并將禁忌表(存放訪問(wèn)過(guò)的城市)的第一個(gè)元素設(shè)置為當(dāng)前所在城市。初始化各

6、路徑上的信息素量，各路徑上信息素量設(shè)為相同。接下來(lái)，每只螞蟻根據(jù)路徑上的信息素量和啟發(fā)式信息獨(dú)立地選擇下一座城市。當(dāng)所有螞蟻完成次周游后，對(duì)各個(gè)路徑上的信息素進(jìn)行更新。在時(shí)刻t,螞蟻k從城市i轉(zhuǎn)移到城市j的概率為：概率公式f*=allowedk其中，a和卩分別表示信息素和期望啟發(fā)式因子的相對(duì)重要程度。Tij(t)表示信息素量。表示啟發(fā)式因子，通常取城市i與城市j的距離的倒數(shù)。表示螞蟻k尚未訪問(wèn)城市的集合。螞蟻周游一次后信息素按照下式進(jìn)行更新:牛(f+町=(1一Q奇+A信息素更新公式其中，p表示信息素蒸發(fā)系數(shù)，i-p即為信息素殘留系數(shù)G(+)表示n只螞蟻周游后的信息素量ifJIfCl表示信息素的

7、增量根據(jù)信息素增量的不同計(jì)算規(guī)則，蟻群算法分為三種模型:Q是一個(gè)正常數(shù)Lk是螞蟻k本次周游中所走過(guò)的路徑的長(zhǎng)度蟻周模型Ant-Cycle直當(dāng)嗎蟻斤在本次周游中經(jīng)過(guò)邊如寸0.其他蟻量模型Ant-QuantityZ,當(dāng)螞蟻k在時(shí)刻f和/十1經(jīng)遼邊帀時(shí)h其他*蟻密模型Ant-Density卜0,當(dāng)螞蟻無(wú)在時(shí)刻f和2+1經(jīng)過(guò)邊Ar.=勺0其他2各參數(shù)分析信息素啟發(fā)式因子aa代表信息素量對(duì)是否選擇當(dāng)前路徑的影響程度，反映了蟻群在路徑搜索中隨機(jī)性因素作用的強(qiáng)度。a越大，螞蟻選擇以前走過(guò)的路徑的可能性越大，搜索的隨機(jī)性就會(huì)減弱。a過(guò)小，會(huì)導(dǎo)致蟻群搜索過(guò)早陷入局部最優(yōu)，取值范圍通常為1,4。期望啟發(fā)式因子BB

8、反映了啟發(fā)式信息在指導(dǎo)蟻群搜索中的相對(duì)重要程度，蟻群尋優(yōu)過(guò)程中先驗(yàn)性、確定性因素作用的強(qiáng)度。B過(guò)大，雖然收斂速度加快，但是易陷入局部最優(yōu)。B過(guò)小，蟻群易陷入純粹的隨機(jī)搜索，很難找到最優(yōu)解。通常取0,5。信息蒸發(fā)系數(shù)PP反映了信息素的蒸發(fā)程度，相反，1-Q表示信息素的保留水平P過(guò)大，信息素會(huì)發(fā)過(guò)快，容易導(dǎo)致最優(yōu)路徑被排除。P過(guò)小，各路徑上信息素含量差別過(guò)小，以前搜索過(guò)的路徑被在此選擇的可能性過(guò)大，會(huì)影響算法的隨機(jī)性和全局搜索能力。通常取0.2,0.5。螞蟻數(shù)目mm過(guò)大，每條路徑上信息素趨于平均，正反饋?zhàn)饔脺p弱，從而導(dǎo)致收斂速度減慢。m過(guò)小，可能導(dǎo)致一些從未搜索過(guò)的路徑信息素濃度減小為0，導(dǎo)致過(guò)早

9、收斂，解的全局最優(yōu)性降低信息素強(qiáng)度Q總信息量Q對(duì)算法性能的影響有賴(lài)于aBp的選取，以及算法模型的選擇。Q對(duì)ant-cycle模型蟻群算法的性能沒(méi)有明顯影響，不必特別考慮，可任意選取。3算法步驟三、蟻群算法實(shí)例#-*-coding:utf-8-*-Author:WuXianTime:2020/10/3021:17File:antTSP.pyTitle:蟻群算法解決TSP的Python實(shí)現(xiàn)frommatplotlibimportpyplotaspltimportnumpyasnpimportmathimportrandom”符號(hào)注釋?zhuān)篶ities:數(shù)組，記錄個(gè)城市坐標(biāo)n:整型，城市數(shù)量m:整型，螞

10、蟻個(gè)數(shù)，取城市數(shù)目的1.5倍NC:迭代計(jì)數(shù)器NC_MAX:最大迭代次數(shù)ALPHA:常數(shù)，a,信息素啟發(fā)式因子，a選擇1,4比較合適BETA:常數(shù)，B，期望啟發(fā)因子，B選擇345比較合適RHO:常數(shù)，p,信息素蒸發(fā)系數(shù)，p選擇0.1,0.2,0.5比較合適Q:常數(shù)，信息素強(qiáng)度Eta(i,j):啟發(fā)因子n，距離的倒數(shù)est_pathi各代最佳路toBest_Path_Len:各代最佳路線長(zhǎng)度Best_Path_Len_Average:各代路線的平均長(zhǎng)度Table_Phe=叩.ones(n,n)#n*n信息素矩陣，初始值都為1Table_Path=叩.zeros(m,n)#m*n路徑記錄表Dista

11、nce=叩.zeros(n,n)#n*n兩城市間距離矩陣flHfl1.參數(shù)初始化cities=1304,2312,3639,1315,4177,2244,3712,1399,3488,1535,3326,1556,3238,1229,4196,1044,4312,790,4386,570,3007,1970,2562,1756,2788,1491,2381,1676,1332,695,3715,1678,3918,2179,4061,2370,3780,2212,3676,2578,4029,2838,4263,2931,3429,1908,3507,2376,3394,2643,3439,3

12、201,2935,3240,3140,3550,2545,2357,2778,2826,2370,2975#城市坐標(biāo)矩陣n=len(cities)#城市數(shù)量m=int(n*1.5)#螞蟻數(shù)量，取城市數(shù)的1.5倍NC=0#迭代計(jì)數(shù)器，從0開(kāi)始，表示第NC+1次迭代NC_MAX=100#最大迭代次數(shù)，取100500之間ALPHA=1#常數(shù)，a,信息素啟發(fā)式因子BETA=5#常數(shù)，B，期望啟發(fā)因子RHO=0.1#常數(shù)，p,信息素蒸發(fā)系數(shù)Q=100#常數(shù)，信息素強(qiáng)度Best_Path=叩.zeros(NC_MAX,n)#NC_MAX*n矩陣，記錄NC_MAX次迭代的所求最佳路徑，每條記錄表示一次迭代所

13、的最優(yōu)路徑Best_Path_Len=叩.zeros(NC_MAX,1)#NC_MAX*1矩陣，記錄每次的最佳路徑長(zhǎng)度Best_Path_Len:,:=np.inf#暫時(shí)賦值為infBest_Path_Len_Average=叩.zeros(NC_MAX,1)#最優(yōu)路徑長(zhǎng)度平均Table_Phe=叩.ones(n,n)#n*n信息素矩陣，初始值都為1Table_Path=叩.zeros(m,n)#m*n路徑記錄表Distance=叩.zeros(n,n)#n*n兩城市間距離矩陣#計(jì)算兩城市間的距離foriinrange(0,n):forjinrange(0,n):ifi!=j:Distance

14、i,j=math.sqrt(citiesj0-citiesi0)*2+(citiesj1-citiesi1)*2)else:Distanceij=1e-4Eta=1./Distance#啟發(fā)因子，取距離的倒數(shù)2迭代尋找最佳路徑whileNCrandom.random()to_visit=Unvisited:,int(SelectO)Table_Pathi,j=to_visit#將代訪問(wèn)城市加入Table_Path矩陣，代表該城市被訪問(wèn)2.3.記錄本次迭代最佳路線Length=叩.zeros(m,1)#m*1矩陣，記錄每只螞蟻的路徑長(zhǎng)度f(wàn)oriinrangem):#計(jì)算每只螞蟻的路徑長(zhǎng)度Rout

15、e=Table_Pathi,:#在Table_Path表中找到該螞蟻的路徑行，將整行賦給Routeforjinrange(0,n-1):#對(duì)路徑長(zhǎng)度求和Lengthi=Lengthi+Distanceint(Routej),int(Routej+1)Lengthi=Lengthi+Distanceint(Route0),int(Routen-1)#從最后一個(gè)節(jié)點(diǎn)回到起點(diǎn)的距離ifNC=0:#第一次迭代min_length=叩.min(Length)#m只螞蟻路徑長(zhǎng)度最小值min_index=np.argmin(Length)#最小值索弓IBest_PathNC,:=Table_Pathmin_

16、index,:#最優(yōu)路徑表Best_Path_LenNC,:=min_length#最優(yōu)路徑長(zhǎng)度為最小值Best_Path_Len_AverageNC,:=叩.mean(Length)#求平均print(f最短路徑：Best_Path_LenNC,:)else:#第NC次迭代minength=np.min(Length)min_index=np.argmin(Length)Best_Path_LenNC,:=min(Best_Path_LenNC-1,minength)Best_Path_Len_AverageNC,:=叩.mean(Length)ifBest_Path_LenNC,:=min

17、ength:Best_PathNC,:=Table_Pathmin_index,:else:Best_PathNC,:=Best_PathNC-1,:print(f最短路徑：Best_Path_LenNC,:)2.4.更新信息素Delta_Table_Phe=叩.zeros(n,n)#信息素變化量矩陣foriinrange(0,m):forjinrange(0,n-1):Delta_Table_Pheint(Table_Pathi,j),int(Table_Pathi,j+1)=Delta_Table_Pheint(Table_Pathi,j),int(Table_Pathi,j+1)+Q/L

18、engthi,:Delta_Table_Pheint(Table_Pathi,n-1),int(Table_Pathi,0)=Delta_Table_Pheint(Table_Pathi,n-1),int(Table_Pathi,0)+Q/Lengthi,:Table_Phe=(1-RHO)*Table_Phe+Delta_Table_Phe2.5.禁忌表清零Table_Path=np.zeros(m,n)print(*100)NC=NC+1#進(jìn)入下一次迭代3.迭代結(jié)束，結(jié)果輸出shortest_length=叩.min(Best_Path_Len)#在Best_Path_Len中找出最短長(zhǎng)度

19、shortest_index=叩.argmin(Best_Path_Len)#取得該最短長(zhǎng)的的路徑在Best_Path_Len中的位置Shortest_Route=Best_Pathshortest_index,:#根據(jù)位置在bast_path中找到該路徑print(f最短路徑:Shortest_Route+1)print(f最短路徑長(zhǎng)度:shortest_length)4可視化輸出4.1最短路徑可視化#創(chuàng)建窗口fig1=plt.figure(figsize=(10,8),dpi=120)#這只圖片大小figsize(len,width),dpi設(shè)置像素值#準(zhǔn)備數(shù)據(jù)x=#存放各城市橫坐標(biāo)y=#

20、存放各城市縱坐標(biāo)foriinrange(0,len(cities):#取值route=citiesint(Shortest_Routei)append(route0)y.append(route1)#繪制坐標(biāo)plt.xticks(np.arange(O,5000,500)plt.yticks(np.arange(O,5000,500)plt.xlabel(x)plt.ylabel(y)plt.title(*最優(yōu)路徑圖)c=0fori,jinzip(x,y):#給各個(gè)點(diǎn)標(biāo)注plt.text(i+0.1,j+0.3,str(int(Shortest_Routec+1),ha=center,va=bottom,fontsize=10.5)c+=1plt.rcParamsfont.sans-serif=MicrosoftYaHei#解決matplotlib不顯示中文plt.grid(alpha=0.2)#繪制網(wǎng)格,alpha=0.2表示透明度#畫(huà)圖plt.plot(x,y,color=orange)plt.scatter(x,y,c=black,marker=o)end2Start_x=兇len(x)-1,x0end2Start_y=ylen(y)-1,y0plt.plot(end2Start_x,end2Start_y,color