量子進(jìn)化算法在揀選路徑優(yōu)化中的應(yīng)用

宮正

【摘要】隨著電子商務(wù)的迅速發(fā)展，商品流通速度加快，物流運(yùn)作成本居高不下，怎樣降低物流成本成為人們?nèi)找骊P(guān)注的焦點(diǎn)。本文以雙區(qū)型倉庫為研究對(duì)象，以揀選行走距離最短為目標(biāo)建立數(shù)學(xué)模型，對(duì)量子進(jìn)化算法改進(jìn)，具有更好的種群多樣性特征，與傳統(tǒng)進(jìn)化算法相比，量子進(jìn)化算法具有種群規(guī)模小、全局尋優(yōu)能力強(qiáng)、不易陷入局部最優(yōu)解的特點(diǎn)。通過MATLAB編程實(shí)現(xiàn)對(duì)揀選路徑問題的優(yōu)化。

【關(guān)鍵詞】量子進(jìn)化算法 旋轉(zhuǎn)門 量子位編碼

一、引言

時(shí)代不斷地改變，經(jīng)濟(jì)快速發(fā)展，我們的購(gòu)物模式從原來的低頻率、少品種向高頻率、多品種的模式轉(zhuǎn)變，從過去在實(shí)體店的購(gòu)物模式向“線上購(gòu)買”加上“線下體驗(yàn)”的方向改變，這種高頻率、多品種的購(gòu)物模式向電商企業(yè)提出了挑戰(zhàn)，電商企業(yè)一定要適應(yīng)這種消費(fèi)模式，快速有效地面對(duì)挑戰(zhàn)，加強(qiáng)對(duì)配送中心的重視力度，提供更快速的物流配送服務(wù)，更大程度上提高顧客的滿意度，滿足顧客的需求。

在配送中心的活動(dòng)中，揀選作業(yè)的時(shí)間大約是配送中心工作時(shí)間的三分之一，占總成本的百分之九十。而揀選人員行走的時(shí)間又是揀選作業(yè)時(shí)間的比重較大的部分。對(duì)揀選路徑進(jìn)行優(yōu)化可以大大地縮短行走距離，從而可以減少揀選作業(yè)所花費(fèi)的時(shí)間。揀選路徑的優(yōu)化是提高工作效率、提高配送的速度、降低物流成本以及增加客戶滿意度的重要手段。

到目前為止，學(xué)者們已經(jīng)研究出許許多多對(duì)路徑優(yōu)化的方法如禁忌搜索、模擬退火算法、進(jìn)化算法等，這些優(yōu)化方法都在揀選路徑優(yōu)化的問題中取得了很好的效果。但是在路徑優(yōu)化的具體應(yīng)用過程中經(jīng)常會(huì)陷入早熟收斂、易陷入局部等困境，很難得到最優(yōu)解。本文基于Bloch球?qū)α孔舆M(jìn)化算法改進(jìn)，在旋轉(zhuǎn)策略加入獎(jiǎng)勵(lì)函數(shù)，鼓勵(lì)種群向他們有利的方向進(jìn)化。這種方法克服了量子進(jìn)化算法的收斂速度慢、受初始種群影響的缺點(diǎn)，能夠更好地解決路徑優(yōu)化問題。通過MATLAB編程的方式來實(shí)現(xiàn)對(duì)揀選路徑的優(yōu)化，然后與其他智能算法優(yōu)化結(jié)果作比較，驗(yàn)證改進(jìn)量子進(jìn)化算法的優(yōu)越性。

二、量子進(jìn)化算法的基本原理

（一）哈密頓圖

