近年来, 新的智能算法随着计算机技术的发展得到了迅速推广, 这些算法被运用到电子、机械、物流等各个领域, 以解决各种计算与决策问题[1]。自动化立体仓库堆垛机拣选路径优化问题是一个NP-完全问题, 无法求得最优解[2]。因此, 国内很多学者针对该问题开展研究, 运用各种优化算法及混合算法解决路径优化问题。如李梅娟等[3]根据蚁群算法相关特性改进了算法参数设置, 采用自适应方式调整参数, 同时引入选择算子;蔺媛媛等[4]采用动态调整参数与精英调整方法更新信息素, 明显提高了算法寻优性能;倪虹[5]与冯无恙[6]分别提出顺序编码方式及正弦式自适应遗传算法, 对立体仓库路径优化问题进行求解;杨玮等[7]运用模拟退火算法与混合粒子群算法对立体仓库拣选作业进行优化求解。在国外的相关研究中, 如文献[8]中提出一种Embbo算法, 同时对自动化仓库调度问题模型进行求解;AlperBasturka等[9,10]提出一种粗粒度并行模式用于人工蜂群算法并行模型的详细性能分析, 并应用硬件开发服务的多个处理单元减少算法运行时间。这些算法对于求解N-P问题都有着良好效果[11]。

然而, 当求解问题规模大且复杂度高时, 传统优化算法求解效率较低, 而如今硬件技术的迅速发展为实现并行计算提供了可能。粗粒度并行遗传算法是一种易于并行化的算法, 近年来被很多研究者用于求解各种最优化问题。一些学者将各种并行技术如OpenCL技术、Spark技术、Cuda技术与MPI模式, 运用到粗粒度并行遗传算法中, 并在计算机平台上进行计算, 从而极大地提高了算法求解效率。

本文针对粗粒度并行遗传算法后期进化速度慢且容易过早收敛的缺点, 对各子种群采用不同的变异与交叉策略, 并根据粗粒度各子种群独立进化的特点, 运用易与之结合的SPMD并行结构进行编程, 缩短算法优化时间。最后通过对自动化立体仓库路径优化问题的求解, 验证改进的粗粒度并行遗传算法并行计算的性能与求解效果。

在接收到调度中心指令后, 堆垛机从起点位置出发, 根据拣选货单的顺序依次拣选货物, 之后回到起始位置将货物放到出库台, 完成拣选工作[11]。由于拣选货物的数量与拣选位置都是随机的, 货物拣选顺序则会影响作业时间, 图1为堆垛机拣选过程原理。

图1 堆垛机拣选路径  下载原图

假设1:堆垛机拣选货物时间只与拣选货物顺序相关, 与拣选货物种类及数量无关。

假设2:忽略堆垛机取出货物的时间, 拣选货物容量不大于周转箱的容量M。

假设3:将堆垛机横向运行速度设为Vx, 纵向升降速度设为Vy。堆垛机设计运行的速度为Vx与Vy的叠加, 堆垛机升降与前进速度恒定。

假设4:在实际操作中, 堆垛机并非匀速运行, 但为了计算方便, 本文假设堆垛机全程匀速行驶。该方式虽然对计算值有一定影响, 但对拣选顺序的选择没有影响。

以坐标 (x, y) 表示货位点坐标, x与y分别表示货架的层号与列号, 其中 (0, 0) 为堆垛机出发点, 也是巷道口位置, 货位i到货位j的时间可表示为t (i, j) [12]。

式 (1) 中的Xi与Xj表示货位点横坐标, Yi与Yj表示货位点纵坐标, Cx、、Cy分别表示堆垛机水平及垂直运行速度。a为单个货格宽度, b为单个货格高度。结合式 (1) 可以得到拣选n件货物所需的总时间[12]。

式 (2) 中的t (i, j) 表示第i个货位点到第j个货位点所需的时间, t (n, 0) 表示拣选最后一个货位点到原点的时间。

自动化立体仓库货物拣选问题类似于对称旅行商问题 (TSP问题) 。假设有n个城市的集合C={c1, c2, c3, …, cn}, L={lij|ci, cjC}是集合C中元素两两连接的集合, G= (C, L) 是一个有向图[13], 求有向图最短路径的数学模型可表示为:

其中第1个与第2个约束条件是保证每个货位点只拣选一次, 第3个约束条件中的0与1分别表示不拣选该货位点与拣选该货位点, 第4个约束条件是保证拣选的货位数小于S集合中货位之间两两相连的路径数。

