基于PSO算法的離散制造車間物料供應(yīng)路徑優(yōu)化*

姚　勇，李少波，張成龍

(貴州大學(xué) a.機(jī)械工程學(xué)院；b.大數(shù)據(jù)與信息工程學(xué)院，貴陽　550025)

0　引言

在實(shí)際的送料過程中，送料車根據(jù)生產(chǎn)計(jì)劃部門的物料計(jì)劃對(duì)加工車間的機(jī)床進(jìn)行送料且計(jì)劃中的每個(gè)機(jī)床都至少到達(dá)一次。于是在忽略了各種偶然因素之后，加工車間送料問題可大致歸結(jié)為一個(gè)旅行商問題(TSP問題)。

目前，為求解高復(fù)雜度TSP問題主要采用遺傳算法[2]、模擬退火算法[3]、蟻群算法[4]、粒子群算法等啟發(fā)式算法。鑒于粒子群算法具有個(gè)體數(shù)目少、搜索能力快、運(yùn)算簡單等特點(diǎn)，成為了近年來求解TSP問題的一個(gè)熱門方法。而為了克服粒子群算法在離散問題中速度難以表達(dá)，易早熟收斂等問題。學(xué)者們從以下幾個(gè)方面對(duì)粒子群算法提出改進(jìn)。第一類是重新定義粒子群算法的運(yùn)算符號(hào)和規(guī)則，例如文獻(xiàn)[5]采用的離散粒子群算法，文獻(xiàn)[6]提出的基于交換子交換序的粒子群算法。第二類是通過與遺傳算法、退火算法、蟻群算法相融合[1-3]，借助交叉、變異等方法來實(shí)現(xiàn)改進(jìn)。雖然上述方法在具體應(yīng)用中均取得了一定的效果，但是對(duì)新型改進(jìn)方法的探索仍然是一個(gè)研究熱點(diǎn)。

本文基于交換子與交換序的概念，針對(duì)現(xiàn)有算法求解效率不佳的問題，提出一種慣性權(quán)重非線性遞減，加速因子隨慣性權(quán)重進(jìn)行動(dòng)態(tài)調(diào)整的改進(jìn)策略來提高算法的全局搜索能力，同時(shí)克服早熟收斂問題。通過車間模擬實(shí)驗(yàn)的測試驗(yàn)證了該算法能對(duì)車間送料路徑優(yōu)化起到良好的作用。

1　相關(guān)問題描述及物料供應(yīng)數(shù)學(xué)模型

經(jīng)典旅行商問題描述如下：給定一系列城市和兩兩城市之間的距離，求解訪問每一座城市一次并回到起始城市的最短回路。我們首先將車間各加工機(jī)床與倉庫所構(gòu)成的網(wǎng)絡(luò)圖轉(zhuǎn)換為帶權(quán)完全無向圖。則其圖論描述為：G=(V,A)，V表示為圖中結(jié)點(diǎn)的集合，一個(gè)結(jié)點(diǎn)代表加工車間被送料的機(jī)床，A表示圖中弧的集合，已知各結(jié)點(diǎn)間的連接距離，找一個(gè)權(quán)值最小的Hamilton回路。即遍歷所有頂點(diǎn)一次且僅一次的最短回路，設(shè)dij為加工機(jī)床i與j之間的距離，即弧(i,j)長度，引入決策變量：

(1)

則其目標(biāo)函數(shù)為：

(2)

TSP問題描述很容易，但由于該問題的可行解是所有頂點(diǎn)的全排列，隨著頂點(diǎn)數(shù)的增加，會(huì)產(chǎn)生組合爆炸。求解相當(dāng)困難，本文尋求通過對(duì)基本PSO算法進(jìn)行改造來應(yīng)用于求解TSP問題。

2　標(biāo)準(zhǔn)粒子群優(yōu)化模型

基本粒子群算法是基于種群的全局搜索策略，將每一個(gè)可能產(chǎn)生的解表述為群中的一個(gè)粒子，通過粒子間的合作與競爭，在復(fù)雜空間中找到最優(yōu)解，之后為了使粒子群保持運(yùn)動(dòng)的慣性，在保證具有全局搜索能力的同時(shí)擴(kuò)展其搜索的空間，使其有能力搜索新的區(qū)域。Eberhart和shi在速度更新方程中引入慣性權(quán)重ω的概念[7]，從而得到了標(biāo)準(zhǔn)粒子群優(yōu)化算法。算法中所有的粒子都有一個(gè)被優(yōu)化函數(shù)決定的適應(yīng)值，并且同時(shí)具有速度與位置兩個(gè)屬性。每一次迭代過程中粒子通過追蹤個(gè)體極值Pi與全局極值Pg來更新自己。個(gè)體極值表示粒子本身所找到的最優(yōu)解。全局極值表示整個(gè)種群目前的最優(yōu)解。粒子i的信息用d維向量表示，位置表示為Xi=(Xi1,…,Xid),速度表示為Vi=(Vi1,…,Vid)其中Vid(t)是粒子i在第t次迭代中第d維速度，Xid(t)是粒子i在第t次迭代中d維當(dāng)前位置。粒子通過公式(3)、(4)對(duì)速度與位置進(jìn)行動(dòng)態(tài)調(diào)整。

