蚁群算法-TSP旅行商

本实验利用蚁群算法，对TSP旅行商问题进行应用和优化。 随机生成不同的城市序列。 选取不同的参数，验证蚁群算法的效率。 对蚁群算法进行改进，改造成精英蚂蚁算法，并进行分析。 输入：不同维度的城市序列 输出：最优路径所经过的城市序列以及最优路径长度。

%% 旅行商问题（TSP）优化
%% 清空环境变量
clear all
clc
tic%计算运行事件
%% 导入数据
%load citys_data.mat
load data
citys=city30;
%% 计算城市间相互距离
fprintf（‘Computing Distance Matrix... \n‘）;
n = size（citys1）;%一共多少个城市
D = zeros（nn）;%邻接矩阵
for i = 1:n
    for j = 1:n
        if i ~= j %判断 i 的值是否等于j，若等于1，则返回0；否则，返回1
            D（ij） = sqrt（sum（（citys（i:） - citys（j:））.^2））;%存放第i点到第j点的距离（一次计算一个点）
        else
            D（ij） = 1e-4; %i==j处，（1.0000e-04）对角线 （两侧对称）
        end
    end
end

%% 初始化参数
fprintf（‘Initializing Parameters... \n‘）;
m = 30;                              % 蚂蚁数量
alpha = 1;                           % 信息素重要程度因子
beta = 2;                            % 启发函数重要程度因子
rho = 0.7;                           % 信息素挥发因子
Q = 1;                               % 常系数
Eta = 1./D;                          % 启发函数
Tau = ones（nn）;                     % 信息素矩阵 %初始化为全1矩阵
Table = zeros（mn）;                  % 路径记录表
iter = 1;                            % 迭代次数初值
iter_max = 150;                      % 最大迭代次数
Route_best = zeros（iter_maxn）;      % 各代最佳路径
Length_best = zeros（iter_max1）;     % 各代最佳路径的长度
Length_ave = zeros（iter_max1）;      % 各代路径的平均长度

e=0.3;
%% 迭代寻找最佳路径
figure;
while iter <= iter_max
    %%
    flag=0;
    %%
    fprintf（‘迭代第%d次\n‘iter）;
    % 随机产生各个蚂蚁的起点城市
    start = zeros（m1）; %m*1的全0矩阵
    for i = 1:m
        temp = randperm（n）; %1*n矩阵 随机打乱一个数字序列（1-n）
        start（i） = temp（1）; %当前随机城市
    end
    Table（:1） = start; %放入第一列
    % 构建解空间
    citys_index = 1:n;%1*n矩阵（1-n）
    for i = 1:m %第i只蚂蚁
        % 逐个城市路径选择
        for j = 2:n %从第2个城市开始，第1个城市已经随机生成
            tabu = Table（i1:（j - 1））;           % 已访问的城市集合（禁忌表）
            %~ismember（citys_indextabu）是看矩阵citys_index中的数是不是矩阵citys_index中的成员，是的话结果返回0，不是返回1
            allow_index = ~ismember（citys_indextabu）;%访问过的地方未0
            allow = citys_index（allow_index）;  % 待访问的城市集合（访问过的城市删掉了，因为为0）
            P = allow;
            % 计算城市间转移概率
            %剩下的城市
            for k = 1:length（allow）
                P（k） = Tau（tabu（end）allow（k））^alpha * Eta（tabu（end）allow（k））^beta;%tabu（end）当前城市
            end
            P = P/sum（P）;
            % 轮盘赌法选择下一个访问城市
            Pc = cumsum（P）;
            %Pc（1）为1.7665e-05 其实为0.0000，为了防止错位变成一个很小的值 sum（P）=1
            target_index = find（Pc >= rand）; %备选城市（满足条件的，不是剩下的所有城市）
            target = allow（target_index（1））;%访问备选城市中的第一个
            Table（ij） = target;%接下来要访问的城市
        end
    end
    % 计算各个蚂蚁的路径距离
    Length = zeros（m1）;%m*1矩阵
    for i = 1:m %第i只蚂蚁
        Route = Table（i:）; %保存当前蚂蚁的路径
        for j = 1:（n - 1）
            Length（i） = Length（i） + D（Route（j）Route（j + 1））;
        end
        Length（i） = Length（i） + D（Route（n）Route（1））; %m*1矩阵，保存每只蚂蚁的总路径
    end
    % 计算最短路径距离及平均距离
    %第iter代蚂蚁
    if iter == 1
        [min_Lengthmin_index] = min（Length）;
        Length_best（iter） = min_Length;
        Length_ave（iter） = mean（Length）;
        Route_best（iter:） =

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-12-13 10:09  sy_蚁群算法\
     目录           0  2018-12-13 10:09  sy_蚁群算法\ACO\
     目录           0  2018-12-19 22:54  sy_蚁群算法\ACO\ACO\
     文件        6364  2018-12-19 21:48  sy_蚁群算法\ACO\ACO\ACO.m
     文件         309  2013-08-15 08:34  sy_蚁群算法\ACO\ACO\citys_data.mat
     文件        1024  2018-12-18 14:31  sy_蚁群算法\ACO\ACO\data.mat
     文件         240  2018-12-18 14:31  sy_蚁群算法\ACO\ACO\testcity.m