基于SPMD的粗粒度并行遺傳算法在立體倉(cāng)庫(kù)路徑優(yōu)化中的應(yīng)用

陳榮虎 何運(yùn)杰

摘要：為了提高粗粒度并行遺傳算法性能，縮短對(duì)立體倉(cāng)庫(kù)路徑優(yōu)化問(wèn)題的求解時(shí)間，將一種單程序多數(shù)據(jù)流（簡(jiǎn)稱SPMD）并行結(jié)構(gòu)運(yùn)用到粗粒度并行遺傳算法中，并對(duì)算法進(jìn)行改進(jìn)。通過(guò)對(duì)自動(dòng)化立體倉(cāng)庫(kù)揀選路徑優(yōu)化模型的求解，得到串行與并行計(jì)算兩種情況下的運(yùn)算時(shí)間與加速比，并在求解精度相差不大的情況下，將改進(jìn)算法的計(jì)算時(shí)間與遺傳算法、蟻群遺傳算法進(jìn)行比較。對(duì)比結(jié)果表明，并行計(jì)算能有效提高算法優(yōu)化效率，縮短程序執(zhí)行時(shí)間。該研究對(duì)于解決自動(dòng)化立體倉(cāng)庫(kù)堆垛揀選路徑優(yōu)化問(wèn)題有著重要的現(xiàn)實(shí)意義。

關(guān)鍵詞：粗粒度并行遺傳算法;SPMD并行結(jié)構(gòu);自動(dòng)化立體倉(cāng)庫(kù);并行計(jì)算;加速比

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?引言

近年來(lái)，新的智能算法隨著計(jì)算機(jī)技術(shù)的發(fā)展得到了迅速推廣，這些算法被運(yùn)用到電子、機(jī)械、物流等各個(gè)領(lǐng)域，以解決各種計(jì)算與決策問(wèn)題[1]。自動(dòng)化立體倉(cāng)庫(kù)堆垛機(jī)揀選路徑優(yōu)化問(wèn)題是一個(gè)NP?完全問(wèn)題，無(wú)法求得最優(yōu)解[2]。因此，國(guó)內(nèi)很多學(xué)者針對(duì)該問(wèn)題開展研究，運(yùn)用各種優(yōu)化算法及混合算法解決路徑優(yōu)化問(wèn)題。如李梅娟等[3]根據(jù)蟻群算法相關(guān)特性改進(jìn)了算法參數(shù)設(shè)置，采用自適應(yīng)方式調(diào)整參數(shù)，同時(shí)引入選擇算子;藺媛媛等[4]采用動(dòng)態(tài)調(diào)整參數(shù)與精英調(diào)整方法更新信息素，明顯提高了算法尋優(yōu)性能;倪虹[5]與馮無(wú)恙[6]分別提出順序編碼方式及正弦式自適應(yīng)遺傳算法，對(duì)立體倉(cāng)庫(kù)路徑優(yōu)化問(wèn)題進(jìn)行求解;楊瑋等[7]運(yùn)用模擬退火算法與混合粒子群算法對(duì)立體倉(cāng)庫(kù)揀選作業(yè)進(jìn)行優(yōu)化求解。在國(guó)外的相關(guān)研究中，如文獻(xiàn)[8]中提出一種Embbo算法，同時(shí)對(duì)自動(dòng)化倉(cāng)庫(kù)調(diào)度問(wèn)題模型進(jìn)行求解;AlperBasturka等[9?10]提出一種粗粒度并行模式用于人工蜂群算法并行模型的詳細(xì)性能分析，并應(yīng)用硬件開發(fā)服務(wù)的多個(gè)處理單元減少算法運(yùn)行時(shí)間。這些算法對(duì)于求解N?P問(wèn)題都有著良好效果[11]。

