PSO-AFSA融合算法在揀選路徑優(yōu)化中的應(yīng)用

周娟娟 吳蒙蒙

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

【關(guān)鍵詞】PSO-AFSA 融合算法 揀選路徑優(yōu)化

一、緒論

目前對(duì)求解揀選路徑優(yōu)化問(wèn)題的研究非常多，除了人至物揀選系統(tǒng)中分類(lèi)存儲(chǔ)模式研究、揀貨方式與存儲(chǔ)策略等的協(xié)同研究等揀選路徑優(yōu)化問(wèn)題的影響因素研究之外，越來(lái)越多的智能算法應(yīng)用到該問(wèn)題中，如a*算法、蟻群算法與遺傳算法、雙層遺傳算法、最小生成樹(shù)算法等。這些算法都能夠?qū)x路徑進(jìn)行合理優(yōu)化，在一定程度上提高揀選作業(yè)效率、降低揀選作業(yè)時(shí)間成本。本文提出PSO-AFSA融合算法用來(lái)進(jìn)行揀選路徑的優(yōu)化，在一定程度上克服了粒子群算法易陷入局部最優(yōu)、人工魚(yú)群算法后期收斂速度慢的缺點(diǎn)，提高了求解效率與求解精確度。

二、PSO-AFSA融合算法

通過(guò)對(duì)粒子群算法與人工魚(yú)群算法基本原理、流程步驟的研究，從粒子群算法收斂速度快但是容易陷入局部最優(yōu)值出發(fā)，綜合考慮人工魚(yú)群算法的全局最優(yōu)，但是后期收斂速度慢的特點(diǎn)，設(shè)計(jì)出一種既能提高算法后期收斂速度，又能提高算法的求解準(zhǔn)確度的融合算法一粒子群與人工魚(yú)群融合算法。

PSO-AFSA融合算法的實(shí)現(xiàn)大致分為以下幾步：

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

第二步：設(shè)置人工魚(yú)群與粒子群相關(guān)參數(shù)，包括粒子數(shù)、人工魚(yú)數(shù)目、迭代次數(shù)、感知距離、擁擠度因子、最多試探次數(shù)、認(rèn)知系數(shù)、社會(huì)學(xué)習(xí)系數(shù)等基本參數(shù);

第三步：先用人工魚(yú)群算法的適應(yīng)度函數(shù)算出每個(gè)個(gè)體的適應(yīng)度值，得到最好值，最好值賦值給公告板;

第四步：按照人工魚(yú)群算法操作，得到最好解與新的種群，并將尋優(yōu)結(jié)果賦值給粒子群算法，運(yùn)用粒子群算法的快速收斂性進(jìn)行后續(xù)尋優(yōu)，并將結(jié)果與公告板上的值進(jìn)行對(duì)比，更新公告板;

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

三、揀選路徑優(yōu)化模型

揀選路徑優(yōu)化問(wèn)題類(lèi)似旅行商問(wèn)題，屬于NP難問(wèn)題，即一個(gè)人從一個(gè)城市出發(fā)，途徑多個(gè)城市，每個(gè)城市僅且只能到達(dá)一次，最后回到出發(fā)點(diǎn)，同時(shí)要求所走路程最短。經(jīng)典的旅行商問(wèn)題模型如下：

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

揀選路徑優(yōu)化問(wèn)題中，每一件待揀選的商品所在位置可以看作旅行商問(wèn)題中的城市位置，揀選人員從倉(cāng)庫(kù)出口出發(fā)，對(duì)商品進(jìn)行逐個(gè)揀選，每一個(gè)貨位都只揀選一次，最后回到倉(cāng)庫(kù)入口處，這一過(guò)程中，揀選路徑優(yōu)化的目的是對(duì)揀選人員行走的路徑進(jìn)行規(guī)劃，使得揀貨作業(yè)完成后，所行走的路程最短。

四、算法應(yīng)用及結(jié)論

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

五、結(jié)論

本文通過(guò)對(duì)粒子群與人工魚(yú)群兩種算法進(jìn)行融合，形成PSO-AFSA融合算法，并將其應(yīng)用于揀選路徑優(yōu)化問(wèn)題中，并通過(guò)結(jié)果分析證實(shí)融合后的新算法具有求解優(yōu)越性，為求解揀選路徑優(yōu)化問(wèn)題提出一種新的算法。