基于反向擴(kuò)散災(zāi)變和精英增強(qiáng)進(jìn)化的自適應(yīng)蝴蝶算法求解MFCAP問(wèn)題

高 帥，管興胤，郝 帥，葉 洋

(西北核技術(shù)研究所，陜西 西安 710024)

設(shè)施布局問(wèn)題(facility layout problem，F(xiàn)LP) 是制造業(yè)和服務(wù)產(chǎn)業(yè)中廣泛存在的一個(gè)重要問(wèn)題，主要是針對(duì)工業(yè)和服務(wù)部門空間中的設(shè)施進(jìn)行優(yōu)化布局，以降低系統(tǒng)運(yùn)行過(guò)程中的運(yùn)輸成本、時(shí)間成本和交流成本，提高生產(chǎn)效率和生產(chǎn)質(zhì)量。據(jù)估計(jì)，在制造業(yè)系統(tǒng)中，物料運(yùn)輸成本約占產(chǎn)品總生產(chǎn)成本的20%～ 50%左右，而合理的設(shè)施布局可使這一費(fèi)用減少約10%～ 30%[1]。因此，設(shè)施布局優(yōu)化對(duì)于降低生產(chǎn)成本和提升作業(yè)效率具有顯著的實(shí)際意義。

過(guò)道布置問(wèn)題(corridor allocation problem，CAP)是一種典型的設(shè)施布局問(wèn)題，由Amaral[2]2012年首次提出。該問(wèn)題針對(duì)固定規(guī)模的設(shè)施，將設(shè)施從過(guò)道的最左端開(kāi)始平行地布置在過(guò)道兩邊，通過(guò)合理布置設(shè)施順序使得各設(shè)施間的總物流成本達(dá)到最小。過(guò)道設(shè)施布置結(jié)構(gòu)具有較高的物流運(yùn)輸效率和較低的生產(chǎn)成本，在物流倉(cāng)儲(chǔ)、車間廠房、芯片電路、工業(yè)流水線的布局和醫(yī)院學(xué)校、行政辦公大樓、商業(yè)建筑的規(guī)劃等方面具有重要的應(yīng)用價(jià)值。

CAP屬于NP-hard問(wèn)題，設(shè)施規(guī)模的增加會(huì)使解空間迅速增大且變得稀疏，進(jìn)而導(dǎo)致CAP問(wèn)題陷入維度災(zāi)難，求解難度呈指數(shù)級(jí)增長(zhǎng)。近年來(lái)，許多學(xué)者針對(duì)該問(wèn)題開(kāi)展了廣泛研究。Amaral[2]首先提出并建立了CAP問(wèn)題的數(shù)學(xué)模型，同時(shí)基于2-op算法、3-op算法和爬山法對(duì)CAP問(wèn)題進(jìn)行求解，取得了良好的效果。Ghosh等[3]提出結(jié)合局部搜索策略的遺傳算法和結(jié)合路徑重鏈接策略的分散算法，并應(yīng)用于49個(gè)基準(zhǔn)測(cè)試算例，測(cè)試結(jié)果表明兩種方法均能有效解決CAP問(wèn)題。Ahonen等[4]針對(duì)過(guò)道布置問(wèn)題分別測(cè)試了模擬退火算法和禁忌搜索算法的求解性能，實(shí)驗(yàn)結(jié)果表明，對(duì)于設(shè)施數(shù)量小于30的CAP問(wèn)題，兩種算法均能得到最優(yōu)解；對(duì)于設(shè)施規(guī)模為42～ 70的CAP問(wèn)題，模擬退火算法在求解效率和求解精度方面更有優(yōu)勢(shì)。陳鳳等[5]提出一種考慮設(shè)施布置方向的雙目標(biāo)過(guò)道布置問(wèn)題，采用改進(jìn)分散搜索算法對(duì)其進(jìn)行求解并取得了良好的求解效果。劉俊琦等[6]提出一種考慮多縱向傳輸通道的雙層過(guò)道布置問(wèn)題，并將一種基于路徑重連策略與逆轉(zhuǎn)擾動(dòng)操作策略改進(jìn)的模擬退火-禁忌搜索混合算法應(yīng)用于雙層過(guò)道布置問(wèn)題，數(shù)值實(shí)驗(yàn)結(jié)果表明該算法具有較好的求解性能。管超等[7]構(gòu)建考慮設(shè)施空間布局的雙層過(guò)道布置問(wèn)題，提出一種由改進(jìn)退火過(guò)程與改進(jìn)抽樣過(guò)程構(gòu)成的兩階段改進(jìn)模擬退火算法，顯著提高了算法求解性能。劉思璐等[8]建立一種考慮設(shè)施深度的過(guò)道布置問(wèn)題數(shù)學(xué)模型，并采用改進(jìn)煙花算法進(jìn)行求解，結(jié)果表明，相較于傳統(tǒng)煙花算法，改進(jìn)煙花算法在求解效率和求解質(zhì)量方面具有顯著優(yōu)勢(shì)。

