蚁群算法商旅问题matlab程序

%%蚁群算法商旅问题matlab程序 %%导入数据(城市的坐标)

citys=[1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1229;4196 1004;4312 790;4386 570;3007 1970;2562 1756;2788 1676;1332 695;3715 1678;3918 2179;4061 2370;3780 2212;3676 2838;4263 2931;3429 1908;3507 2367;3394 2643;3439 3201;2935 3550;2545 2357;2778 2826;2370 2975];

%%计算城市之间相互距离 n=size(citys,1); D=zeros(n,n); for i=1:n for j=1:n if i~=j

D(i,j)=sqrt(sum((citys(i,:)-citys(j,:)).^2)); else

D(i,j)=1e-4; end end end

%%初始化参数 m=31; alpha=1; beta=5; rho=0.1; Q=1; Eta=1./D;

Tau=ones(n,n); Table=zeros(n,n); iter=1;

iter_max=200;

Route_best=zeros(iter_max,n); Leng_best=zeros(iter_max,1); Leng_ave=zeros(iter_max,1);

%%迭代寻找最佳路径（主体循环） while iter<=iter_max

%（1）随机产生各个蚂蚁的起点城市 start=zeros(m,1); for i=1:m

temp=randperm(n); start(i)=temp(1); end

1556;3238 1491;2381 2578;4029 3240;3140

Table(:,1)=start;

%（2）构建解空间 citys_index=1:n;

for i=1:m %逐个蚂蚁路径选择 for j=2:n %逐个城市路径选择

tabu=Table(i,1:(j-1)); %已访问的城市集合（禁忌表） allow_index=~ismember(citys_index,tabu);

allow=citys_index(allow_index); %待访问的城市集合 P=allow;

%计算城市间转移概率 for k=1:length(allow)

P(k)=Tau(tabu(end),allow(k))^alpha*Eta(tabu(end),allow(k))^beta; end

P=P/sum(P);

%轮盘赌法选择下一个访问城市 Pc=cumsum(P);

target_index=find(Pc>=rand); target=allow(target_index(1)); Table(i,j)=target; end end

%（3）计算各个蚂蚁的路径距离 Length=zeros(m,1); for i=1:m

Route=Table(i,:); for j=1:(n-1)

Length(i)=Length(i)+D(Route(j),Route(j+1)); end

Length(i)=Length(i)+D(Route(n),Route(1)); end

%（4）计算最短路径距离及平均距离 if iter==1

[min_Length,min_index]=min(Length); Length_best(iter)=min_Length; Length_ave(iter)=mean(Length);

Route_best(iter,:)=Table(min_index,:); else

[min_Length,min_index]=min(Length);

Length_best(iter)=min(Length_best(iter-1),min_Length); Length_ave(iter)=mean(Length); if Length_best(iter)==min_Length

Route_best(iter,:)=Table(min_index,:); else

Route_best(iter,:)=Route_best((iter-1),:);

end end

%（5）更新信息素

Delta_Tau=zeros(n,n);

%逐个蚂蚁计算 for i=1:m

%逐个城市计算 for j=1:(n-1)

Delta_Tau(Table(i,j),Table(i,j+1))=Delta_Tau(Table(i,j),Table(i,j+1))+Q/Length(i); end

Delta_Tau(Table(i,n),Table(i,1))=Delta_Tau(Table(i,j),Table(i,1))+Q/Length(i); end

Tau=(1-rho)*Tau+Delta_Tau;

%迭代次数加1，清空路径记录表 iter=iter+1;

Table=zeros(m,n); end

%%结果显示

[Shortest_Length,index]=min(Length_best); Shortest_Route=Route_best(index,:);

disp(['最短距离：' num2str(Shortest_Length)]);

disp(['最短路径：' num2str([Shortest_Route Route_best(1)])]);

%%绘图 figure(1)

plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],[citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'b-'); grid on

for i=1:size(citys,1)

text(citys(i,1),citys(i,2),[' ' num2str(i)]); end

text(citys(Shortest_Route(1),1),citys(Shortest_Route(1),2),'起点');

text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),'终点'); xlabel('城市位置横坐标') ylabel('城市位置纵坐标') figure(2)

plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r') legend('最短距离','平均距离''') xlabel('迭代次数') ylabel('距离')

text('各代最短距离与平均距离对比')

本文来源：https://www.bwwdw.com/article/rqkf.html