PSO-AFSA融合算法在拣选路径优化中的应用

周娟娟 吴蒙蒙

【摘要】拣选路径优化问题属于NP难问题，很难求得精确解，因此拣选路径优化的求解方法一直是研究的热点。本文提出PSO-AFSA融合算法（粒子群与人工鱼群融合算法）用于求解拣选路径优化问题，首先利用人工鱼群寻得初始解，然后利用粒子群算法进行寻优，并将结果与公告板上的最优值进行判断，根据判断结果选择迭代寻优算法进行最后的收敛，证实该融合算法在克服粒子群算法易陷入局部最优这一缺陷的同时，求解效率得到很大提高。

【关键词】PSO-AFSA 融合算法 拣选路径优化

一、绪论

目前对求解拣选路径优化问题的研究非常多，除了人至物拣选系统中分类存储模式研究、拣货方式与存储策略等的协同研究等拣选路径优化问题的影响因素研究之外，越来越多的智能算法应用到该问题中，如a*算法、蚁群算法与遗传算法、双层遗传算法、最小生成树算法等。这些算法都能够对拣选路径进行合理优化，在一定程度上提高拣选作业效率、降低拣选作业时间成本。本文提出PSO-AFSA融合算法用来进行拣选路径的优化，在一定程度上克服了粒子群算法易陷入局部最优、人工鱼群算法后期收敛速度慢的缺点，提高了求解效率与求解精确度。

二、PSO-AFSA融合算法

通过对粒子群算法与人工鱼群算法基本原理、流程步骤的研究，从粒子群算法收敛速度快但是容易陷入局部最优值出发，综合考虑人工鱼群算法的全局最优，但是后期收敛速度慢的特点，设计出一种既能提高算法后期收敛速度，又能提高算法的求解准确度的融合算法一粒子群与人工鱼群融合算法。

PSO-AFSA融合算法的实现大致分为以下几步：

第一步：读取待拣选商品坐标，从而获得待拣选商品间的距离矩阵。

第二步：设置人工鱼群与粒子群相关参数，包括粒子数、人工鱼数目、迭代次数、感知距离、拥挤度因子、最多试探次数、认知系数、社会学习系数等基本参数;

第三步：先用人工鱼群算法的适应度函数算出每个个体的适应度值，得到最好值，最好值赋值给公告板;

第四步：按照人工鱼群算法操作，得到最好解与新的种群，并将寻优结果赋值给粒子群算法，运用粒子群算法的快速收敛性进行后续寻优，并将结果与公告板上的值进行对比，更新公告板;

第五步：判断是否满足终止条件，若满足则终止，如果不满足条件，则重复步骤二、三、四步，直至终止。

三、拣选路径优化模型

拣选路径优化问题类似旅行商问题，属于NP难问题，即一个人从一个城市出发，途径多个城市，每个城市仅且只能到达一次，最后回到出发点，同时要求所走路程最短。经典的旅行商问题模型如下：

目標函数（3-1）表示旅行商行走完所有城市的最短距离。约束条件（3-2）和（3-3）表示每个城市只能经过一次，式（3-4）是一个决策变量，如果城市j是在到达城市i后立即到达的则取值为1，否则取值为0，式（3-5）表示不存在小回路。

拣选路径优化问题中，每一件待拣选的商品所在位置可以看作旅行商问题中的城市位置，拣选人员从仓库出口出发，对商品进行逐个拣选，每一个货位都只拣选一次，最后回到仓库入口处，这一过程中，拣选路径优化的目的是对拣选人员行走的路径进行规划，使得拣货作业完成后，所行走的路程最短。

四、算法应用及结论

将融合后的新算法、粒子群算法、人工鱼群算法分别用于所建模型，分别取最优10组解，图1为三种算法分别求解同一组数据所需时间以及求得精确解的对比分析图，每种算法测试十次。由表格对比分析结果可知：在三种算法基本参数相同，数据相同的前提下，粒子群算法的求解速度最快，融合算法次之，人工鱼群算法的求解速度最慢，但是人工鱼群算法与融合算法精确度基本相同，粒子群算法的求解精度最差。PSO-AFSA融合算法在求解时间上虽然稍慢于粒子群，但是其求解精度较好，同时其在求解精度基本相似的情况下，求解效率比基本的人工鱼群算法更高，因此可以得出PSO-AFSA融合算法在一定程度上对两种基本算法有一定的改进。

五、结论

本文通过对粒子群与人工鱼群两种算法进行融合，形成PSO-AFSA融合算法，并将其应用于拣选路径优化问题中，并通过结果分析证实融合后的新算法具有求解优越性，为求解拣选路径优化问题提出一种新的算法。