蚁群算法解决TSP问题

clear all

close all

clc

C=[0.4 0.4439;0.2439 0.1463;0.1707 0.2293;0.2293 0.761;0.5171 0.9414;0.8732 0.6536;0.6878 0.5219;0.8488 0.3609;0.6683 0.2536;0.6195 0.2634];%**********

m=length(C(:,1));%蚂蚁数*******************

Nc_max=50;%最大循环次数

alpha=1;%信息素增量权重

beta=5;%启发因子权重

rho=0.8;%信息素挥发因子

Q=100;%信息素增量常数

n=size(C,1);%城市数量

D=ones(n,n);%城市之间的距离

for i=1:n

for j=1:n

if i<j%对角线上方元素

D(i,j)=sqrt((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2);

end

D(j,i)=D(i,j);

end

end

eta=1./D;%启发因子，取为城市之间距离的倒数

tao=ones(n,n);%信息素矩阵——————关键所在

tabu_list=zeros(m,n);%禁忌表，记录蚂蚁已经走过的城市

Nc=0;%循环次数记录器

route_best=zeros(Nc_max,n);%各次循环的最短路径

length_best=ones(Nc_max,1);%各次循环最短路径的长度

while Nc<Nc_max

%将m只蚂蚁放在n个城市上

ant_pos=randperm(n);%randperm随机打乱一个数字序列

tabu_list(:,1)=(ant_pos(1:m))';%m只蚂蚁的初始位置

for j=2:n

for i=1:m

city_visited=tabu_list(i,1:(j-1));

city_remained=zeros(1,(n-(j-1)));%尚未访问城市

prob=zeros(1,(n-(j-1)));%尚未访问城市概率初始化

cr=1;%尚未访问城市计数器

for k=1:n %搜索尚未访问的城市

if length(find(city_visited==k))==0

city_remained(cr)=k;

cr=cr+1;

end

end

%蚂蚁i访问城市k的概率

for k=1:length(city_remained)

ii=city_visited(end);

jj=city_remained(k);

prob(k)=(tao(ii,jj))^alpha*(eta(ii,jj))^beta;

end

prob=prob/sum(prob);

pcum=cumsum(prob);

select=find(pcum>=rand);

to_visit=city_remained(select(1));%第i只蚂蚁访问的下一个城市

tabu_list(i,j)=to_visit;

end

end

%记录本次循环的最佳路线

if Nc>0

tabu_list(1,:)=route_best(Nc,:);%将上一次的最短路径带入了下一次中进行比较----非常好

end

total_length=zeros(m,1);% m只蚂蚁走过的路径长

for i=1:m

r=tabu_list(i,:);%取出第i只蚂蚁在本次循环中所走的路径

for j=1:(n-1)

total_length(i)=total_length(i)+D(r(j),r(j+1));

end

total_length(i)=total_length(i)+D(r(1),r(n));%第i只蚂蚁走过的路径长度

end

[length_best(Nc+1),pos]=min(total_length);%本次循环的最短路程

route_best(Nc+1,:)=tabu_list(pos(1),:);%本次循环中的最短路径

%信息素增量

delta_tao=zeros(n,n);

for i=1:m

for j=1:(n-1)

ii=tabu_list(i,j);

jj=tabu_list(i,j+1);

delta_tao(ii,jj)=delta_tao(ii,jj)+Q/D(ii,jj);

end

ii=tabu_list(i,n);

jj=tabu_list(i,1);

delta_tao(ii,jj)=delta_tao(ii,jj)+Q/D(ii,jj);

end

%更新信息素表

tao=rho*tao+delta_tao;

%禁忌表清零

Nc=Nc+1;

tabu_list=zeros(m,n);

end

%输出结果

disp('********************************')

fprintf('l

ength_best=%f\

',length_best(Nc_max));

route_best=route_best(Nc_max,:)

disp('*******************************')