量子進化算法在揀選路徑優化中的應用
來源:用戶上傳
作者:
【摘要】隨著電子商務的迅速發展，商品流通速度加快，物流運作成本居高不下，怎樣降低物流成本成為人們日益關注的焦點。本文以雙區型倉庫為研究對象，以揀選行走距離最短為目標建立數學模型，對量子進化算法改進，具有更好的種群多樣性特征，與傳統進化算法相比，量子進化算法具有種群規模小、全局尋優能力強、不易陷入局部最優解的特點。通過MATLAB編程實現對揀選路徑問題的優化。
【關鍵詞】量子進化算法 旋轉門 量子位編碼
一、引言
時代不斷地改變，經濟快速發展，我們的購物模式從原來的低頻率、少品種向高頻率、多品種的模式轉變，從過去在實體店的購物模式向“線上購買”加上“線下體驗”的方向改變，這種高頻率、多品種的購物模式向電商企業提出了挑戰，電商企業一定要適應這種消費模式，快速有效地面對挑戰，加強對配送中心的重視力度，提供更快速的物流配送服務，更大程度上提高顧客的滿意度，滿足顧客的需求。
在配送中心的活動中，揀選作業的時間大約是配送中心工作時間的三分之一，占總成本的百分之九十。而揀選人員行走的時間又是揀選作業時間的比重較大的部分。對揀選路徑進行優化可以大大地縮短行走距離，從而可以減少揀選作業所花費的時間。揀選路徑的優化是提高工作效率、提高配送的速度、降低物流成本以及增加客戶滿意度的重要手段。
到目前為止，學者們已經研究出許許多多對路徑優化的方法如禁忌搜索、模擬退火算法、進化算法等，這些優化方法都在揀選路徑優化的問題中取得了很好的效果。但是在路徑優化的具體應用過程中經常會陷入早熟收斂、易陷入局部等困境，很難得到最優解。本文基于Bloch球對量子進化算法改進，在旋轉策略加入獎勵函數，鼓勵種群向他們有利的方向進化。這種方法克服了量子進化算法的收斂速度慢、受初始種群影響的缺點，能夠更好地解決路徑優化問題。通過MATLAB編程的方式來實現對揀選路徑的優化，然后與其他智能算法優化結果作比較，驗證改進量子進化算法的優越性。
二、量子進化算法的基本原理
（一）哈密頓圖
哈密頓圖（Hamiltonian path）是由天文學家哈密頓提出一個無向圖。從圖中的任意一點出發，路途中經過圖中每一個結點當且僅當一次，則成為哈密頓回路（Hamiltonian cycle），含有圖中所有頂點的路徑稱作哈密頓路徑。這與求解配送中心的揀選路徑類似，唯一不同的是由于小車的總載重量的限制，當揀選人員揀選的貨物超出揀選人員時，要回到出發點，然后再重現揀選。如待揀選貨物順序為1-2-3-4-5-6-7-8-9-10-1（1代表了出發點和結束點），這代表了一個完整的哈密頓圖，其中在揀選到編號為5號的貨物時，如果揀選5號貨物，那么已經揀選的貨物超出了小車的載重量，揀選人員需要回去把小車貨物卸下，繼續揀選，那么實際的哈密頓圖有兩個，分別為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，總的揀選行走距離沒有變化。生成多少個哈密頓圖對揀選路徑的優化沒有影響。
?。ǘ┝孔舆M化算法編碼求解
在量子計算中，一個量子比特是一個可以在二維希爾伯特空間中描述的二階量子系統，根據量子比特的特性，量子比特在二維希爾伯特空間中可以表示為：
借助哈密頓圖對基于Bloch球的進化算法進行改進，對種群染色體初始化得到Q（to），其中種群染色體的量子比特編碼都為，使得每個染色體所表達的全部狀態是等概率的（配送中心的訂單都是隨機產生的），對量子染色體進行初始化種群進行特殊的二進制編碼，然后生成哈密頓圖即揀選路線，在量子進化算法中的哈密頓圖通過編碼可以如上6*6矩陣（式（2-6））所示。通過這種特殊的哈密頓圖的形式，矩陣中的每一個1的變換都具有實際意義，有利于種群的多樣性。其中矩陣的每一行的1所在行數表示揀選路徑的順序，每一列的1所在列數表示待揀選貨物的位置，起始位置默認為1，因此上面的矩陣所代表的揀選路徑為1-5-3-2-6-4-1，滿足了哈密頓圈路途中經過圖中每一個結點當且僅當一次，但是這種必須要保證矩陣的每行每列都為1，而且保證矩陣的最后一個1在第n（n表示種群規模）行第1列只有這樣才能保證哈密頓圖是一個完整的回路，如果不能保證，再生成揀選路線時，會導致生成的初始種群對最優結果產生不好的影響。因此在生成二進制矩陣的時候，確保每行每列只有一個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分別表示第一變量的最小值和最大值。經過轉換之后就是所要求得的解。
在基于Bloch球改進的量子進化算法求解揀選路徑優化問題中，求解出之后的是特殊的哈密頓圈（二進制編碼），這種特殊的哈密頓圈只是為了我們更方便的求解，加快收斂速度、增加種群的多樣性，并不是我們最終需要的揀選路徑，需要通過對這種編碼進行解碼，最終轉變為我們需要的揀選路徑。
?。ㄋ模┝孔尤旧w的更換
量子染色體的更新是經過量子旋轉門更新量子位的相位來完成的。量子位相位旋轉的作用在于使當前種群中每一個染色體逼近當代最優染色體，但在這種逼近過程中，也有可能產生出更好的當代最優染色體，從而使群體不斷得到進化。因此量子旋轉門，形式為：
但是在量子旋轉門中旋轉角是固定不變的，無論當前的適應度大于還是小于最優適應度，都是按著同樣的速度進行染色體的更新，這種策略降低了算法的收斂速度。因此在此加入獎勵函數，如下所示：
其中fitness（i）表示第次進化時的最小適應度，best.fitness當前種群的最小適應度，通過加入這種獎勵函數，當第次進化時的最小適應度小于當前種群的最小適應度時，能夠加快量子旋轉門的更新速度，提高種群的收斂速度。旋轉角策略如下表1所示：
?。ㄎ澹┝孔尤旧w的災變
在揀選路徑中，為了防止陷入最優解，需要在量子進化算法中加入種群災變，當量子進化算法經過一定的迭代次數，最優的染色體就會保持不變，就很有可能陷入局部最優解，因此加入災變操作，使其跳出局部最優，從種群的第100次進化代數實行變異，通過對初始生成的哈密頓圖施加較大的擾動，重新生成哈密頓圖，增加種群的多樣性，使得算法不易陷入局部最優解。
三、仿真運行與結果分析
通過MATLAB編程對問題求解，驗證算法的有效性，分別使用基于Bloch球的量子進化算法會與量子進化算法、蟻群算法以及禁忌搜索算法對揀選路徑進行優化，結果如下表2、圖2所示：
從以上圖表可以看出模擬退火算法優化的揀選行走距離最大，它的曲線普遍在其它兩個之上，它優化的平均距離和最短距離都是最大的，優化效果相對較差?；贐loch改進的量子進化算法優化效果最好，不論是優化的平均距離還是優化的最短距離都是最小的，相比其他兩個智能算法優化減少的距離程度較大，優化效果更好，收斂速度更快。因此基于Bloch球改進的量子進化算法在揀選路徑優化問題中有著很好的適用性，能夠較好的解決揀選路徑優化問題。
四、結論
量子進化算法由于量子態的疊加性和相干性能夠表達多個態的疊加，具有更好的多樣性特征。與傳統進化算法相比，量子進化算法具有種群規模小、全局尋優能力強、不易陷入局部最優解的特點，能夠更好地解決路徑優化問題。
轉載注明來源:http://www.hailuomaifang.com/2/view-14829081.htm