上述文獻(xiàn)都對(duì)CAP問(wèn)題進(jìn)行了深入研究，取得了豐富且具有意義的成果。但上述文獻(xiàn)均假設(shè)物流交互點(diǎn)處于設(shè)施過(guò)道邊線中點(diǎn)位置，未考慮當(dāng)設(shè)施物流交互點(diǎn)與其靠過(guò)道邊線中點(diǎn)不重合時(shí)，設(shè)施作業(yè)鏡像布置情況對(duì)流量成本的影響。

蝴蝶優(yōu)化算法(butterfly optimization algorithm，BOA) 是Arora等[9]于2018年提出一種全局優(yōu)化算法，通過(guò)模擬蝴蝶的覓食和求偶行為實(shí)現(xiàn)對(duì)目標(biāo)問(wèn)題的求解。蝴蝶優(yōu)化算法具有原理清晰明了、調(diào)試方便簡(jiǎn)單、求解結(jié)果穩(wěn)定可靠等優(yōu)點(diǎn)，在旅行商問(wèn)題(traveling salesman problem，TSP) 路徑規(guī)劃[10]、經(jīng)濟(jì)負(fù)荷分配[11-12]、電網(wǎng)資源配置[13]、車間生產(chǎn)調(diào)度[14]、工程設(shè)計(jì)優(yōu)化[15]、圖像降噪處理[16]等工程實(shí)踐中取得了良好的應(yīng)用效果。但迄今為止，尚未發(fā)現(xiàn)有關(guān)BOA求解過(guò)道布置問(wèn)題的公開(kāi)報(bào)道。

鑒于當(dāng)前研究未考慮工業(yè)實(shí)際中設(shè)施物流交互點(diǎn)與其靠過(guò)道邊線中點(diǎn)存在不重合的情況，本文提出一種考慮設(shè)施左右鏡像情況的過(guò)道布置問(wèn)題(mirrorable facility corridor allocation problem,MFCAP)，并建立該問(wèn)題的整數(shù)規(guī)劃模型。利用蝴蝶優(yōu)化算法的特征優(yōu)點(diǎn)，提出一種適用于MFCAP的改進(jìn)離散蝴蝶優(yōu)化算法(improved butterfly optimization algorithm，IBOA) 。該算法在標(biāo)準(zhǔn)蝴蝶優(yōu)化算法的基礎(chǔ)上對(duì)編碼方法和相關(guān)操作進(jìn)行離散化構(gòu)造，并通過(guò)自適應(yīng)模式切換概率、精英增強(qiáng)進(jìn)化、反向擴(kuò)散災(zāi)變等策略提高算法的搜索速度和搜索精度。采用分支定界法(branch and bound algorithm,BBA) 和IBOA兩種方法對(duì)10個(gè)小規(guī)模算例進(jìn)行精確求解以驗(yàn)證所提模型的正確性。分別對(duì)IBOA與BOA及其他啟發(fā)式算法在48個(gè)較大規(guī)模算例中的求解結(jié)果進(jìn)行對(duì)比，以驗(yàn)證所提算法的有效性。

1 MFCAP數(shù)學(xué)模型

1.1 問(wèn)題描述

傳統(tǒng)CAP問(wèn)題中的設(shè)施物流交互點(diǎn)位于設(shè)施靠近通道一側(cè)的中點(diǎn)，但在實(shí)際生產(chǎn)和設(shè)計(jì)要求中，大部分設(shè)施的物流交互點(diǎn)并不位于靠近通道一側(cè)的中點(diǎn)，其與設(shè)施中點(diǎn)之間的距離是設(shè)施布局中需要考慮的重要影響因素。另外，在自動(dòng)化生產(chǎn)線、柔性制造車間和服務(wù)部門建筑結(jié)構(gòu)布局設(shè)計(jì)中，設(shè)施往往可以進(jìn)行左右鏡像布置，進(jìn)而影響物流交互點(diǎn)在過(guò)道上的坐標(biāo)位置。因此，在相同的排列順序下，不同的設(shè)施左右布局情況會(huì)導(dǎo)致總物流成本的不同。圖1為布置順序相同的兩種7規(guī)模設(shè)施布局方案(第1行：{2 5 7 1}；第2行：{4 3 6}) 。a布局方案中所有設(shè)施的物流交互點(diǎn)均位于邊線中心的右側(cè)，b布局方案中設(shè)施4的物流交互點(diǎn)位于邊線中心的左側(cè)，其他設(shè)施的物流交互點(diǎn)均位于邊線中心的右側(cè)。li代表設(shè)施i靠過(guò)道一側(cè)邊線的長(zhǎng)度，ei代表設(shè)施i的邊線中心與物流交互點(diǎn)之間的距離。由圖1可以看出，相較于方案a，方案b中設(shè)施4的物流交互點(diǎn)與其他設(shè)施的物流交互點(diǎn)之間距離均增加了2e4，導(dǎo)致總物流成本的增加。

圖17 規(guī)?？社R像設(shè)施的CAP布局方案Figure 1 CAP layout of 7 mirrorable facilities

