蚁群算法求解TSP最短路径规划

旅行商问题(Traveling Saleman Problem，TSP)是车辆路径调度问题(VRP)的特例，由于数学家已证明TSP问题是NP难题，因此，VRP也属于NP难题。旅行商问题（TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。

function [R_bestL_bestL_aveShortest_RouteShortest_Length]=ACATSP（CNC_maxmAlphaBetaRhoQ）
%%第一步：变量初始化
n=size（C1）;%n表示问题的规模（城市个数）
D=zeros（nn）;%D表示完全图的赋权邻接矩阵
for i=1:n
    for j=1:n
        if i~=j
            D（ij）=（（C（i1）-C（j1））^2+（C（i2）-C（j2））^2）^0.5;
        else
            D（ij）=eps;
        end
        D（ji）=D（ij）;
    end
end

Eta=1./D;%Eta为启发因子，这里设为距离的倒数
Tau=ones（nn）;%Tau为信息素矩阵
Tabu=zeros（mn）;%存储并记录路径的生成
NC=1;%迭代计数器
R_best=zeros（NC_maxn）;%各代最佳路线
L_best=inf.*ones（NC_max1）;%各代最佳路线的长度
L_ave=zeros（NC_max1）;%各代路线的平均长度

while NC<=NC_max%停止条件之一：达到最大迭代次数
    %%第二步：将m只蚂蚁放到n个城市上
    Randpos=[];
    for i=1:（ceil（m/n））
        Randpos=[Randposrandperm（n）];
    end
    Tabu（:1）=（Randpos（11:m））‘;
    %%第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的周游
    for j=2:n
        for i=1:m
            visited=Tabu（i1:（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（ij）=to_visit;
        end
    end
    if NC>=2