使用蚁群算法解决旅行商问题步骤如下：
初始化参数。
将蚂蚁随机的放在城市上。
蚂蚁各自按概率选择下一座城市。
蚂蚁完成各自的周游。
更新信息素，进行下一次迭代。
在更新信息素的过程中，只有最优路线上的信息素会进行增加操作，且不能超过信息素最大值。
结果如下：
最短路径变化图
蚁群算法找到的最优路径
主函数
主函数如下：
clc;
clear;
pos = load('berlin52.txt'); % 7542pos = 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);endlen = 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;endntau(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以防止除0eta = 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)); endendlen = 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;endplot([pos(1,v(end)), pos(1,v(1))], [pos(2,v(end)), pos(2,v(1))], 'b'); hold off;end
作者：mwangjs
链接：https://www.jianshu.com/p/f7ff8e3933be