1、蚁群算法是上世纪90年代初由M数学建模蚁群算法是上世纪90年代初由M. Dorigo等学者提出的一种利用蚂蚁觅食行为的内在机制来求解复杂问题的方法。在研究蚂蚁觅食行为的过程中，人们发现，尽管单只蚂蚁的能力十分有限，而整个蚁群却能在觅食过程中发现从蚁巢到食物源的最短路径。蚂蚁能够通过一种称为“媒介质”（stigmergy）的机制来解决复杂问题：每当蚂蚁发现了一条通往食物源的路径，它就会向该路径上释放一定量的化学物质信息素。同时，随后的蚂蚁具有感知信息素浓度的能力，并根据信息素的浓度的大小来选择它将要移动的方向。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多（或者较长的路上蚂蚁多
2、，这也无关紧要）。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素；而长的路正相反，因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就近似找到了。可以说，蚂蚁以信息素作为媒介实现了群体内部的间接通信，依赖自身催化与正向反馈的机制最终发现觅食的最短路径。 在蚂蚁觅食行为的启发下，学者们在计算机上模拟真实蚂蚁的群体行为，并把该思想用于解决众多复杂的实际应用问题，这就产生了蚁群算法。蚁群算法是人们受到真实世界中蚂蚁群体行为的启示而提
3、出的一种优化算法，通过个体之间的信息交流与相互协作，最终得到待求问题的解。计算机学者首先把待解问题转换成相应的构建图，然后让人工蚁群在构建图中仿照真实蚂蚁的行为：人工蚂蚁在构建图中游走，并根据某些规则释放一定量的人工信息素，随着信息素在构建图中某些成分上的不断积累，人工蚂蚁可以探测人工信息素的浓度并以此为依据构造出问题的解。这种方法具有分布性、并行性、全局寻优、无须依赖具体问题的数学特性等特点，能够在较短的时间内发现问题的近似最优解，并迅速成为最成功的启发式算法之一。 在网络路由处理中，网络的流量分布不断变化，网络链路或结点也会随机地失效或重新加入。蚁群的自身催化与正向反馈机制正好符合了这类问
4、题的求解特点，因而，蚁群算法在网络领域得到一定应用。 蚁群觅食行为所呈现出的并行与分布特性使得算法特别适合于并行化处理。因而，实现算法的并行化执行对于大量复杂的实际应用问题的求解来说是极具潜力的。 蚂蚁算法还在聚类、网页文档分类及主题图显示、智能机器人控制等领域得到成功的应用。 在某群体中若存在众多无智能的个体，它们通过相互之间的简单合作所表现出来的智能行为即称为集群智能（Swarm Intelligence）。互联网上的交流，不过是更多的神经元连接（人脑）通过互联网相互作用的结果，光缆和路由器不过是轴突和突触的延伸。 从自组织现象的角度上看，人脑的智能和蚁群也没有本质上的区别，单个神经元没有
5、智能可言，单个蚂蚁也没有，但是通过连接形成的体系，是一个智能体。该程序试图对具有31个城市的VRP进行求解，已知的最优解为784.1，我用该程序只能优化到810左右，应该是陷入局部最优，但我不知问题出在什么地方。请用过蚁群算法的高手指教。 蚁群算法的matlab源码，同时请指出为何不能优化到已知的最好解 % % % the procedure of ant colony algorithm for VRP % % % % % % % % % % % % %initialize the parameters of ant colony algorithms load data.txt; d=da
6、ta(:,2:3); g=data(:,4); m=31; % 蚂蚁数 alpha=1; belta=4;% 决定tao和miu重要性的参数 lmda=0; rou=0.9; %衰减系数 q0=0.95; % 概率 tao0=1/(31*841.04);%初始信息素 Q=1;% 蚂蚁循环一周所释放的信息素 defined_phrm=15.0; % initial pheromone level value QV=100; % 车辆容量 vehicle_best=round(sum(g)/QV)+1; %所完成任务所需的最少车数 V=40; % 计算两点的距离 for i=1:32; for j
7、=1:32; dist(i,j)=sqrt(d(i,1)-d(j,1)2+(d(i,2)-d(j,2)2); end; end; %给tao miu赋初值 for i=1:32; for j=1:32; if i=j; %s(i,j)=dist(i,1)+dist(1,j)-dist(i,j); tao(i,j)=defined_phrm; miu(i,j)=1/dist(i,j); end; end; end; for k=1:32; for k=1:32; deltao(i,j)=0; end; end; best_cost=10000; for n_gen=1:50; print_hea
8、d(n_gen); for i=1:m; %best_solution=; print_head2(i); sumload=0; cur_pos(i)=1; rn=randperm(32); n=1; nn=1; part_sol(nn)=1; %cost(n_gen,i)=0.0; n_sol=0; % 由蚂蚁产生的路径数量 M_vehicle=500; t=0; %最佳路径数组的元素数为0 while sumload=QV; for k=1:length(rn); if sumload+g(rn(k)maxp maxp=p(j); index_max=j; end; end; old_po
9、s=cur_pos(i); if rand(1)q0 cur_pos(i)=A(index_max); else krnd=randperm(na); cur_pos(i)=A(krnd(1); bbb=old_pos cur_pos(i); ccc=1 1; if bbb=ccc; cur_pos(i)=A(krnd(2); end; end; tao(old_pos,cur_pos(i)=taolocalupdate(tao(old_pos,cur_pos(i),rou,tao0);%对所经弧进行局部更新 sumload=sumload+g(cur_pos(i); nn=nn+1; par
10、t_sol(nn)=cur_pos(i); temp_load=sumload; if cur_pos(i)=1; rn=setdiff(rn,cur_pos(i); n=1; A=; end; if cur_pos(i)=1; % 如果当前点为车场,将当前路径中的已访问用户去掉后,开始产生新路径 if setdiff(part_sol,1)=; n_sol=n_sol+1; % 表示产生的路径数,n_sol=1,2,3,.5,6.,超过5条对其费用加上车辆的派遣费用 fid=fopen(out_solution.txt,a+); fprintf(fid,%s%i%s,NO.,n_sol,条路
11、径是:); fprintf(fid,%i ,part_sol); fprintf(fid,n); fprintf(fid,%s,当前的用户需求量是:); fprintf(fid,%in,temp_load); fprintf(fid,-n); fclose(fid); % 对所得路径进行路径内3-opt优化 final_sol=exchange(part_sol); for nt=1:length(final_sol); % 将所有产生的路径传给一个数组 temp(t+nt)=final_sol(nt); end; t=t+length(final_sol)-1; sumload=0; fin
12、al_sol=setdiff(final_sol,1); rn=setdiff(rn,final_sol); part_sol=; final_sol=; nn=1; part_sol(nn)=cur_pos(i); A=; n=1; end; end; if setdiff(rn,1)=;% 产生最后一条终点不为1的路径 n_sol=n_sol+1; nl=length(part_sol); part_sol(nl+1)=1;%将路径的最后1位补1 % 对所得路径进行路径内3-opt优化 final_sol=exchange(part_sol); for nt=1:length(final_
13、sol); % 将所有产生的路径传给一个数组 temp(t+nt)=final_sol(nt); end; cost(n_gen,i)=cost_sol(temp,dist)+M_vehicle*(n_sol-vehicle_best); %计算由蚂蚁i产生的路径总长度 for ki=1:length(temp)-1; deltao(temp(ki),temp(ki+1)=deltao(temp(ki),temp(ki+1)+Q/cost(n_gen,i); end; if cost(n_gen,i)best_cost; best_cost=cost(n_gen,i); old_cost=be
14、st_cost; best_gen=n_gen; % 产生最小费用的代数 best_ant=i; %产生最小费用的蚂蚁 best_solution=temp; end; if i=m; %如果所有蚂蚁均完成一次循环，则用最佳费用所对应的路径对弧进行整体更新 for ii=1:32; for jj=1:32; tao(ii,jj)=(1-rou)*tao(ii,jj); end; end; for kk=1:length(best_solution)-1; tao(best_solution(kk),best_solution(kk+1)=tao(best_solution(kk),best_s
15、olution(kk+1)+deltao(best_solution(kk),best_solution(kk+1); end; end; fid=fopen(out_solution.txt,a+); fprintf(fid,%s%i%s,NO.,n_sol,路径是:); fprintf(fid,%i ,part_sol); fprintf(fid,n); fprintf(fid,%s %in,当前的用户需求量是:,temp_load); fprintf(fid,%s %fn,总费用是:,cost(n_gen,i); fprintf(fid,-n); fprintf(fid,%sn,最终路径
16、是:); fprintf(fid,%i-,temp); fprintf(fid,n); fclose(fid); temp=; break; end; end; end; end; 我现在也在研究它,希望能共同进步.建义可以看一下段海滨的关于蚁群算法的书.讲的不错,李士勇的也可以,还有一本我在图书馆见过,记不得名字了.简单蚁群算法求解TSP的源程序(我帮你找的) 蚁群算法是新兴的仿生算法，最初是由意大利学者Dorigo M于1991年首次提出，由于具有较强的鲁棒性，优良的分布式计算机制和易于与其它方法结合等优点，成为人工智能领域的一个研究热点。本程序是实现简单的蚁群算法，TSP问题取的是att
17、48，可从http:/www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95获取，程序运行时间可能会比较长，在我的这台CPU 1.6G+内存256M的机器上运行时间大概是13分钟左右。我用的语言是MATLAB 7.1。此程序仅供学习所用，如有问题请反馈。谢谢。（注：程序没有计算最后一个城市回来起点城市的距离） function y,val=QACS tic load att48 att48; MAXIT=300; % 最大循环次数 NC=48; % 城市个数 tao=ones(48,48);% 初始时刻各边上的信息最为1 rho=0.
18、2; % 挥发系数 alpha=1; beta=2; Q=100; mant=20; % 蚂蚁数量 iter=0; % 记录迭代次数 for i=1:NC % 计算各城市间的距离 for j=1:NC distance(i,j)=sqrt(att48(i,2)-att48(j,2)2+(att48(i,3)-att48(j,3)2); end end bestroute=zeros(1,48); % 用来记录最优路径 routelength=inf; % 用来记录当前找到的最优路径长度 % for i=1:mant % 确定各蚂蚁初始的位置 % end for ite=1:MAXIT for
19、ka=1:mant %考查第K只蚂蚁 deltatao=zeros(48,48); % 第K只蚂蚁移动前各边上的信息增量为零 routek,lengthk=travel(distance,tao,alpha,beta); if lengthkroutelength % 找到一条更好的路径 routelength=lengthk; bestroute=routek; end for i=1:NC-1 % 第K只蚂蚁在路径上释放的信息量 deltatao(routek(i),routek(i+1)=deltatao(routek(i),routek(i+1)+Q/lengthk; end delt
20、atao(routek(48),1)=deltatao(routek(48),1)+Q/lengthk; end for i=1:NC-1 for j=i+1:NC if deltatao(i,j)=0 deltatao(i,j)=deltatao(j,i); end end end tao=(1-rho).*tao+deltatao; end y=bestroute; val=routelength; toc function y,val=travel(distance,tao,alpha,beta) % 某只蚂蚁找到的某条路径 m,n=size(distance); p=fix(m*ran
21、d)+1; val=0; % 初始路径长度设为 0 tabuk=p; % 假设该蚂蚁都是从第 p 个城市出发的 for i=1:m-1 np=tabuk(length(tabuk); % 蚂蚁当前所在的城市号 p_sum=0; for j=1:m if isin(j,tabuk) continue; else ada=1/distance(np,j); p_sum=p_sum+tao(np,j)alpha*adabeta; end end cp=zeros(1,m); % 转移概率 for j=1:m if isin(j,tabuk) continue; else ada=1/distance
22、(np,j); cp(j)=tao(np,j)alpha*adabeta/p_sum; end end NextCity=pchoice(cp); tabuk=tabuk,NextCity; val=val+distance(np,NextCity); end y=tabuk; function y=isin(x,A) % 判断数 x 是否在向量 A 中，如在返回 1 ，否则返回 0 y=0; for i=1:length(A) if A(i)=x y=1; break; end end function y=pchoice(A) a=rand; tempA=zeros(1,length(A)
23、+1); for i=1:length(A) tempA(i+1)=tempA(i)+A(i); end for i=2:length(tempA) if a=tempA(i) y=i-1; break; end end 蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值.蚁群算法是一种求解组合最优化问题的新型通用启发式方法，该方法具有正反馈、分布式计算和富于建设性的贪婪启发式搜索的特点。通过建立适当的数学模型，基于故障过电流的配电网故障定位变为一种非线性全局寻优问题。由柳洪平创建。
