字木交流
理．＾，研发，设汁／嗣港
基于改进粒子群算法的移动机器人全局路径规划
徐会成，单建华
（安徽工业大学机械工程学院，安徽马鞍山２４３００２）
Ｇｌｏｂａｌ Ｐａｔｈ Ｐｌａｎｎｉｎｇ ｆｏｒ Ｍｏｂｉｌｅ Ｒｏｂｏｔ Ｂａｓｅｄ ｏｎ Ｉｍｐｒｏｖｅｄ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ ＸＵ Ｈｕｉ－ｃｈｅｎｇ，ＳＨＡＮ Ｊｉａｎ—ｈｕａ 【Ｃｏｌｌｅｇｅ ｏｆ Ｍｅｃｈａｎｉｃａｌ Ｅｎｇｉｎｅｅｒｉｎｇ，Ａｎｈｕｉ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，Ｍａａｎｓｈａｎ ２４３００２，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｔｈｉｓ ａｒｔｉｃｌｅ，ｃｈａｏｓ ｊｎｉｔｉａｌｉｚａｔｉｏｎ，ｍｕｔａｔｉｏｎ ａｎｄ ｃｒｏｓｓ ｏｐｅｒａｔｉｏｎ ｗｅｒｅ ａｄｄｅｄ ｔｏ ｔｈｅ ｓｔａｎｄａｒｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ
ｏｐｔｉｍｉｚａｔｉｏｎ．Ｗｈｉｌｅ ｍａｉｎｔａｉｎｉｎｇ ｔｈｅ ｓｉｍｐｌｅ ｓｔｒｕｃｔｕｒｅ ａｎｄ ｆａｓｔ ｃｏｎｖｅｒｇｅｎｃｅ ｏｆ ｔｈｅ ｓｔａｎｄａｒｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ， ｔｈｅ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍｓ ｉｎｃｒｅａｓｅ ｔｈｅ ｄｉｖｅｒｓｉｔｙ ｏｆ ｇｒｏｕｐ，ｅｎｌａｒｇｅ ｔｈｅ ｓｅａｒｃｈ ｓｐａｃｅ，ａｖｏｉｄ ｔｈｅ ｐｒｅｍａｔｕｒｅ ｃｏｎｖｅｒｇｅｎｃｅ
ｐｒｏｂｌｅｍ ｅｆｆｅｃｔｉｖｅｌｙ ａｎｄ ｏｂｔａｉｎ ｔｈｅ ｏｐｔｉｍａｌ ｐａｔｈ ｆｒｏｍ ｓｔａｒｔｉｎｇ ｐｏｉｎｔ ｔｏ ｔａｒｇｅｔ ｐｏｉｎｔ．Ｔｈｕｓ，ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ａｎｄ
ｐｒａｃｔｉｃａｂｉｌｉｔｙ ｏｆ ｔｈｉｓ ｍｅｔｈｏｄ Ｗｅｌ’ｅ ｐｒｏｖｅｄ． Ｋｅｙ ｗｏｒｄｓ：ｐａｔｈ ｐｌａｎｎｉｎｇ；ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ；ｃｈａｏｓ ｉｎｉｔｉａｈｚａｔｉｏｎ；ｍｕｔａｔｉｏｎ ａｎｄ ｃｒｏｓｓ
１ 引 言 移动机器人路径规划问题是机器人研究领域中的一
个重要课题。路径规划是指按照某一性能指标ｆ如路径最
短、使用时间最短或消耗能量最少等）搜索一条从起始点
到目标点的无碰撞最优或近似最优的路径。根据对环境
信息的了解情况，移动机器人的路径规划可分为环境信
息完全已知的全局路径规划和环境信息部分未知或完全
未知的局部路径规划。
栅格法是目前研究最广泛的路径规划方法之一。本
文用栅格法建立环境模型，将改进的粒子群优化算法直
接运用到栅格模型中，得到移动机器人的全局最优路径。
２标准粒子群算法
粒子群算法与其它进化类算法相类似，也采用“群
体”与“进化”的概念，每一个粒子都是一个解，粒子的好
坏由适应度函数Ｆ（ｘ）决定。每一次迭代，粒子通过自己的 飞行经验ｐｂｓｅｔ（粒子到目前为止发现的最好位置）和群
体的飞行经验ｇｂｅｓｔ（整个种群到目前为止所发现的最好
位置）来更新自己的速度和位置。
假设搜索空间为ｍ维，粒子总数为Ⅳ，在每一次迭代
中，粒子根据以下公式‘ 味更新自己的速度和位置：
ｆ ： ＝∞ ． ＋ｃＩｒｌ（ 一 。 ）＋ｃ２ｒ２（ ，一 ） （１）
： ＋Ｔ ‘ （２） 其中， ， 分别表示粒子 （ｉ＝ｌ，２，…， ）第ｄ（ｄ＝ｌ，２，…，
ｍ）维在第ｔ次迭代后的速度和位置； 表示粒子ｉ第ｄ
维分量在第ｔ次迭代后的最优位置； 表示整个种群第ｄ 基金项目：２０１０年高校省级优秀青年人才基金项目 （２０１０ＳＱＲＬ０３６ＺＤ）
２４ 机械工程师２０１０年第１１期 维分量在第ｔ次迭代后的最优位置；ｃＩ、ｃ 称为加速因子；
ｒＩ、ｒ：为区间（０，１）内变化的随机数；第ｄ维的位置变化范
同为［‰ …］，速度变化范围为［ｆ）ｒａｉｎ， ～］，迭代中若位置
和速度超过边界范围则取边界值；ｔｏ为惯性权重，一般取
值为［０，１．４］，惯性权重线性递减能显著改善算法的收敛
性能 ，一般采用下面的公式：
（３）
其中，？ｃ为当前迭代次数，＆一为总的迭代次数。当迭代完
成后，最后输出的ｇｂｅｓｔ就是算法寻到的最优解。
分析标准粒子群优化算法搜索过程，它有两点基本
不足口］： （１）初始化过程是随机的，虽然大多数可以保证初始
解分布均匀，但是不能保证解的质量，如果初始解比较
好，将会有助于提高求解效率与解的质量。
（２）通过分析式（１）、（２）可知，粒子是利用本身信息、
个体极值信息和全局信息来决定下一步的迭代位置，算
法运行过程中，如果某个粒子发现了一个当前最优位置，
其它粒子将迅速向它靠拢，而且随着迭代的进行，粒子的
速度会越来越小直至接近或等于零，出现“聚集”现象，表
现 强烈的趋同性。当该位置为局部最优点时，粒子就不 能在解空间内重新搜索新的全局最优位置ｇｂｅｓｔ．因此算
法陷入局部最优，出现所谓的早熟收敛 。
３改进粒子群算法 针对标准粒子群算法的两点不足，本文对其进行如
下改进：
（１）加入混沌初始化。目前对混沌尚无严格的定义，
一般将由确定性方程得到的具有随机性的运动状态称为
混沌。它具有随机性、遍历性和规律性的特点。其中的遍 历性就是指能在一定范围内按其自身规律不重复地遍历
所有状态。本文就是利用这一特点，产生大量的初始群
体，从中选择较优的一部分作为初始群体，以此来提高初
始解的质量。
本文采用比较常用的Ｌｏｇｉｓｔｉｃ映射，该种映射是一个
典型的混沌系统，其迭代公式如下：
ｚ Ｊ （１ ） ｉ＝０，１，２，…， ∈（２，４ｊ （４） 用式（４）产生大量粒子，然后计算出所有粒子的适应
度值，选择适应度值好的一半粒子作为初始群体。
（２）引入变异和杂交操作。 将初始群体中所有粒子的适应度值进行排序。
从排序后的粒子中取适应度值差的一半粒子，然后 以一定的变异概率 进行变异，具体变异方法是：适应度
值最差的粒子和适应度值最好的粒子交换位置，适应度 值次差的粒子和适应度值次好的粒子交换位置，以此类
推，同时保留每个个体所记忆的个体最好位置。为了不破
坏种群结构，变异概率不能太大。
从排序后的粒子中取适应度值好的一半粒子，然后 以一定的杂交概率 从这部分粒子中选出一定数量的粒
子随机地两两杂交，产生相同数目的子代，并用子代粒子
取代父代粒子，以保持种群的粒子数目不变。杂交算法的
计算公式 如下：
＝ｒ ：＋（１．０一ｒ） （５）
＝ ＋（１．Ｏ－ｒ）Ｘ＇， （６）
＝ ）Ｌ ｆ （７） ；＋ｖｌＩ
ｆ Ｔｌ＝ 竿 Ｊ （８） ：＋ｖｉＩ 式中，ｒ为在区间（０，１）内变化的随机数。ｘ 、 、 和
分别表示子代粒子和父代粒子的位置； 、 ； 、 ：和 ：分
别为子代粒子和父代粒子的速度。
４基于改进粒子群算法的路径规划
路径规划，就是
寻找移动机器人在
环境中移动时所必 须经过的点的集合。
如图１所示，在全局
坐标系０一ＸＹ中，ｓ
为起始点，Ｇ为终点，
黑色实心填充物表
示障碍物，在起点Ｓ 与终点Ｇ之间作图示等分，得到平行直线族（ｆ。，ｚ ，…，
ｆ ），它们与路径的交点（ 。， ，…，Ｋｍ）即为所求的点的集
合。其中点Ｋ 为非障碍物点，它与相邻点的连线上不存
在障碍物点。
在路径规划中适应度函数Ｆ（ｘ）就是起点到终点的无
碰撞距离函数。假设有Ⅳ个粒子，每个粒子都是／＇／＇ｔ维，粒 理论／研发／设计，制造 字木交流
子的各维位置分量取值在对应直线ｆ ，ｆ ，…，ｆ 上。令Ｓ为 Ｋ。，Ｇ为Ｋ ，若不考虑任意两点之间的连线是否穿过障
碍物，则以点所在坐标表示适应度函数为：
＝ 、／（ ）２＋（ｍｍ） ’，Ｎ （９）
由于任意两点间连线有可能穿过障碍物，所以为了
使迭代过程中适应度函数值更合理，同时增加粒子选择
的随机性，对任意两点间距离做如下调整：
假设 为线段Ｋ 上障碍物比例，令
、／‘ ） （ｍ －）
则任意两点问的距离为：
Ｌ “ ，Ｊ Ｍ＝０
Ｌ＇ｘ（１＋ｔａｌｌ（搬手）） ＞争
Ｌ＇ｘ（１＋ｔａｎ（Ｍ× ））其它
改进算法流程如图２所示。
取机器人的活动空间为４００ｘ４００的平面坐标，取种 群规模Ｎ＝５０，粒子维数ｍ＝２０，加速因子Ｃ１＝ｃ ：２，惯性权
重０９随迭代次数增加从０．９５到０．２线性递减，变异概率
＝０．１，杂交概率ｓ＝０．１，取３种不同的地图环境进行研
究，各运行算法２０次，对
应迭代次数分别取 一＝
８００， 一＝８００，ｋ，，￣＝１３００， 允许误差不超过１％。
仿真结果如图３～图 ５所示。图３显示的是在
椭圆形和圆形障碍物群 中找到的最优路径，路径
机械工程师２０１０年第１１期《
２５ 字木交ｉ赢
瑶＇＾，砩发／设计，嗣碴
Ｎ轴承与配件公司质量检测分析及质量责任解决
於骞，金士良，李毅
（上海大学机械工程及自动化学院，上海２０００７２
Ｓｏｌｕｔｉｏｎ ｏｆ Ｑｕａｌｉｔｙ Ｒｅｓｐｏｎｓ．ｂ．１ｉｔｙ ａｎｄ Ａｎａｌｙｓｉｓ ｏｆ Ｑｕａｌｉｔｙ Ｔｅｓｔ ｉｎ Ｎ Ｂｅａｒｉｎｇ ａｎｄ Ａｃｃｅｓｓｏｒｉｅｓ Ｃｏｍｐａｎｙ ＹＵ Ｑｉａｎ，ＪＩＮ Ｓｈｉ－ｌｉａｎｇ。Ｌｉ Ｙｉ （Ｓｃｈｏｏｌ ｕｆ Ｍｅｃｈａｔｒｏｎｉｃｓ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｕｔｏｍａｔｉｏｎ，Ｓｈａｎｇｈａｉ Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ ２０００７２，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｓｏｌｕｔｉｏｎ ｏｆ ｑｕａｌｉｔｙ ｃｏｍｐｌａｉｎｔ ｉＳ ｎｅｃｅｓｓａｒｙ，ｂｅｃａｕｓｅ ｃｏｍｐｌａｉｎｔ ｉＳ ａｌｗａｙｓ ｅｘｉｓｔｅｄ．Ｔｈｅ ｂｅｓｔ ｍｅｔｈｏｄ ｔｏ ＳＯｌＶｅ ｔ’《ｎｎｐｌａｉｎｔ ｉｓ ｕｓｉｎｇ ｄｅｔｅｃｔｉｏｎ．Ｔｈｉｓ ｐａｐｅｒ ｗｉｌｌ ｉｎｔｒｏｄｕｃｅ ｔｈｅ ｔｙｐｅ ｏｆ ｂｅａｒｉｎｇ ｃｏｍｐｌａｉｎｔ ｉｎ Ｎ ｂｅａｒｉｎｇ ａｎｄ ａｃｃｅｓｓｏｒｉｅｓ
ｃｏｍｐａｎｙ ａｎｄ ｔｅｓｔ ｍｅｔｈｏｄ ｗｈｉｃｈ ｃａｎ ｂｅ ｕｓｅｄ ｔｏ ｓｏｌｖｅ ｃｏｍｐｌａｉｎｔ．Ａｔ ｌａｓｔ，ａ ｍｏｄｅｌｉｎｇ ｉｓ ｇｉｖｅｎ ｆｏｒ ｔｏ ｅｘｐｌａｉｎｉｎｇ ｈｏｗ ｔｏ
ｃｏｎｆｉｒｍ ｔｈｅ ｑｕａｌｉｔｙ ｒｅｓｐｏｎｓｉｂｉｌｉｔｙ ｂｙ ｕｓｉｎｇ ｄｅｔｅｃｔｉｏｎ． Ｋｅｙ ｗｏｒｄｓ：ｑｕａｌｉｔｙ ｃｏｍｐｌａｉｎｔ；ｂｅａｒｉｎｇ；ｄｅｔｅｃｔｉｏｎ；ｑｕａｌｉｔｙ ｒｅｓｐｏｎｓｉｂｉｌｉｔｙ
１引言
我们知道，企业在接到客户质量投诉时，如果不及时
处理并给予客户一个满意的答复，就会影响企业与客户
之间的关系。那么应该采用什么方法可以及时地处理质
量投诉问题呢，那就是检测与标准化。 本文将针对轴承公司出现的质量投诉，利用检测分
析的基本方法来解决这些问题，找到质量责任单位，平衡
客户、企业和供应商之间的利益关系。
２ Ｎ轴承企业的轴承质量投诉分类
Ｎ轴承企业的产品质量投诉，主要分为两大类：（１）
长度是５５５．２４３８，在误差范围内成功寻优１８次；图４显
示的是在含有ｕ型障碍物陷阱的障碍物群中所找到的最
优路径，路径长度是５７２．Ｉ３ｌ９，在误差范围内成功寻优
ｌ９次；图５显示的是在复杂的障碍物群中所找到的最优
路径，路径长度为５６１．４３６３，在误差范围内成功寻优ｌ６
次。以上结果表明，该方法可以较好地运用于多种不同的
障碍物环境，即使是在有障碍物陷阱的环境中，机器人也 能很好地逃出陷阱并能找到一条最优路径。虽然不能保 证算法每次都能准确找到最优路径，但是在误差范围内
寻优能力比较高，比较稳定，具有一定的实用价值。 ６结语 本文直接运用改进的粒子群优化算法在环境模型中
进行全局路径搜索，该方法建模容易，理论简单，可以在
２６｛机械工程师２０１０年第１１期 不同的障碍物环境中得到相应的优化轨迹。从仿真结果
可以看出，本文提出的路径规划算法完全可以用于移动
机器人全局路径规划，不失为移动机器人路径规划方面
的一个新方法。 ［参考文献］ ｌ ｌ Ｊ ＫＥＮＮＥＤＹ Ｊ，ＥＢＥＲＨＡＲＴ Ｒ ｃ．Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ ［Ｃ］／／Ｐｒｏｅ．１ＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ，
ＩＶ．Ｐｉｓｃａｔａｗａｙ，ＮＪ：ＩＥＥＥ Ｓｅｒｖｉｃｅ Ｃｅｎｔｅｒ，１９９５：ｌ９４２－１９４８． １ ２ Ｊ ＥＢＥＲＨＡＲＴ Ｒ，ＳＨＩ Ｙ ａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉ ｏＩ１｜ｄｅｖｅｌ０ｐｍｅｎ Ｌ， ａｐｐｌｉｃａｔｉｏｎｓ ａｎｄ ｒｅｓｏｕｒｃｅ［Ｃ］／／１ＥＥＥ Ｉｎｔ Ｃｏｎｇ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ，２００１：８ １－８６． ［３ Ｊ高尚，杨静宇．群智能算法及其应用［Ｍ Ｊ．北京：中国水利水电出 版社，２００６：６３—７９． ［４］ 吕振肃，侯志荣．自适应变异的粒子群优化算法［Ｊ］．电子学报， ２００４．３２（３）：４１６－４２Ｏ． ［５］曾建潮．等．微粒群算法［Ｍ］．北京：科学出版社，２００４． （编辑立明）
作者简介：徐会成（１９８３一）．男。硕士研究生，从事移动机器人路径规 划方面研究： 单建华（１９７９一），男．副教授，博士学位，研究方向为移动机 器人智能控制
收稿日期：２０１０—０８—０４