考慮到設(shè)施交互中心位置和設(shè)施左右鏡像布局情況對(duì)物流成本的影響，本文提出一種MFCAP問(wèn)題，在傳統(tǒng)CAP數(shù)學(xué)模型的基礎(chǔ)上，通過(guò)引入決策變量來(lái)表示設(shè)施交互中心與邊線中心之間的距離，進(jìn)而建立考慮設(shè)施交互中心位置和設(shè)施左右鏡像布局的MFCAP模型。

1.2 基本假設(shè)條件

為建立MFCAP問(wèn)題的數(shù)學(xué)模型，作出如下假設(shè)和簡(jiǎn)化：

1) 所有設(shè)施的形狀均為矩形，且有一邊緊靠過(guò)道布置；

2) 各設(shè)施間的物流交互成本為一固定且已知量；

3) 各設(shè)施的物流交互點(diǎn)與設(shè)施靠近過(guò)道的邊線中點(diǎn)之間的距離為已知量；

4) 各設(shè)施均可沿自身中心軸線進(jìn)行鏡像；

5) 相鄰設(shè)施之間緊密布置，距離為0；

6) 各行最左端設(shè)施的橫坐標(biāo)均為0，即所有設(shè)施均從所在行的最左端開(kāi)始布放；

7) 過(guò)道的寬度相對(duì)物料搬運(yùn)距離可以忽略不計(jì)，即假設(shè)過(guò)道的寬度為0；

1.3 變量與數(shù)定義

為能夠有效描述模型，定義如下參數(shù)與變量：

n為問(wèn)題規(guī)模，即所需布置的設(shè)施數(shù)量；

I為設(shè)施編號(hào)集合，I={1,2,···,n}；

i，j為設(shè)施編號(hào)，i,j∈I；

cij為設(shè)施i、j之間的單位距離物流成本，?i∈I1，?j∈I2，I1={1,2,···,n-1},I2={i+1,i+2,···,n}；

li為設(shè)施i靠近過(guò)道邊線的長(zhǎng)度；

dij為設(shè)施i和設(shè)施j物流交互點(diǎn)間的橫坐標(biāo)距離；

αij為二進(jìn)制變量，若設(shè)施i、j分配在同一行，且設(shè)施i布置在設(shè)施j的左邊，則αij=1，否則αij=0；

ei為設(shè)施i的物流交互點(diǎn)與其靠過(guò)道邊線中點(diǎn)之間距離；

βi為二進(jìn)制決策變量，若設(shè)施i的流量交互點(diǎn)在該設(shè)施靠過(guò)道邊線中點(diǎn)的左邊，則βi=1，否則βi=0。

1.4 數(shù)學(xué)模型

針對(duì)所提的MFCAP問(wèn)題，建立考慮設(shè)施交互中心位置和設(shè)施左右鏡像布局的過(guò)道布置問(wèn)題數(shù)學(xué)模型。

上述數(shù)學(xué)模型中，式(1) 為目標(biāo)函數(shù)，即最小化總流量成本；式(2) 和式(3) 用于約束確定各設(shè)施之間的距離；式(4) 用于約束避免設(shè)施產(chǎn)生干涉；式(5)～(7) 用于約束決策變量αij的可行域，式(8) 和式(9) 用于約束決策變量αij、βi的可行域。

相較于傳統(tǒng)CAP數(shù)學(xué)模型，MFCAP數(shù)學(xué)模型引入了參數(shù)變量ei表示設(shè)施i的物流交互點(diǎn)與其靠過(guò)道邊線中點(diǎn)之間距離，由于物流交互點(diǎn)必然位于設(shè)施內(nèi)，因此0≤ei＜li/2。引入決策變量βi表示設(shè)施i的流量交互點(diǎn)與靠過(guò)道邊線中點(diǎn)的位置關(guān)系，βi=1表示設(shè)施i的流量交互點(diǎn)在該設(shè)施靠過(guò)道邊線中點(diǎn)的左邊，βi=0表示在右邊或重合。

2 離散蝴蝶優(yōu)化算法

2.1 標(biāo)準(zhǔn)蝴蝶優(yōu)化算法

蝴蝶優(yōu)化算法啟發(fā)于蝴蝶的覓食和求偶行為。群體中的蝴蝶個(gè)體會(huì)產(chǎn)生與其適應(yīng)度相關(guān)的香味，由于蝴蝶個(gè)體所能感受到的香味強(qiáng)度與其所處位置有關(guān)，所以蝴蝶的適應(yīng)度會(huì)隨其位置的改變發(fā)生變化。該算法主要有兩種搜索模式。全局搜索模式為此時(shí)蝴蝶個(gè)體主要受到香味刺激將向香味最濃位置移動(dòng)；局部搜索模式為此時(shí)蝴蝶個(gè)體受香味刺激強(qiáng)度減小，將主要進(jìn)行隨機(jī)移動(dòng)。

香味的大小h由刺激的物理強(qiáng)度來(lái)決定，其計(jì)算公式為

其中，K為刺激強(qiáng)度；λ為冪指數(shù)；ρ為感官因子。

隨機(jī)產(chǎn)生初始蝴蝶種群，并根據(jù)式(10) 計(jì)算每只蝴蝶產(chǎn)生的香味，根據(jù)算法所處的搜索模式來(lái)確定蝴蝶的移動(dòng)方式。