并行遗传算法可分为3类:主从式模型 (masterslave) 、细粒度模型 (fine-graining) 与粗粒度模型 (coarsegraning) 。相比于其它两种模型, 粗粒度模型更易于实现, 且应用更加广泛, 因此本文主要研究粗粒度模型的并行计算[14]。粗粒度模型也称为岛屿模型, 在该模型的处理机上, 子种群所含个体数量大于1, 每个子种群的运算过程相当于一个单独标准遗传算法的计算过程。

粗粒度并行遗传算法步骤与遗传算法基本一致, 但也存在一些差异:一是在初始种群产生后, 主进程对初始种群进行划分, 得到若干子种群;二是在变异操作执行完成后, 要判断是否达到可迁移的代数, 然后进行种群迁移操作。粗粒度并行遗传算法运行流程如图2所示。

本文将两种不同的自适应变异方法相结合, 并运用到不同种群, 可有效发挥不同变异策略的优点。第一种自适应变异策略主要利用适应度值的变化调整变异概率, 该策略被很多学者采用并取得了较好效果;第二种策略设置了两个变异概率, 使变异概率大小不仅受种群适应度值大小影响, 还受到两个变异参数制约[15]。

图2 粗粒度并行遗传算法流程  下载原图

公式中的参数意义如下:Pm1是变异概率参数, 大小根据实际情况加以确定;式 (4) 、式 (5) 中的fmax是种群中的最大适应度值;favg是种群中所有个体的平均适应度值;f是当前计算个体的适应度值。

传统的粗粒度并行遗传算法利用完全网络拓扑方式实现子种群之间的迁移, 该迁移方式的迁移率是固定的, 也有学者对迁移率进行了调整并取得了很好效果。本文将一种新的动态调整迁移率策略与完全网络拓扑相结合, 从而使各种群能够协同进化、均衡进化, 避免陷入局部最优。

(1) 动调整迁移率策略[16]。假设N个子种群中有i、j两个子种群, 则M (i, j) 表示i到j的迁移率。i和j的相对平均适应度分别为:。

其中fa表示第i个子种群的平均适应度值, fb表示第j个子种群的平均适应度值, Mij表示i到j的迁移率。

(2) 完全网络拓扑。将各子种群中适应度值最大的个体迁入其它种群中, 使精英个体得以保留, 群体的平均适应度值逐步增加[17]。

(3) 种群个体迁移。本文采用同步迁移策略, 同步迁移指种群中个体迁移步调一致, 子种群进化到一定代数后则进行同步迁移[14,15]。子种群个体迁移原理如图3所示。

图3 子种群个体迁移原理  下载原图

Matlab语言自带并行计算工具箱, 只要编写符合要求的并行程序, 便可利用多核处理器对程序进行加速, 提高程序执行效率。Matlab有多种并行结构, 常用且并行效率较高的并行结构有parfor并行结构与SPMD并行结构。由于SPMD并行结构的灵活性比parfor并行结构好, 而且子任务之间可以实现数据交换, 因此本文选用SPMD并行结构对粗粒并行遗传算法进行并行编程。

SPMD (Single Program, Mutiple Data) 是Matlab支持的一种并行结构。在该结构中, 每个worker都接收相同程序, 但是处理的数据各不相同。SPMD并行结构比parfor并行结构更加灵活, 但也引入了更加复杂的数据类型与操作方法[10]。

在Matlab并行计算池中存在多个lab, 每个lab对应唯一编号。如果开启共有两个lab的Matlab并行计算池, 则第一个lab编号为1, 第二个lab编号为2。在SPMD并行结构中可以采用labindex函数获取或接收数据[18,19]。

Matlab客户端通过composite数据类型访问SPMD并行结构中的变量, Matlab客户端与lab之间的数据通信原理如图4所示。

图4 Matlab客户端与lab之间数据通信  下载原图

步骤1:参数设置、时间矩阵产生。交叉概率Pc=0.9, 变异概率Pm1=0.1, Pm2=0.03;初始种群大小popsize=200;子种群规模subpopsize=50;货位点数量citys-ize=30。

步骤2:随机产生初始种群。population (i, :) =rand-perm (citysize)

步骤3:种群划分。子种群数目设置为4, 并将数据类型转换为元胞数组。

步骤4:进入SPMD循环体并行计算。

求出种群中个体的适应值:

找到最优个体位置:

轮盘赌选择:

