简介

蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。

定义

各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种挥发性分泌物pheromone (称为信息素,该物质随着时间的推移会逐渐挥发消失，信息素浓度的大小表征路径的远近)来实现的，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物。有些蚂蚁并没有像其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果另开辟的道路比原来的其他道路更短，那么，渐渐地，更多的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复着。

解决的问题

三维地形中，给出起点和重点，找到其最优路径。

作图源码：

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051from mpl_toolkits.mplot3d import proj3dfrom mpl_toolkits.mplot3d import Axes3Dimport numpy as np height3d = 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)

基本原理

蚂蚁k根据各个城市间链接路径上的信息素浓度决定其下一个访问城市，设Pkij(t)表示t时刻蚂蚁k从城市i转移到矩阵j的概率，其计算公式为

计算完城市间的转移概率后，采用与遗传算法中一样的轮盘赌方法选择下一个待访问的城市。

当所有的蚂蚁完成一次循环后，各个城市间链接路径上的信息素浓度需进行更新，计算公式为

其中，Δτkij表示第k只蚂蚁在城市i与城市j连接路径上释放的信息素浓度；Δτij表示所有蚂蚁在城市i与城市j连接路径上释放的信息素浓度之和。

蚂蚁释放信息素的模型 

程序代码：

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117import numpy as npimport matplotlib.pyplot as plt%pylabcoordinates = np.array([[565.0,575.0],[25.0,185.0],[345.0,750.0],[945.0,685.0],[845.0,655.0],            [880.0,660.0],[25.0,230.0],[525.0,1000.0],[580.0,1175.0],[650.0,1130.0],            [1605.0,620.0],[1220.0,580.0],[1465.0,200.0],[1530.0, 5.0],[845.0,680.0],            [725.0,370.0],[145.0,665.0],[415.0,635.0],[510.0,875.0],[560.0,365.0],            [300.0,465.0],[520.0,585.0],[480.0,415.0],[835.0,625.0],[975.0,580.0],            [1215.0,245.0],[1320.0,315.0],[1250.0,400.0],[660.0,180.0],[410.0,250.0],            [420.0,555.0],[575.0,665.0],[1150.0,1160.0],[700.0,580.0],[685.0,595.0],            [685.0,610.0],[770.0,610.0],[795.0,645.0],[720.0,635.0],[760.0,650.0],            [475.0,960.0],[95.0,260.0],[875.0,920.0],[700.0,500.0],[555.0,815.0],            [830.0,485.0],[1170.0, 65.0],[830.0,610.0],[605.0,625.0],[595.0,360.0],            [1340.0,725.0],[1740.0,245.0]])def getdistmat(coordinates):  num = coordinates.shape[0]  distmat = np.zeros((52,52))  for i in range(num):    for j in range(i,num):      distmat[i][j] = distmat[j][i]=np.linalg.norm(coordinates[i]-coordinates[j])  return distmatdistmat = getdistmat(coordinates)numant = 40 #蚂蚁个数numcity = coordinates.shape[0] #城市个数alpha = 1  #信息素重要程度因子beta = 5  #启发函数重要程度因子rho = 0.1  #信息素的挥发速度Q = 1iter = 0itermax = 250etatable = 1.0/(distmat+np.diag([1e10]*numcity)) #启发函数矩阵，表示蚂蚁从城市i转移到矩阵j的期望程度pheromonetable = np.ones((numcity,numcity)) # 信息素矩阵pathtable = np.zeros((numant,numcity)).astype(int) #路径记录表distmat = getdistmat(coordinates) #城市的距离矩阵lengthaver = np.zeros(itermax) #各代路径的平均长度lengthbest = np.zeros(itermax) #各代及其之前遇到的最佳路径长度pathbest = np.zeros((itermax,numcity)) # 各代及其之前遇到的最佳路径长度while iter <itermax:  # 随机产生各个蚂蚁的起点城市  if numant <= numcity:#城市数比蚂蚁数多    pathtable[:,0] = np.random.permutation(range(0,numcity))[:numant]  else: #蚂蚁数比城市数多，需要补足    pathtable[:numcity,0] = np.random.permutation(range(0,numcity))[:]    pathtable[numcity:,0] = np.random.permutation(range(0,numcity))[:numant-numcity]  length = np.zeros(numant) #计算各个蚂蚁的路径距离  for i in range(numant):    visiting = pathtable[i,0] # 当前所在的城市    #visited = set() #已访问过的城市，防止重复    #visited.add(visiting) #增加元素    unvisited = set(range(numcity))#未访问的城市    unvisited.remove(visiting) #删除元素    for j in range(1,numcity):#循环numcity-1次，访问剩余的numcity-1个城市      #每次用轮盘法选择下一个要访问的城市      listunvisited = list(unvisited)      probtrans = np.zeros(len(listunvisited))      for k in range(len(listunvisited)):        probtrans[k] = np.power(pheromonetable[visiting][listunvisited[k]],alpha)\            *np.power(etatable[visiting][listunvisited[k]],alpha)      cumsumprobtrans = (probtrans/sum(probtrans)).cumsum()      cumsumprobtrans -= np.random.rand()      k = listunvisited[find(cumsumprobtrans>0)[0]] #下一个要访问的城市      pathtable[i,j] = k      unvisited.remove(k)      #visited.add(k)      length[i] += distmat[visiting][k]      visiting = k    length[i] += distmat[visiting][pathtable[i,0]] #蚂蚁的路径距离包括最后一个城市和第一个城市的距离  #print length  # 包含所有蚂蚁的一个迭代结束后，统计本次迭代的若干统计参数  lengthaver[iter] = length.mean()  if iter == 0:    lengthbest[iter] = length.min()    pathbest[iter] = pathtable[length.argmin()].copy()    else:    if length.min() >lengthbest[iter-1]:      lengthbest[iter] = lengthbest[iter-1]      pathbest[iter] = pathbest[iter-1].copy()    else:      lengthbest[iter] = length.min()      pathbest[iter] = pathtable[length.argmin()].copy()   # 更新信息素  changepheromonetable = np.zeros((numcity,numcity))  for i in range(numant):    for j in range(numcity-1):      changepheromonetable[pathtable[i,j]][pathtable[i,j+1]] += Q/distmat[pathtable[i,j]][pathtable[i,j+1]]    changepheromonetable[pathtable[i,j+1]][pathtable[i,0]] += Q/distmat[pathtable[i,j+1]][pathtable[i,0]]  pheromonetable = (1-rho)*pheromonetable + changepheromonetable  iter += 1 #迭代次数指示器+1  #观察程序执行进度，该功能是非必须的  if (iter-1)%20==0:    print iter-1# 做出平均路径长度和最优路径长度   fig,axes = plt.subplots(nrows=2,ncols=1,figsize=(12,10))axes[0].plot(lengthaver,'k',marker = u'')axes[0].set_title('Average Length')axes[0].set_xlabel(u'iteration')axes[1].plot(lengthbest,'k',marker = u'')axes[1].set_title('Best Length')axes[1].set_xlabel(u'iteration')fig.savefig('Average_Best.png',dpi=500,bbox_inches='tight')plt.close()#作出找到的最优路径图bestpath = pathbest[-1]plt.plot(coordinates[:,0],coordinates[:,1],'r.',marker=u'$\cdot$')plt.xlim([-100,2000])plt.ylim([-100,1500])for i in range(numcity-1):#  m,n = bestpath[i],bestpath[i+1]  print m,n  plt.plot([coordinates[m][0],coordinates[n][0]],[coordinates[m][1],coordinates[n][1]],'k')plt.plot([coordinates[bestpath[0]][0],coordinates[n][0]],[coordinates[bestpath[0]][1],coordinates[n][1]],'b')ax=plt.gca()ax.set_title("Best Path")ax.set_xlabel('X axis')ax.set_ylabel('Y_axis')plt.savefig('Best Path.png',dpi=500,bbox_inches='tight')plt.close()