當(dāng)算法處于全局搜索模式中時(shí)，每只蝴蝶將向著當(dāng)前全局最優(yōu)個(gè)體移動(dòng)，其位置更新公式如下。

當(dāng)算法處于局部搜索模式中時(shí)，每只蝴蝶向另外2只隨機(jī)選擇的蝴蝶移動(dòng)，其位置更新公式如下。

算法在搜索過(guò)程中，進(jìn)行全局搜索還是局部搜索由模式切換概率P決定。對(duì)于每個(gè)個(gè)體進(jìn)行移動(dòng)前，先生成一個(gè)[0,1]內(nèi)的隨機(jī)數(shù)r3，若r3≤P，進(jìn)行全局搜索，否則進(jìn)行局部搜索。

2.2 求解MFCAP的BOA

MFCAP問(wèn)題屬于典型的離散組合優(yōu)化問(wèn)題，標(biāo)準(zhǔn)蝴蝶優(yōu)化算法無(wú)法直接對(duì)該問(wèn)題進(jìn)行搜索尋優(yōu)，因此需要針對(duì)MFCAP問(wèn)題的特點(diǎn)對(duì)BOA算法進(jìn)行離散化。

2.2.1 個(gè)體編碼及種群初始化

采用多層整數(shù)編碼方式表示MFCAP問(wèn)題的可行解，對(duì)于設(shè)施數(shù)量為n的MFCAP問(wèn)題，個(gè)體可表示為長(zhǎng)度為2n+1的整數(shù)序列。序列的前n位為小于等于n的不重復(fù)非零整數(shù)，表示設(shè)施的排列順序，序列的第n+1～ 2n位為0-1二進(jìn)制整數(shù)，表示設(shè)施物流交互點(diǎn)與其靠過(guò)道邊線中點(diǎn)之間的位置關(guān)系，序列的第2n+1位表示位于布局第1行的設(shè)施數(shù)量。圖2給出了一種設(shè)施規(guī)模為9的MFCAP問(wèn)題編碼和解碼過(guò)程，將設(shè)施編號(hào)隨機(jī)排序后即可得到一個(gè)設(shè)施的可行解[4,9,2,3,1,7,8,5,6,0,1,1,0,1,1,0,0,1,4]。本文采用隨機(jī)方法生成Npop個(gè)長(zhǎng)度為2n+1的整數(shù)序列作為初始種群，Npop為蝴蝶種群的個(gè)體規(guī)模。

圖2 個(gè)體編碼和解碼Figure 2 Encoding and decoding of individual

2.2.2 香味強(qiáng)度

蝴蝶種群個(gè)體的香味強(qiáng)度與其適應(yīng)度有關(guān)，由于求解MFCAP的BOA算法更新個(gè)體位置時(shí)所參與運(yùn)算的實(shí)數(shù)參數(shù)屬于[0,1]，因此需要對(duì)式(10) 進(jìn)行變換以保證0≤hp≤1，變換后的香味計(jì)算公式為

其中，Kp=1/fp，fp為第p個(gè)種群個(gè)體的總流量成本，Kp為第p個(gè)種群個(gè)體的刺激強(qiáng)度，Kmax為所有種群個(gè)體中的最大刺激強(qiáng)度。

2.2.3 位置更新公式

標(biāo)準(zhǔn)蝴蝶算法中的位置更新公式無(wú)法直接應(yīng)用于MFCAP問(wèn)題，需要針對(duì)MFCAP問(wèn)題的離散化特征和個(gè)體編碼方式對(duì)式(11) 和式(12) 進(jìn)行重新定義以實(shí)現(xiàn)算法離散化，離散化后的BOA算法位置更新公式為

其中，各參數(shù)的定義與標(biāo)準(zhǔn)蝴蝶算法相同，但種群個(gè)體編碼為多層編碼方式，編碼的各序列段采用不同形式的編碼序列，因此需要針對(duì)各層編碼定義相應(yīng)的運(yùn)算方法。

對(duì)于前n位的設(shè)施排列序列，“ Θ”表示減法運(yùn)算，整數(shù)序列之間的減法運(yùn)算結(jié)果為位置交換對(duì)集合。設(shè)Z=xqΘxp，則Z為將整數(shù)序列xp調(diào)整為xq所需要進(jìn)行的所有位置調(diào)整所組成的集合?！??”表示乘法運(yùn)算，交換對(duì)集合與實(shí)數(shù)之間的乘法運(yùn)算結(jié)果仍為交換對(duì)集合，設(shè)Z′=λ?Z，則Z′為由Z的前L個(gè)交換對(duì)組成的集合?！?⊕”表示加法運(yùn)算，整數(shù)序列與交換對(duì)集合之間的加法運(yùn)算結(jié)果仍為整數(shù)序列，設(shè)x′=x⊕Z′，則x′為按照Z(yǔ)′中的交換對(duì)逐個(gè)對(duì)x中的設(shè)施位置進(jìn)行交換后得到的新整數(shù)序列。

