蚁群算法解决旅行商(TSP)问题

使用蚁群算法解决旅行商问题步骤如下:

  1. 初始化参数。
  2. 将蚂蚁随机的放在城市上。
  3. 蚂蚁各自按概率选择下一座城市。
  4. 蚂蚁完成各自的周游。
  5. 更新信息素,进行下一次迭代。

在更新信息素的过程中,只有最优路线上的信息素会进行增加操作,且不能超过信息素最大值。

结果如下:

最短路径变化图

蚁群算法找到的最优路径

主函数

主函数如下:

clc;
clear;

pos = load('berlin52.txt'); % 7542
pos = pos(:, 2:3);
pos = pos';

dm = makeDistanceMatrix(pos);           % 距离矩阵
n = size(dm, 1);        % 城市个数
m = 80;                 % 蚂蚁个数
alpha = 1.4;            % 信息素重要程度
beta = 2.2;             % 启发式因子重要程度
rho = 0.15;             % 信息素挥发系数
Q = 10^6;               % 信息素增加强度
eta = makeEta(dm);      % 启发因子,为距离的倒数
tau = ones(n, n);       % 信息素矩阵
taumax = 1;             % 信息素上界

maxgen = 120;
path = zeros(m, n);
bestpath = zeros(maxgen, n);

for gen = 1:maxgen
    % 随机生成第1个城市
    for i = 1:m
        path(i, :) = randperm(n);
    end
    for i = 1:m
        % 确定后续城市
        for j = 2:n
            surepath = path(i, 1:j-1);
            testcities = path(i, j:n);
            city = surepath(end);
            % 使用轮盘赌法进行选择
            [nextcity, lastcities] =  ...
                getNextCity(city, testcities, tau, alpha, eta, beta);
            path(i, :) = [surepath nextcity lastcities];
        end
    end
    % 记录最优路线
    len = callength(path, dm);
    [~, minindex] = min(len);
    bestpath(gen, :) = path(minindex, :);

    % 更新信息素
    bpath = path(minindex, :);
    blen = len(minindex);
    tau = updateTau(tau, rho, Q, taumax, bpath, blen);
end
len = callength(bestpath, dm);
[~, minindex] = min(len);
bpath = bestpath(minindex, :);
plotroute(pos, bpath);

figure();
plot([1:1:maxgen], len');

一些其他函数

轮盘赌法求下一个城市的方法如下:

function [nextcity, lastcities] = getNextCity(city, testcities, tau, alpha, eta, beta)
% 使用轮盘赌法给出下一个城市
% city          input  当前城市
% testcities    input  待选城市
% tau           input  信息素矩阵
% alpha         input  信息素重要程度
% eta           input  启发式因子矩阵
% beta          input  启发式因子重要程度
% nextcity      output 下一个城市
% lastcities    output 待选城市
p = tau(city, testcities) .^ alpha .* eta(city, testcities) .^ beta;
p = p / (sum(p));
p = cumsum(p);
index = find(p >= rand);
nextcity = testcities(index(1));
lastcities = testcities(testcities ~= nextcity);
end

更新信息素矩阵的函数如下:

function ntau = updateTau(tau, rho, q, taumax, bestpath, bestlen)
% 更新信息素矩阵,只有最优路径上的信息素会被增加
% tau           input  信息素矩阵
% rho           input  信息素挥发系数
% q             input  信息素增加系数
% taumax        input  信息素上限
% bestpath      input  最优路径
% bestlen       input  最优路径长度
% ntau          output 更新后的信息素矩阵
n = size(tau, 1);
ntau = (1 - rho) .* tau;
for i = 2:n
    city1 = bestpath(i-1);
    city2 = bestpath(i);
    ntau(city1, city2) = ntau(city1, city2) + q / bestlen;
    ntau(city2, city1) = ntau(city2, city1) + q / bestlen;
end
ntau(ntau > taumax) = taumax;
end

制作距离矩阵的函数如下:

function dm = makeDistanceMatrix(pos)
% 制作距离矩阵
% pos       input  城市坐标
% dm        output 距离矩阵
[~, len] = size(pos);
deltax = repmat(pos(1,:)', 1, len) - repmat(pos(1,:), len, 1);
deltay = repmat(pos(2,:)', 1, len) - repmat(pos(2,:), len, 1);
dm = round((deltax .^ 2 + deltay .^ 2) .^ 0.5);
end

制作启发式因子矩阵的函数如下:

function eta = makeEta(dm)
% 制作启发式因子的倒数,是距离矩阵的倒数
% dm            input  距离矩阵
% eta           output 启发式因子矩阵
[rn, cn] = size(dm);
dm = dm + ones(rn, cn); % 加1以防止除0
eta = 1 ./ dm;
end

求路径距离的函数如下:

function len = callength(pop, dm)
% 求路径距离
% pop           input  种群
% dm            input  距离矩阵
% len           output 距离
[NP, D] = size(pop);
pop = [pop pop(:,1)];
sum = zeros(NP, 1);
for i = 1:NP
    for j = 1:D
        sum(i,1) = sum(i,1) + dm(pop(i, j), pop(i, j+1));
    end
end
len = sum;
end

绘制路径的函数如下:

function plotroute(pos, v)
% 绘制路径
% pos           input  城市坐标点
% v             input  城市序列
figure();
plot(pos(1,:), pos(2,:), 'bo');
hold on;
for i = 1:(size(v,2)-1)
    x1 = pos(1,v(i)); y1 = pos(2,v(i));
    x2 = pos(1,v(i+1)); y2 = pos(2,v(i+1));
    plot([x1, x2], [y1, y2], 'b');
    hold on;
end
plot([pos(1,v(end)), pos(1,v(1))], [pos(2,v(end)), pos(2,v(1))], 'b');
hold off;
end

发表评论

电子邮件地址不会被公开。 必填项已用*标注