您现在的位置是：首页 > 技术资料 > 改进ACO及其在移动机器人路径规划中的应用

推荐星级：

改进ACO及其在移动机器人路径规划中的应用

更新时间：2019-12-30 14:03:47 大小：2M 上传用户：songhuahua 查看TA发布的资源 标签：移动机器人路径规划 Python 下载积分：1分评价赚积分（如何评价?）打赏收藏评论(0) 举报

资料介绍

针对基本ACO存在收敛精度不高、收敛速度慢、容易陷入局部最优的不足现象展开研究。通过基本ACO原理和数学模型分析,得出参数设置不当和信息素更新迟滞是基本ACO容易产生不足的原因。在此基础上,提出基于狼群分配原则信息素更新策略的改进ACO。采用Python模型和Matlab模拟计算相结合的方式进行ACO参数优化设计和Griewank函数、Ackly函数的对比实验。结果表明,蚂蚁数量m与城市数量n关系系数为1.5、信息素启发式因子α为[1.0,3.0]、期望启发式因子β为[2.0,4.0]、信息素挥发系数ρ为[0.5,0.7]、信息素强度Q为[10,1000]时,所得算法性能较好。采用栅格法的移动机器人路径规划研究进一步表明,改进ACO收敛精度更高、收敛速度更快、不易陷入局部最优,与基本ACO相比,算法性能大大提高。

部分文件列表

文件名	大小
改进ACO及其在移动机器人路径规划中的应用.pdf	2M

立即下载

【关注B站账户领20积分】

部分页面预览

（完整内容请下载后查看）

机械设计与制造

Machinery Design ＆ Manufacture

第 10 期

2019 年 10 月

226

改进 ACO 及其在移动机器人路径规划中的应用

1 1 2

刚，马震，刘紫燕，何妍

梁

（1.贵州大学明德学院，贵州贵阳 550ꢀ25；2ꢁ贵州大学大数据与信息工程学院，贵州贵阳 55ꢀꢀ25；

3.新松机器人自动化股份有限公司，辽宁沈阳 11ꢀ168）

摘

要：针对基本 ACO 存在收敛精度不高、收敛速度慢、容易陷入局部最优的不足现象展开研究。通过基本 ACO 原理和

数学模型分析，得出参数设置不当和信息素更新迟滞是基本 ACO 容易产生不足的原因。在此基础上，提出基于狼群分配

原则信息素更新策略的改进 ACO。采用 Python 模型和 Matlab 模拟计算相结合的方式进行 ACO 参数优化设计和

Griewank 函数、Ackly 函数的对比实验。结果表明，蚂蚁数量 m 与城市数量 n 关系系数为 1ꢁ5、信息素启发式因子 α 为

［1ꢁꢀ，3ꢁꢀ］、期望启发式因子 β 为［2ꢁꢀ，4ꢁꢀ］、信息素挥发系数 ρ 为［ꢀꢁ5，ꢀꢁ7］、信息素强度 Q 为［1ꢀ，1ꢀꢀꢀ］时，所得算法性能较

好。采用栅格法的移动机器人路径规划研究进一步表明，改进 ACO 收敛精度更高、收敛速度更快、不易陷入局部最优，与

基本 ACO 相比，算法性能大大提高。

关键词：ACO；Python；移动机器人；路径规划

中图分类号：TH16；TP391 文献标识码：A

文章编号：1001-3997（2019）1ꢀ-ꢀ226-ꢀ5

Improving ACO And Its Application in Mobile Robot Path Planning

1 1 2

LIANG Gang ，MA Zhen ，LIU Zi-yan ，HE Yan

（1ꢁMingde College of Guizhou University，Guizhou Guiyang 550025，China；2ꢁSchool of Big Data and Information Engineering

Guizhou University，Guizhou Guiyang 550025，China；3ꢁXinsong Robot Automation Coꢁ，Ltd，Liaoning Shenyang 110168，China）

Abstract：The study is focused on solving the questions of basic ACO（Ant Colony Optimization），such as the low convergence

accuracy，the slow convergence speed and easily falling into local optimality. It is concluded that improper parameter setting

and pheromone update hysteresis are the reasons why the basic ACO is prone to insufficient through the basic ACO principle

and mathematical model analysis. Subsequently，the improved ACO that based on the pheromone update strategy of the wolf

group allocation principle is proposed. ꢀhe ACO parameter optimization design and the comparison experiment of Griewank

function and Ackly function were carried out by combining the Python model and Matlab simulation. ꢀhe results show that

when the relationship between m and n is 1ꢁ5，α is［1ꢁ0，3ꢁ0］，β is［2ꢁ0，4ꢁ0］，ρ is［0ꢁ5，0ꢁ7］，ꢁ is［10，1000］，the obtained