對(duì)于第n+1～ 2n位的二進(jìn)制整數(shù)序列?！?Θ”表示減法運(yùn)算，二進(jìn)制整數(shù)序列之間的減法運(yùn)算結(jié)果為整數(shù)序列。設(shè)Z=xqΘxp，則Z為二進(jìn)制整數(shù)序列xq調(diào)整為xp所需要進(jìn)行的取反操作位置所組成的集合。“ ?”表示乘法運(yùn)算，整數(shù)序列與實(shí)數(shù)之間的乘法運(yùn)算結(jié)果仍為整數(shù)序列，設(shè)Z′=λ⊕Z，則Z′為由Z的前L個(gè)元素組成的整數(shù)序列?！?⊕”表示加法運(yùn)算，二進(jìn)制整數(shù)序列與整數(shù)序列之間的加法運(yùn)算結(jié)果仍為二進(jìn)制整數(shù)序列，設(shè)x'=x⊕Z'，則x′為按照Z(yǔ)′中的元素逐個(gè)對(duì)x中的元素取反得到的新整數(shù)序列。

對(duì)于第2n+1位的整數(shù)，各數(shù)學(xué)運(yùn)算符號(hào)定義與實(shí)數(shù)運(yùn)算法則相同，對(duì)于公式最終得到的在[0,n]范圍內(nèi)取整。

3 算法改進(jìn)策略

蝴蝶算法具有較強(qiáng)的全局搜索能力和較高的搜索精度，但在求解MFCAP這一離散尋優(yōu)問(wèn)題時(shí)算法容易陷入局部最優(yōu)而導(dǎo)致種群早熟，求解精度和穩(wěn)定性不高，為此本文對(duì)離散蝴蝶算法進(jìn)行了改進(jìn)，以提高尋優(yōu)質(zhì)量。

3.1 自適應(yīng)模式切換概率

標(biāo)準(zhǔn)蝴蝶算法采用固定的模式切換概率P控制局部搜索和全局搜索。如果P取值較大，則算法主要進(jìn)行全局搜索，收斂速度較快，但解的質(zhì)量會(huì)下降，求解精度較低。如果P取值較小，則算法主要進(jìn)行局部搜索，搜索精度高，但搜索效率較低，且容易陷入局部最優(yōu)解。較為理想的搜索過(guò)程是在算法的前期主要進(jìn)行全局搜索，以快速定位搜索空間中的全局最優(yōu)解所在范圍，在算法的后期主要進(jìn)行局部搜素，以提高搜素精度和質(zhì)量。為此，本文引入自適應(yīng)模式切換概率來(lái)平衡全局搜索和局部搜素在尋優(yōu)過(guò)程中的執(zhí)行概率，模式切換概率隨著算法迭代的進(jìn)程進(jìn)行動(dòng)態(tài)調(diào)整，以提升算法的搜索效率。經(jīng)多次試驗(yàn)比較，模式切換概率P在[0.5,0.8]范圍內(nèi)取值為宜，第t次迭代過(guò)程的模式切換概率P(t)計(jì)算公式為

其中，Pstart為模式切換概率的取值上限；Pend為模式切換概率的取值下限；Mmax為算法最大迭代次數(shù)。

3.2 精英增強(qiáng)進(jìn)化

蝴蝶算法的全局搜索階段主要是為了定位最優(yōu)解搜索空間，局部搜索階段主要是為了在全局最優(yōu)解附近進(jìn)行精細(xì)搜索，以提高算法的搜索精度。由蝴蝶算法的局部搜索公式可知，新個(gè)體的產(chǎn)生方式是在現(xiàn)有個(gè)體的基礎(chǔ)上，隨機(jī)選擇第t代種群空間中的兩個(gè)個(gè)體，由它們產(chǎn)生搜索步長(zhǎng)，與當(dāng)前個(gè)體交叉組合構(gòu)成新的個(gè)體。一方面，在滿足收斂的條件下，種群中的個(gè)體逐步逼近某一最優(yōu)解，若上一代個(gè)體所處的位置不理想，按照此策略更新后的當(dāng)前解也難以盡如人意。另一方面，在尋優(yōu)后期由于種群多樣性逐漸降低，搜索步長(zhǎng)趨近于零，經(jīng)過(guò)一定次數(shù)的迭代后，種群進(jìn)化逐漸停滯，出現(xiàn)早熟收斂。

本文采用一種精英增強(qiáng)進(jìn)化策略來(lái)提高算法的局部搜索能力，在每次迭代蝴蝶算法搜索開(kāi)始前，先通過(guò)比較適應(yīng)度函數(shù)得到當(dāng)前種群中的最優(yōu)個(gè)體，然后對(duì)最優(yōu)個(gè)體的鄰域進(jìn)行搜索，若發(fā)現(xiàn)適應(yīng)度優(yōu)于當(dāng)前最優(yōu)個(gè)體的新個(gè)體，則將替換為，然后再開(kāi)始蝴蝶算法搜索。針對(duì)不同的編碼序列段，其鄰域構(gòu)造方法如下。