哈密頓圖（Hamiltonian path）是由天文學(xué)家哈密頓提出一個(gè)無向圖。從圖中的任意一點(diǎn)出發(fā)，路途中經(jīng)過圖中每一個(gè)結(jié)點(diǎn)當(dāng)且僅當(dāng)一次，則成為哈密頓回路（Hamiltonian cycle），含有圖中所有頂點(diǎn)的路徑稱作哈密頓路徑。這與求解配送中心的揀選路徑類似，唯一不同的是由于小車的總載重量的限制，當(dāng)揀選人員揀選的貨物超出揀選人員時(shí)，要回到出發(fā)點(diǎn)，然后再重現(xiàn)揀選。如待揀選貨物順序?yàn)?-2-3-4-5-6-7-8-9-10-1（1代表了出發(fā)點(diǎn)和結(jié)束點(diǎn)），這代表了一個(gè)完整的哈密頓圖，其中在揀選到編號(hào)為5號(hào)的貨物時(shí)，如果揀選5號(hào)貨物，那么已經(jīng)揀選的貨物超出了小車的載重量，揀選人員需要回去把小車貨物卸下，繼續(xù)揀選，那么實(shí)際的哈密頓圖有兩個(gè)，分別為1-2-3-4-5-1，1-6-7-8-9-10-1，但是總的揀選路線還是1-2-3-4-5-6-7-8-9-10-1或者是1-6-7-8-9-10-2-3-4-5-1，總的揀選行走距離沒有變化。生成多少個(gè)哈密頓圖對(duì)揀選路徑的優(yōu)化沒有影響。

（二）量子進(jìn)化算法編碼求解

在量子計(jì)算中，一個(gè)量子比特是一個(gè)可以在二維希爾伯特空間中描述的二階量子系統(tǒng)，根據(jù)量子比特的特性，量子比特在二維希爾伯特空間中可以表示為：

借助哈密頓圖對(duì)基于Bloch球的進(jìn)化算法進(jìn)行改進(jìn)，對(duì)種群染色體初始化得到Q（t_o），其中種群染色體的量子比特編碼都為，使得每個(gè)染色體所表達(dá)的全部狀態(tài)是等概率的（配送中心的訂單都是隨機(jī)產(chǎn)生的），對(duì)量子染色體進(jìn)行初始化種群進(jìn)行特殊的二進(jìn)制編碼，然后生成哈密頓圖即揀選路線，在量子進(jìn)化算法中的哈密頓圖通過編碼可以如上6*6矩陣（式（2-6））所示。通過這種特殊的哈密頓圖的形式，矩陣中的每一個(gè)1的變換都具有實(shí)際意義，有利于種群的多樣性。其中矩陣的每一行的1所在行數(shù)表示揀選路徑的順序，每一列的1所在列數(shù)表示待揀選貨物的位置，起始位置默認(rèn)為1，因此上面的矩陣所代表的揀選路徑為1-5-3-2-6-4-1，滿足了哈密頓圈路途中經(jīng)過圖中每一個(gè)結(jié)點(diǎn)當(dāng)且僅當(dāng)一次，但是這種必須要保證矩陣的每行每列都為1，而且保證矩陣的最后一個(gè)1在第n（n表示種群規(guī)模）行第1列只有這樣才能保證哈密頓圖是一個(gè)完整的回路，如果不能保證，再生成揀選路線時(shí)，會(huì)導(dǎo)致生成的初始種群對(duì)最優(yōu)結(jié)果產(chǎn)生不好的影響。因此在生成二進(jìn)制矩陣的時(shí)候，確保每行每列只有一個(gè)1。

其中minx（1，1）x，maxx（1，2）x分別表示第一變量的最小值和最大值，miny（1，1）y，maxy（1，2）y分別表示第一變量的最小值和最大值，minz（1，1）z，maxz（1，2）z分別表示第一變量的最小值和最大值。經(jīng)過轉(zhuǎn)換之后就是所要求得的解。

在基于Bloch球改進(jìn)的量子進(jìn)化算法求解揀選路徑優(yōu)化問題中，求解出之后的是特殊的哈密頓圈（二進(jìn)制編碼），這種特殊的哈密頓圈只是為了我們更方便的求解，加快收斂速度、增加種群的多樣性，并不是我們最終需要的揀選路徑，需要通過對(duì)這種編碼進(jìn)行解碼，最終轉(zhuǎn)變?yōu)槲覀冃枰膾x路徑。

