function PSOforTSP 
%初始化
Alpha=0.25; %個體經驗保留概率
Beta=0.25; %全局經驗保留概率 
NC_max=200; %最大迭代次數
m=80;  %微粒數
CityNum=10;  %問題的規模（城市個數）
[dislist,Clist]=tsp(CityNum);

NC=1;%迭代計數器
R_best=zeros(NC_max,CityNum); %各代最佳路線
L_best=inf.*ones(NC_max,1);%各代最佳路線的長度
L_ave=zeros(NC_max,1);%各代路線的平均長度

%產生微粒的初始位置
for i=1:m
    x(i,:)=randperm(CityNum);
    L(i)=CalDist(dislist,x(i,:));
end
p=x; %p為個體最好解
pL=L;
[L_best(1,1) n_best]=min(L);
R_best(1,:)=x(n_best,:);
L_ave(1,1)=mean(L);

%初始交換序
v=ones(CityNum-1,2,m)*(round(rand*(CityNum-1))+1);

figure(1);
while NC<=NC_max %停止條件之一：達到最大迭代次數
    for i=1:m
        xnew(i,:)=changeFun(x(i,:),v(:,:,i));
        A=changeNum(x(i,:),p(i,:));
        Arand=randFun(A,Alpha);
        xnew(i,:)=changeFun(xnew(i,:),Arand);
        B=changeNum(x(i,:),R_best(NC,:));
        Brand=randFun(B,Beta);
        xnew(i,:)=changeFun(xnew(i,:),Brand);
        v(:,:,i)=changeNum(x(i,:),xnew(i,:));
        L(i)=CalDist(dislist,xnew(i,:));
        if L(i)<pL(i)
            p(i,:)=xnew(i,:);
            pL(i)=L(i);
        end
    end
    [L_bestnew n_best]=min(L);
    R_bestnew=xnew(n_best,:);
    L_ave(NC+1,1)=mean(L);
    if L_bestnew<L_best(NC,1)
        L_best(NC+1,1)=L_bestnew;
        R_best(NC+1,:)=R_bestnew;
    else
        L_best(NC+1,1)=L_best(NC,1);
        R_best(NC+1,:)=R_best(NC,:);
    end
    x=xnew;
    drawTSP10(Clist,R_best(NC,:),L_best(NC,1),NC,0);
    %pause;
    NC=NC+1;
end

%輸出結果
Pos=find(L_best==min(L_best));
Shortest_Route=R_best(Pos(1),:);
Shortest_Length=L_best(Pos(1));
figure(2);
plot([L_best L_ave]);
legend('最短距離','平均距離');
end

function xnew=changeFun(x,C);
changeLen=size(C,1);
xnew=x;
for i=1:changeLen
    a=xnew(C(i,1));
    xnew(C(i,1))=xnew(C(i,2));
    xnew(C(i,2))=a;
end
end

function C=changeNum(x,y);
CityNum=size(x,2);
C=ones(CityNum-1,2);
for i=1:CityNum-1
    pos=find(x==y(i));
    C(i,:)=[i pos];
    x=changeFun(x,C(i,:));
end
end

function v=randFun(v,w);
randLen=size(v,1);

for i=1:randLen
    if rand>w
        v(i,2)=v(i,1);
    end
end    
end