1) 對(duì)于設(shè)施編號(hào)序列，有3種鄰域構(gòu)造方法(如圖3所示) ：(1) 隨機(jī)選擇2個(gè)設(shè)施交換其位置；(2) 隨機(jī)選擇1個(gè)設(shè)施插入到設(shè)施編號(hào)序列的任意位置；(3) 隨機(jī)選擇2個(gè)設(shè)施，將這2個(gè)設(shè)施及其之間的設(shè)施反轉(zhuǎn)排列。

圖3 設(shè)施編號(hào)序列鄰域構(gòu)造方法Figure 3 Neighborhood of number sequence

2) 對(duì)于設(shè)施偏心決策變量序列，有2種鄰域構(gòu)造方法(如圖4所示) ：(1) 隨機(jī)選擇1個(gè)設(shè)施的偏心決策變量取反；(2) 隨機(jī)選擇2個(gè)設(shè)施，將這2個(gè)設(shè)施及其之間的偏心決策變量全部取反。

圖4 偏心決策變量序列鄰域構(gòu)造方法Figure 4 Neighborhood of eccentric decision variables

3) 對(duì)于第1行的設(shè)施數(shù)，在[1,n]之間隨機(jī)生成1個(gè)不相等的整數(shù)進(jìn)行替換。

3.3 反向擴(kuò)散災(zāi)變

求解MFCAP問(wèn)題的BOA在迭代后期的搜索空間逐漸縮小，算法容易由于種群同質(zhì)化而提前收斂至局部最優(yōu)，導(dǎo)致搜索精度受到限制。為此，本文提出一種基于反向?qū)W習(xí)機(jī)制(opposition-based learning,OBL) 的種群災(zāi)變策略，該策略借助歷史信息使算法后期的同質(zhì)化種群向解空間邊界反向擴(kuò)散，以擴(kuò)展搜索空間，提高算法的搜索性能，其具體操作方法為：記錄每次迭代過(guò)程的全局最優(yōu)解，若全局最優(yōu)解在連續(xù)Jrep次迭代過(guò)程中均保持不變，則認(rèn)為此時(shí)算法已收斂到局部最優(yōu)，此時(shí)，為了增強(qiáng)種群多樣性使算法跳出局部最優(yōu)，對(duì)種群進(jìn)行反向擴(kuò)散災(zāi)變操作。將當(dāng)前種群中的每個(gè)個(gè)體替換為其對(duì)應(yīng)的反向解，另外再隨機(jī)產(chǎn)生Npop個(gè)隨機(jī)個(gè)體，從反向種群和新生成的隨機(jī)種群中選擇較優(yōu)個(gè)體組成新的蝴蝶種群，繼續(xù)進(jìn)行搜索。

假設(shè)xp=[ετ η]為搜索空間中的第p個(gè)體，ε=[ε1,ε2,···,εn]為設(shè)施編號(hào)排列順序，τ=[τ1,τ2,···,τn]為對(duì)應(yīng)設(shè)施的偏心決策變量，η為排列在第一行的設(shè)施數(shù)量，則其反向解的定義如下。

1) 對(duì)于設(shè)施編號(hào)序列，依次將第w個(gè)設(shè)施與第w'個(gè)設(shè)施交換位置即得到ε的反向解εˉ、εˉw的計(jì)算公式為

2) 對(duì)于設(shè)施偏心決策變量序列，依次對(duì)第w個(gè)決策變量τw進(jìn)行隨機(jī)概率取反，計(jì)算公式為

3.4 IBOA流程

本文所提IBOA算法的流程如圖5所示，其中，Mmax為算法的最大迭代次數(shù)，G為災(zāi)變決策變量，為第t次迭代種群中的最優(yōu)個(gè)體編碼，為個(gè)體對(duì)應(yīng)的適應(yīng)度值，為第t次迭代時(shí)的歷史最優(yōu)個(gè)體及其適應(yīng)度。

圖5 IBOA流程圖Figure 5 Flow chart of IBOA

4 實(shí)驗(yàn)結(jié)果與分析

針對(duì)所提的MFCAP數(shù)學(xué)模型及IBOA求解方法，選擇設(shè)施規(guī)模為5～ 49不等的常規(guī)CAP算例進(jìn)行仿真實(shí)驗(yàn)，其中，假設(shè)各設(shè)施物流交互點(diǎn)位于其靠過(guò)道邊線的1/4處，即ei=li/4。所有實(shí)驗(yàn)采用的計(jì)算機(jī)硬件配置為Intel(R) Core(TM) i7-3770，主頻3.40 GHz，內(nèi)存8 GB，Windows 7操作系統(tǒng)。

4.1 MFCAP模型驗(yàn)證

由于MFCAP問(wèn)題尚無(wú)相關(guān)測(cè)試算例的運(yùn)算結(jié)果，因此本文采用BBA整數(shù)規(guī)劃求解算法對(duì)所提數(shù)學(xué)模型進(jìn)行小規(guī)模的精確算例求解。另外，采用本文所提的IBOA算法對(duì)相同算例進(jìn)行最優(yōu)解搜索，每個(gè)算例求解10次，共計(jì)100個(gè)計(jì)算結(jié)果，通過(guò)對(duì)比計(jì)算結(jié)果進(jìn)行模型和算法正確性的相互驗(yàn)證。將所有運(yùn)算結(jié)果進(jìn)行統(tǒng)計(jì)得到其最大值fmax、最小值fmin、平均值favg、標(biāo)準(zhǔn)差SD，如表1所示。IBOA算法中Pstart=0.8，Pend=0.5，a=0.7，其他參數(shù)設(shè)置如表1所示，計(jì)算結(jié)果如表2所示。

