antcolonyalgorithmfortspproblem.txt

蚁群算法求解TSP问题的源程序及简要说明

1 54 67
2 54 62
3 37 84
4 41 94
5 2 99
6 7 64
7 25 62
8 22 60
9 18 54
10 4 50
11 13 40
12 18 40
13 24 42
14 25 38
15 44 35
16 41 26
17 45 21
18 58 35
19 62 32
20 82 7
21 91 38
22 83 46
23 71 44
24 64 60
25 68 58
26 83 69
27 87 76
28 74 78
29 71 71
30 58 69 

best_length = 423.7406; %整数距离为420

best_path = [2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
21 22 23 25 24 26 27 28 29 30]; 

[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 25 24 26 27 28 29 30]

整数距离也为420
常数距离为423.9117 

急求oliver30 TSP的数据 





蚁群算法求解TSP问题的源程序及简要说明


该程序试图对具有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=data(:,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=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_head(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))<=QV; 
gama(cur_pos(i),rn(k))=(sumload+g(rn(k)))/QV; 
A(n)=rn(k); 
n=n+1; 
end; 
end; 

fid=fopen('out_customer.txt','a+'); 
fprintf(fid,'%s %i\t','the current position is:',cur_pos(i)); 
fprintf(fid,'\n%s','the possible customer set is:') 
fprintf(fid,'\t%i\n',A); 
fprintf(fid,'------------------------------\n'); 
fclose(fid); 

p=compute_prob(A,cur_pos(i),tao,miu,alpha,belta,gama,lmda,i); 
maxp=1e-8; 
na=length(A); 
for j=1:na; 
if p(j)>maxp 
maxp=p(j); 
index_max=j; 
end; 
end; 

old_pos=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; 
part_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,'条路径是:'); 
fprintf(fid,'%i ',part_sol); 
fprintf(fid,'\n'); 
fprintf(fid,'%s','当前的用户需求量是:'); 
fprintf(fid,'%i\n',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; 
final_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_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=best_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_solution(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 %i\n','当前的用户需求量是:',temp_load); 
fprintf(fid,'%s %f\n','总费用是:',cost(n_gen,i)); 
fprintf(fid,'------------------------------\n'); 
fprintf(fid,'%s\n','最终路径是:'); 
fprintf(fid,'%i-',temp); 
fprintf(fid,'\n'); 
fclose(fid); 
temp=[]; 
break; 
end; 
end; 

end; 
end; 
我现在也在研究它,希望能共同进步.建义可以看一下段海滨的关于蚁群算法的书.讲的不错,李士勇的也可以,还有一本我在图书馆见过,记不得名字了.



简单蚁群算法求解TSP的源程序(我帮你找的) 

蚁群算法是新兴的仿生算法，最初是由意大利学者Dorigo M于1991年首次提出，由于具有较强的鲁棒性，优良的分布式计算机制和易于与其它方法结合等优点，成为人工智能领域的一个研究热点。本程序是实现简单的蚁群算法，TSP问题取的是att48，可从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.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 ka=1:mant %考查第K只蚂蚁 
deltatao=zeros(48,48); % 第K只蚂蚁移动前各边上的信息增量为零 
[routek,lengthk]=travel(distance,tao,alpha,beta); 
if lengthk<routelength % 找到一条更好的路径 
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 
deltatao(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*rand)+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*ada^beta; 
end 
end 
cp=zeros(1,m); % 转移概率 
for j=1:m 
if isin(j,tabuk) 
continue; 
else 
ada=1/distance(np,j); 
cp(j)=tao(np,j)^alpha*ada^beta/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)+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