封建湖，张婷宇，封 硕，郑宝娟

（1.长安大学理学院，陕西 西安710064；2.长安大学工程机械学院，陕西 西安710064）

1 引言

路径规划问题是在有复杂障碍物环境中搜索从初始点到目标点的无碰撞路径［1］。机器人的路径规划即对机器人行驶路径进行合理的决策。对于已知地图环境的情况，粒子群优化（PSO）算法是一种模拟鸟类飞行的优化算法，具有收敛速度快、算法易于实现等优点；遗传算法（GA）是基于生物种群进化的算法，具有全局收敛性的优势。然而这两种算法都有各自的局限性：粒子群算法容易陷入早熟、遗传算法收敛速度较慢等问题。针对这种情况，文献［2］提出了一种PSO和GA的混合算法，混合算法的初始种群由PSO生成，文献［3］人提出了一种只与GA突变算子结合的PSO算法，避免了粒子陷入局部最优。文献［4］在为旅客提供最佳路径选择的旅行商问题中提出PSO-GA算法，得到了很好的效果，但是会造成收敛代数大幅度增加。

针对算法中的不足，引入基于划分的聚类方法中的Kmeans算法，对粒子进行聚类，把粒子划分为若干个子群，使相当数量的具有较优适应度值的粒子位置信息传递到下一代粒子中。对每个子群采用一定规则的交叉和变异算子，从而提高粒子群算法的种群多样性。在每个子区内更新粒子速度和位置时，随着代数的增加改变惯性权重和加速系数。最后通过计算机仿真实验验证了该算法的有效性。

2 传统粒子群算法

粒子群算法是用位置、速度、适应度来描述粒子的运动特征，每次迭代通过跟踪粒子的个体极值Pbest和群体极值Gbest动态更新［5］。……