表1 算法參數(shù)設(shè)置Table 1 Parameters of algorithm

表2 BBA算法和IBOA算法求解MFCAP的計(jì)算結(jié)果Table 2 Calculation results of BBA and IBOA for solving MFCAP

對(duì)比BBA和IBOA計(jì)算結(jié)果可知，對(duì)于設(shè)施規(guī)模小于10的測(cè)試算例，兩種方法得到的最優(yōu)目標(biāo)值和最優(yōu)排列序列均相同，對(duì)于測(cè)試算例S11、Am12a、Am12b，雖然IBOA得到的平均目標(biāo)值較BBA解存在一定的誤差，但其fmin均等于BBA的精確解，證明了本文所提模型和算法的正確性。

進(jìn)一步分析兩種方法的求解消耗時(shí)間可知，針對(duì)所選10個(gè)CAP測(cè)試問(wèn)題，IBOA在求解效率上明顯優(yōu)于BBA算法。對(duì)于設(shè)施規(guī)模小于11的測(cè)試算例，BBA算法與IBOA算法均可求得精確解，且BBA算法計(jì)算所消耗時(shí)間多于IBOA算法，但總體時(shí)長(zhǎng)均在可接受范圍內(nèi)。隨著問(wèn)題規(guī)模的增加，精確方法求解問(wèn)題耗時(shí)也急劇增長(zhǎng)，Am12a、Am12b的精確求解時(shí)間分別為 8 608.17 s、13 013.81 s，遠(yuǎn)超常規(guī)可接受的求解時(shí)間3 600 s。對(duì)于IBOA算法，求解所選測(cè)試算例所消耗的時(shí)間均小于30 s，明顯小于BBA算法的求解時(shí)間。以Am12b測(cè)試問(wèn)題為例，BBA算法消耗時(shí)間為IBOA消耗時(shí)間的477倍，證明了所提IBOA求解效率的優(yōu)異。

4.2 改進(jìn)策略有效性驗(yàn)證

為驗(yàn)證本文所提算法改進(jìn)策略的有效性，選擇18個(gè)測(cè)試算例，采用BOA和IBOA分別進(jìn)行求解，參數(shù)設(shè)置見(jiàn)表3。為方便對(duì)比兩種算法之間的性能差異，對(duì)其計(jì)算結(jié)果進(jìn)行歸納統(tǒng)一，定義BOA和IBOA所求得的運(yùn)算結(jié)果與BBA算法所求得的精確解之間的偏差為E，其計(jì)算公式為

表3 BOA與IBOA算法參數(shù)設(shè)置Table 3 Algorithm parameters of BOA and IBOA

其中，f為該算例多次計(jì)算結(jié)果的平均目標(biāo)函數(shù)值，f0為應(yīng)用BBA算法得到的精確最小目標(biāo)函數(shù)值。對(duì)于設(shè)施規(guī)模大于12的算例，由于BBA算法已無(wú)法在合理時(shí)間內(nèi)求得精確解，因此使用啟發(fā)式算法得到近似最優(yōu)解作為f0，使用“ *”進(jìn)行標(biāo)記。針對(duì)每個(gè)測(cè)試問(wèn)題，兩種算法采用相同的參數(shù)設(shè)置，分別進(jìn)行10次運(yùn)算，共計(jì)180個(gè)運(yùn)算結(jié)果。將所有運(yùn)算結(jié)果進(jìn)行統(tǒng)計(jì)得到表4所示結(jié)果，其中，favg為單個(gè)算例的平均最優(yōu)目標(biāo)值，SDf為最優(yōu)目標(biāo)值的標(biāo)準(zhǔn)差，SDE為偏差的標(biāo)準(zhǔn)差。

分析表4中求解結(jié)果可知，對(duì)于設(shè)施規(guī)模小于9的測(cè)試算例，兩種方法均能求得最優(yōu)解，但BOA的求解質(zhì)量有微小波動(dòng)。對(duì)于設(shè)施規(guī)模大于9的測(cè)試算例，IBOA求得的最優(yōu)解均優(yōu)于BOA求得的最優(yōu)解，表明IBOA較BOA更具有求解優(yōu)勢(shì)。其中，BOA的求解結(jié)果與f0的最大偏差為7.28%，大于IBOA的最大偏差0.98%，證明本文所采用的改進(jìn)策略具有顯著效果。