總之，本研究發(fā)現(xiàn)PET/CT聯(lián)合HRCT可以提高對(duì)不同大小SPN診斷的準(zhǔn)確率，尤其是對(duì)于直徑≥2cm的SPN，準(zhǔn)確率達(dá)到90.9%。對(duì)于直徑＜2cm的SPN，為提高診斷的準(zhǔn)確率，有必要臨床醫(yī)生、CT室、PET/CT多學(xué)科的討論，才能避免不必要的誤診及漏診。

Vi(t+1)=ω·Vi(t)+c1r1(Pid(t)-Xid(t))+
c2r2(Pid(t)-Xid(t))

(3)

Xid(t+1)=Xid(t)+Vid(t+1)

(4)

c1,c2是加速度系數(shù)，其作用是表示將每個(gè)粒子移向兩極值位置的統(tǒng)計(jì)加速項(xiàng)權(quán)重。取值為(0,2)之間的隨機(jī)數(shù)。r1,r2是(0,1)上的隨機(jī)數(shù)，ω為慣性權(quán)重，用來控制前面速度對(duì)后面速度的影響ω取值較大時(shí)，粒子具有較好的全局搜索能力，ω取值較小時(shí)則具有較好的局部搜索能力。在基本PSO算法中，一般設(shè)定c1=c2=2，ω=1。但在此情況下粒子的軌跡會(huì)出現(xiàn)發(fā)散的現(xiàn)象所以需要限制每一個(gè)粒子的每一維速度范圍[Vmin，Vmax]，以此來限定粒子的運(yùn)動(dòng)軌跡，當(dāng)Vt>Vmax時(shí)，Vt=Vmax，當(dāng)Vt

3　基于交換序的改進(jìn)PSO求解TSP

3.1　求解TSP的基本PSO算法

由于TSP問題為一個(gè)離散問題，而在基本PSO算法中速度向量難以表達(dá)離散域問題，因此要解決TSP問題需要對(duì)基本PSO算法中運(yùn)算符號(hào)和規(guī)則進(jìn)行重新定義，文獻(xiàn)[6]通過引入交換子和交換序的概念，對(duì)PSO算法進(jìn)行了改造。使其能應(yīng)用于求解TSP問題中。其重新構(gòu)造速度-位置公式如下：

Vi(t+1)=ω·Vi(t)+α(Pid(t)-Xid(t))+
β(Pid(t)-Xid(t))

(5)

Xid(t+1)=Xid(t)+Vid(t+1)

(6)

式中，α(Pid(t)-Xid(t))表示粒子與個(gè)體極值的交換序以概率α保留，β(Pgd(t)-Xid(t))表示粒子與全局極值的交換序以概率β保留，α，β取值為(0,1),反應(yīng)了個(gè)體極值和全局極值對(duì)粒子的影響程度。

3.2　求解TSP的改進(jìn)自組織PSO算法

文獻(xiàn)[6]引入交換子的方式來解決TSP問題。該算法設(shè)置100個(gè)粒子，并迭代2000次得到14個(gè)點(diǎn)的最優(yōu)解。擴(kuò)展了PSO算法在離散條件下的應(yīng)用。但是該算法的全局搜索能力并不強(qiáng)，易于產(chǎn)生早熟收斂的情況，同時(shí)沒有考慮粒子的慣性權(quán)重，這樣隨著進(jìn)化的進(jìn)行，算法性能會(huì)急劇惡化，使算法的求解能力大大衰減。文獻(xiàn)[9]在此基礎(chǔ)上提出了一種基于交換序的改進(jìn)自組織PSO算法，利用自組織臨界性理論對(duì)自組織慣性權(quán)重和自組織加速系數(shù)進(jìn)行重新設(shè)置，并引入變異等策略來提高算法的優(yōu)越性。其自組織慣性權(quán)重并未采用常規(guī)的(0.9,0.4)上線性遞減的方式，而是按自組織臨界系統(tǒng)的冪分布規(guī)律進(jìn)行變化。將慣性權(quán)重的變換分為兩個(gè)階段，定義如下：