algorithm is better.ꢀhe research on path planning of mobile robots using grid method further shows that the improved ACO has

higher convergence precision，faster convergence speed ，and it is not easy to fall into local optimality. Compared with the

basic ACO，the performance of the algorithm is greatly improved.

Key Words：ACO；Python；Mobile Robot；Path Planning

相结合的更新策略以及调整状态转移概率公式对基本 ACO 进行

1 引言

[6]

了优化改进。文献结合捕食搜索策略对多态蚁群算法进行改良，

[1-3]

蚁群算法（Ant Colony Optimization，ACO）是文献在研究

通过引入设置侦查素路径为优先，为非侦查素路径设置惩罚因子，

利用权值在侦查素和非侦查素路径都施加信息素，从而避免多态蚁

群算法陷入停滞，并通过竞争机制选择最优解更新信息素。

通过基本 ACO 原理和数学模型分析，得出基本 ACO 容易产

生不足的原因，采用 Python模型和 Matlab 模拟计算相结合的方

[4]

蚂蚁觅食行为的基础上，提出的一种仿生类优化算法。文献对算

法原理、信息素感应阈值进行研究分析，提出了信息素自适应调

[5]

整方法，兼顾了算法前期的大范围搜索和后期的快速收敛。文献

以智能立体车库中自动导引运输车（Automated Guided Vehicle，

AGV）存取车路径规划问题为研究对象，通过信息素局部和全局

来稿日期：2ꢀ19-ꢀ2-ꢀ8

基金项目：贵州省科学技术基金计划（黔科合基础［2ꢀ16］1ꢀ54）

作者简介：梁刚，（1977-），男，贵州贵阳人，硕士研究生，讲师，主要研究方向：智能控制系统；

马

震，（199ꢀ-），男，河南新乡人，硕士研究生，主要研究方向：机电一体化技术

第 10 期

227

梁

刚等：改进 ACO 及其在移动机器人路径规划中的应用

式进行 ACO 参数优化设计和 Griewank 函数、Ackly 函数的对比

实验。在此基础上，提出基于狼群分配原则信息素更新策略的改

进 ACO，改进 ACO 收敛精度更高、收敛速度更快，同时可有效避

免陷入局部最优的不足，算法性能显著提高。

式中：ρ—信息素挥发系数，且 ρ⊂［0，1］；1-ρ—信息素残留系数；

△τ（t）—本次循环中残留在路径（i，j）上的信息素增量；△τ

（0）=0，△τ（t）—地 k 只蚂蚁在 t 时刻停留在路径（i，j）上的

信息素量。

信息素挥发系数 ρ 影响 ACO 的搜索能力和收敛速度，ρ 过小

时，路径上留存的信息素量越高，搜索过路径再次被选择的概率越

高，这会导致蚂蚁搜索范围减小，全局搜索能力下降，ACO 容易产

2 基本 ACO 分析及改进

针对基本 ACO 存在收敛精度不高、收敛速度慢、容易陷入

[1-3]

局部最优的不足现象展开研究。通过基本 ACO 原理和数学模

生陷入局部最优的不足现象；ρ 过大时，可能使得某些路径上的 τ

型分析，得出基本 ACO 容易产生不足的原因。

2.1 基本 ACO 原理和数学模型分析

（t）接近于 0，蚂蚁进入随机路径选择，这会导致 ACO 陷入盲

[1-6]

目无序的混乱状态，ACO 容易产生收敛速度慢的不足现象。

ACO 数学模型如下：G=（C，L）是一个有向图，C=｛C₁，C₂，…，

基本 ACO 模型采用 Ant-Cycle 模型（5），即蚂蚁走完一个循

C_n｝是 n 个城市的集合，L= c ，c ⊂ꢀ 是城市两两相连的集合，即

环后再更新的全局信息。

城市间两两连接的路径，d（i，jꢁ1，2，…，n）是 l_ij的距离。

如果第 K 只蚂蚁在本次循环中经过路径（i，j）

蚂蚁 k（k=1，2，…，m）在觅食过程中根据概率选择式（1）选

｛

△τ（t）=

（5）

择下一个城市。

0otherwise

式中：Q—蚂蚁完成一次完整的路径搜索后所释放的信息素总

量；L_k—蚂蚁 k 在本次循环经过的路径总长度。

η（t）=

（1）

■

ꢀ

τ（t）η（t）

信息素强度 Q 表示一次循环后路径上留存影响 ACO 正反

j∈allowed

ꢀ

ꢁ

P（t）=^ꢁ

ꢀ

（2）

馈功能的信息素总量，AꢀO 在正反馈的作用下搜索到全局最优

τ（t）η（t）

ꢀ

s∈allowed_k

[1-3]

ꢀ

解

。Q 过大时，路径上的信息素总量越高，搜索过路径再次被选

_ꢂ0 otherwise

