一 引言
蚁群算法(ant colony
optimization，ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。它由Marco
Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法。初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。蚁群算法是一种求解组合最优化问题的新型通用启发式方法，该方法具有正反馈、分布式计算和富于建设性的贪婪启发式搜索的特点。正因为蚁群算法有这些优点，很多研究者都在致力研究和改过它，本文的目的正是为了介绍蚁群算法，学习如何编写蚁群算法。
二 蚁群算法的介绍
昆虫世界中，蚂蚁的组成是一种群居的世袭大家庭，我们称之为蚁群。蚂蚁分为世袭制的蚁王(后)和工蚁两种，它们具有高度组织的社会性，彼此沟通不仅可以借助触觉和视觉的联系，在大规模的协调行动中还可以借助外激素(有些书称信息素)之类的信息介质。
首先我们要理解蚂蚁是如何觅食的，蚂蚁平时在巢穴附近作无规则行走，一量发现食物并不立即进食而是将之搬回蚁穴与其它蚂蚁分享，在食物小时则独自搬回蚁穴，否则就回蚁穴搬兵，一路上会留下外激素，食物越大外激素的浓度就越大，越能吸引其它的蚂蚁过去一起搬去食物，这样最终就能将食物全部搬回蚁穴。这个过程用程序实现看似非常复杂，要编写一个“智能”的蚂蚁也看似不太可能，事实上每个蚂蚁只做了非常简单的工作：检查某个范围内有无食物，并逐渐向外激素浓的方向运动。简而言之，蚁群运动无非是同时反复执行多个简单规则而已。下面详细说明蚁群中的这些简单规则：
1、范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径(一般是3)，那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。
2、环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有外激素，外激素有两种，一种是找到食物的蚂蚁洒下的食物外激素，一种是找到窝的蚂蚁洒下的窝的外激素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让外激素消失。
3、觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有外激素，并且比较在能感知的范围内哪一点的外激素最多，这样，它就朝外激素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往外激素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的外激素做出反应，而对食物外激素没反应。
4、移动规则：每只蚂蚁都朝向外激素最多的方向移，并且，当周围没有外激素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。
5、避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有外激素指引的话，它会按照觅食的规则行为。
7、播撒外激素规则：每只蚂蚁在刚找到食物或者窝的时候撒发的外激素最多，并随着它走远的距离，播撒的外激素越来越少。
根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过外激素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒外激素，当其它的蚂蚁经过它附近的时候，就会感觉到外激素的存在，进而根据外激素的指引找到了食物。成功的觅食算法正是最小化搜索食物的时间。
这种优化过程的本质在于：
选择机制：信息素越多的路径，被选择的概率越大。
更新机制：路径上面的信息素会随蚂蚁的经过而增长，而且同时也随时间的推移逐渐挥发消失。
协调机制：蚂蚁间实际上是通过分泌物来互相通信、协同工作的。
蚁群算法正是充分利用了选择、更新和协调的优化机制，即通过个体之间的信息交流与相互协作最终找到最优解，使它具有很强的发现较优解的能力。
三 蚁群算法的实现
理解蚁群算法的实质之后写出一个简单蚁群算法也不是太困难，关键是实现以上介绍的几个规则，下面用JAVA简单讲述一下以上规则的实现。
1、蚂蚁：蚂蚁是蚁群中最小的单位，是所以简单规则应用的最小个体。
public class Ant
{
public
Square
SQUARE; //蚂蚁所在方格
public Food
CARRYING =
null; //所搬的食物数
public int
ID; //蚂蚁的编号
public
boolean HELPING =
false; //是否帮忙搬运食物
public void move(int turn)
{
//蚂蚁移动到下一个方格
}
}
2、范围：蚂蚁所在的方格应该包含附近的方格编号，所含食物数量，蚂蚁数量，外激素的浓度，以及坐标等信息。
public class Square
{ public Square
NE; //附近的8个方向的方格
public
Square N;
public
Square NW;
public
Square W;
public
Square SW;
public
Square S;
public
Square SE;
public
Square E;
public
LinkedList
ANTS; //本方格中包含的蚂蚁
public
Food
FOOD; //本方格中包含的食物数
public
Nest
NEST; //方格为蚁穴
public
Pheromone_1
PHEROMONE_1; //本方格中的外激素含量
public
int
X; //本方格的坐标
public
int Y;
private
World
WORLD; //所属的环境
public
boolean
WALL; //是否有障碍物
public
Square(int x, int y, World world)
{
FOOD
= null;
NEST
= null;
PHEROMONE_1
= null;
X
= x;
Y
= y;
WORLD
= world;
WALL
= false;
ANTS
= new LinkedList();
}
3、环境：环境是由多个方格组成的，是一个平面的，因此用一个方格的二维数组来表示是最合适不过的。
public class World
{
private
Square[][]
WORLD; //定义环境二维数组
private
int
WIDTH; //环境的长宽
private
int HEIGHT;
private
Pheromone_1List
P1LIST; //保存所有外激素的列表
public
World(Pheromone_1List p1list)
{
this.WIDTH
= Settings.WIDTH;
this.HEIGHT
= Settings.HEIGHT;
this.P1LIST
= p1list;
WORLD
= new Square[WIDTH][HEIGHT];
}
4、觅食规则，移动规则和避障规则：这三种规则全都跟蚂蚁的移动方向有关，并在移动前都要先计算周围方格的外激素浓度，选择外激素浓度最高的方格方向移动。
private Square chooseBestSquare()
{
Square[] square_list = {SQUARE.E, SQUARE.NE, SQUARE.N, SQUARE.NW,
SQUARE.W, SQUARE.SW, SQUARE.S, SQUARE.SE};
double
current_best_value = 0;
double
value = 0;
Square
square = SQUARE;
//
选择最好的方格
for(int
i=0;i
{
value
= calculateSquareValue(square_list[i]);//计算方格值
if(value
> current_best_value)
{
current_best_value
= value;
square
= square_list[i];
}
}
if(square.ANTS.size()
>= Settings.MAXIMUM_NUMBER_OF_ANTS)
{
return SQUARE;
}
return
square;
}
private double
calculateSquareValue(Square s)
{
double[]
thresholds = Settings.THRESHOLDS;
if(s==null
|| s.WALL) // 方格有障碍物
{
return
-100000;
}
//
计算方格中各项参数的值
return
s.getFood()*thresholds[0] //
食物
+
s.getPheromone_1() *
thresholds[1] //
外激素
}
5、播撒外激素规则：每只蚂蚁找到食物后会根据食物的数量播撒相应量的外激素，以便其它蚂蚁能够更快得找到这堆食物。
private void putPheromone_1(double
amount)
{
if(SQUARE.getPheromone_1()
< Settings.PHEROMONE_LIMIT)
SQUARE.addPheromone_1(amount);
}
从以上蚁群算法中各个要素的代码来看，实现蚁群算法并不难。每只蚂蚁并不是像我们想象的需要知道整个环境的信息，它们只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律。
四 蚁群算法的不足
本文实现的蚁群算法只是简单的大致模拟蚁群的觅食过程，真正的蚂蚁觅食过程远比这个复杂，比如增加蚂蚁搬运食物的距离和数量，蚂蚁在搬运食物发现更大的食物可能会丢弃原有食物，还可以增加蚂蚁搬运食物回蚁穴的最短路径的求解。同时需要注意的是，由于蚁群算法觅食的过程，蚁群算法可能会过早的收敛并陷入局部最优解。
JAVA实现蚁群算法
说明：信息素权重，路径权重和信息素蒸发率对最后的结果影响很大，需要微调。
目前发现2 / 5 /
0.5 能达到稍微让人满意的效果。本程序离完美的ACO还差很远，仅供参考。
本蚁群算法为AS算法。
用法：
1.new一个对象
ACOforTSP tsp = new
ACPforTSP(tsp数据文件名,迭代次数，蚂蚁数量，信息素权重，路径权重，信息素蒸发率);
2.用go()方法运行
tsp.go();
ACOforTSP.java
___________________________________________________________________
import java.io.File;
import static java.lang.Math.pow;
import static java.lang.Math.sqrt;
import static java.lang.Math.random;
import java.util.HashMap;
import java.io.FileReader;
import java.io.BufferedReader;
public class ACOforTSP {
//城市的距离表
private
double[][]
distance; //距离的倒数表
private
double[][] heuristic; //启发信息表
private
double[][] pheromone; //权重
private int
alpha, beta;
//迭代的次数
private int
iterationTimes;
//蚂蚁的数量
private int
numbersOfAnt;
//蒸发率
private
double rate;
ACOforTSP
(String file, int iterationTimes, int numbersOfAnt, int alpha, int
beta, double rate) {
//加载文件
this.initializeData(file);
//初始化参数
this.iterationTimes = iterationTimes;
//设置蚂蚁数量
this.numbersOfAnt = numbersOfAnt;
//设置权重
this.alpha = alpha;
this.beta = beta;
//设置蒸发率
this.rate = rate;
}
private void
initializeData(String filename) {
//定义内部类
class City {
int no;
double x;
double y;
City(int no, double x, double y) {
this.no = no;
this.x = x;

简介
蚁群算法(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先序遍历二叉树问题等，有什么问题可以随时留言，小编会及时回复大家的。感谢朋友们对本站的支持！
时间： 2017-11-10

1.蚁群算法简介

蚁群算法（Ant Clony Optimization， ACO）是一种群智能算法，它是由一群无智能或有轻微智能的个体（Agent）通过相互协作而表现出智能行为，从而为求解复杂问题提供了一个新的可能性。蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。

蚁群算法是一种仿生学算法，是由自然界中蚂蚁觅食的行为而启发的。在自然界中，蚂蚁觅食过程中，蚁群总能够按照寻找到一条从蚁巢和食物源的最优路径。图（1）显示了这样一个觅食的过程。


在图1（a）中，有一群蚂蚁，假如A是蚁巢，E是食物源（反之亦然）。这群蚂蚁将沿着蚁巢和食物源之间的直线路径行驶。假如在A和E之间突然出现了一个障碍物（图1（b）），那么，在B点（或D点）的蚂蚁将要做出决策，到底是向左行驶还是向右行驶？由于一开始路上没有前面蚂蚁留下的信息素（pheromone），蚂蚁朝着两个方向行进的概率是相等的。但是当有蚂蚁走过时，它将会在它行进的路上释放出信息素，并且这种信息素会以一定的速率散发掉。信息素是蚂蚁之间交流的工具之一。它后面的蚂蚁通过路上信息素的浓度，做出决策，往左还是往右。很明显，沿着短边的的路径上信息素将会越来越浓（图1（c）），从而吸引了越来越多的蚂蚁沿着这条路径行驶。

2.TSP问题描述

蚁群算法最早用来求解TSP问题，并且表现出了很大的优越性，因为它分布式特性，鲁棒性强并且容易与其它算法结合，但是同时也存在这收敛速度慢，容易陷入局部最优（local optimal）等缺点。

TSP问题（Travel Salesperson Problem，即旅行商问题或者称为中国邮递员问题），是一种NP-hard问题，此类问题用一般的算法是很大得到最优解的，所以一般需要借助一些启发式算法求解，例如遗传算法（GA），蚁群算法（ACO），微粒群算法（PSO）等等。

TSP问题可以分为两类，一类是对称TSP问题（Symmetric TSP），另一类是非对称问题（Asymmetric TSP）。所有的TSP问题都可以用一个图（Graph）来描述：

令V={C1,C2,…,Ci,…,Cn},i=1,2,…,n是所有城市的集合，Ci表示第i个城市，n为城市的数目；

E={(r,s):r,s∈V}是所有城市之间连接的集合；

C={Crs:r,s∈V}是所有城市之间连接的成本度量（一般为城市之间的距离）；

如果Crs=Csr，那么该TSP问题为对称的，否则为非对称的。

一个TSP问题可以表达为：

求解遍历图G=(V,E,C)，所有的节点一次并且回到起始节点，使得连接这些节点的路径成本最低。

3.蚁群算法原理

假如蚁群中所有蚂蚁的数量为m，所有城市之间的信息素用矩阵pheromone表示，最短路径为bestLength，最佳路径为bestTour。每只蚂蚁都有自己的内存，内存中用一个禁忌表（Tabu）来存储该蚂蚁已经访问过的城市，表示其在以后的搜索中将不能访问这些城市；还有用另外一个允许访问的城市表（Allowed）来存储它还可以访问的城市；另外还用一个矩阵（Delta）来存储它在一个循环（或者迭代）中给所经过的路径释放的信息素；还有另外一些数据，例如一些控制参数(α，β，ρ，Q)，该蚂蚁行走完全程的总成本或距离（tourLength），等等。假定算法总共运行MAX_GEN次，运行时间为t。

蚁群算法计算过程如下：

（1）初始化

设t=0，初始化bestLength为一个非常大的数（正无穷），bestTour为空。初始化所有的蚂蚁的Delt矩阵所有元素初始化为0，Tabu表清空，Allowed表中加入所有的城市节点。随机选择它们的起始位置（也可以人工指定）。在Tabu中加入起始节点，Allowed中去掉该起始节点。

（2）为每只蚂蚁选择下一个节点。

为每只蚂蚁选择下一个节点，该节点只能从Allowed中以某种概率（公式1）搜索到，每搜到一个，就将该节点加入到Tabu中，并且从Allowed中删除该节点。该过程重复n-1次，直到所有的城市都遍历过一次。遍历完所有节点后，将起始节点加入到Tabu中。此时Tabu表元素数量为n+1（n为城市数量），Allowed元素数量为0。接下来按照（公式2）计算每个蚂蚁的Delta矩阵值。最后计算最佳路径，比较每个蚂蚁的路径成本，然后和bestLength比较，若它的路径成本比bestLength小，则将该值赋予bestLength，并且将其Tabu赋予BestTour。


（公式1）


（公式2）


（公式3）

其中pij(t)表示选择城市j的概率，k表示第k个蚂蚁，τij (t)表示城市i,j在第t时刻的信息素浓度，ηij表示从城市i到城市j的可见度，ηij=1/dij，dij表示城市i,j之间的成本（或距离）。由此可见dij越小，ηij越大，也就是从城市i到j的可见性就越大。

Δτkij表示蚂蚁k在城市i与j之间留下的信息素。

Lk表示蚂蚁k经过一个循环（或迭代）锁经过路径的总成本（或距离），即tourLength,α,β,Q 均为控制参数。

（3）更新信息素矩阵

令t=t+nt，按照（公式3）更新信息素矩阵phermone。
（公式4）

τij(t+n)为t+n时刻城市i与j之间的信息素浓度。ρ为控制参数，Deltaij为城市i与j之间信息素经过一个迭代后的增量。并且有
（公式5）

其中Δτkij由公式计算得到。

（4）检查终止条件

如果达到最大代数MAX_GEN，算法终止，转到第（5）步；否则，重新初始化所有的蚂蚁的Delt矩阵所有元素初始化为0，Tabu表清空，Allowed表中加入所有的城市节点。随机选择它们的起始位置（也可以人工指定）。在Tabu中加入起始节点，Allowed中去掉该起始节点，重复执行（2），（3）,(4)步。

（5）输出最优值

4.算法流程图



5.java实现

在该java实现中我们选择使用tsplib上的数据att48，这是一个对称tsp问题，城市规模为48，其最优值为10628.其距离计算方法如图（2）所示：


图2 att48距离计算方法

实现中，使用了两个java类，一个Ant类，一个ACO类。

Ant类

package com.gbs.bean;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Random;
/**
 * 蚂蚁类
 * Cloneable这个类为克隆类，使用Object的clone()方法
 * @author gbs
 *
 */
public class Ant implements Cloneable{

    /**
     * Vector与ArrayList一样，也是通过数组实现的，不同的是它支持线程的同步，
     * 即某一时刻只有一个线程能够写Vector，避免多线程同时写而引起的不一致性，
     * 但实现同步需要很高的花费，因此，访问它比访问ArrayList慢。
     */
    private ArrayList<Integer> allowedCities;//允许访问的城市

    private ArrayList<Integer> tabu;//禁忌表，记录已经访问过的城市

    private int [][] distance;//距离矩阵

    private double[][] delta; //信息素变化矩阵

    private double alpha;

    private double beta;

    private int cityNum;//城市数量

    private int tourLength;//路径的长度

    private int firstCity; //起始城市

    private int currentCity; //当前城市

    public Ant(int cityNum) {
        this.cityNum = cityNum;
        this.tourLength = 0;
    }

    public Ant() {
        this.cityNum = 30;
        this.tourLength = 0;
    }

    /**
     * 初始化蚂蚁，并为蚂蚁随机选择第一个城市
     * @param distance
     * @param a
     * @param b
     */
    public void init(int[][] distance,double a,double b) {
        this.alpha = a;
        this.beta = b;
        this.distance = distance;
        this.allowedCities = new ArrayList<Integer>();
        this.tabu = new ArrayList<Integer>();
        this.delta = new double[cityNum][cityNum];
        for(int i = 0;i < this.cityNum;i++) {
            Integer city = new Integer(i);
            this.allowedCities.add(city);
            for (int j = 0;j < this.cityNum;j++) {
                this.delta[i][j] = 0.d;
            }
        }

        Random random = new Random(System.currentTimeMillis());
        this.firstCity = random.nextInt(this.cityNum);

        for (Integer city:this.allowedCities) {
            if(city.intValue() == this.firstCity) {
                this.allowedCities.remove(city);
                this.tabu.add(city);
                break;
            }
        }

        this.currentCity = this.firstCity;
    }

    /**
     * 选择下一个城市
     * @param pheromone 信息素矩阵
     */
    public void selectNextCity(double[][] pheromone) {
        double[] p = new double[this.cityNum];//转移概率
        double sum = 0.d;//转移概率的分母
        for (Integer city : this.allowedCities) {
            sum += Math.pow(pheromone[this.currentCity][city.intValue()],
                    this.alpha)*Math.pow(1.d/this.distance[this.currentCity][city.intValue()], this.beta);
        }
        for (int i = 0; i < this.cityNum; i++) {
            boolean flag = false;
            for (Integer city : this.allowedCities) {
                if(i == city.intValue()) {
                     p[i] = (double) ((Math.pow(pheromone[this.currentCity][i], 
                             this.alpha)*Math.pow(1.d/this.distance[this.currentCity][i], this.beta))/sum);
                     flag = true;
                     break;
                }
            }
            if(!flag)
                p[i] = 0.d;
        }

        /**
         * 如果每次都直接选择最大概率的城市作为下一个城市，就会使算法过早收敛，
         * 最后停止搜索可能获得的仅仅是次优解，而使用轮盘赌可以提高算法的全局搜索能力，又不失局部搜索
         * 所以这里选择轮盘赌选择下一个城市。参考《计算智能》清华大学出版社
         */
        //轮盘赌选择下一个城市
         double sumSelect = 0.d;
         int selectCity = -1;
         Random random = new Random(System.currentTimeMillis());
         double selectP = random.nextDouble();
         while(selectP == 0.f) {
             selectP = random.nextDouble();
         }
         for(int i = 0;i < this.cityNum;i++) {
             sumSelect += p[i];
             if(sumSelect >= selectP) {
                 selectCity = i;
                //从允许选择的城市中去除select city
                 this.allowedCities.remove(Integer.valueOf(selectCity));
                //在禁忌表中添加select city
                 this.tabu.add(Integer.valueOf(selectCity));
                //将当前城市改为选择的城市
                 this.currentCity = selectCity;
                 break;
             }
         }
    }

    /**
     * 计算路径长度
     * @return
     */
    public int calculateTourLength() {
        int length = 0;

        for(int i = 0;i < this.tabu.size()-1;i++) {
            length += this.distance[this.tabu.get(i).intValue()][this.tabu.get(i+1).intValue()];
        }
        return length;
    }

    public ArrayList<Integer> getAllowedCities() {
        return allowedCities;
    }

    public void setAllowedCities(ArrayList<Integer> allowedCities) {
        this.allowedCities = allowedCities;
    }

    public ArrayList<Integer> getTabu() {
        return tabu;
    }

    public void setTabu(ArrayList<Integer> tabu) {
        this.tabu = tabu;
    }

    public int[][] getDistance() {
        return distance;
    }

    public void setDistance(int[][] distance) {
        this.distance = distance;
    }

    public double[][] getDelta() {
        return delta;
    }

    public void setDelta(double[][] delta) {
        this.delta = delta;
    }

    public double getAlpha() {
        return alpha;
    }

    public void setAlpha(double alpha) {
        this.alpha = alpha;
    }

    public double getBeta() {
        return beta;
    }

    public void setBeta(double beta) {
        this.beta = beta;
    }

    public int getCityNum() {
        return cityNum;
    }

    public void setCityNum(int cityNum) {
        this.cityNum = cityNum;
    }

    public int getTourLength() {
        return tourLength;
    }

    public void setTourLength(int tourLength) {
        this.tourLength = tourLength;
    }

    public int getFirstCity() {
        return firstCity;
    }

    public void setFirstCity(int firstCity) {
        this.firstCity = firstCity;
    }

    public int getCurrentCity() {
        return currentCity;
    }

    public void setCurrentCity(int currentCity) {
        this.currentCity = currentCity;
    }

    @Override
    public String toString() {
        return "Ant [allowedCities=" + allowedCities + ", tabu=" + tabu + ", distance=" + Arrays.toString(distance)
                + ", delta=" + Arrays.toString(delta) + ", alpha=" + alpha + ", beta=" + beta + ", cityNum=" + cityNum
                + ", tourLength=" + tourLength + ", firstCity=" + firstCity + ", currentCity=" + currentCity + "]";
    }

}

ACO类

package com.gbs.bean;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 * 蚁群算法类
 * @author gbs
 *
 */
public class ACO {

    private Ant[] ants; //蚂蚁
    private int antNum; //蚂蚁数量
    private int cityNum; //城市数量
    private int MAX_GEN; //运行代数
    private double[][] pheromone; //信息素矩阵
    private int[][] distance; //距离矩阵
    private int bestLength; //最佳长度
    private int[] bestTour; //最佳路径
    //三个参数
    private double alpha;
    private double beta;
    private double rho;

    public ACO() {

    }

    public ACO(int antNum, int cityNum, int mAX_GEN, double alpha, double beta, double rho) {
        this.antNum = antNum;
        this.cityNum = cityNum;
        this.MAX_GEN = mAX_GEN;
        this.alpha = alpha;
        this.beta = beta;
        this.rho = rho;
        this.ants = new Ant[this.antNum];
    }

    public void init(String path) {
        int []x;
        int []y;
        String buffer;
        BufferedReader br;
        try {
            br = new BufferedReader(new InputStreamReader(new FileInputStream(path)));
            this.distance = new int[this.cityNum][this.cityNum];
            x = new int[cityNum];  
            y = new int[cityNum];  
            //读取城市的坐标
            for (int i = 0; i < cityNum; i++) {  
                buffer = br.readLine();
                String[] str = buffer.split(" ");  
                x[i] = Integer.valueOf(str[1]);  
                y[i] = Integer.valueOf(str[2]);  
            } 
            /**
             * 计算距离矩阵 ，针对具体问题，距离计算方法也不一样，此处用的是att48作为案例，
             * 它有48个城市，距离计算方法为伪欧氏距离，最优值为10628
             */
            for(int i = 0;i < this.cityNum - 1;i++) {
                for(int j = i + 1;j < this.cityNum;j++) {
                    double rij = Math.sqrt(((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]))/10.0);
                    int tij = (int)Math.round(rij);
                    if(tij < rij)
                        tij++;
                    this.distance[i][j] = tij;
                    this.distance[j][i] = tij;
                }
            }
            this.distance[this.cityNum-1][this.cityNum-1] = 0;
            //初始化信息素矩阵
            this.pheromone=new double[this.cityNum][this.cityNum];
            for(int i = 0;i < this.cityNum;i++) {
                for(int j = 0;j < this.cityNum;j++) {
                    this.pheromone[i][j] = 0.1d;
                }
            }
            //初始化最优路径的长度
            this.bestLength=Integer.MAX_VALUE;
            //初始化最优路径
            this.bestTour=new int[this.cityNum+1];  
            //随机放置蚂蚁  
            for(int i = 0;i < this.antNum;i++){  
                this.ants[i]=new Ant(this.cityNum);  
                this.ants[i].init(this.distance, this.alpha, this.beta);  
            }  
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    /**
     * 更新信息素
     */
    private void updatePheromone() {
        //信息素挥发  
        for(int i = 0;i < this.cityNum;i++)  
            for(int j = 0;j < this.cityNum;j++)  
                this.pheromone[i][j] = this.pheromone[i][j] * (1 - this.rho);
        //信息素更新
        for(int i = 0;i < this.cityNum;i++) {
            for(int j = 0;j < this.cityNum;j++) {
                for(int k = 0;k < this.antNum;k++) {
                    this.pheromone[i][j] += this.ants[k].getDelta()[i][j];
                }
            }
        }
    }

    public void solve() {
        for (int g = 0; g < this.MAX_GEN; g++) {
            //每一只蚂蚁移动的过程
            for (int i = 0; i < this.antNum; i++) {
                for (int j = 0; j < this.cityNum; j++) {
                    this.ants[i].selectNextCity(this.pheromone);
                }
                this.ants[i].getTabu().add(this.ants[i].getFirstCity());
                //计算蚂蚁获得的路径长度  
                this.ants[i].setTourLength(this.ants[i].calculateTourLength());  
                if(this.ants[i].getTourLength() < this.bestLength){  
                    //保留最优路径  
                    this.bestLength = this.ants[i].getTourLength();  
                    System.out.println("第"+g+"代，发现新的解"+this.bestLength); 
                    for(int k = 0;k < this.ants[i].getTabu().size();k++)  
                        this.bestTour[k] = this.ants[i].getTabu().get(k).intValue();;  
                }
                //更新信息素变化矩阵
                for (int j = 0; j < this.ants[i].getTabu().size()-1; j++) {
                    this.ants[i].getDelta()[this.ants[i].getTabu().get(j).intValue()][this.ants[i].getTabu().get(j+1).intValue()] = (double) (1.0/this.ants[i].getTourLength());
                    this.ants[i].getDelta()[this.ants[i].getTabu().get(j+1).intValue()][this.ants[i].getTabu().get(j).intValue()] = (double) (1.0/this.ants[i].getTourLength());
                }
            }
            //更新信息素
            this.updatePheromone();
            //重新初始化蚂蚁
            for(int i = 0;i < this.antNum;i++){  
                this.ants[i].init(this.distance, this.alpha, this.beta);
            }
        }
        //打印最佳结果
        this.printOptimal();
    }

    public void printOptimal() {
         System.out.println("The optimal length is: " + this.bestLength);
         System.out.println("The optimal tour is: ");
         for (int i = 0; i < this.bestTour.length; i++) {
             System.out.println(this.bestTour[i]);
         }
    }

    public Ant[] getAnts() {
        return ants;
    }

    public void setAnts(Ant[] ants) {
        this.ants = ants;
    }

    public int getAntNum() {
        return antNum;
    }

    public void setAntNum(int antNum) {
        this.antNum = antNum;
    }

    public int getCityNum() {
        return cityNum;
    }

    public void setCityNum(int cityNum) {
        this.cityNum = cityNum;
    }

    public int getMAX_GEN() {
        return MAX_GEN;
    }

    public void setMAX_GEN(int mAX_GEN) {
        MAX_GEN = mAX_GEN;
    }

    public double[][] getPheromone() {
        return pheromone;
    }

    public void setPheromone(double[][] pheromone) {
        this.pheromone = pheromone;
    }

    public int[][] getDistance() {
        return distance;
    }

    public void setDistance(int[][] distance) {
        this.distance = distance;
    }

    public int getBestLength() {
        return bestLength;
    }

    public void setBestLength(int bestLength) {
        this.bestLength = bestLength;
    }

    public int[] getBestTour() {
        return bestTour;
    }

    public void setBestTour(int[] bestTour) {
        this.bestTour = bestTour;
    }

    public double getAlpha() {
        return alpha;
    }

    public void setAlpha(double alpha) {
        this.alpha = alpha;
    }

    public double getBeta() {
        return beta;
    }

    public void setBeta(double beta) {
        this.beta = beta;
    }

    public double getRho() {
        return rho;
    }

    public void setRho(double rho) {
        this.rho = rho;
    }

    @Override
    public String toString() {
        return "ACO [ants=" + Arrays.toString(ants) + ", antNum=" + antNum + ", cityNum=" + cityNum + ", MAX_GEN="
                + MAX_GEN + ", pheromone=" + Arrays.toString(pheromone) + ", distance=" + Arrays.toString(distance)
                + ", bestLength=" + bestLength + ", bestTour=" + Arrays.toString(bestTour) + ", alpha=" + alpha
                + ", beta=" + beta + ", rho=" + rho + "]";
    }

}

Test类：

package com.gbs.test;

import com.gbs.bean.ACO;

public class Test {
    public static void main(String[] args) {
        ACO aco = new ACO(200, 48, 2000, 1.d, 5.d, 0.5d);
        aco.init("d://cities.txt");
        aco.solve();
    }
}

注：调试代码时遇到一个致命的问题就是忽略了float和double的精度。浪费了三四个小时debug居然是这个错误引起的，float的精度一旦不够，在java中会出现NAN和INFINITY。
https://www.cnblogs.com/zhisuoyu/archive/2016/03/24/5314541.html（此网址讲述了NAN和INFINITY的区别）。

6.存在问题

（1）对于大规模组合优化问题，算法的计算时间而且复杂。由于蚁群算法的时间复杂度是，因此在处理较大规模的组合优化问题时，运算量较大，时间较长。

（2）算法容易在某个或某些局部最优解的邻域附近发生停滞现象，造成早熟收敛，即搜索进行到一定程度后，所有蚂蚁发现的解完全一致，不能继续对解空间进一步搜索，不利于发现全局最优解。

（3）不能较好的解决连续域问题。

（4）由于蚁群算法中蚂蚁个体的运动过程的随机性，当群体规模设置较大时，很难在较短时间内从杂乱无章的路径中找出一条较好的路径。

（5）信息素更新策略，路径搜索策略和最优解保留策略都带有经验性，没有经过严格的理论论证。因此基本蚁群算法的求解效率不高、收敛性较差、求解结果具有较大的分散性。

附件：https://download.csdn.net/download/msc694955868/13123019

 

简介
蚁群算法(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先序遍历二叉树问题等，有什么问题可以随时留言，小编会及时回复大家的。感谢朋友们对本站的支持！