(7)

(8)

iter為當(dāng)前迭代次數(shù)，Maxiter為最大迭代次數(shù)，ωstart和ωend分別為初始和終止的慣性權(quán)重。第一階段中通過公式(1)延緩慣性權(quán)重的減小趨勢，從而促使粒子擴(kuò)大搜索區(qū)域，減小陷入局部最優(yōu)解的可能。第二階段中通過公式(2)使慣性權(quán)重快速下降，促使粒子對(duì)局部區(qū)域進(jìn)行精細(xì)搜索。自組織加速系數(shù)同樣按照自組織臨界系統(tǒng)的冪律分布規(guī)律進(jìn)行如下定義：

(1)α=Cmax，β=Cmin

(2)α=Cmin，β=Cmax

α=c1r1，β=c2r2，Cmax，Cmin為不相等的常數(shù)。

這種方法較基本PSO而言擴(kuò)大了粒子搜索區(qū)域，有效的克服了算法的早熟收斂問題，提升了算法的性能，但是此方法中慣性權(quán)重調(diào)整策略與加速因子的調(diào)整策略相互脫離，一定程度上削弱了算法進(jìn)化過程中的統(tǒng)一性，不利于算法優(yōu)化搜索。

3.3　算法改進(jìn)

因此，為了能擴(kuò)大粒子搜索區(qū)域，避免陷入局部最優(yōu)解，克服早熟收斂問題。同時(shí)盡可能的讓慣性權(quán)重與加速因子在進(jìn)化過程中保持統(tǒng)一性，進(jìn)一步優(yōu)化算法。提出一種慣性權(quán)重改進(jìn)方法，此方法參考文獻(xiàn)[9]所提出的基于交換序的改進(jìn)自組織PSO算法并結(jié)合慣性權(quán)重ω在(0.9，0.4)線性遞減的方法，得出了一種慣性權(quán)重ω非線性遞減的調(diào)整策略。該策略首先將慣性權(quán)重ω初始化為0.9，以保證算法在初期具有較強(qiáng)的全局搜索能力，再利用非線性遞減的迭代關(guān)系式來減緩慣性權(quán)重ω在前期的下降速度，以此來開發(fā)更多的搜索區(qū)域，規(guī)避早熟收斂問題，改進(jìn)的慣性權(quán)重表達(dá)式如下：

(9)

同時(shí)為了盡可能的讓慣性權(quán)重與加速因子在進(jìn)化過程中保持統(tǒng)一的進(jìn)化性，進(jìn)一步優(yōu)化算法，加速因子需要與慣性權(quán)重ω在迭代過程中非線性變化的特點(diǎn)相互匹配。因此本算法提出一組加速因子調(diào)整式：

(10)

通過該式構(gòu)建c、ω的聯(lián)系，使c、ω呈非線性函數(shù)關(guān)系。并借鑒已有的加速因子調(diào)整策略確定系數(shù)組合[10]。加速系數(shù)α=c1r1，β=c2r2；α、β為[0,1]上隨機(jī)數(shù)。

3.4　改進(jìn)算法流程

基于交換序的改進(jìn)PSO算法求解TSP的流程如圖1所示。

圖1　改進(jìn)粒子群算法流程

4　算法驗(yàn)證

4.1　實(shí)驗(yàn)環(huán)境

為了模擬加工車間機(jī)床、送料倉庫的布局情況，本實(shí)驗(yàn)采用將車間中機(jī)床、送料倉庫位置坐標(biāo)化的方式劃為各坐標(biāo)點(diǎn)，同時(shí)將實(shí)驗(yàn)空間設(shè)置為30m×60m的長方形區(qū)域，并以橫縱坐標(biāo)劃分為300×600的單位網(wǎng)格。然后將各節(jié)點(diǎn)布置于單位網(wǎng)格中，并在節(jié)點(diǎn)位置裝上傳感器進(jìn)行位置感知。

實(shí)驗(yàn)運(yùn)行平臺(tái)是采用Matlab軟件，針對(duì)車間送料路徑優(yōu)化問題，對(duì)文獻(xiàn)所采用的基于交換序的PSO算法，基于交換序的慣性權(quán)重線性遞減PSO算法以及本文所設(shè)計(jì)的基于交換序的改進(jìn)PSO算法各做50次獨(dú)立仿真實(shí)驗(yàn)，并進(jìn)行對(duì)比。其參數(shù)設(shè)置見表1。