為更直觀地分析改進(jìn)策略對(duì)算法搜索性能的影響，根據(jù)表4中的計(jì)算結(jié)果，繪制BOA與IBOA求解偏差對(duì)比圖(如圖6所示) 和E標(biāo)準(zhǔn)差對(duì)比圖(如圖7所示) 。由圖6可知，對(duì)于設(shè)施規(guī)模小于9的小規(guī)模算例，兩種算法的求解偏差均小于等于0.25%，二者求解性能較為接近；對(duì)于設(shè)施規(guī)模大于13的較大規(guī)模算例，BOA的求解偏差明顯增大，且隨著設(shè)施規(guī)模的增加呈上升趨勢(shì)，而IBOA的求解偏差均小于1%，證明采用改進(jìn)策略后的IBOA求解性能更優(yōu)。由圖7可知，對(duì)于表4中所有測(cè)試算例，IBOA的E標(biāo)準(zhǔn)差均小于BOA的E標(biāo)準(zhǔn)差，對(duì)于設(shè)施規(guī)模大于9的測(cè)試算例，BOA的E標(biāo)準(zhǔn)差上升明顯，總體在1.5左右上下波動(dòng)，而IBOA的E標(biāo)準(zhǔn)差穩(wěn)定在0.7%以內(nèi)，證明IBOA具有良好的求解平穩(wěn)性。由此可知，所提IBOA算法在求解質(zhì)量和平穩(wěn)性方面均得到了一定改善。

表4 BOA和IBOA計(jì)算結(jié)果對(duì)比Table 4 Comparison of calculation results of BOA and IBOA

圖6 BOA與IBOA求解偏差E 對(duì)比Figure 6 Comparison of E% between BOA and IBOA

圖7 BOA與IBOA的SDE對(duì)比Figure 7 Comparison of SDE between BOA and IBOA

4.3 IBOA與其他算法對(duì)比

為進(jìn)一步驗(yàn)證本文所提算法的求解性能，應(yīng)用IBOA求解較大規(guī)模的MFCAP問(wèn)題，將所得結(jié)果與禁忌算法(TS)、模擬退火算法(SA)、遺傳算法(GA) 求解結(jié)果進(jìn)行對(duì)比，為保證計(jì)算結(jié)果的可比性，各算法的主要參數(shù)采用相同設(shè)置(如表5所示) 。對(duì)每個(gè)算例運(yùn)行10次，共統(tǒng)計(jì)250個(gè)計(jì)算結(jié)果如表6所示。

表5 IBOA與其他算法參數(shù)設(shè)置Table 5 Parameter setting of IBOA and other algorithms

分析表6中的計(jì)算結(jié)果可知，針對(duì)所選的25個(gè)MFCAP測(cè)試算例，IBOA求解得到的平均最優(yōu)解優(yōu)于其他算法的平均最優(yōu)解，且設(shè)施規(guī)模大于20時(shí)，其求解所消耗的時(shí)間也少于其他算法的消耗時(shí)間，證明了IBOA相較于其他算法具有一定的求解優(yōu)勢(shì)。為更直觀地對(duì)比IBOA與其他算法的求解消耗時(shí)間，繪制如圖8所示的算法運(yùn)行時(shí)間對(duì)比曲線。由圖8可知，對(duì)于設(shè)施規(guī)模小于20的MFCAP，IBOA與其他3種方法消耗的時(shí)間基本一致；對(duì)于設(shè)施規(guī)模大于20的MFCAP，隨著設(shè)施規(guī)模的增加，其他3種算法消耗的時(shí)間迅速增加，而IBOA消耗的時(shí)間增長(zhǎng)較為平緩，證明了IBOA具有較高的求解效率。

圖8 IBOA與其他算法運(yùn)行時(shí)間對(duì)比Figure 8 Comparison of running time between IBOA and other algorithms

表6 IBOA與其他算法計(jì)算結(jié)果對(duì)比Table 6 Comparison of calculation results between IBOA and other algorithms

5 結(jié)論

本文針對(duì)工業(yè)實(shí)際中設(shè)施物流交互點(diǎn)與其靠過(guò)道邊線中點(diǎn)存在不重合的情況，提出一種考慮設(shè)施左右鏡像情況的過(guò)道布置問(wèn)題，并建立了該問(wèn)題的數(shù)學(xué)模型。提出一種適用于MFCAP的改進(jìn)離散蝴蝶優(yōu)化算法，應(yīng)用BBA算法和IBOA求解所選的10個(gè)小規(guī)模測(cè)試算例，證明了所提模型和算法的正確性。分別采用IBOA和BOA對(duì)選取18個(gè)中小規(guī)模測(cè)試算例進(jìn)行求解，結(jié)果表明所提改進(jìn)策略能夠有效提升算法的求解質(zhì)量和求解穩(wěn)定性。為進(jìn)一步驗(yàn)證所提算法先進(jìn)性，應(yīng)用IBOA求解25個(gè)較大規(guī)模的MFCAP測(cè)試算例，并將計(jì)算結(jié)果與TS、SA、GA計(jì)算結(jié)果進(jìn)行對(duì)比，結(jié)果表明IBOA在求解質(zhì)量和求解效率方面均具有優(yōu)勢(shì)。在未來(lái)研究中，可進(jìn)一步結(jié)合實(shí)際情況，針對(duì)多層可鏡像設(shè)施過(guò)道布置問(wèn)題及動(dòng)態(tài)設(shè)施流量成本特征進(jìn)行建模優(yōu)化。