蚁群算法tsp
㈠ 请教，采用蚁群算法求解TSP问题的oliver30最优路径
给你产考产考//蚁群算法关于简单的TSP问题求解//#include#include#include#include#include#defineM13//蚂蚁的数量#defineN144//城市的数量#defineR1000//迭代次数#defineIN1//初始化的信息素的量#defineMAX0x7fffffff//定义最大值structcoordinate{charcity[15];//城市名intx;//城市相对横坐标inty;//城市相对纵坐标}coords[N];doublegraph[N][N];//储存城市之间的距离的邻接矩阵,自己到自己记作MAXdoublephe[N][N];//每条路径上的信息素的量doubleadd[N][N];//代表相应路径上的信息素的增量doubleyita[N][N];//启发函数,yita[i][j]=1/graph[i][j]intvis[M][N];//标记已经走过的城市intmap[M][N];//map[K][N]记录第K只蚂蚁走的路线doublesolution[M];//记录某次循环中每只蚂蚁走的路线的距离intbestway[N];//记录最近的那条路线doublebestsolution=MAX;intNcMax;//代表迭代次数,理论上迭代次数越多所求的解更接近最优解,最具有说服力doublealpha,betra,rou,Q;voidInitialize();//信息初始化voidInputcoords(FILE*fp);//将文件中的坐标信息读入voidGreateGraph();//根据坐标信息建图doubleDistance(int*p);//计算蚂蚁所走的路线的总长度voidResult();//将结果保存到out.txt中voidInitialize(){alpha=2;betra=2;rou=0.7;Q=5000;NcMax=R;return;}voidInputcoords(FILE*fp){inti;intnumber;if(fp==NULL){printf("Sorry,thefileisnotexist\n");exit(1);}else{for(i=0;idrand)break;}vis[k][j]=1;//将走过的城市标记起来map[k][s]=j;//记录城市的顺序}s++;}memset(add,0,sizeof(add));for(k=0;k20)//设立一个上界,防止启发因子的作用被淹没phe[i][j]=20;}}memset(vis,0,sizeof(vis));memset(map,-1,sizeof(map));}Result();printf("Resultissavedinout.txt\n");return0;}
㈡ TSP中用蚁群算法和遗传算法有区别么
TSP,只是一个普通但很经典的NP-C问题。具有大的难以想象的解空间。一般的branch-and-bound算法是很难搞定的。于是,人们尝试智能算法,包括遗传算法,蚁群算法,粒子群算法等。遗传算法和蚁群算法都是基于种群的。但是这两个算法有着本质区别。遗传算法的进化机制是基于个体竞争,而蚁群算法的搜索机制则是蚂蚁之间的信息素传导机制下的群体合作。因此,蚁群算法,粒子群算法,人工鱼群算法等,被归纳为群智能算法,成为了一个有别于遗传算法的另一个进化计算领域的分支。由于搜索机制的不同,这两种算法对于不同的问题,具有不同的效率。就拿标准遗传算法和标准蚁群算法来说,应该是蚁群算法更适合求解TSP。然而,无论是遗传算法还是蚁群算法,都有大量的变种算法或者称为改进算法,所以很难简单的说谁更适合TSP。
记得采纳啊
㈢ MATLAB 蚁群算法求解TSP问题
n个城市，编号为1---n
for循环的次数是蚂蚁重复城市的次数，比如5个蚂蚁放到4个城市，需要重复两遍才能放完蚂蚁，每次循环产生n个1---n的随机数,相当于随机n个城市，产生城市序列
循环结束
Tabu一句表示将m个蚂蚁随机，每个蚂蚁放到前面产生的城市序列中，每个蚂蚁一个城市，需要m个，所以提取前面1：m个序列
'表示转置，没有多大用处，可能参与后面的计算方便。
我感觉如果m,n很大的话，你这样做会产生很大的浪费，计算很多的随机数，这样的话更好，一句就得：(如果变量Randpos后面没有用到的话，如果用到了，还要用你的程序)
Tabu=ceil(n*rand(1,m))'
㈣ 遗传算法和蚁群算法在求解TSP问题上的对比分析
【原创】比遗传算法性能更好：蚁群算法TSP(旅行商问题)通用matlab程序
声明：本程序为本人原创，在研学论坛首次发表，本人保留一切权利，仅供学习交流用，如转载请注明原作者！
function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)
%%=========================================================================
%% ACATSP.m
%% Ant Colony Algorithm for Traveling Salesman Problem
%% ChengAihua,PLA Information Engineering University,ZhengZhou,China
%% Email:[email protected]
%% All rights reserved
%%-------------------------------------------------------------------------
%% 主要符号说明
%% 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;
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
J(Jc)=k;
Jc=Jc+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);
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);
for i=1:m
R=Tabu(i,:);
for j=1:(n-1)
L(i)=L(i)+D(R(j),R(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);
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);
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));
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)
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)])
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)])
hold on
end
设置初始参数如下：
m=31;Alpha=1;Beta=5;Rho=0.1;NC_max=200;Q=100;
31城市坐标为：
1304 2312
3639 1315
4177 2244
3712 1399
3488 1535
3326 1556
3238 1229
4196 1004
4312 790
4386 570
3007 1970
2562 1756
2788 1491
2381 1676
1332 695
3715 1678
3918 2179
4061 2370
3780 2212
3676 2578
4029 2838
4263 2931
3429 1908
3507 2367
3394 2643
3439 3201
2935 3240
3140 3550
2545 2357
2778 2826
2370 2975
运行后得到15602的巡游路径，
㈤ 关于神经网络，蚁群算法和遗传算法
神经网络并行性和自适应性很强，应用领域很广，在任何非线性问题中都可以应用，如控制、信息、预测等各领域都能应用。
蚁群算法最开始应用于TSP问题，获得了成功，后来又广泛应用于各类组合优化问题。但是该算法理论基础较薄弱，算法收敛性都没有得到证明，很多参数的设定也仅靠经验，实际效果也一般，使用中也常常早熟。
遗传算法是比较成熟的算法，它的全局寻优能力很强，能够很快地趋近较优解。主要应用于解决组合优化的NP问题。
这三种算法可以相互融合，例如GA可以优化神经网络初始权值，防止神经网络训练陷入局部极小且加快收敛速度。蚁群算法也可用于训练神经网络，但一定要使用优化后的蚁群算法，如最大-最小蚁群算法和带精英策略。
㈥ 蚁群算法
在蚂蚁种群中，蚂蚁间相互交流的方式是通过一种名为信息素的物质，它可以是蚂蚁行动时留下的物质，可以被其他蚂蚁所感知。
在寻找食物的过程中，如左图所示，三角形ABC是等边三角形，蚂蚁窝在A点，C点有食物，A点的两只蚂蚁选择了两条路线前往C点，一条为AB->BC，另一条A->C，当走远路的蚂蚁，到达C点时，延AC边上的蚂蚁已经走了一个来回，路径上信息素如右图所示。后到会感知到边AC上的信息素浓度更高一些，于是他也会选择AC来行走，因为相同时间内，信息素浓度更高的说明，路程更短。
蚁群算法便是基于这样的一个思想来解决如TSP等优化问题，一下介绍便是拿TSP问题来介绍蚁群算法
信息素用符号τ来表示，如下式，下标i，j表示从城市i到城市j这条道路上的信息素，上标0表示这是初次计算，也就是初始信息素，初始信息素都设置为1，或者一个较小的常数，表示每条道路上的信息素都相等，这样通过运算蚂蚁爬向各个城市的概率都相等
基于信息素，每只蚂蚁都有一个选择道路的公式，如下式
其中
当所有蚂蚁完成一次周游后，各个路径上的信息素进行一次更新
㈦ 蚁群算法解决TSP问题，最优解是多少，参数如何选择
概念：蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值
其原理：为什么小小的蚂蚁能够找到食物？他们具有智能么？设想，如果我们要为蚂蚁设计一个人工智能的程序，那么这个程序要多么复杂呢？首先，你要让蚂蚁能够避开障碍物，就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物，其次，要让蚂蚁找到食物，就需要让他们遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路径，那么需要计算所有可能的路径并且比较它们的大小，而且更重要的是，你要小心翼翼的编程，因为程序的错误也许会让你前功尽弃。这是多么不可思议的程序！太复杂了，恐怕没人能够完成这样繁琐冗余的程序
应用范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内
引申：跟着蚂蚁的踪迹，你找到了什么？通过上面的原理叙述和实际操作，我们不难发现蚂蚁之所以具有智能行为，完全归功于它的简单行为规则，而这些规则综合起来具有下面两个方面的特点： 1、多样性 2、正反馈 多样性保证了蚂蚁在觅食的时候不置走进死胡同而无限循环，正反馈机制则保证了相对优良的信息能够被保存下来。我们可以把多样性看成是一种创造能力，而正反馈是一种学习强化能力。正反馈的力量也可以比喻成权威的意见，而多样性是打破权威体现的创造性，正是这两点小心翼翼的巧妙结合才使得智能行为涌现出来了。 引申来讲，大自然的进化，社会的进步、人类的创新实际上都离不开这两样东西，多样性保证了系统的创新能力，正反馈保证了优良特性能够得到强化，两者要恰到好处的结合。如果多样性过剩，也就是系统过于活跃，这相当于蚂蚁会过多的随机运动，它就会陷入混沌状态；而相反，多样性不够，正反馈机制过强，那么系统就好比一潭死水。这在蚁群中来讲就表现为，蚂蚁的行为过于僵硬，当环境变化了，蚂蚁群仍然不能适当的调整。 既然复杂性、智能行为是根据底层规则涌现的，既然底层规则具有多样性和正反馈特点，那么也许你会问这些规则是哪里来的？多样性和正反馈又是哪里来的？我本人的意见：规则来源于大自然的进化。而大自然的进化根据刚才讲的也体现为多样性和正反馈的巧妙结合。而这样的巧妙结合又是为什么呢？为什么在你眼前呈现的世界是如此栩栩如生呢？答案在于环境造就了这一切，之所以你看到栩栩如生的世界，是因为那些不能够适应环境的多样性与正反馈的结合都已经死掉了，被环境淘汰了！ 蚁群算法的实现 下面的程序开始运行之后，蚂蚁们开始从窝里出动了，寻找食物；他们会顺着屏幕爬满整个画面，直到找到食物再返回窝。 其中，‘F’点表示食物，‘H’表示窝，白色块表示障碍物，‘+’就是蚂蚁了。
具体参考http://ke..com/view/539346.htm
希望对你有帮助，谢谢。
㈧ 量子蚁群算法求解TSP问题的matlab编程实现
可以的 你的点坐标都是多少
㈨ TSP是什么意思啊
TSP即旅行商问题，即TSP问题（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中着名问题之一。
假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市，路径的选择目标是要求得的路径路程为所有路径之中的最小值。
TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。
(9)蚁群算法tsp扩展阅读：
描述
TSP问题作为图论问题可以用无向加权图来对TSP建模，则城市是图的顶点，道路是图的边，道路的距离就是该边的长度。它是起点和终点都在一个特定顶点，访问每个顶点恰好一次的最小化问题。通常，该模型是一个完全图（即每对顶点由一条边连接）。
如果两个城市之间不存在路径，则增加一条非常长的边就可以完成图，而不影响计算最优回路。
TSP问题非对称和对称，在对称TSP问题中，两座城市之间来回的距离是相等的，形成一个无向图。这种对称性将解的数量减少了一半。
㈩ 几种蚁群算法介绍
最早的蚁群算法，其在小规模TSP中性能尚可，再大规模TSP问题中性能下降，容易停滞。其解决旅行商问题（TSP）过程大致如下：
在初始时刻，m只蚂蚁被随机的放到城市中，在各条路径上的信息素初始值相等。
蚂蚁按照随机比例规则从允许的城市中选择下一个城市：
τ为信息素，η 为启发式因子，a_k 为下一步被允许城市的集合。
使用禁忌表记录蚂蚁走过的城市，不允许蚂蚁选择已经访问过的城市。
所有蚂蚁完成一次周游后，计算每只蚂蚁的路径长度，裂颤保存最短路径长度。敬桐
更新每个城市信息素：
τ=(1−ρ)τ+∑Δτ, 0≤ρ≤1
Δτ=1/d
由上可知，先挥发信息素，再增加信息素。其中d为路径距离，路径越短，信息素增加越多。∑Δτ表示所有本次觅食过程中所有经过此城市的觅食成功的路线的信息素累加。
清空禁忌表，开始下一次周游。
对算法每次循环之后给予最亮源坦优路径额外的信息素。
对于普通路径中的每个城市：
τ(t+1)=(1−ρ)τ(t)+∑Δτ
对于最优路径中的每个城市：
τ(t+1)=(1−ρ)τ(t)+∑Δτ+eΔτ^(bs)
Δτ^(bs)=1/L
其中L代表最优路径长度，e是一个参数，表示权值大小。
目前解决TSP问题最好的蚁群算法之一，在蚂蚁系统的基础上进行了如下更改：
对于一般城市： τ(t+1)=(1−ρ)τ(t)
对于最优路径上的城市：τ(t+1)=(1−ρ)τ(t)+∑Δτ