概念：蚁群算法(ant colony optimization,ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法.它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为.蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值

其原理：为什么小小的蚂蚁能够找到食物?他们具有智能么?设想,如果我们要为蚂蚁设计一个人工智能的程序,那么这个程序要多么复杂呢?首先,你要让蚂蚁能够避开障碍物,就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物,其次,要让蚂蚁找到食物,就需要让他们遍历空间上的所有点；再次,如果要让蚂蚁找到最短的路径,那么需要计算所有可能的路径并且比较它们的大小,而且更重要的是,你要小心翼翼的编程,因为程序的错误也许会让你前功尽弃.这是多么不可思议的程序!太复杂了,恐怕没人能够完成这样繁琐冗余的程序

应用范围：蚂蚁观察到的范围是一个方格世界,蚂蚁有一个参数为速度半径（一般是3）,那么它能观察到的范围就是3*3个方格世界,并且能移动的距离也在这个范围之内

引申：跟着蚂蚁的踪迹,你找到了什么?通过上面的原理叙述和实际操作,我们不难发现蚂蚁之所以具有智能行为,完全归功于它的简单行为规则,而这些规则综合起来具有下面两个方面的特点：1、多样性 2、正反馈 多样性保证了蚂蚁在觅食的时候不置走进死胡同而无限循环,正反馈机制则保证了相对优良的信息能够被保存下来.我们可以把多样性看成是一种创造能力,而正反馈是一种学习强化能力.正反馈的力量也可以比喻成权威的意见,而多样性是打破权威体现的创造性,正是这两点小心翼翼的巧妙结合才使得智能行为涌现出来了.引申来讲,大自然的进化,社会的进步、人类的创新实际上都离不开这两样东西,多样性保证了系统的创新能力,正反馈保证了优良特性能够得到强化,两者要恰到好处的结合.如果多样性过剩,也就是系统过于活跃,这相当于蚂蚁会过多的随机运动,它就会陷入混沌状态；而相反,多样性不够,正反馈机制过强,那么系统就好比一潭死水.这在蚁群中来讲就表现为,蚂蚁的行为过于僵硬,当环境变化了,蚂蚁群仍然不能适当的调整.既然复杂性、智能行为是根据底层规则涌现的,既然底层规则具有多样性和正反馈特点,那么也许你会问这些规则是哪里来的?多样性和正反馈又是哪里来的?我本人的意见：规则来源于大自然的进化.而大自然的进化根据刚才讲的也体现为多样性和正反馈的巧妙结合.而这样的巧妙结合又是为什么呢?为什么在你眼前呈现的世界是如此栩栩如生呢?答案在于环境造就了这一切,之所以你看到栩栩如生的世界,是因为那些不能够适应环境的多样性与正反馈的结合都已经死掉了,被环境淘汰了!蚁群算法的实现 下面的程序开始运行之后,蚂蚁们开始从窝里出动了,寻找食物；他们会顺着屏幕爬满整个画面,直到找到食物再返回窝.其中,‘F’点表示食物,‘H’表示窝,白色块表示障碍物,‘+’就是蚂蚁了.

蚁群算法java实现以及TSP问题蚁群算法求解

蚁群算法原理与应用讲解

蚁群算法原理与应用1 -自然计算与群体智能

1、蚁群算法(Ant Clony Optimization,ACO)是一种群智能算法，它是由一群无智能或有轻微智能的个体（Agent）通过相互协作而表现出智能行为，从而为求解复杂问题提供了一个新的可能性。

2、是一种仿生学的算法，是由自然界中蚂蚁觅食的行为而启发。（artificial ants；双桥实验）

3、运作机理：当一定路径上通过的蚂蚁越来越多时，其留下的信息素轨迹也越来越多，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度，而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制。

4、蚁群算法欧化过程中的两个重要原则：

     a、蚂蚁在众多路径中转移路线的选择规则。

     b、全局化信息素更新规则。信息素更新的实质就是人工蚂蚁根据真实蚂蚁在访问过的边上留下的信息素和蒸发的信息素来模拟真实信息素数量的变化，从而使得越好的解得到越多的增强。这就形成了一种自催化强化学习(Autocatalytic Reinforcement Learning)的正反馈机制。

1、描述：蚂蚁数量m；城市之间的信息素矩阵pheromone；每次迭代的m个蚂蚁的最短路径    BestLength；最佳路径BestTour。                                                                                                                                     每只蚂蚁都有 ：禁忌表(Tabu)存储已访问过的城市，允许访问的城市表(Allowed)存储还可以访问的城市，矩阵（ Delta ）来存储它在一个循环（或者迭代）中给所经过的路径释放的信息素。

2、 状态转移概率 ：在搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。在t时刻蚂蚁k由元素（城市）i转移到元素（城市）j的状态转移概率：

τij (t) ：时刻路径(i, j)上的信息量。ηij=1/dij ：启发函数。

α为信息启发式因子 ，表示轨迹的相对重要性，反映了蚂蚁在运动过程中积累的信息在蚂蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其它蚂蚁经过的路径，蚂蚁之间的协作性越强；

β为期望启发式因子 ，表示能见度的相对重要性，反映蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度，其值越大，则该状态状态转移概率越接近于贪心规则；

3、 息素更新规则 ：

ρ表示信息素挥发系数；Δτij(t)表示本次循环中路径(i, j)上的信息素增量，初始时刻Δτij(t) =0。

4、三种信息增量计算方法：

区别：第一种利用了全局信息，在走一圈后更新。二、三中都利用的是局部信息。通常使用第一种。

5、TSP中流程图

---