使用蟻群算法解決旅行商問題步驟如下：
- 初始化參數(shù)劈彪。
- 將螞蟻隨機的放在城市上。
- 螞蟻各自按概率選擇下一座城市筝野。
- 螞蟻完成各自的周游培他。
- 更新信息素鹃两，進行下一次迭代。
在更新信息素的過程中舀凛，只有最優(yōu)路線上的信息素會進行增加操作俊扳，且不能超過信息素最大值。
結果如下：
最短路徑變化圖
蟻群算法找到的最優(yōu)路徑
主函數(shù)
主函數(shù)如下：
clc;
clear;
pos = load('berlin52.txt'); % 7542
pos = pos(:, 2:3);
pos = pos';
dm = makeDistanceMatrix(pos); % 距離矩陣
n = size(dm, 1); % 城市個數(shù)
m = 80; % 螞蟻個數(shù)
alpha = 1.4; % 信息素重要程度
beta = 2.2; % 啟發(fā)式因子重要程度
rho = 0.15; % 信息素揮發(fā)系數(shù)
Q = 10^6; % 信息素增加強度
eta = makeEta(dm); % 啟發(fā)因子猛遍，為距離的倒數(shù)
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
% 確定后續(xù)城市
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
% 記錄最優(yōu)路線
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');
一些其他函數(shù)
輪盤賭法求下一個城市的方法如下：
function [nextcity, lastcities] = getNextCity(city, testcities, tau, alpha, eta, beta)
% 使用輪盤賭法給出下一個城市
% city input 當前城市
% testcities input 待選城市
% tau input 信息素矩陣
% alpha input 信息素重要程度
% eta input 啟發(fā)式因子矩陣
% beta input 啟發(fā)式因子重要程度
% 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
更新信息素矩陣的函數(shù)如下：
function ntau = updateTau(tau, rho, q, taumax, bestpath, bestlen)
% 更新信息素矩陣馋记，只有最優(yōu)路徑上的信息素會被增加
% tau input 信息素矩陣
% rho input 信息素揮發(fā)系數(shù)
% q input 信息素增加系數(shù)
% taumax input 信息素上限
% bestpath input 最優(yōu)路徑
% bestlen input 最優(yōu)路徑長度
% 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
制作距離矩陣的函數(shù)如下：
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
制作啟發(fā)式因子矩陣的函數(shù)如下：
function eta = makeEta(dm)
% 制作啟發(fā)式因子的倒數(shù)，是距離矩陣的倒數(shù)
% dm input 距離矩陣
% eta output 啟發(fā)式因子矩陣
[rn, cn] = size(dm);
dm = dm + ones(rn, cn); % 加1以防止除0
eta = 1 ./ dm;
end
求路徑距離的函數(shù)如下：
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
繪制路徑的函數(shù)如下：
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
