PSO-AFSA融合算法在揀選路徑優化中的應用

周娟娟 吳蒙蒙

【摘要】揀選路徑優化問題屬于NP難問題，很難求得精確解，因此揀選路徑優化的求解方法一直是研究的熱點。本文提出PSO-AFSA融合算法（粒子群與人工魚群融合算法）用于求解揀選路徑優化問題，首先利用人工魚群尋得初始解，然后利用粒子群算法進行尋優，并將結果與公告板上的最優值進行判斷，根據判斷結果選擇迭代尋優算法進行最后的收斂，證實該融合算法在克服粒子群算法易陷入局部最優這一缺陷的同時，求解效率得到很大提高。

【關鍵詞】PSO-AFSA 融合算法 揀選路徑優化

一、緒論

目前對求解揀選路徑優化問題的研究非常多，除了人至物揀選系統中分類存儲模式研究、揀貨方式與存儲策略等的協同研究等揀選路徑優化問題的影響因素研究之外，越來越多的智能算法應用到該問題中，如a*算法、蟻群算法與遺傳算法、雙層遺傳算法、最小生成樹算法等。這些算法都能夠對揀選路徑進行合理優化，在一定程度上提高揀選作業效率、降低揀選作業時間成本。本文提出PSO-AFSA融合算法用來進行揀選路徑的優化，在一定程度上克服了粒子群算法易陷入局部最優、人工魚群算法后期收斂速度慢的缺點，提高了求解效率與求解精確度。

二、PSO-AFSA融合算法

通過對粒子群算法與人工魚群算法基本原理、流程步驟的研究，從粒子群算法收斂速度快但是容易陷入局部最優值出發，綜合考慮人工魚群算法的全局最優，但是后期收斂速度慢的特點，設計出一種既能提高算法后期收斂速度，又能提高算法的求解準確度的融合算法一粒子群與人工魚群融合算法。

PSO-AFSA融合算法的實現大致分為以下幾步：

第一步：讀取待揀選商品坐標，從而獲得待揀選商品間的距離矩陣。

第二步：設置人工魚群與粒子群相關參數，包括粒子數、人工魚數目、迭代次數、感知距離、擁擠度因子、最多試探次數、認知系數、社會學習系數等基本參數;

第三步：先用人工魚群算法的適應度函數算出每個個體的適應度值，得到最好值，最好值賦值給公告板;

第四步：按照人工魚群算法操作，得到最好解與新的種群，并將尋優結果賦值給粒子群算法，運用粒子群算法的快速收斂性進行后續尋優，并將結果與公告板上的值進行對比，更新公告板;

第五步：判斷是否滿足終止條件，若滿足則終止，如果不滿足條件，則重復步驟二、三、四步，直至終止。

三、揀選路徑優化模型

揀選路徑優化問題類似旅行商問題，屬于NP難問題，即一個人從一個城市出發，途徑多個城市，每個城市僅且只能到達一次，最后回到出發點，同時要求所走路程最短。經典的旅行商問題模型如下：

目標函數（3-1）表示旅行商行走完所有城市的最短距離。約束條件（3-2）和（3-3）表示每個城市只能經過一次，式（3-4）是一個決策變量，如果城市j是在到達城市i后立即到達的則取值為1，否則取值為0，式（3-5）表示不存在小回路。

揀選路徑優化問題中，每一件待揀選的商品所在位置可以看作旅行商問題中的城市位置，揀選人員從倉庫出口出發，對商品進行逐個揀選，每一個貨位都只揀選一次，最后回到倉庫入口處，這一過程中，揀選路徑優化的目的是對揀選人員行走的路徑進行規劃，使得揀貨作業完成后，所行走的路程最短。

四、算法應用及結論

將融合后的新算法、粒子群算法、人工魚群算法分別用于所建模型，分別取最優10組解，圖1為三種算法分別求解同一組數據所需時間以及求得精確解的對比分析圖，每種算法測試十次。由表格對比分析結果可知：在三種算法基本參數相同，數據相同的前提下，粒子群算法的求解速度最快，融合算法次之，人工魚群算法的求解速度最慢，但是人工魚群算法與融合算法精確度基本相同，粒子群算法的求解精度最差。PSO-AFSA融合算法在求解時間上雖然稍慢于粒子群，但是其求解精度較好，同時其在求解精度基本相似的情況下，求解效率比基本的人工魚群算法更高，因此可以得出PSO-AFSA融合算法在一定程度上對兩種基本算法有一定的改進。

五、結論

本文通過對粒子群與人工魚群兩種算法進行融合，形成PSO-AFSA融合算法，并將其應用于揀選路徑優化問題中，并通過結果分析證實融合后的新算法具有求解優越性，為求解揀選路徑優化問題提出一種新的算法。