然而，當(dāng)求解問(wèn)題規(guī)模大且復(fù)雜度高時(shí)，傳統(tǒng)優(yōu)化算法求解效率較低，而如今硬件技術(shù)的迅速發(fā)展為實(shí)現(xiàn)并行計(jì)算提供了可能。粗粒度并行遺傳算法是一種易于并行化的算法，近年來(lái)被很多研究者用于求解各種最優(yōu)化問(wèn)題。一些學(xué)者將各種并行技術(shù)如OpenCL技術(shù)、Spark技術(shù)、Cuda技術(shù)與MPI模式，運(yùn)用到粗粒度并行遺傳算法中，并在計(jì)算機(jī)平臺(tái)上進(jìn)行計(jì)算，從而極大地提高了算法求解效率。

3?粗粒度并行遺傳算法并行計(jì)算

3.1?SPMD并行結(jié)構(gòu)

Matlab語(yǔ)言自帶并行計(jì)算工具箱，只要編寫符合要求的并行程序，便可利用多核處理器對(duì)程序進(jìn)行加速，提高程序執(zhí)行效率。Matlab有多種并行結(jié)構(gòu)，常用且并行效率較高的并行結(jié)構(gòu)有parfor并行結(jié)構(gòu)與SPMD并行結(jié)構(gòu)。由于SPMD并行結(jié)構(gòu)的靈活性比parfor并行結(jié)構(gòu)好，而且子任務(wù)之間可以實(shí)現(xiàn)數(shù)據(jù)交換，因此本文選用SPMD并行結(jié)構(gòu)對(duì)粗粒并行遺傳算法進(jìn)行并行編程。

3.1.1?SPMD并行結(jié)構(gòu)原理

SPMD（Single Program，Mutiple Data）是Matlab支持的一種并行結(jié)構(gòu)。在該結(jié)構(gòu)中，每個(gè)worker都接收相同程序，但是處理的數(shù)據(jù)各不相同。SPMD并行結(jié)構(gòu)比parfor并行結(jié)構(gòu)更加靈活，但也引入了更加復(fù)雜的數(shù)據(jù)類型與操作方法[10]。

3.1.2?Matlab客戶端lab之間的通信

在Matlab并行計(jì)算池中存在多個(gè)lab，每個(gè)lab對(duì)應(yīng)唯一編號(hào)。如果開啟共有兩個(gè)lab的Matlab并行計(jì)算池，則第一個(gè)lab編號(hào)為1，第二個(gè)lab編號(hào)為2。在SPMD并行結(jié)構(gòu)中可以采用labindex函數(shù)獲取或接收數(shù)據(jù)[18?19]。

Matlab客戶端通過(guò)composite數(shù)據(jù)類型訪問(wèn)SPMD并行結(jié)構(gòu)中的變量，Matlab客戶端與lab之間的數(shù)據(jù)通信原理如圖4所示。

3.2?粗粒度并行遺傳算法計(jì)算

步驟1：參數(shù)設(shè)置、時(shí)間矩陣產(chǎn)生。交叉概率Pc=0.9，變異概率 P?m1=0.1，P?m2=0.03;初始種群大小popsize=200;子種群規(guī)模subpopsize=50;貨位點(diǎn)數(shù)量citysize=30。

步驟2：隨機(jī)產(chǎn)生初始種群。 population（i，：）=randperm（citysize）

步驟3：種群劃分。子種群數(shù)目設(shè)置為4，并將數(shù)據(jù)類型轉(zhuǎn)換為元胞數(shù)組。

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

步驟4：進(jìn)入SPMD循環(huán)體并行計(jì)算。

求出種群中個(gè)體的適應(yīng)值：

ftemp=fitness（Chrom{i}，D）

找到最優(yōu)個(gè)體位置：

[fmax，posbest]=max（ftemp）

輪盤賭選擇：

sigma=sigma+probability（c，1）

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

交叉操作：種群1分為B?1和B?2，隨機(jī)產(chǎn)生交叉點(diǎn)p=unidrnd（（citysize-1），1，1）;M（i，1：p）=B?1（i，1：p）;M（i，p：）=B?2（i，：） 。

