基于SPMD的粗粒度并行遗传算法在立体仓库路径优化中的应用

陈荣虎 何运杰

摘要：为了提高粗粒度并行遗传算法性能，缩短对立体仓库路径优化问题的求解时间，将一种单程序多数据流（简称SPMD）并行结构运用到粗粒度并行遗传算法中，并对算法进行改进。通过对自动化立体仓库拣选路径优化模型的求解，得到串行与并行计算两种情况下的运算时间与加速比，并在求解精度相差不大的情况下，将改进算法的计算时间与遗传算法、蚁群遗传算法进行比较。对比结果表明，并行计算能有效提高算法优化效率，缩短程序执行时间。该研究对于解决自动化立体仓库堆垛拣选路径优化问题有着重要的现实意义。

关键词：粗粒度并行遗传算法;SPMD并行结构;自动化立体仓库;并行计算;加速比

Application of Coarse grained Parallel Genetic Algorithm

Based on SPMD in Path Optimization of Stereo Warehouse

CHEN Rong hu， HE Yun jie

（School of Management Science & Engineering， Anhui University of Technology， Maanshan 243032，China）

Abstract：In order to improve the performance of coarse grained parallel genetic algorithm and shorten the time to solve the problem of path optimization of stereoscopic warehouse， this paper applies a single program multi data stream （SPMD based） parallel structure to coarse grained parallel genetic algorithm and improves the algorithm. By solving the optimization model of picking path in automated warehouse， the computing time and speedup ratio are obtained in the case of serial and parallel algorithm， and the computation time of the improved algorithm are compared with the genetic algorithm and Ant colony genetic algorithm （AGA） when the accuracy of the solution is not different from each other. The results show that parallel computing can effectively improve the optimization efficiency and shorten the program execution time. This paper has a certain reference to the research of parallel genetic algorithm and also to the study of parallel computing. It is of great practical significance to solve the problem of route optimization of stacking and picking in automated stereoscopic warehouse.

Key Words：coarse grained parallel genetic algorithm;SPMD parallel structure; automated stereoscopic warehouse; parallel computing;speed up ratio

0 引言

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

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

3 粗粒度并行遗传算法并行计算

3.1 SPMD并行结构

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

3.1.1 SPMD并行结构原理

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

3.1.2 Matlab客户端lab之间的通信

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

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

3.2 粗粒度并行遗传算法计算

步骤1：参数设置、时间矩阵产生。交叉概率Pc=0.9，变异概率 P m1=0.1，P m2=0.03;初始种群大小popsize=200;子种群规模subpopsize=50;货位点数量citysize=30。

步骤2：随机产生初始种群。 population（i，：）=randperm（citysize）

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

Chrom=cell（4，1）;Chrom{i}=population{i}

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

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

ftemp=fitness（Chrom{i}，D）

找到最优个体位置：

[fmax，posbest]=max（ftemp）

轮盘赌选择：

sigma=sigma+probability（c，1）

chosednum（j，1）=c;B=Chrom{i}（chosednum，：）

交叉操作：种群1分为B 1和B 2，随机产生交叉点p=unidrnd（（citysize-1），1，1）;M（i，1：p）=B 1（i，1：p）;M（i，p：）=B 2（i，：） 。

变异操作：根据 P m=P m1-（P m1-P m2）*（fmax-ftemp（d））/（fmax-favg）与P m=（fmax-ftemp（d））/（fmax-favg）变异概率判断是否变异。

随机生成两个变异：

m=unidrnd（citysize，1，2）

两个变异点序号互换：

M（d，mini：maxin）=M（d，maxin：-1：minin）

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

A=labBroadcast（1，Chrom{i}（1：c，：））

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

M=labBroadcast（1）;Chrom{i}（1：c，：）=M

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

A=labBroadcast（1，Chrom{i}（1：c，：）

B=labBroadcast（2，Chrom{i}（1：c，：））

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

M=labBroadcast（1）;Chrom{i}（nmin3，：）=M;N=labBroadcast（2）;Chrom{i}（nmin4，：）=N

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

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

