基于混沌的粒子群优化算法的物料空间内货位拣选路径优化

 基于混沌的粒子群优化算法的物料空间内货位拣选路径优化

王霄霄,艾建,杨鹏

河南中烟工业有限责任公司漯河卷烟厂

摘要  针对货位拣选经常陷入局部最优的问题，本文提出了一种高效求解局部优化问题的改进算法，即为混沌粒子群优化算法，运用高效非支配排序法中的顺序搜索策略以大大减少时间复杂度，以及利用混沌映射来提高MOPSO的全局收敛性，最后运用Matlab7.0软件仿真验证， 结果表明该模型能较好的优化货位分配与拣货路径，提高拣货效率，取得了较好的效果。

关键词  局部最优 粒子群优化算法 货位分配

1 引言

随着AGV小车在智能仓储系统中被广泛应用，AGV的路径规划成为系统的关键技术之一。路径规划即在一定障碍物和多种约束条件的环境中，依据多个优化目标，搜索出一条从指定起点到终点的无碰撞路径。粒子群算法是一种群搜索算法，初始化种群的搜索空间看作是数学模型中的多维空间，按照某种规则传递信息，并根据人为规定改变粒子移动的行为。

郭江等针对栅格环境下蚁群算法（ACS）搜索的路径转折次数多、累计转角大等问题，提出一种将Bezier曲线与ACS进行融合的算法，虽然提高了路径规划效率，但实验仿真的模拟环境比较简单，不具有现实意义。李伟光等考虑到AGV在弯道处时减小速度行驶，并且要灵活地调整自身姿态，这种情况会浪费很多时间，在评估函数中将转弯因素加入考虑，从而得到了较平滑的路径，但容易陷入局部最优，仿真实验同样不具卷烟企业的实际情况。

考虑到粒子群算法和AGV路径规划具有某种关系，本文将粒子群算法引入到AGV路径规划，并将传统粒子群优化算法进行改进，以此提高AGV路径搜索的全局性，并通过Matlab7.0软件仿真验证其有效性和可行性。

2 AGV路径规划模型的建立

2.1 AGV工作环境建模

在“工业互联网”环境，智能移动机器人参与仓储管理系统运行，研究一种便于计算机进行路径规划使用的环境模型，即将一种AGV参与下的物料货位拣选的二维物理空间抽象成算法能够处理的抽象空间。

栅格建模法是一种平面移动机器人运动轨迹规划的抽象模型，是研究平面移动机器人运动路径规划的最常用的方法之一。该方法是由W.E.Howden在1968年提出，他在进行路径规划时采用了栅格（Grid）表示地图。设环境的最大长度为L，宽度为W，栅格的尺度（长、宽）均为b，则栅格数为（L/b）x（W/b）,所有空间fw由栅格fi构成：

}

其中fi=0表示该方格为自由区域，即为白色方格，fi=1表示该方格为障碍区域，即为黑色方格。如图2所示。

图2 栅格环境模型

所以，AGV路径规划是机器人A寻找到一条从初始位置S到目标位置T的避障路径，如图2所示，红色线条表示AGV路径。

2.2 适应度函数的建立

在优化问题中，目标函数在整个算法中至关重要，严重影响算法的难易程度。在本章中，智能物流中AGV物料货位拣选动态路径优化问题明显就是一个种群优化问题，表述如下：

式中,m为路径点的数量; xi和yi为每个路径点坐标。

3 混沌粒子群优化算法

由于传统的粒子群优化算法易陷落局部极值，运算结尾时收敛速度慢，精度差。本文引入混沌映射的信息素更新策略，以及考虑在路径搜索阶段避免陷入局部最优解等问题, 以达到收敛速度快和寻优能力强。

3.1 改进算法的关键因子

传统的进化算法已经成功地应用到许多领域，其中有一个关键性的挑战是，解决局部优化和收敛性的问题。为了寻找更加优秀的全局解代替当前最优解，本文主要利用混沌映射中的逻辑映射，来达到全局收敛的目的。

在2014年，逻辑映射[5]被引入解决优化算法，它是其中一个最简单的映射。该映射的复杂行为来源于一个简单的非线性动力学方程。逻辑映射产生(0,1)内的混沌序列。公式(3-1)理论化定义了逻辑映射。

(3-1)

在仿真中，参数a设置为4。

3.2 改进的算法流程

本节提出的改进算法是一种高效的混沌粒子群优化算法，其中运用混沌映射处理局部优化问题。同时，仿真实验表明，该算法具有较好的收敛性和可行性，可以尝试理论联系实际，处理有关局部优化问题的实际问题。

混沌粒子群优化算法的流程如下：

第一步：建立一个二维搜索空间，初始化种群大小为N：

第步：初始化种群粒子的位置与速度；

第步：计算初始粒子的目标函数适应度值，并通过支配关系得到初始化适应度值的个体极值与全局极值。

第二步：根据公式(3-1)、(3-2)，利用当前粒子的位置和速度更新下一时刻粒子的位置与速度。

公式(3-1)，(3-2)更新粒子的变化，如下：

(3-1)

                         (3-2)

其中，w是权值，c1和c2是学习因子，r1和r2是在[0,1]内的随机变量，pid(t)表示个体极值的第d维分量。pgd(t)表示全局极值的第d维分量。公式(3-1)表示更新粒子的速度，和公式(3-2)表示更新粒子的位置。

第三步：对更新粒子的适应度值，进一步

更新个体极值与全局极值。

第四步：运用混沌思想优化全局最优解集。

第五步：若满足最大的迭代次数或者实际工程中的要求，则停止迭代，并输出当前最优解集；若不满足要求，则返回至第二步进行下一次迭代，直到满足要求为止。

3 仿真分析

为了证明算法在收敛性和稳定性方面的优越性，本文将CPSO算法与遗传算法（GA）、和粒子群算法（PSO）各自单独运行100次，将它们的平均收敛代数、寻找到全局最优解的概率及搜索用时统计如表3-1 所示。

表 3-1 三种算法求解拣选路径优化模型时运行 100次的对比图

从表 3-1 中可以看出，CPSO算法在求解本文提出的货物拣选优化模型时具有最好的稳定性，将实验单独运行100次有95次都得到了最优解，概率高达 95%，而且算法得到最优解的实验用时也是最少的。与之相比，GA 算法具有最差的稳定性和最长的实验用时。

4 结 论

本文提出了一种新的粒子群优化算法，该算法采用栅格建模法，通过引入混沌映射算子更新全局最优解，仿真表明，该新算法具有更高的精度、更快的速度，即使在复杂的环境中，也可以有效地解决了路径搜索的计算量过大，效率不高等问题。同时，也说明本文提出的混沌粒子群优化算法应用于AGV路径规划具有有效性和可行性。未来我们还将继续优化该算法模型，并希望能将该优化算法推广到更广泛的实时动态路径变换的应用场景中。

参考文献:

[1] 郭江，肖宇峰等，《Bezier曲线与A*算法融合的移动机器人路径》[J]，微型机与应用，2017，36（2）.

[2] 李伟光，苏霞, 《基于改进A* 算法的AGV路径规划》[J]，现代制造工程，2015.10.

[3]李松，刘力军，翟曼．改进粒子群算法优化BP 神经网络的短时交通流预测［J］．系统工程理论与实践，2012 ( 9 )．

无线传感器网络在智能电网中的应用