蚁群算法解决旅行商（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 nextcitylastcities];

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 = [poppop(:,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

绘制路径的函数如下：

functionplotroute(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