[gbest，posbest]=min（cell2mat（timeson{1，2}））。

获取最优路径：bestpath=pop（posbest，：）。

输出最优解：disp（gbest）。

绘制优化曲线：plot（trace1（：，1），'g'） 。

4 实例求解

以浙江某电器公司自动化立体仓库的货物拣选为例，公司的自动化立体仓库货架类型为单巷道双排固定货架（9层×70列），每条巷道由一台堆垛机进行拣选。根据公司仓库的特点，堆垛机在巷道内按 X、Y、Z 3个坐标方向运行，将货格内产品装载到周转箱，然后沿指定路径送到出库台，堆垛机的水平运行速度范围为0.3～0.8m/s，升降速度范围为0.1～0.5m/s，堆垛机平均运行速度为： V x =0.4m/s， V y= 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}。粗粒度并行遗传算法参数设置为：P c=0.9;P m1=0.1;P m2=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所示。

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

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

5 结语

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

参考文献：

[1] 曾强，张泽斌，杨龙飞，等.有容量限制的自动化立体仓库堆垛机路径规划优化方法[J].机械设计与制造，2015（1）：172 176.

[2] GIANNIKAS V， LU W， ROBERTSON B， et al. An interventionist strategy for warehouse order picking： evidence from two case studies[J]. International Journal of Production Economics， 2017：189.

[3] 李梅娟，陈雪波，王莉.多巷道固定货架拣选作业优化问题的研究[J].控制与决策，2008，23（12）：1338 1342.

[4] 蔺媛媛，刘云.立体仓库固定货架拣选路径优化的蚁群算法研究[J].中国西部科技，2010，9（11）：12 14.

[5] 马清悦，张纪会，宋晓鹏，等.基于启发式算法的自动化立体仓库拣货路径优化研究[J].青岛大学学报：工程技术版，2012，27（3）：31 34.

[6] 冯无恙.基于自适应遗传算法的自动化立体仓库堆垛机路径优化研究[D].兰州：兰州理工大学，2011.

[7] 杨玮，李程，傅卫平，等.自动化立体仓库固定货架拣选路径问题研究[J].上海理工大学学报，2015（1）：84 88.

[8] MA H， SU S， DAN S， et al. Ensemble multi objective biogeography based optimization with application to automated warehouse scheduling[J]. Engineering Applications of Artificial Intelligence， 2015， 44：79 90.

[9] S S HERAGU， L DU， R J MANTEL， et al. Mathematical model for warehouse design and product allocation[J]. International Journal of Production Research， 2005，43（2）：327 338.

[10] BASTURK A， AKAY R. Performance analysis of the coarse grained parallel model of the artificial bee colony algorithm[J]. Information Sciences， 2013，253：34 55.

[11] 李士勇.智能优化算法原理与应用[M].哈尔滨：哈尔滨工业大学出版社，2012.

[12] CHANG F L， LIU Z X， XIN Z， et al. Research on order picking optimization problem of automated warehouse[J]. Systems Engineering Theory & Practice， 2007，27（2）：139 143.

[13] 梁旭，黄明，宁涛.现代智能优化混合算法及其应用[M].北京：电子工业出版社，2014.

[14] 岳嵚.粗粒度并行遗传算法的计算性能及其应用研究[D].武汉：华中科技大学，2008.

[15] 许智宏，赵嘉伟，董永峰，等.基于Spark的并行遗传算法在旅行商问题中的应用[J].计算机应用研究，2017，34（7）：2080 2083.

[16] URSANI Z， ESSAM D， CORNFORTH D， et al. Localized genetic algorithm for vehicle routing problem with time windows[J]. Applied Soft Computing， 2011，11（8）：5375 5390.

[17] 肖国强，王丽萍，彭斌.遗传算法及其并行性研究[J].微处理机，2007，28（5）：68 70.

[18] 刘维.实战Matlab之并行程序设计[M].北京：北京航空航天大学出版社，2012.

[19] 刘文志.并行算法设计与性能优化[M].北京：机械工业出版社，2015.