簡介

蟻群算法(ant colony optimization, ACO)，又稱螞蟻算法，是一種用來在圖中尋找優化路徑的機率型算法。它由Marco Dorigo于1992年在他的博士論文中提出，其靈感來源于螞蟻在尋找食物過程中發現路徑的行為。蟻群算法是一種模擬進化算法，初步的研究表明該算法具有許多優良的性質。針對PID控制器參數優化設計問題，將蟻群算法設計的結果與遺傳算法設計的結果進行了比較，數值仿真結果表明，蟻群算法具有一種新的模擬進化優化方法的有效性和應用價值。
定義

各個螞蟻在沒有事先告訴他們食物在什么地方的前提下開始尋找食物。當一只找到食物以后，它會向環境釋放一種揮發性分泌物pheromone (稱為信息素,該物質隨著時間的推移會逐漸揮發消失，信息素濃度的大小表征路徑的遠近)來實現的，吸引其他的螞蟻過來，這樣越來越多的螞蟻會找到食物。有些螞蟻并沒有像其它螞蟻一樣總重復同樣的路，他們會另辟蹊徑，如果另開辟的道路比原來的其他道路更短，那么，漸漸地，更多的螞蟻被吸引到這條較短的路上來。最后，經過一段時間運行，可能會出現一條最短的路徑被大多數螞蟻重復著。

解決的問題

三維地形中，給出起點和重點，找到其最優路徑。

作圖源碼：

from mpl_toolkits.mplot3d import proj3dfrom mpl_toolkits.mplot3d import Axes3Dimport numpy as npheight3d = np.array([[2000,1400,800,650,500,750,1000,950,900,800,700,900,1100,1050,1000,1150,1300,1250,1200,1350,1500],          [1100,900,700,625,550,825,1100,1150,1200,925,650,750,850,950,1050,1175,1300,1350,1400,1425,1450],          [200,400,600,600,600,900,1200,1350,1500,1050,600,600,600,850,1100,1200,1300,1450,1600,1500,1400],          [450,500,550,575,600,725,850,875,900,750,600,600,600,725,850,900,950,1150,1350,1400,1450],          [700,600,500,550,600,550,500,400,300,450,600,600,600,600,600,600,600,850,1100,1300,1500],          [500,525,550,575,600,575,550,450,350,475,600,650,700,650,600,600,600,725,850,1150,1450],          [300,450,600,600,600,600,600,500,400,500,600,700,800,700,600,600,600,600,600,1000,1400],          [550,525,500,550,600,875,1150,900,650,725,800,700,600,875,1150,1175,1200,975,750,875,1000],          [800,600,400,500,600,1150,1700,1300,900,950,1000,700,400,1050,1700,1750,1800,1350,900,750,600],          [650,600,550,625,700,1175,1650,1275,900,1100,1300,1275,1250,1475,1700,1525,1350,1200,1050,950,850],          [500,600,700,750,800,1200,1600,1250,900,1250,1600,1850,2100,1900,1700,1300,900,1050,1200,1150,1100],          [400,375,350,600,850,1200,1550,1250,950,1225,1500,1750,2000,1950,1900,1475,1050,975,900,1175,1450],          [300,150,0,450,900,1200,1500,1250,1000,1200,1400,1650,1900,2000,2100,1650,1200,900,600,1200,1800],          [600,575,550,750,950,1275,1600,1450,1300,1300,1300,1525,1750,1625,1500,1450,1400,1125,850,1200,1550],          [900,1000,1100,1050,1000,1350,1700,1650,1600,1400,1200,1400,1600,1250,900,1250,1600,1350,1100,1200,1300],          [750,850,950,900,850,1000,1150,1175,1200,1300,1400,1325,1250,1125,1000,1150,1300,1075,850,975,1100],          [600,700,800,750,700,650,600,700,800,1200,1600,1250,900,1000,1100,1050,1000,800,600,750,900],          [750,775,800,725,650,700,750,775,800,1000,1200,1025,850,975,1100,950,800,900,1000,1050,1100],          [900,850,800,700,600,750,900,850,800,800,800,800,800,950,1100,850,600,1000,1400,1350,1300],          [750,800,850,850,850,850,850,825,800,750,700,775,850,1000,1150,875,600,925,1250,1100,950],          [600,750,900,1000,1100,950,800,800,800,700,600,750,900,1050,1200,900,600,850,1100,850,600]])fig = figure()ax = Axes3D(fig)X = np.arange(21)Y = np.arange(21)X, Y = np.meshgrid(X, Y)Z = -20*np.exp(-0.2*np.sqrt(np.sqrt(((X-10)**2+(Y-10)**2)/2)))+20+np.e-np.exp((np.cos(2*np.pi*X)+np.sin(2*np.pi*Y))/2)ax.plot_surface(X, Y, Z, rstride=1, cstride=1, cmap='cool')ax.set_xlabel('X axis')ax.set_ylabel('Y axis')ax.set_zlabel('Z')ax.set_title('3D map')point0 = [0,9,Z[0][9]] point1 = [20,7,Z[20][7]]ax.plot([point0[0]],[point0[1]],[point0[2]],'r',marker = u'o',markersize = 15)ax.plot([point1[0]],[point1[1]],[point1[2]],'r',marker = u'o',markersize = 15)x0,y0,_ = proj3d.proj_transform(point0[0],point0[1],point0[2], ax.get_proj())x1,y1,_ = proj3d.proj_transform(point1[0],point1[1],point1[2], ax.get_proj())label = pylab.annotate(  "start",   xy = (x0, y0), xytext = (-20, 20),  textcoords = 'offset points', ha = 'right', va = 'bottom',  bbox = dict(boxstyle = 'round,pad=0.5', fc = 'yellow', alpha = 1),  arrowprops = dict(arrowstyle = '->', connectionstyle = 'arc3,rad=0'),fontsize=15)label2 = pylab.annotate(  "end",   xy = (x1, y1), xytext = (-20, 20),  textcoords = 'offset points', ha = 'right', va = 'bottom',  bbox = dict(boxstyle = 'round,pad=0.5', fc = 'yellow', alpha = 1),  arrowprops = dict(arrowstyle = '->', connectionstyle = 'arc3,rad=0'),fontsize=15)def update_position(e):  x2, y2, _ = proj3d.proj_transform(point0[0],point0[1],point0[2],ax.get_proj())  label.xy = x2,y2  label.update_positions(fig.canvas.renderer)  x1,y1,_ = proj3d.proj_transform(point1[0],point1[1],point1[2],ax.get_proj())  label2.xy = x1,y1  label2.update_positions(fig.canvas.renderer)  fig.canvas.draw()fig.canvas.mpl_connect('button_release_event', update_position)