變異操作：根據(jù) P?m=P?m1-（P?m1-P?m2）*（fmax-ftemp（d））/（fmax-favg）與P?m=（fmax-ftemp（d））/（fmax-favg）變異概率判斷是否變異。

隨機(jī)生成兩個(gè)變異：

m=unidrnd（citysize，1，2）

兩個(gè)變異點(diǎn)序號(hào)互換：

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

種群遷移：種群1、2個(gè)體遷移到種群3、4。

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

種群3、4接收種群1、2傳入的個(gè)體。

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

完全網(wǎng)絡(luò)拓?fù)洌悍N群1、2將最優(yōu)個(gè)體傳輸給種群3、4。

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

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

種群3、4接收種群1、2傳入的個(gè)體并賦值給最小個(gè)體。

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

步驟5：獲取結(jié)果并輸出。

數(shù)據(jù)類型轉(zhuǎn)換以及求最優(yōu)解：

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

獲取最優(yōu)路徑：bestpath=pop（posbest，：）。

輸出最優(yōu)解：disp（gbest）。

繪制優(yōu)化曲線：plot（trace1（：，1），'g'） 。

4?實(shí)例求解

以浙江某電器公司自動(dòng)化立體倉(cāng)庫(kù)的貨物揀選為例，公司的自動(dòng)化立體倉(cāng)庫(kù)貨架類型為單巷道雙排固定貨架（9層×70列），每條巷道由一臺(tái)堆垛機(jī)進(jìn)行揀選。根據(jù)公司倉(cāng)庫(kù)的特點(diǎn)，堆垛機(jī)在巷道內(nèi)按?X、Y、Z?3個(gè)坐標(biāo)方向運(yùn)行，將貨格內(nèi)產(chǎn)品裝載到周轉(zhuǎn)箱，然后沿指定路徑送到出庫(kù)臺(tái)，堆垛機(jī)的水平運(yùn)行速度范圍為0.3～0.8m/s，升降速度范圍為0.1～0.5m/s，堆垛機(jī)平均運(yùn)行速度為：?V?x?=0.4m/s，?V?y=?0.2m/s。隨機(jī)產(chǎn)生訂貨單并根據(jù)出庫(kù)單揀選貨物，得到50個(gè)待揀選貨物，其貨位點(diǎn)坐標(biāo)為： {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}。粗粒度并行遺傳算法參數(shù)設(shè)置為：P?c=0.9;P?m1=0.1;P?m2=0.03;popsize=200;subpopsize=50; citysize=30，子種群個(gè)數(shù)為4個(gè)。在matlab2016a上編程并在處理器型號(hào)為Intel（R）Core（TM） i3-2330M CPU @2.20GHz的計(jì)算機(jī)上各求解20次，得到粗粒度并行遺傳算法計(jì)算結(jié)果及加速比如表1所示。

分別用遺傳算法、蟻群遺傳算法求解自動(dòng)化立體倉(cāng)庫(kù)堆垛機(jī)揀選路徑，并將最優(yōu)迭代次數(shù)下的計(jì)算結(jié)果與粗粒度并行遺傳算法計(jì)算結(jié)果進(jìn)行比較，如表2所示。

并行計(jì)算過(guò)程CPU利用率如圖5所示，粗粒度并行遺傳算法迭代1 000次的最優(yōu)解變化曲線如圖6所示。

表1顯示了并行計(jì)算加速效果，理論上加速比接近2倍，但是由于通信消耗、數(shù)據(jù)交互的影響，加速效果尚不是最佳，但仍可以有效提高處理器利用率，實(shí)現(xiàn)對(duì)程序的加速，并提高算法性能。

由表2可以看出，粗粒度并行遺傳算法的計(jì)算時(shí)間比其它幾種算法明顯偏短，且收斂速度更快。這是因?yàn)榇至６炔⑿羞z傳算法在求解時(shí)，CPU利用率達(dá)到100%，其在并行計(jì)算過(guò)程中充分利用了計(jì)算機(jī)多核運(yùn)算能力，從而極大縮短了計(jì)算時(shí)間。圖6的優(yōu)化曲線也顯示了改進(jìn)后的粗粒度并行遺傳算法進(jìn)化速度較快，這是因?yàn)閼?yīng)用變異策略與遷移策略的結(jié)果。

