蚁群算法规划路径

蚁群算法可以用于路径规划,在本例中,地形矩阵用0表示无障碍物、用1表示有障碍物,机器人从1x1处走到10x10处,使用蚁群算法找最短路径。

步骤如下:

  1. 初始化参数、地形矩阵、信息素矩阵和启发式因子矩阵。启发式因子矩阵中一点的值为该点到终点距离的倒数,距离越短,启发式因子越大,障碍物处的启发式因子为0。信息素矩阵被初始化为一个统一的值。
  2. 在本例中,将一条路径表示如下:[路径长度点1 点2 ……],例如[2 1 2 0 0]表示该路径长度为2,路径为[1 2]。
  3. 对每次迭代中的每只蚂蚁,进行如下3步,直至到达终点或者陷入死胡同:
  4. 创建一个禁忌矩阵,禁忌矩阵中已经访问过的点为0,其余点与启发式因子矩阵中相应点的值相同。
  5. 设置初始点,根据信息素、启发式因子、禁忌表,通过轮盘赌方法,选择下一个城市。
  6. 更新路径和禁忌矩阵。
  7. 每次迭代后,更新信息素,只对最优路径中的点进行增加信息素操作。
  8. 迭代,直至结束。

结果如下,其中黄色块为障碍物,红色线为路线:

主函数

主函数如下:

functionmain()

rn = 10; cn =10;

G = makeG(rn, cn); % 地形图

tau = 8 .* ones(rn, cn); % 初始化信息素

MaxGen = 100; % 迭代次数

N = 50; % 蚂蚁个数

S = 1; % 路径起始点

E = rn * cn; % 路径终点

Alpha = 1; % 信息素重要程度

Beta = 30; % 启发式因子重要程度

Rho = 0.3; % 信息素挥发系数

Q = 5; % 信息素增加系数

Eta = makeEta(G); % 距离倒数矩阵

gpath= zeros(MaxGen, rn*cn+1); % 每代最优路径 [地点个数 地点……]

for g =1:MaxGen

npath = zeros(N, rn*cn+1); % 每个路径 [地点个数 地点……]

for n = 1:N

D = Eta; % 禁忌矩阵

path = zeros(1, rn*cn+1); % 路径

% 更新点、路径和禁忌矩阵

point = S;

path(1, 1) = path(1, 1) + 1;

path(1, path(1,1)+1) = point;

D(point) = 0;

% 搜索下一个点的坐标范围

nextlist = getNextList(point, rn, cn,D);

% 一直前进,直到到达食物或者陷入死胡同

while point ~= E &&~isempty(nextlist)

% 轮盘赌算法取下一点

p = zeros(1, length(nextlist));

for i = 1:length(nextlist)

p(1, i) =(tau(nextlist(i))^Alpha) * (Eta(nextlist(i))^Beta);

end

nextpoint =nextlist(getNextPoint(p));

% 更新点、路径和禁忌矩阵

point = nextpoint;

path(1, 1) = path(1, 1) + 1;

path(1, path(1,1)+1) = point;

D(point) = 0;

nextlist = getNextList(point, rn,cn, D);

end

% 记录成功成功到达终点的蚂蚁的路径

if (path(1, 1+path(1,1)) == E)

npath(n, :) = path;

end

end

npath = npath(find(sum(npath,2)), :); % 保留到达终点的路径

lk = calLk(npath, rn, cn); % 计算lk距离

% 更新信息素

tau = (1 - Rho) .* tau;

for i = 1:size(npath, 1)

for j = 2:npath(i,1)+1

tau(npath(i,j)) = tau(npath(i,j)) +Q / lk(i);

end

end

[~, minindex] = min(lk);

if size(npath, 1) > 0

gpath(g, :) = npath(minindex, :);

end

end

lk =calLk(npath, rn, cn);

[minvalue,minindex] = min(lk);

fprintf("minlength: %f\n", minvalue);

bestpath =gpath(minindex,:);

bestpath =bestpath(2:1+bestpath(1,1));

figure;

imagesc(G);

hold on;

for i =2:length(bestpath)

[x1, y1] = ind2sub([rn, cn],bestpath(i-1));

[x2, y2] = ind2sub([rn, cn], bestpath(i));

plot([y1, y2], [x1, x2], 'r');

hold on;

end

end

得到下一点函数

每只蚂蚁的下一步候选点应该是这样的:

  1. 没有障碍物
  2. 该蚂蚁之前没有经过
  3. 紧邻蚂蚁(蚂蚁不能飞)

得到待选点函数如下:

functionnextlist = getNextList(point, rn, cn, D)

%给出待选点列表

%point input 当前点

%rn input 地图行数

%cn input 地图列数

%D input 禁忌地图

%nextlist output 待选点列表

list =find(D);

nextlist =zeros(1, length(list)+1);

[pointx,pointy] = ind2sub([rn, cn], point);

for i =1:length(list)

[indexx, indexy] = ind2sub([rn, cn],list(i));

if (indexx >= pointx-1 && indexx<= pointx+1 ...

&& indexy >= pointy-1&& indexy <= pointy+1)