交叉操作:种群1分为B1和B2, 随机产生交叉点p=unidrnd ( (citysize-1) , 1, 1) ;M (i, 1:p) =B1 (i, 1:p) ;M (i, p:) =B2 (i, :) 。

变异操作:根据Pm=Pm1- (Pm1-Pm2) * (fmaxftemp (d) ) / (fmax-favg) 与Pm= (fmax-ftemp (d) ) / (fmax-favg) 变异概率判断是否变异。

随机生成两个变异:

两个变异点序号互换:

种群迁移:种群1、2个体迁移到种群3、4。

种群3、4接收种群1、2传入的个体。

完全网络拓扑:种群1、2将最优个体传输给种群3、4。

种群3、4接收种群1、2传入的个体并赋值给最小个体。

步骤5:获取结果并输出。

数据类型转换以及求最优解:

获取最优路径:bestpath=pop (posbest, :) 。

输出最优解:disp (gbest) 。

绘制优化曲线:plot (trace1 (:, 1) , 'g') 。

以浙江某电器公司自动化立体仓库的货物拣选为例, 公司的自动化立体仓库货架类型为单巷道双排固定货架 (9层×70列) , 每条巷道由一台堆垛机进行拣选。根据公司仓库的特点, 堆垛机在巷道内按X、Y、Z3个坐标方向运行, 将货格内产品装载到周转箱, 然后沿指定路径送到出库台, 堆垛机的水平运行速度范围为0.3~0.8m/s, 升降速度范围为0.1~0.5m/s, 堆垛机平均运行速度为:Vx=0.4m/s, Vy=0.2m/s。随机产生订货单并根据出库单拣选货物, 得到50个待拣选货物, 其货位点坐标为:{0, 0;31, 5;33, 7;3, 8;8, 2;14, 6;44, 5;0, 7;23, 1;46, 1;57, 6;25, 0;32, 5;42, 5;30, 8;29, 7;4, 5;70, 9;58, 3;66, 8;53, 3;19, 8;18, 7;55, 4;65, 5;52, 1;10, 9;16, 3;64, 9;70, 1;33, 6;18, 6;20, 8;21, 7;32, 4;15, 9;17, 6;11, 4;26, 4;29, 9;47, 3;31, 6;50, 1;36, 7;39, 5;21, 1;37, 5;13, 1;28, 1;22, 2}。粗粒度并行遗传算法参数设置为:Pc=0.9;Pm1=0.1;Pm2=0.03;popsize=200;subpopsize=50;citysize=30, 子种群个数为4个。在matlab2016a上编程并在处理器型号为Intel (R) Core (TM) i3-2330M CPU@2.20GHz的计算机上各求解20次, 得到粗粒度并行遗传算法计算结果及加速比如表1所示。

    下载原表

分别用遗传算法、蚁群遗传算法求解自动化立体仓库堆垛机拣选路径, 并将最优迭代次数下的计算结果与粗粒度并行遗传算法计算结果进行比较, 如表2所示。

    下载原表

并行计算过程CPU利用率如图5所示, 粗粒度并行遗传算法迭代1 000次的最优解变化曲线如图6所示。

图5 CPU利用率  下载原图

表1显示了并行计算加速效果, 理论上加速比接近2倍, 但是由于通信消耗、数据交互的影响, 加速效果尚不是最佳, 但仍可以有效提高处理器利用率, 实现对程序的加速, 并提高算法性能。

由表2可以看出, 粗粒度并行遗传算法的计算时间比其它几种算法明显偏短, 且收敛速度更快。这是因为粗粒度并行遗传算法在求解时, CPU利用率达到100%, 其在并行计算过程中充分利用了计算机多核运算能力, 从而极大缩短了计算时间。图6的优化曲线也显示了改进后的粗粒度并行遗传算法进化速度较快, 这是因为应用变异策略与迁移策略的结果。

图6 粗粒度并行遗传算法迭代过程曲线  下载原图

本文在传统粗粒度并行遗传算法基础上对算法的变异策略进行改进, 同时对传统粗粒度并行遗传算法的迁移策略进行优化, 采用动态迁移策略与完全网络拓扑相结合的迁移方式, 以提高子算法的进化速度与个体多样性。同时本文重点介绍了SPMD并行计算方法的应用, 采用SPMD并行结构对程序进行并行编程, 实现了对程序的加速, 提高了程序执行效率。实践结果表明, 基于SPMD的并行遗传算法能够有效提高自动化立体仓库的拣选效率。本文研究结果可为解决相似问题提供参考, 还可以作为多处理机并行计算的基础。