表1　算法參數(shù)設(shè)置

4.2　結(jié)果分析

3種算法的仿真實(shí)驗(yàn)結(jié)果如表2所示。

表2　實(shí)驗(yàn)結(jié)果對(duì)比

對(duì)比表2中數(shù)據(jù)可發(fā)現(xiàn)改進(jìn)后的PSO算法其平均解與最優(yōu)解均優(yōu)于其余兩種算法。

3種算法的收斂曲線如圖2所示。

圖2　路徑優(yōu)化曲線對(duì)比

通過觀察收斂曲線圖發(fā)現(xiàn)本文所設(shè)計(jì)的改進(jìn)PSO算法迭代到34代左右適應(yīng)度函數(shù)趨于穩(wěn)定得到全局最優(yōu)解337.5447，而其余兩種算法則分別迭代到43與47代才進(jìn)行收斂。這表明基于交換序的基本PSO算法和

基于交換序的慣性權(quán)重線性遞減PSO算法(LDW-PSO)的整體收斂過程緩慢，全局尋優(yōu)效果不理想，而本文改進(jìn)的PSO算法在收斂速度上較前兩種方法有明顯的優(yōu)勢，同時(shí)在搜索最優(yōu)解的能力上也得到了增強(qiáng)，可以大幅縮短物流供應(yīng)路徑，總的來說改進(jìn)后的PSO算法體現(xiàn)出了良好的優(yōu)化性能。

5　結(jié)論

本文針對(duì)加工車間送料路徑優(yōu)化進(jìn)行了研究，通過構(gòu)建實(shí)驗(yàn)環(huán)境對(duì)車間現(xiàn)場場景進(jìn)行了模擬，建立了TSP模型。并基于交換子和交換序的概念設(shè)計(jì)了一種慣性權(quán)重非線性遞減，同時(shí)加速因子隨慣性權(quán)重的改變而調(diào)整的PSO算法來求解該問題。通過仿真實(shí)驗(yàn)與其余兩種基于交換序的算法進(jìn)行對(duì)比，結(jié)果表明本文所設(shè)計(jì)的算法具有更好的全局搜索能力和收斂結(jié)果。說明本算法在解決車間送料路徑優(yōu)化問題具有更好的優(yōu)越性。

[參考文獻(xiàn)]

[1] 賀長鵬,鄭宇,王麗亞,等. 面向離散制造過程的RFID應(yīng)用研究綜述[J]. 計(jì)算機(jī)集成制造系統(tǒng),2014,20(5):1160-1170.

[2] 沈繼紅,王侃. 求解旅行商問題的混合粒子群優(yōu)化算法[J]. 智能系統(tǒng)學(xué)報(bào),2012,7(2):174-182.

[3] 易正俊,李勇霞,易校石. 自適應(yīng)蟻群算法求解最短路徑和TSP問題[J]. 計(jì)算機(jī)技術(shù)與發(fā)展,2016(12):1-5.

[4] 孫凱，吳紅星，王浩，等. 蟻群與粒子群混合算法求解TSP問題[J]. 計(jì)算機(jī)工程與應(yīng)用，2012，48(34):60-63.

[5] Li Y, Jiao L, Shang R, et al. Dynamic-context cooperative quantum-behaved particle swarm optimization based on multilevel thresholding applied to medical image segmentation[J]. Information Sciences, 2015, 294:408-422.

[6] Fan T E, Liu T D, Zheng J W, et al. Structural optimization of Pt-Pd-Au trimetallic nanoparticles by discrete particle swarm algorithms[J]. Journal of Materials Science,2015, 50(9):3308-3319.

[7] Kennedy J, Eberhart R. Particle swarm optimization[C]//Neural Networks, IEEE International Conference on. IEEE, 1995, 4: 1942-1948.

[8] Shi Y, Eberhart R. A modified particle swarm optimizer[C]//Evolutionary Computation Proceedings, 1998. IEEE World Congress on Computational Intelligence, The 1998 IEEE International Conference on. IEEE, 1998: 69-73.

[9] 孫晶晶，雷秀娟. 求解TSP的改進(jìn)自組織PSO算法 [J]. 計(jì)算機(jī)工程與應(yīng)用，2009,45(31):30-33.

[10] 趙遠(yuǎn)東,方正華.帶有權(quán)重函數(shù)學(xué)習(xí)因子的粒子群算法[J]. 計(jì)算機(jī)應(yīng)用，2013,33(8):2265-2268.

(編輯李秀敏)