新建 文本文档 (3).txt

应用matlab解决tsp问题

附录1：Dijkstra算法程序
function [S，D]=dijk2(W，i，m)
% 图与网络论中求最短路径的Dijkstra算法M函数
%格式[S，D]=minroute(i，m，W)
% i为最短路径的起始点，m为图顶点数，W为图的带权邻接矩阵，
%不构成边的两顶点之间的权用inf表示。显示结果为：S的每一列从上到下记录了从始点到终点的最短路径所经顶点的序号；
% D是一行向量，记录了S中所示路径大小；
dd=[ ]；
tt=[ ]；
ss=[ ]；
ss(1，1)=i；  
V=1:m；
V(i)=[ ]；
dd=[0；i]；
% dd的第二行是每次求出的最短路径的终点，第一行是最短路径的值
kk=2；
[mdd，ndd]=size(dd)；
while ~isempty(V)
    [tmpd，j]=min(W(i，V))；
    tmpj=V(j)；
    for k=2:ndd
        [tmp1，jj]=min(dd(1，k)+W(dd(2，k)，V))；
        tmp2=V(jj)；
        tt(k-1，:)=[tmp1，tmp2，jj]；
    end
   tmp=[tmpd，tmpj，j；tt]；
   [tmp3，tmp4]=min(tmp( :，1))；
   if tmp3==tmpd
       ss(1:2，kk)=[i；tmp(tmp4，2)]；
   else
       tmp5=find(ss(:，tmp4)~=0)；
       tmp6=length(tmp5)；
       if dd(2，tmp4)==ss(tmp6，tmp4)
           ss(1:tmp6+1，kk)=[ss(tmp5，tmp4)；tmp(tmp4，2)]；
       else
            ss(1:3，kk)=[ss(2，tmp4)；tmp(tmp4，2)]；
        end
    end
    dd=[dd，[tmp3；tmp(tmp4，2)]]；
    V(tmp(tmp4，3))=[]；
    [mdd，ndd]=size(dd)；
    kk=kk+1；
end
S=ss；
D=dd(1，:)；

附录2：蚁群算法解决单旅行商问题的程序
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:[e-mail]
%% All rights reserved
%%-------------------------------------------------------------------------
%% 主要符号说明
%% C n个节点的邻接矩阵
%% NC_max 最大迭代次数
%% m 蚂蚁个数
%% Alpha 表征信息素重要程度的参数
%% Beta 表征启发式因子重要程度的参数
%% Rho 信息素蒸发系数
%% Q 信息素增加强度系数
%% R_best 各代最佳路线
%% L_best 各代最佳路线的长度
%%=========================================================================
n=size(C，1)；
D=C；%赋权值
Eta=1./D；
Tau=ones(n，n)；
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
Randpos=[]；
for i=1:(ceil(m/n))
 Randpos=[Randpos，randperm(n)]；
end
Tabu(:，1)=(Randpos(1，1: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(n)，R(1))；
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；
if mod(NC，50)==0
    NC
end
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))

附录3：蚁群算法解决带有约束条件的多旅行商问题的程序
function [R_best，L_best，L_ave，Shortest_Route，Shortest_Length]=ACATSP_dev(C，NC_max，m，Alpha，Beta，Rho，Q)
st=[8 13 6 9 7 15 10 5 12 9]；
n=size(C，1)； 
D=C； 
Eta=1./D； 
Tau=ones(n，n)； 
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
Randpos=[]；
for i=1:(ceil(m/n))
Randpos=[Randpos，randperm(n)]；
end
Tabu(:，1)=(Randpos(1，1: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，:)；
    R(find(R==11))=1；
    uu=find(R==1)；
    a1=[]；
    for l=uu(1):uu(2)
        a1=[a1 R(l)]；
    end
    a2=[]；
    for l=uu(2):(uu(1)+11)
        if mod(l，11)~=0
            a2=[a2 R(mod(l，11))]；
        else
            a2=[a2 R(mod(l，11)+11)]；
        end
    end
    L1=0；
    L2=0；
    for j=1:length(a1)-1
        L1=L1+D(a1(j)，a1(j+1))；
    end
    for j=1:length(a2)-1
        L2=L2+D(a2(j)，a2(j+1))；
    end
    pp1=0；
    pp2=0；
    if length(a1)~=2&&length(a2)~=2
        for j=2:length(a1)-1
            pp1=pp1+st(a1(j))；
        end
        for j=2:length(a2)-1
            pp2=pp2+st(a2(j))；
        end
        pp2=pp2+4；
        pp1=pp1+4；
        cc1=max(pp1-50-4，0)；
        cc2=max(pp2-50-4，0)；
        L(i)=L1+L2+1e8*(cc1+cc2)；
    else
        L(i)=1e10；
    end
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；
if mod(NC，50)==0
    NC
end
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))