function ACO()
%用蚂蚁算法求解TSP问题,采用蚁周模型。
%数学0705班，江云胜，200712031，200年11月1号
CityPos=10*rand(30,2); %随机生成10座城市的坐标，也可以直接赋值。
MaxTime=100; %最大迭代次数
[CityNum temp]=size(CityPos); %返回城市的个数
tao=ones(CityNum,CityNum); %初始信息素浓度
Q=100;
rho=0.2; %挥发因子
alpha=1;
beta=5;
AntNum=10; %蚂蚁数量
for i=1:CityNum
for j=1:CityNum
Distance(i,j)=sqrt((CityPos(i,1)-CityPos(j,1))^2+(CityPos(i,2)-CityPos(j,2))^2); %城市间的距离
end
end
BestLength=inf; %初始化最优路径长度
for time=1:MaxTime
for k=1:AntNum
[k_route k_length]=travel(Distance,tao,alpha,beta,k);
k_length
if k_length<BestLength
BestRoute=k_route;
BestLength=k_length
end
end
delta_tao=zeros(CityNum,CityNum);
for i=1:CityNum-1
delta_tao(BestRoute(i),BestRoute(i+1))=Q/BestLength; %最优路径上的信息素浓度要修改
end
delta_tao(BestRoute(CityNum),BestRoute(1))=Q/BestLength;
delta_tao=delta_tao+delta_tao';
tao=(1-rho).*tao+delta_tao; %修改信息素浓度
end
disp('%%%%%%%%%%%%%%%%%%%%%%%%%%%');
fprintf('\n最佳路径:\n')
fprintf('BestRoute: ')
for i=1:length(BestRoute)
fprintf('%d-->',BestRoute(i));
end
fprintf('%d .\n\n',BestRoute(1));
fprintf('\n\n最佳路径长度：%f\n\n',BestLength);
disp('%%%%%%%%%%%%%%%%%%%%%%%%%%%');
figure
plot(CityPos(BestRoute,1),CityPos(BestRoute,2));
hold on
plot(CityPos(BestRoute([1,CityNum]),1),CityPos(BestRoute([1,CityNum]),2));
plot(CityPos(:,1),CityPos(:,2),'r*')
title('最佳路径')
end
%蚂蚁从StartCity出发，周游所有城市，返回路径Route和路径长度Length。
function [Route Length]=travel(Distance,tao,alpha,beta,StartCity)
[Num,n]=size(Distance);
% StartCity=fix(Num*rand)+1; %蚂蚁的出发城市也可以是随机的。
PassedCity=[StartCity]; %初始化已走过城市名单
Length=0; %初始化路径长度
for i=1:Num-1
NowCity=PassedCity(end);
p_next=zeros(1,Num);
for j=1:Num
if ismember(j,PassedCity) %判断该城市是否已走过。
continue;
else
eta=1/Distance(NowCity,j);
p_next(j)=tao(NowCity,j)^alpha*eta^beta;
end
end
NextCity=Choice(p_next); %选择下一个城市
PassedCity=[PassedCity NextCity]; %将下一个城市加入到已走过城市名单中。
Length=Length+Distance(NowCity,NextCity); %修改路径长度
end
Route=PassedCity;
Length=Length+Distance(Route(end),Route(1));
end
%采用赌轮法选择下一个城市
function NextCity=Choice(p_next)
NextCity=size(p_next,2);
p_next=p_next/sum(p_next);
p=rand; %随机生成一个0和1之间的数
for next=1:length(p_next)
if (p>=sum(p_next(1:next-1)))&(p<sum(p_next(1:next)))
NextCity=next;
break;
end
end
end
TSP.rar_tsp_蚂蚁算法_蚂蚁算法 tsp
版权申诉
85 浏览量
2022-09-24
02:49:00
上传
评论
收藏 108KB RAR 举报
TSP.rar （11个子文件） 
蚂蚁算法解TSP问题 
20个城市.JPG 32KB 25个城市.JPG 32KB
_25个城市.fig 3KB _10个城市.fig 3KB _20个城市.fig 3KB 10个城市.JPG 29KB 30个城市.JPG 35KB 15个城市.JPG 29KB ACO.m 3KB _15个城市.fig 3KB _30个城市.fig 4KB
评论0