Python编程实现蚁群算法详解

简介

蚁群算法(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)