蚁群算法，又称蚂蚁算法，是一个外国人发现的，不得不说，外国的兄弟就是厉害，赞一个！言归正传，首先说以下蚁群算法是怎么回事吧！
蚁群算法是一个寻找最优路径的方法，在蚂蚁的世界，每天的工作就是找食物，搬食物。首先，每个蚂蚁在没找到食物的时候，它们的行动会有一定的惯性，也就是说他们会朝着一个方向一直走，但这不是绝对的，那要是一直走也找不到食物岂不是要累死。在它们遇见障碍的时候就会改变方向，这个方向是随机的，这是蚂蚁的行动看起来不像一个傻子一样，起码还知道遇到障碍物躲开。但是这个举动往往是蚁群算法能找到路径的关键，因为他不是一成不变的，蚂蚁在行动的时候会有一定的随机性，用在现代我们叫做创新。蚂蚁懂得创新，你说它厉不厉害！怪不得蚂蚁总能找到最短的路径。
当蚂蚁找到食物的时候，就会向环境周围散发一种信息素，当然了，信息素是在一定范围内有效的，随着时间推移会消失，跟喷了香水一样。其他的蚂蚁如果发现这种信息素了就会过来，这样，就会有更多的蚂蚁找到食物。当然了，如果最开始的蚂蚁找到的路径可能不是最优的，那么蚂蚁是怎样找到最优的路径呢？这就要归功于蚂蚁的创新精神了。在蚂蚁感受到信息素的时候他会沿着信息素多的方向走，但是他们偶尔也会另辟蹊径，如果他们通过这条路也找到了食物，而且这条路比之前的路更短，那么逐渐的更多的蚂蚁会被吸引到这条路径上来。为什么会有这样的事情发生呢？因为在相同的时间里，路径越短，蚂蚁走的次数就越多，散发的信息素浓度越高。
上面这个图我感觉很好的解释了这个问题。
蚁群算法规则：
1、觅食规则
蚂蚁感知范围是一个3*3的格子，也就是说，他这个格子中有食物就直接过去。
2、移动规则
蚂蚁会朝着信息素浓的地方移动，如果没有感知到信息素，就会按着惯性一直走下去，别忘了，蚂蚁会创新呦！
3、避障规则
蚂蚁在遇到障碍物的时候会选择随机方向移动，同时遵循上面两个规则。
4、信息素规则
蚂蚁在刚发现食物的时候挥洒的信息素会多，距离越远，信息素越少。
准备工作，该了解的都知道了，下面程序搞起来吧！
MATLAB程序：此代码引用于http://blog.csdn.net/lyp2003ok/article/details/3706247
function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q) %% 主要符号说明 %% C n个城市的坐标，n×2的矩阵 %% NC_max 最大迭代次数 %% m 蚂蚁个数 %% Alpha 表征信息素重要程度的参数 %% Beta 表征启发式因子重要程度的参数 %% Rho 信息素蒸发系数 %% Q 信息素增加强度系数 %% R_best 各代最佳路线 %% L_best 各代最佳路线的长度 %%第一步：变量初始化 n=size(C,1);%n表示问题的规模（城市个数） D=zeros(n,n);%D表示完全图的赋权邻接矩阵 for i=1:n for j=1:n if i~=j D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5; else D(i,j)=eps; %i=j时不计算，应该为0，但后面的启发因子要取倒数，用eps（浮点相对精度）表示 end D(j,i)=D(i,j); %对称矩阵 end end Eta=1./D; %Eta为启发因子，这里设为距离的倒数 Tau=ones(n,n); %Tau为信息素矩阵 Tabu=zeros(m,n); %存储并记录路径的生成 NC=1; %迭代计数器，记录迭代次数 R_best=zeros(NC_max,n); %各代最佳路线 L_best=inf.*ones(NC_max,1); %各代最佳路线的长度 L_ave=zeros(NC_max,1); %各代路线的平均长度 while NC<=NC_max %停止条件之一：达到最大迭代次数，停止 %%第二步：将m只蚂蚁放到n个城市上 Randpos=[]; %随即存取 for i=1:(ceil(m/n)) Randpos=[Randpos,randperm(n)]; end Tabu(:,1)=(Randpos(1,1:m))'; %此句不太理解？ %%第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的周游 for j=2:n %所在城市不计算 for i=1:m visited=Tabu(i,1:(j-1)); %记录已访问的城市，避免重复访问 J=zeros(1,(n-j+1)); %待访问的城市 P=J; %待访问城市的选择概率分布 Jc=1; for k=1:n if length(find(visited==k))==0 %开始时置0 J(Jc)=k; Jc=Jc+1; %访问的城市个数自加1 end end %下面计算待选城市的概率分布 for k=1:length(J) P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta); end P=P/(sum(P)); %按概率原则选取下一个城市 Pcum=cumsum(P); %cumsum，元素累加即求和 Select=find(Pcum>=rand); %若计算的概率大于原来的就选择这条路线 to_visit=J(Select(1)); Tabu(i,j)=to_visit; end end if NC>=2 Tabu(1,:)=R_best(NC-1,:); end %%第四步：记录本次迭代最佳路线 L=zeros(m,1); %开始距离为0，m*1的列向量 for i=1:m R=Tabu(i,:); for j=1:(n-1) L(i)=L(i)+D(R(j),R(j+1)); %原距离加上第j个城市到第j+1个城市的距离 end L(i)=L(i)+D(R(1),R(n)); %一轮下来后走过的距离 end L_best(NC)=min(L); %最佳距离取最小 pos=find(L==L_best(NC)); R_best(NC,:)=Tabu(pos(1),:); %此轮迭代后的最佳路线 L_ave(NC)=mean(L); %此轮迭代后的平均距离 NC=NC+1 %迭代继续 %%第五步：更新信息素 Delta_Tau=zeros(n,n); %开始时信息素为n*n的0矩阵 for i=1:m for j=1:(n-1) Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i); %此次循环在路径（i，j）上的信息素增量 end Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i); %此次循环在整个路径上的信息素增量 end Tau=(1-Rho).*Tau+Delta_Tau; %考虑信息素挥发，更新后的信息素 %%第六步：禁忌表清零 Tabu=zeros(m,n); %%直到最大迭代次数 end %%第七步：输出结果 Pos=find(L_best==min(L_best)); %找到最佳路径（非0为真） Shortest_Route=R_best(Pos(1),:) %最大迭代次数后最佳路径 Shortest_Length=L_best(Pos(1)) %最大迭代次数后最短距离 subplot(1,2,1) %绘制第一个子图形 DrawRoute(C,Shortest_Route) %画路线图的子函数 subplot(1,2,2) %绘制第二个子图形 plot(L_best) hold on %保持图形 plot(L_ave,'r') title('平均距离和最短距离') %标题 function DrawRoute(C,R) %%========================================================================= %% DrawRoute.m %% 画路线图的子函数 %%------------------------------------------------------------------------- %% C Coordinate 节点坐标，由一个N×2的矩阵存储 %% R Route 路线 %%========================================================================= N=length(R); scatter(C(:,1),C(:,2)); hold on plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)],'g') hold on for ii=2:N plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)],'g') hold on end title('旅行商问题优化结果 ')
蚁群算法java程序：此代码引用于http://blog.csdn.net/fashionxu/article/details/5484864
同样可以参考http://www.cnblogs.com/biaoyu/archive/2012/09/26/2704456.html
package tspsolver; import java.util.Random; /** *蚂蚁类 * @author FashionXu */ public class ant { /** * 蚂蚁获得的路径 */ public int[]tour; //unvisitedcity 取值是0或1， //1表示没有访问过，0表示访问过 int[] unvisitedcity; /** * 蚂蚁获得的路径长度 */ public int tourlength; int citys; /** * 随机分配蚂蚁到某个城市中 * 同时完成蚂蚁包含字段的初始化工作 * @param citycount 总的城市数量 */ public void RandomSelectCity(int citycount){ citys=citycount; unvisitedcity=new int[citycount]; tour=new int[citycount+1]; tourlength=0; for(int i=0;i<citycount;i++){ tour[i]=-1; unvisitedcity[i]=1; } long r1 = System.currentTimeMillis(); Random rnd=new Random(r1); int firstcity=rnd.nextInt(citycount); unvisitedcity[firstcity]=0; tour[0]=firstcity; } /** * 选择下一个城市 * @param index 需要选择第index个城市了 * @param tao 全局的信息素信息 * @param distance 全局的距离矩阵信息 */ public void SelectNextCity(int index,double[][]tao,int[][]distance){ double []p; p=new double[citys]; double alpha=1.0; double beta=2.0; double sum=0; int currentcity=tour[index-1]; //计算公式中的分母部分 for(int i=0;i<citys;i++){ if(unvisitedcity[i]==1) sum+=(Math.pow(tao[currentcity][i], alpha)* Math.pow(1.0/distance[currentcity][i], beta)); } //计算每个城市被选中的概率 for(int i=0;i<citys;i++){ if(unvisitedcity[i]==0) p[i]=0.0; else{ p[i]=(Math.pow(tao[currentcity][i], alpha)* Math.pow(1.0/distance[currentcity][i], beta))/sum; } } long r1 = System.currentTimeMillis(); Random rnd=new Random(r1); double selectp=rnd.nextDouble(); //轮盘赌选择一个城市； double sumselect=0; int selectcity=-1; for(int i=0;i<citys;i++){ sumselect+=p[i]; if(sumselect>=selectp){ selectcity=i; break; } } if (selectcity==-1) System.out.println(); tour[index]=selectcity; unvisitedcity[selectcity]=0; } /** * 计算蚂蚁获得的路径的长度 * @param distance 全局的距离矩阵信息 */ public void CalTourLength(int [][]distance){ tourlength=0; tour[citys]=tour[0]; for(int i=0;i<citys;i++){ tourlength+=distance[tour[i]][tour[i+1]]; } } }
蚁群算法c++程序：此代码引用于http://blog.sina.com.cn/s/blog_8f06da990100vinl.html
#pragma once #include <iostream> #include <math.h> #include <time.h> const double ALPHA=1.0; //启发因子，信息素的重要程度 const double BETA=2.0; //期望因子，城市间距离的重要程度 const double ROU=0.5; //信息素残留参数 const int N_ANT_COUNT=34; //蚂蚁数量 const int N_IT_COUNT=1000; //迭代次数 const int N_CITY_COUNT=51; //城市数量 const double DBQ=100.0; //总的信息素 const double DB_MAX=10e9; //一个标志数，10的9次方 double g_Trial[N_CITY_COUNT][N_CITY_COUNT]; //两两城市间信息素，就是环境信息素 double g_Distance[N_CITY_COUNT][N_CITY_COUNT]; //两两城市间距离 //eil51.tsp城市坐标数据 double x_Ary[N_CITY_COUNT]= { 37,49,52,20,40,21,17,31,52,51, 42,31,5,12,36,52,27,17,13,57, 62,42,16,8,7,27,30,43,58,58, 37,38,46,61,62,63,32,45,59,5, 10,21,5,30,39,32,25,25,48,56, 30 }; double y_Ary[N_CITY_COUNT]= { 52,49,64,26,30,47,63,62,33,21, 41,32,25,42,16,41,23,33,13,58, 42,57,57,52,38,68,48,67,48,27, 69,46,10,33,63,69,22,35,15,6, 17,10,64,15,10,39,32,55,28,37, 40 }; //返回指定范围内的随机整数 int rnd(int nLow,int nUpper) { return nLow+(nUpper-nLow)*rand()/(RAND_MAX+1); } //返回指定范围内的随机浮点数 double rnd(double dbLow,double dbUpper) { double dbTemp=rand()/((double)RAND_MAX+1.0); return dbLow+dbTemp*(dbUpper-dbLow); } //返回浮点数四舍五入取整后的浮点数 double ROUND(double dbA) { return (double)((int)(dbA+0.5)); } //定义蚂蚁类 class CAnt { public: CAnt(void); ~CAnt(void); public: int m_nPath[N_CITY_COUNT]; //蚂蚁走的路径 double m_dbPathLength; //蚂蚁走过的路径长度 int m_nAllowedCity[N_CITY_COUNT]; //没去过的城市 int m_nCurCityNo; //当前所在城市编号 int m_nMovedCityCount; //已经去过的城市数量 public: int ChooseNextCity(); //选择下一个城市 void Init(); //初始化 void Move(); //蚂蚁在城市间移动 void Search(); //搜索路径 void CalPathLength(); //计算蚂蚁走过的路径长度 }; //构造函数 CAnt::CAnt(void) { } //析构函数 CAnt::~CAnt(void) { } //初始化函数，蚂蚁搜索前调用 void CAnt::Init() { for (int i=0;i<N_CITY_COUNT;i++) { m_nAllowedCity[i]=1; //设置全部城市为没有去过 m_nPath[i]=0; //蚂蚁走的路径全部设置为0 } //蚂蚁走过的路径长度设置为0 m_dbPathLength=0.0; //随机选择一个出发城市 m_nCurCityNo=rnd(0,N_CITY_COUNT); //把出发城市保存入路径数组中 m_nPath[0]=m_nCurCityNo; //标识出发城市为已经去过了 m_nAllowedCity[m_nCurCityNo]=0; //已经去过的城市数量设置为1 m_nMovedCityCount=1; } //选择下一个城市 //返回值 为城市编号 int CAnt::ChooseNextCity() { int nSelectedCity=-1; //返回结果，先暂时把其设置为-1 //============================================================================== //计算当前城市和没去过的城市之间的信息素总和 double dbTotal=0.0; double prob[N_CITY_COUNT]; //保存各个城市被选中的概率 for (int i=0;i<N_CITY_COUNT;i++) { if (m_nAllowedCity[i] == 1) //城市没去过 { prob[i]=pow(g_Trial[m_nCurCityNo][i],ALPHA)*pow(1.0/g_Distance[m_nCurCityNo][i],BETA); //该城市和当前城市间的信息素 dbTotal=dbTotal+prob[i]; //累加信息素，得到总和 } else //如果城市去过了，则其被选中的概率值为0 { prob[i]=0.0; } } //============================================================================== //进行轮盘选择 double dbTemp=0.0; if (dbTotal > 0.0) //总的信息素值大于0 { dbTemp=rnd(0.0,dbTotal); //取一个随机数 for (int i=0;i<N_CITY_COUNT;i++) { if (m_nAllowedCity[i] == 1) //城市没去过 { dbTemp=dbTemp-prob[i]; //这个操作相当于转动轮盘，如果对轮盘选择不熟悉，仔细考虑一下 if (dbTemp < 0.0) //轮盘停止转动，记下城市编号，直接跳出循环 { nSelectedCity=i; break; } } } } //============================================================================== //如果城市间的信息素非常小 ( 小到比double能够表示的最小的数字还要小 ) //那么由于浮点运算的误差原因，上面计算的概率总和可能为0 //会出现经过上述操作，没有城市被选择出来 //出现这种情况，就把第一个没去过的城市作为返回结果 //题外话：刚开始看的时候，下面这段代码困惑了我很长时间，想不通为何要有这段代码，后来才搞清楚。 if (nSelectedCity == -1) { for (int i=0;i<N_CITY_COUNT;i++) { if (m_nAllowedCity[i] == 1) //城市没去过 { nSelectedCity=i; break; } } } //============================================================================== //返回结果，就是城市的编号 return nSelectedCity; } //蚂蚁在城市间移动 void CAnt::Move() { int nCityNo=ChooseNextCity(); //选择下一个城市 m_nPath[m_nMovedCityCount]=nCityNo; //保存蚂蚁走的路径 m_nAllowedCity[nCityNo]=0;//把这个城市设置成已经去过了 m_nCurCityNo=nCityNo; //改变当前所在城市为选择的城市 m_nMovedCityCount++; //已经去过的城市数量加1 } //蚂蚁进行搜索一次 void CAnt::Search() { Init(); //蚂蚁搜索前，先初始化 //如果蚂蚁去过的城市数量小于城市数量，就继续移动 while (m_nMovedCityCount < N_CITY_COUNT) { Move(); } //完成搜索后计算走过的路径长度 CalPathLength(); } //计算蚂蚁走过的路径长度 void CAnt::CalPathLength() { m_dbPathLength=0.0; //先把路径长度置0 int m=0; int n=0; for (int i=1;i<N_CITY_COUNT;i++) { m=m_nPath[i]; n=m_nPath[i-1]; m_dbPathLength=m_dbPathLength+g_Distance[m][n]; } //加上从最后城市返回出发城市的距离 n=m_nPath[0]; m_dbPathLength=m_dbPathLength+g_Distance[m][n]; } //tsp类 class CTsp { public: CTsp(void); ~CTsp(void); public: CAnt m_cAntAry[N_ANT_COUNT]; //蚂蚁数组 CAnt m_cBestAnt; //定义一个蚂蚁变量，用来保存搜索过程中的最优结果 //该蚂蚁不参与搜索，只是用来保存最优结果 public: //初始化数据 void InitData(); //开始搜索 void Search(); //更新环境信息素 void UpdateTrial(); }; //构造函数 CTsp::CTsp(void) { } CTsp::~CTsp(void) { } //初始化数据 void CTsp::InitData() { //先把最优蚂蚁的路径长度设置成一个很大的值 m_cBestAnt.m_dbPathLength=DB_MAX; //计算两两城市间距离 double dbTemp=0.0; for (int i=0;i<N_CITY_COUNT;i++) { for (int j=0;j<N_CITY_COUNT;j++) { dbTemp=(x_Ary[i]-x_Ary[j])*(x_Ary[i]-x_Ary[j])+(y_Ary[i]-y_Ary[j])*(y_Ary[i]-y_Ary[j]); dbTemp=pow(dbTemp,0.5); g_Distance[i][j]=ROUND(dbTemp); } } //初始化环境信息素，先把城市间的信息素设置成一样 //这里设置成1.0，设置成多少对结果影响不是太大，对算法收敛速度有些影响 for (int i=0;i<N_CITY_COUNT;i++) { for (int j=0;j<N_CITY_COUNT;j++) { g_Trial[i][j]=1.0; } } } //更新环境信息素 void CTsp::UpdateTrial() { //临时数组，保存各只蚂蚁在两两城市间新留下的信息素 double dbTempAry[N_CITY_COUNT][N_CITY_COUNT]; memset(dbTempAry,0,sizeof(dbTempAry)); //先全部设置为0 //计算新增加的信息素,保存到临时数组里 int m=0; int n=0; for (int i=0;i<N_ANT_COUNT;i++) //计算每只蚂蚁留下的信息素 { for (int j=1;j<N_CITY_COUNT;j++) { m=m_cAntAry[i].m_nPath[j]; n=m_cAntAry[i].m_nPath[j-1]; dbTempAry[n][m]=dbTempAry[n][m]+DBQ/m_cAntAry[i].m_dbPathLength; dbTempAry[m][n]=dbTempAry[n][m]; } //最后城市和开始城市之间的信息素 n=m_cAntAry[i].m_nPath[0]; dbTempAry[n][m]=dbTempAry[n][m]+DBQ/m_cAntAry[i].m_dbPathLength; dbTempAry[m][n]=dbTempAry[n][m]; } //================================================================== //更新环境信息素 for (int i=0;i<N_CITY_COUNT;i++) { for (int j=0;j<N_CITY_COUNT;j++) { g_Trial[i][j]=g_Trial[i][j]*ROU+dbTempAry[i][j]; //最新的环境信息素 = 留存的信息素 + 新留下的信息素 } } } void CTsp::Search() { char cBuf[256]; //打印信息用 //在迭代次数内进行循环 for (int i=0;i<N_IT_COUNT;i++) { //每只蚂蚁搜索一遍 for (int j=0;j<N_ANT_COUNT;j++) { m_cAntAry[j].Search(); } //保存最佳结果 for (int j=0;j<N_ANT_COUNT;j++) { if (m_cAntAry[j].m_dbPathLength < m_cBestAnt.m_dbPathLength) { m_cBestAnt=m_cAntAry[j]; } } //更新环境信息素 UpdateTrial(); //输出目前为止找到的最优路径的长度 sprintf(cBuf,"\n[%d] %.0f",i+1,m_cBestAnt.m_dbPathLength); printf(cBuf); } } int main() { //用当前时间点初始化随机种子，防止每次运行的结果都相同 time_t tm; time(&tm); unsigned int nSeed=(unsigned int)tm; srand(nSeed); //开始搜索 CTsp tsp; tsp.InitData(); //初始化 tsp.Search(); //开始搜索 //输出结果 printf("\nThe best tour is :\n"); char cBuf[128]; for (int i=0;i<N_CITY_COUNT;i++) { sprintf(cBuf,"%d ",tsp.m_cBestAnt.m_nPath[i]+1); if (i % 20 == 0) { printf("\n"); } printf(cBuf); } printf("\n\nPress any key to exit!"); getchar(); return 0; }最后总结一下，蚁群算法是寻找最优路径的算法，当然蚁群算法在寻找路径的过程中可能会陷入局部最优解，蚁群算法为自组织寻找路径行为，适用于多无人系统路径规划相关方向。