nextlist(1, 1) = nextlist(1, 1) + 1;

nextlist(1, nextlist(1,1)+1) = list(i);

end

end

a = nextlist(1,1);

nextlist =nextlist(1, 2:1+a);

在得到待选点列表后,就能通过轮盘赌法得到下一点了:

functionnextpointindex = getNextPoint(p)

%使用轮盘赌法给出下一个点

%p input 概率列表

%nextpointindex output 下一个点

sump =sum(p);

p = p / sump;

cumsump =cumsum(p);

list =find(cumsump >= rand);

nextpointindex= list(1);

一些其他函数

制作地形矩阵函数:

functionG = makeG(rn, cn)

% 制作地形矩阵

% rn input 地形矩阵函数

% cn input 地形矩阵函数

% G output 地形矩阵

G= zeros(rn, cn);

G(1:3,2) = 1;

G(7:10,1:5) = 1;

G(5,3) = 1;

G(1,4) = 1;

G(1:5,5) = 1;

G(5:7,7:9) = 1;

制作启发式因子矩阵:

functioneta = makeEta(G)

% 制作启发式因子矩阵(到终点距离倒数,障碍物为0)

% G input 地形矩阵

% eta output 启发式因子矩阵

eta= G;

[rn,cn] = size(G);

fori = 1:rn

for j = 1:cn

if G(i, j) == 1

eta(i, j) = 0;

elseif (i == rn && j == cn)

eta(i, j) = 1;

else

eta(i, j) = 1 / ( (rn-i)^2+(cn-j)^2)^0.5;

end

end

end

计算路径长度矩阵:

function lk =calLk(npath, rn, cn)

%计算路径长度

%npath input 路径

%rn input 地图行数

%cn input 地图列数

%lk output 路径长度rnx1

[nr, ~] =size(npath);

lk =zeros(nr, 1);

for i = 1:nr

path = npath(i, 2:1+npath(1,1));

for j = 2:length(path)

[x1, y1] = ind2sub([rn, cn],path(j-1));

[x2, y2] = ind2sub([rn, cn], path(j));

lk(i) = lk(i) +((x2-x1)^2+(y2-y1)^2)^0.5;

end

end

end

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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏新智元

【重磅】AI 学会“脑补”:神经网络超逼真图像补完从 0 到 1

1 新智元编译 来源:arXiv、Github 编译:张易 【新智元导读】自动图像补全是计算机视觉和图形领域几十年来的研究热点和难点。在神经网络的帮助下,来...

34350
来自专栏AI科技评论

清华朱军团队包揽三项冠军,NIPS 2017对抗样本攻防竞赛总结

AI 科技评论按:自 Ian Goodfellow 等研究者发现了可以让图像分类器给出异常结果的「对抗性样本」(adversarial sample)以来,关于...

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

R语言 使用BP神经网络进行银行客户信用评估

一、学习R语言AMORE包中的newff函数 这是个前馈神经网络工具包,类似的还有nnet,RSNNS等。AMORE比nnet参数要丰富一些。AMORE...

42380
来自专栏PPV课数据科学社区

【V课堂】R语言十八讲(十四)—几大检验

在统计分析中,我们会听到很多检验,有T检验,卡方检验,秩和检验,F检验,费舍尔检验等等,这么多检验,光听就要晕了,还怎么用啊?哪种检验什么时候能用什么时候不能用...

29370
来自专栏Petrichor的专栏

思考: 改进 现有的 网络参数初始化 方法

网络参数初始化方法 最粗暴的 莫过于 全零初始化 。顾名思义,所有参数全部初始化为0。想法很好,简便省事儿,还可使得初始化全零时参数的期望与网络稳定时参数的期望...

12020
来自专栏小小挖掘机

推荐系统遇上深度学习(一)--FM模型理论和实践

1、FM背景 在计算广告和推荐系统中,CTR预估(click-through rate)是非常重要的一个环节,判断一个商品的是否进行推荐需要根据CTR预估的点击...

2.6K100
来自专栏机器之心

资源 | 神经网络目标计数概述:通过Faster R-CNN实现当前最佳的目标计数

选自SoftwareMill 机器之心编译 作者:Krzysztof Grajek 参与:黄小天 在机器学习中,精确地计数给定图像或视频帧中的目标实例是很困难...

434130
来自专栏机器人网

谁是世界上最美的人?看神经网络为每人按颜值魅力打分

「魔镜魔镜告诉我,谁是世界上最美的女人?」这句伴随童年的话也有现实版哦~神经网络可以预测人脸颜值,这方面也出现了不少研究。今年年初华南理工大学的研究者发布论文,...

23240
来自专栏一个会写诗的程序员的博客

BP 神经网络算法

x的值可能为[−∞,+∞],为了方便处理,需要将其压缩到一个合理的范围,还需 这样的激励函数,能够将刚才的区间压缩到[0,1]。

13330
来自专栏机器之心

入门 | 深度学习模型的简单优化技巧

以下是我与同事和学生就如何优化深度模型进行的对话、消息和辩论的摘要。如果你发现了有影响力的技巧,请分享。

13800

扫码关注云+社区

领取腾讯云代金券