蚁群算法求解旅行商最优路径问题

利用MATLAB语言实现蚁群算法求解旅行商最优路径问题

function [R_bestL_bestL_aveShortest_RouteShortest_Length]=aca_tsp（CNC_maxmAlphaBetaRhoQ）
%%  主要符号说明
% C n个城市的坐标，n*2的矩阵
% NC_max：蚁群算法MATLAB程序最大迭代次数
% m：蚂蚁个数
% Alpha：表征信息素重要程度的参数
% Beta：表征启发式因子重要程度的参数
% Rho：信息素蒸发系数
% Q：表示信息素增加强度系数
% R_best：各代最佳路线
% L_best：各代最佳路线的长度

% 变量初始化
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（1n-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
        Tabu（1:）=R_best（NC-1:）;
    end
    % 记录本次迭代最佳路线
    L=zeros（m1）;
    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（1）R（n））;
    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;
    % 更新信息素
    Delta_Tau=zeros（nn）;
    for i=1:m
        for j=1:（n-1）
            Delta_Tau（Tabu（ij）Tabu（ij+1））=Delta_Tau（Tabu（ij）Tabu（ij+1））+Q/L（i）;
            % 此次循环在路径 （ij） 上的信息素增量
        end
        Delta_Tau（Tabu（in）Tabu（i1））=Delta_Tau（Tabu（in）Tabu（i1））+Q/L（i）;
        % 此次循环在整个路径上的信息素增量
    end
    Tau=（1-Rho）.*Tau+Delta_Tau;  % 考虑信息素挥发，更新后的信息素
    % 禁忌表清零
    Tabu=zeros（mn）;
end



NC
% 输出结果
Pos=find（L_best==min（L_best））;
Shortest_Route=R_best（Pos（1）:）
Shortest_Length=L_best（Pos（1））
subplot（121）
draw_route（CShortest_Route）  % 画路线图
subplot（122）
plot（L_best）
hold on
plot（L_ave‘r‘）
title（‘平均距离和最短距离‘）

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2016-07-02 16:32  ACO_TSP\
     文件        3196  2016-06-13 15:15  ACO_TSP\aco_tsp.m
     文件         274  2016-06-11 15:15  ACO_TSP\draw_route.m
     文件         690  2016-07-02 16:31  ACO_TSP\test_aco_tsp.m