择的概率越高，这会导致蚂蚁搜索范围减小，全局搜索能力下降，

ACO 容易产生陷入局部最优的不足现象；Q 过小时，蚂蚁可能进

入随机路径选择，这会导致 ACO 陷入无序的混乱状态，ACO 容

易产生收敛速度慢的不足现象。

式中：P （）t —蚂蚁 k 从城市 i 选择移动到城市 j 的概率；allowed_k—

蚂蚁尚未访问过的城市的集合；ꢀ—信息素启发式因子；ꢁ—

期望启发因子；τ（t）—t 时刻连接城市 i 和城市 j 的路径上

残留信息素浓度，η ；t—由城市 i 到城市 j 的启发信息。

综上所述，参数设置不当和信息素更新迟滞是基本 ACO 容

易产生收敛精度不高、收敛速度慢、容易陷入局部最优等不足现

象的原因。

分析可知，蚂蚁数量 m 较大时，ACO 全局搜索能力提高，但

m 过大时，已经搜索路径上的信息素浓度区别不大，这会导致信

息素正反馈作用降低，ACO 容易产生收敛速度慢的不足现象；m

较小时，小规模 TSP（Traveling Salesman Problem）还能解决，对于

2.2 基于狼群分配原则的信息素更新策略

针对基本 ACO 在运算过程中容易产生信息素更新迟滞的

不足现象，结合狼群分配原则的特性，提出基于狼群分配原则的

大规模 TSP，经过每个路径上的信息素浓度太低，这会导致全局

[1-6]

搜索概率降低，ACO 容易产生陷入局部最优的不足现象

。

[7-9]

信息素更新策略，依照更新式（6）进行信息素更新。

信息素启发式因子 ꢀ 反映 τ（t）在指导蚁群搜索时的相对重

best

worst

^{τ（t+1）ꢁ（1-ρ）·τ（t）+}Σ^{△τ +ε△τ}

ij ij ij

-λ△τ （6）

要程度，ꢀ 过大时，蚂蚁选择走过路径的可能性增大，但这一路径

不一定是最短路径，虽然 ACO 收敛速度加快，但最终解却不一定

是全局最优解，ACO 容易产生收敛精度不高的不足现象；ꢀ 过小

k=1

best

worst

式中：△τ =Q/L —局部最优蚂蚁经过路径释放信息素；△τ

best

Q/L —局部最差蚂蚁经过路径释放的信息素；ε—局部最

worst

优蚂蚁经过路径释放信息素权重因子；λ—局部最差蚂蚁经

过路径释放信息素权重因子。

时，蚂蚁对信息素浓度不敏感，进行无记忆随机搜索，这会导致搜

[2-5]

索时间增加，ACO 容易产生收敛速度慢的不足现象

。

改进 ACO 进行路径规划时，首先找到每次循环中局部最优

期望启发式因子 ꢁ 反映 τ（t）在指导蚁群搜索时的相对重要

best

路径蚂蚁，增大其释放的信息素 △τ ，然后去除掉局部最差路径

度，ꢁ 过大时，蚂蚁在某个局部点上选择局优的可能性越大，这会

导致搜索随机性过弱，ACO 容易产生陷入局部最优的不足现象；

worst

蚂蚁释放的信息素 △τ ，最后各条路径上信息素浓度按狼群分

配原则进行更新，以改善基本 ACO 在运算过程中容易产生信息

素更新迟滞的不足现象，提高算法性能。

ꢁ 过小时，与之对应的确定性因素作用强度过小，这会导致算法

[1-4]

进行盲目随机搜索，ACO 容易产生收敛速度慢的不足现象

。

2.3 ACO 参数优化设计

为防路径上残留的信息素过多引起 ACO 提前结束，在 t+n

时刻每只蚂蚁走完一个城市或者遍历完所有城市，对路径（i，j）上

的信息量依照更新式（3）进行残留信息素更新。

针对信息素启发式因子 ꢀ、期望启发式因子 β 等参数设置不

当导致基本 ACO 容易产生收敛精度不高、收敛速度慢等不足。采用

Python 模型和 Matlab 模拟计算相结合的方式进行 ACO 参数优化

τ（t+n）=（1-ρ）τ（t）+△τ（t）

（3）

（4）

[10-11]

设计。其中，TSP 案例库（TSPLIB）采用 Eil51 作为测试库，设计

^{△τ（t）=}Σ^△τ（t）

ij ij

变量表达式，如式（7）所示。设计变量的上下边界，如表 1 所示。

k=1

全部评论(0)

暂无评论

评论赚积分>>

上传资源上传优质资源有赏金

改进ACO及其在移动机器人路径规划中的应用

资料介绍

部分文件列表

部分页面预览

相关下载

全部评论(0)

热门标签

最新上传

热门下载

资料专题

推荐下载

专栏首页