5?結(jié)語(yǔ)

本文在傳統(tǒng)粗粒度并行遺傳算法基礎(chǔ)上對(duì)算法的變異策略進(jìn)行改進(jìn)，同時(shí)對(duì)傳統(tǒng)粗粒度并行遺傳算法的遷移策略進(jìn)行優(yōu)化，采用動(dòng)態(tài)遷移策略與完全網(wǎng)絡(luò)拓?fù)湎嘟Y(jié)合的遷移方式，以提高子算法的進(jìn)化速度與個(gè)體多樣性。同時(shí)本文重點(diǎn)介紹了SPMD并行計(jì)算方法的應(yīng)用，采用SPMD并行結(jié)構(gòu)對(duì)程序進(jìn)行并行編程，實(shí)現(xiàn)了對(duì)程序的加速，提高了程序執(zhí)行效率。實(shí)踐結(jié)果表明，基于SPMD的并行遺傳算法能夠有效提高自動(dòng)化立體倉(cāng)庫(kù)的揀選效率。本文研究結(jié)果可為解決相似問(wèn)題提供參考，還可以作為多處理機(jī)并行計(jì)算的基礎(chǔ)。

參考文獻(xiàn)：

[1]?曾強(qiáng)，張澤斌，楊龍飛，等.有容量限制的自動(dòng)化立體倉(cāng)庫(kù)堆垛機(jī)路徑規(guī)劃優(yōu)化方法[J].機(jī)械設(shè)計(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]?李梅娟，陳雪波，王莉.多巷道固定貨架揀選作業(yè)優(yōu)化問(wèn)題的研究[J].控制與決策，2008，23（12）：1338?1342.

[4]?藺媛媛，劉云.立體倉(cāng)庫(kù)固定貨架揀選路徑優(yōu)化的蟻群算法研究[J].中國(guó)西部科技，2010，9（11）：12?14.

[5]?馬清悅，張紀(jì)會(huì)，宋曉鵬，等.基于啟發(fā)式算法的自動(dòng)化立體倉(cāng)庫(kù)揀貨路徑優(yōu)化研究[J].青島大學(xué)學(xué)報(bào)：工程技術(shù)版，2012，27（3）：31?34.

[6]?馮無(wú)恙.基于自適應(yīng)遺傳算法的自動(dòng)化立體倉(cāng)庫(kù)堆垛機(jī)路徑優(yōu)化研究[D].蘭州：蘭州理工大學(xué)，2011.

[7]?楊瑋，李程，傅衛(wèi)平，等.自動(dòng)化立體倉(cāng)庫(kù)固定貨架揀選路徑問(wèn)題研究[J].上海理工大學(xué)學(xué)報(bào)，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]?李士勇.智能優(yōu)化算法原理與應(yīng)用[M].哈爾濱：哈爾濱工業(yè)大學(xué)出版社，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]?梁旭，黃明，寧濤.現(xiàn)代智能優(yōu)化混合算法及其應(yīng)用[M].北京：電子工業(yè)出版社，2014.

[14]?岳嵚.粗粒度并行遺傳算法的計(jì)算性能及其應(yīng)用研究[D].武漢：華中科技大學(xué)，2008.

[15]?許智宏，趙嘉偉，董永峰，等.基于Spark的并行遺傳算法在旅行商問(wèn)題中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究，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]?肖國(guó)強(qiáng)，王麗萍，彭斌.遺傳算法及其并行性研究[J].微處理機(jī)，2007，28（5）：68?70.

[18]?劉維.實(shí)戰(zhàn)Matlab之并行程序設(shè)計(jì)[M].北京：北京航空航天大學(xué)出版社，2012.

[19]?劉文志.并行算法設(shè)計(jì)與性能優(yōu)化[M].北京：機(jī)械工業(yè)出版社，2015.