蚁群算法解决旅行商(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

原文发布于微信公众号 - mwangblog(mwangblog)

原文发表时间:2018-11-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ATYUN订阅号

一文读懂在深度学习中使用迁移学习的好处

迁移学习是一种使用为任务开发的模型做第二个任务模型起点的机器学习方法。使用预训练模型作计算机视觉和自然语言处理任务的起点是深度学习中一种流行的方法。因为在这些问...

79980

学习前馈神经网络的数学原理

在我上一篇博客中,我们讨论了人工神经网络的动机是来源于生理。这一篇博文,我们将讨论如何实现人工神经网络。在人工神经网络中,我们使用不同层数的网络来解决问题。使用...

219100
来自专栏奇点大数据

机器学习算法在自动驾驶汽车中扮演怎样的角色

随着电子控制单元传感器数据处理这项技术的继续发展,人们也越来越期待运用更优化的机器学习,来完成更多新挑战。未来的潜在应用场景包括:通过内外部传感器(包括激光雷达...

15610
来自专栏大数据挖掘DT机器学习

机器学习在实践中如何正确应用?

前阵子看到一篇文章,学习了一段时间的机器学习算法后,再回头看机器学习问题,发现要想利用机器学习去很好的求解一个问题,其实并不是一件容易办到的事情,尤其...

39660
来自专栏大数据挖掘DT机器学习

学了统计、算法,如何正确应用机器学习?

原文:http://blog.csdn.net/google19890102/article/details/40680687 学习了一段时间的机器学习算...

33490
来自专栏鸿的学习笔记

精确控制模型预测误差(上)

当评估模型的质量时,能够准确测量其预测误差至关重要。然而,测量误差的技术常常会给出严重误导的结果。因为可能导致会过拟合,就是模型可以非常好地拟合训练数据,但是对...

10010
来自专栏机器之心

推翻剪枝固有观点?清华、伯克利提出NN过参数化真的不重要

在该论文 ICLR 2019 的双盲审评论区,论文「ThiNet」的一作 Jian-Hao Luo 和论文「通道剪枝」的一作 Yihui He 提出了修改意见。...

14030
来自专栏null的专栏

机器学习的应用——关于正确应用机器学习

引言     前阵子看到一篇文章,学习了一段时间的机器学习算法后,再回头看机器学习问题,发现要想利用机器学习去很好的求解一个问题,其实并不是一件容易办到的事情,...

36770
来自专栏量子位

视觉目标检测和识别之过去,现在及可能

作者:李习华 知乎专栏:碧空的cv之旅 量子位 已获授权编辑发布 计算机视觉中目标检测、跟踪、识别是最基本的几个task,尤其又以检测最为重要和基础。同时基本上...

41670
来自专栏数据科学与人工智能

【机器学习】机器学习的应用——关于正确应用机器学习

引言 前阵子看到一篇文章,学习了一段时间的机器学习算法后,再回头看机器学习问题,发现要想利用机器学习去很好的求解一个问题,其实并不是一件容易办到的事情,...

27680

扫码关注云+社区

领取腾讯云代金券