Python编程实现蚁群算法详解

简介

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

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

解决的问题

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

作图源码:

from mpl_toolkits.mplot3d import proj3d
from mpl_toolkits.mplot3d import Axes3D
import 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连接路径上释放的信息素浓度之和。

蚂蚁释放信息素的模型

程序代码:

import numpy as np
import matplotlib.pyplot as plt
%pylab
coordinates = 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 distmat
distmat = getdistmat(coordinates)
numant = 40 #蚂蚁个数
numcity = coordinates.shape[0] #城市个数
alpha = 1  #信息素重要程度因子
beta = 5  #启发函数重要程度因子
rho = 0.1  #信息素的挥发速度
Q = 1
iter = 0
itermax = 250
etatable = 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()

总结

以上就是本文关于Python编程实现蚁群算法详解的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站:python实现图片处理和特征提取详解、python图像常规操作、python先序遍历二叉树问题等,有什么问题可以随时留言,小编会及时回复大家的。感谢朋友们对本站的支持!

(0)

相关推荐

  • Python实现破解猜数游戏算法示例

    本文实例讲述了Python实现破解猜数游戏算法.分享给大家供大家参考,具体如下: QQ群里的聊天机器人会发起猜数小游戏. 玩法如下: 1. 用户发 #猜数    到群里 2. 机器人响应: 猜数已经开始, 范围是1-10000之间的某个数 3. 你发送 #猜数[123] 到群里 4. 机器人响应: 大了或者小了, 或者恭喜你猜中了 5. 你根据刚才猜的123, 和返回, 猜一个更小或更大的数, 发送 #猜数[111] , 即返回第2步 那么最好的猜测方法肯定是找居中的数了, 由于心算耗时, 所以

  • Python实现曲线点抽稀算法的示例

    本文介绍了Python实现曲线点抽稀算法的示例,分享给大家,具体如下: 目录 何为抽稀 道格拉斯-普克(Douglas-Peuker)算法 垂距限值法 最后 正文 何为抽稀 在处理矢量化数据时,记录中往往会有很多重复数据,对进一步数据处理带来诸多不便.多余的数据一方面浪费了较多的存储空间,另一方面造成所要表达的图形不光滑或不符合标准.因此要通过某种规则,在保证矢量曲线形状不变的情况下, 最大限度地减少数据点个数,这个过程称为抽稀. 通俗的讲就是对曲线进行采样简化,即在曲线上取有限个点,将其变为折

  • Python数据结构与算法之列表(链表,linked list)简单实现

    Python 中的 list 并不是我们传统(计算机科学)意义上的列表,这也是其 append 操作会比 insert 操作效率高的原因.传统列表--通常也叫作链表(linked list)--通常是由一系列节点(node)来实现的,其每一个节点(尾节点除外)都持有一个指向下一个节点的引用. 其简单实现: class Node: def __init__(value, next=None): self.value = value self.next = next 接下来,我们就可使用链表的结构来

  • python实现二分查找算法

    二分查找算法:简单的说,就是将一个数组先排序好,比如按照从小到大的顺序排列好,当给定一个数据,比如target,查找target在数组中的位置时,可以先找到数组中间的数array[middle]和target进行比较,当它比target小时,那么target一定是在数组的右边,反之,则target在数组的左边,比如它比target小,则下次就可以只比较[middle+1, end]的数,继续使用二分法,将它一分为二,直到找到target这个数返回或者数组全部遍历完成(target不在数组中) 优

  • Python计算斗牛游戏概率算法实例分析

    本文实例讲述了Python计算斗牛游戏概率算法.分享给大家供大家参考,具体如下: 过年回家,都会约上亲朋好友聚聚会,会上经常会打麻将,斗地主,斗牛.在这些游戏中,斗牛是最受欢迎的,因为可以很多人一起玩,而且没有技术含量,都是看运气(专业术语是概率). 斗牛的玩法是: 1. 把牌中的JQK都拿出来 2. 每个人发5张牌 3. 如果5张牌中任意三张加在一起是10的 倍数,就是有牛.剩下两张牌的和的10的余数就是牛数. 牌的大小: 4条 > 3条 > 牛十 > 牛九 > -- >

  • Python基于分水岭算法解决走迷宫游戏示例

    本文实例讲述了Python基于分水岭算法解决走迷宫游戏.分享给大家供大家参考,具体如下: #Solving maze with morphological transformation """ usage:Solving maze with morphological transformation needed module:cv2/numpy/sys ref: 1.http://www.mazegenerator.net/ 2.http://blog.leanote.com

  • Python算法输出1-9数组形成的结果为100的所有运算式

    问题: 编写一个在1,2,-,9(顺序不能变)数字之间插入+或-或什么都不插入,使得计算结果总是100的程序,并输出所有的可能性.例如:1 + 2 + 34–5 + 67–8 + 9 = 100. from functools import reduce operator = { 1: '+', 2: '-', 0: '' } base = ['1', '2', '3', '4', '5', '6', '7', '8', '9'] def isHundred(num): #转化为8位3进制数,得

  • 遗传算法之Python实现代码

    写在前面 之前的文章中已经讲过了遗传算法的基本流程,并且用MATLAB实现过一遍了.这一篇文章主要面对的人群是看过了我之前的文章,因此我就不再赘述遗传算法是什么以及基本的内容了,假设大家已经知道我是怎么写遗传算法的了. Python的遗传算法主函数 我的思想是,创建一个染色体的类,其中包括了两个变量:染色体chrom与适应度fitness.因此我们就可以通过直接建立对象来作为种群中的个体. #染色体的类 class Chrom: chrom = [] fitness = 0 def showCh

  • Python编程实现蚁群算法详解

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

  • Python编程实现粒子群算法(PSO)详解

    1 原理 粒子群算法是群智能一种,是基于对鸟群觅食行为的研究和模拟而来的.假设在鸟群觅食范围,只在一个地方有食物,所有鸟儿看不到食物(不知道食物的具体位置),但是能闻到食物的味道(能知道食物距离自己位置).最好的策略就是结合自己的经验在距离鸟群中距离食物最近的区域搜索. 利用粒子群算法解决实际问题本质上就是利用粒子群算法求解函数的最值.因此需要事先把实际问题抽象为一个数学函数,称之为适应度函数.在粒子群算法中,每只鸟都可以看成是问题的一个解,这里我们通常把鸟称之为粒子,每个粒子都拥有: 位置,可

  • python编程通过蒙特卡洛法计算定积分详解

    想当初,考研的时候要是知道有这么个好东西,计算定积分...开玩笑,那时候计算定积分根本没有这么简单的.但这确实给我打开了一种思路,用编程语言去解决更多更复杂的数学问题.下面进入正题. 如上图所示,计算区间[a b]上f(x)的积分即求曲线与X轴围成红色区域的面积.下面使用蒙特卡洛法计算区间[2 3]上的定积分:∫(x2+4*x*sin(x))dx # -*- coding: utf-8 -*- import numpy as np import matplotlib.pyplot as plt

  • python实现决策树C4.5算法详解(在ID3基础上改进)

    一.概论 C4.5主要是在ID3的基础上改进,ID3选择(属性)树节点是选择信息增益值最大的属性作为节点.而C4.5引入了新概念"信息增益率",C4.5是选择信息增益率最大的属性作为树节点. 二.信息增益 以上公式是求信息增益率(ID3的知识点) 三.信息增益率 信息增益率是在求出信息增益值在除以. 例如下面公式为求属性为"outlook"的值: 四.C4.5的完整代码 from numpy import * from scipy import * from mat

  • python中实现k-means聚类算法详解

    算法优缺点: 优点:容易实现 缺点:可能收敛到局部最小值,在大规模数据集上收敛较慢 使用数据类型:数值型数据 算法思想 k-means算法实际上就是通过计算不同样本间的距离来判断他们的相近关系的,相近的就会放到同一个类别中去. 1.首先我们需要选择一个k值,也就是我们希望把数据分成多少类,这里k值的选择对结果的影响很大,Ng的课说的选择方法有两种一种是elbow method,简单的说就是根据聚类的结果和k的函数关系判断k为多少的时候效果最好.另一种则是根据具体的需求确定,比如说进行衬衫尺寸的聚

  • python连接mongodb集群方法详解

    简单的测试用例 #!/usr/bin/python # -*- coding: UTF-8 -*- import time from pymongo import MongoClient # 连接单机 # single mongo # c = MongoClient(host="192.168.89.151", port=27017) # 连接集群 c = MongoClient('mongodb://192.168.89.151,192.168.89.152,192.168.89.1

  • Python编程之序列操作实例详解

    本文实例讲述了Python编程之序列操作.分享给大家供大家参考,具体如下: #coding=utf8 ''''' 序列类型有着相同的访问模式:它的每一个元素可以通过指定一个偏移量的方式得到. 可以通过切片操作一次获得多个元素. 序列的下标偏移量是从0开始到总元素数减一结束. 标准类型操作符一般都能试用与所有的序列类型. 序列类型操作符: --------------------------------------------------------------------------- 序列操作

  • Python编程之多态用法实例详解

    本文实例讲述了Python编程之多态用法.分享给大家供大家参考.具体分析如下: 什么是多态?顾名思义,多态就是多种表现形态的意思.它是一种机制.一种能力,而非某个关键字.它在类的继承中得以实现,在类的方法调用中得以体现.多态意味着变量并不知道引用的对象是什么,根据引用对象的不同表现不同的行为方式. 我们先看一个简单的例子,运算符多态: a=34 b=57 print(a+b) a="世界" b="你好" print(a+b) 我们不知道+法运算符左右两个变量是什么类

  • Python编程之列表操作实例详解【创建、使用、更新、删除】

    本文实例讲述了Python列表操作.分享给大家供大家参考,具体如下: #coding=utf8 ''''' 列表类型也是序列式的数据类型, 可以通过下标或者切片操作来访问某一个或者某一块连续的元素. 列表不仅可以包含Python的标准类型, 而且可以用用户定义的对象作为自己的元素. 列表可以包含不同类型的对象, 列表可以执行pop.empt.sort.reverse等操作. 列表可以添加或者减少元素, 还可以与其他列表结合或者把一个列表拆分成几个. 可以对一个元素或者多个元素执行insert.u

  • python决策树之C4.5算法详解

    本文为大家分享了决策树之C4.5算法,供大家参考,具体内容如下 1. C4.5算法简介   C4.5算法是用于生成决策树的一种经典算法,是ID3算法的一种延伸和优化.C4.5算法对ID3算法主要做了一下几点改进:   (1)通过信息增益率选择分裂属性,克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不足:   (2)能够处理离散型和连续型的属性类型,即将连续型的属性进行离散化处理:   (3)构造决策树之后进行剪枝操作:   (4)能够处理具有缺失属性值的训练数据. 2

随机推荐

其他