（四）量子染色體的更換

量子染色體的更新是經(jīng)過量子旋轉(zhuǎn)門更新量子位的相位來完成的。量子位相位旋轉(zhuǎn)的作用在于使當(dāng)前種群中每一個(gè)染色體逼近當(dāng)代最優(yōu)染色體，但在這種逼近過程中，也有可能產(chǎn)生出更好的當(dāng)代最優(yōu)染色體，從而使群體不斷得到進(jìn)化。因此量子旋轉(zhuǎn)門，形式為：

但是在量子旋轉(zhuǎn)門中旋轉(zhuǎn)角是固定不變的，無論當(dāng)前的適應(yīng)度大于還是小于最優(yōu)適應(yīng)度，都是按著同樣的速度進(jìn)行染色體的更新，這種策略降低了算法的收斂速度。因此在此加入獎(jiǎng)勵(lì)函數(shù)，如下所示：

其中fitness（i）表示第次進(jìn)化時(shí)的最小適應(yīng)度，best.fitness當(dāng)前種群的最小適應(yīng)度，通過加入這種獎(jiǎng)勵(lì)函數(shù)，當(dāng)?shù)诖芜M(jìn)化時(shí)的最小適應(yīng)度小于當(dāng)前種群的最小適應(yīng)度時(shí)，能夠加快量子旋轉(zhuǎn)門的更新速度，提高種群的收斂速度。旋轉(zhuǎn)角策略如下表1所示：

（五）量子染色體的災(zāi)變

在揀選路徑中，為了防止陷入最優(yōu)解，需要在量子進(jìn)化算法中加入種群災(zāi)變，當(dāng)量子進(jìn)化算法經(jīng)過一定的迭代次數(shù)，最優(yōu)的染色體就會(huì)保持不變，就很有可能陷入局部最優(yōu)解，因此加入災(zāi)變操作，使其跳出局部最優(yōu)，從種群的第100次進(jìn)化代數(shù)實(shí)行變異，通過對(duì)初始生成的哈密頓圖施加較大的擾動(dòng)，重新生成哈密頓圖，增加種群的多樣性，使得算法不易陷入局部最優(yōu)解。

三、仿真運(yùn)行與結(jié)果分析

通過MATLAB編程對(duì)問題求解，驗(yàn)證算法的有效性，分別使用基于Bloch球的量子進(jìn)化算法會(huì)與量子進(jìn)化算法、蟻群算法以及禁忌搜索算法對(duì)揀選路徑進(jìn)行優(yōu)化，結(jié)果如下表2、圖2所示：

從以上圖表可以看出模擬退火算法優(yōu)化的揀選行走距離最大，它的曲線普遍在其它兩個(gè)之上，它優(yōu)化的平均距離和最短距離都是最大的，優(yōu)化效果相對(duì)較差?；贐loch改進(jìn)的量子進(jìn)化算法優(yōu)化效果最好，不論是優(yōu)化的平均距離還是優(yōu)化的最短距離都是最小的，相比其他兩個(gè)智能算法優(yōu)化減少的距離程度較大，優(yōu)化效果更好，收斂速度更快。因此基于Bloch球改進(jìn)的量子進(jìn)化算法在揀選路徑優(yōu)化問題中有著很好的適用性，能夠較好的解決揀選路徑優(yōu)化問題。

四、結(jié)論

量子進(jìn)化算法由于量子態(tài)的疊加性和相干性能夠表達(dá)多個(gè)態(tài)的疊加，具有更好的多樣性特征。與傳統(tǒng)進(jìn)化算法相比，量子進(jìn)化算法具有種群規(guī)模小、全局尋優(yōu)能力強(qiáng)、不易陷入局部最優(yōu)解的特點(diǎn)，能夠更好地解決路徑優(yōu)化問題。