基于ACO蚁群算法的tsp优化问题matlab仿真

时间：2023-01-23 22:56:39

1.算法描述 “基本原理 蚁群算法(Ant Colony Optimization,ACO)是一种基于种群寻优的启发式搜索算法,有意大利学者M.Dorigo等人于1991年首先提出。该算 法受到自然界真实蚁群集体在觅食过程中行为的启发,利用真实蚁群通过个体间的信息传递、搜索从蚁穴到食物间的最短路径等集体寻优特 征,来解决一些离散系统优化中的困难问题。

   算法基本思想：

（1）根据具体问题设置多只蚂蚁，分头并行搜索。

（2）每只蚂蚁完成一次周游后，在行进的路上释放信息素，信息素量与解的质量成正比。

（3）蚂蚁路径的选择根据信息素强度大小（初始信息素量设为相等），同时考虑两点之间的距离，采用随机的局部搜索策略。这使得距离较短的边，其上的信息素量较大，后来的蚂蚁选择该边的概率也较大。

（4）每只蚂蚁只能走合法路线（经过每个城市1次且仅1次），为此设置禁忌表来控制。

（5）所有蚂蚁都搜索完一次就是迭代一次，每迭代一次就对所有的边做一次信息素更新，原来的蚂蚁死掉，新的蚂蚁进行新一轮搜索。

（6）更新信息素包括原有信息素的蒸发和经过的路径上信息素的增加。

（7）达到预定的迭代步数，或出现停滞现象（所有蚂蚁都选择同样的路径，解不再变化），则算法结束，以当前最优解作为问题的最优解。

  将各个蚂蚁随机地置于不同的出发地，对每个蚂蚁k ( k = 1 , 2 , ⋯  , m ) ，按照轮盘赌法得到下面的转移概率公式计算其下一个待访问的城市，直到所有蚂蚁访问完所有的城市。

基于ACO蚁群算法的tsp优化问题matlab仿真

2.仿真效果预览 matlab2022a仿真结果如下：

基于ACO蚁群算法的tsp优化问题matlab仿真基于ACO蚁群算法的tsp优化问题matlab仿真 3.MATLAB核心程序

CityNum=30;
[dislist,Clist]=tsp(CityNum);
 
Tlist=zeros(CityNum);%禁忌表(tabu list)
cl=100;%保留前cl个最好候选解
bsf=Inf;
tl=50; %禁忌长度(tabu length)
l1=200;%候选解(candidate),不大于n*(n-1)/2(全部领域解个数)
S0=randperm(CityNum);
S=S0;
BSF=S0;
Si=zeros(l1,CityNum);
StopL=200; %终止步数
p=1;
clf;
figure(1);
 
while (p<StopL+1)
    if l1>CityNum*(CityNum)/2
        disp('候选解个数,不大于n*(n-1)/2(全部领域解个数)！ 系统自动退出！');
        l1=(CityNum*(CityNum)/2)^.5;
        break;
    end
    ArrS(p)=CalDist(dislist,S);        
    i=1;
    A=zeros(l1,2);
    while i<=l1        
        M=CityNum*rand(1,2);
        M=ceil(M);
        if M(1)~=M(2)
            m1=max(M(1),M(2));m2=min(M(1),M(2));
            A(i,1)=m1;A(i,2)=m2;
            if i==1
                isdel=0;
            else
                for j=1:i-1
                    if A(i,1)==A(j,1)&&A(i,2)==A(j,2)
                        isdel=1;
                        break;
                    else
                        isdel=0;
                    end
                end
            end
            if ~isdel
                i=i+1;
            else
                i=i;
            end
        else 
            i=i;
        end
    end
    
    for i=1:l1
        Si(i,:)=S;
        Si(i,[A(i,1),A(i,2)])=S([A(i,2),A(i,1)]);
        CCL(i,1)=i;
        CCL(i,2)=CalDist(dislist,Si(i,:));
        CCL(i,3)=S(A(i,1));
        CCL(i,4)=S(A(i,2));   
    end
    [fs fin]=sort(CCL(:,2));
    for i=1:cl
        CL(i,:)=CCL(fin(i),:);
    end
    
    if CL(1,2)<bsf  %藐视准则(aspiration criterion)
        bsf=CL(1,2);
        S=Si(CL(1,1),:);        
        BSF=S;
        for m=1:CityNum
            for n=1:CityNum
                if Tlist(m,n)~=0
                    Tlist(m,n)=Tlist(m,n)-1;
                end
            end
        end
        Tlist(CL(1,3),CL(1,4))=tl;
    else  
        for i=1:cl
            if Tlist(CL(i,3),CL(i,4))==0
                S=Si(CL(i,1),:);
                for m=1:CityNum
                    for n=1:CityNum
                        if Tlist(m,n)~=0
                            Tlist(m,n)=Tlist(m,n)-1;
                        end
                    end
                end
                Tlist(CL(i,3),CL(i,4))=tl;
                break;
            end
        end
    end
    
    Arrbsf(p)=bsf;
    drawTSP(Clist,BSF,bsf,p,0);
    p=p+1;
end
BestShortcut=BSF
theMinDistance=bsf
 
figure(2);
plot(Arrbsf,'r'); hold on;
plot(ArrS,'b');grid;
title('搜索过程');
legend('最优解','当前解');
A_073
标签：

相关文章