改進的粒子群算法在ＶＲＰ中的應用

摘 要：運輸調度問題在理論和實踐方面都是一個難題。粒子群算法是一種可以解決復雜組合優化問題的有效求解算法。提出了改變慣性權重的粒子群算法，并應用該方法用于求解典型的運輸調度問題，結果表明，所提出的方法不僅能得到理想的結果，而且減少運算時間。

關鍵詞：粒子群算法;運輸調度;慣性權重

中圖分類號：O₂4文獻標識碼：A文章編號：1672-3198（2008）08-0393-02

1 VRP的數學模型

一般運輸調度問題的文字描述：已知需求點的位置坐標和貨物需求量，一個車隊（有多個車輛）從一個供應點（配送中心）出發，每個需求點只被一輛車訪問，且該車所訪問需求點的需求量總和不能超過車輛的負載能力，應如何安排車輛的行走路線使得總路線最短。要求：每輛車運輸完畢后回到出發點（供應點）。設供應點有K輛車，每輛車的載重為Qk（k=1，2…K），需求點個數為L，每個需求點的需求量為qi（i=1，2...，L）;需求點i到j的距離為qi（i，j=0，1，2...，L，其中i=0或j=0表示該點為供應點）；第k輛車訪問的需求點個數為nk(nk=0表示未使用第k輛車)；用集合Rk表示第k輛車的行駛路線，rki代表Rk中一個需求點，它在路線Rk中的順序為i，rk0表示供應點。借鑒的數學模型：

minZ=∑kk=1nk-1i=0drkirk(i+1)+drknkrk0（1）

∑nki=1qrn≤Qk，0≤nk≤L（2）

0kk=1nk=L（3）

Rk=rki｜rki∈1，2…，L，i=1，2 …nk，Rk1∩Rk2=，k1≠k2(4)

sign(nk)=1nk≥10其他(5)

其中式（1）為目標函數；式（2）保證每條路徑上各需求點需求量之和不超過汽車的重量并表明每條路徑上的需求點數不超過總需求點數；式（3）表明每個需求點都得到配送服務；式（4）為每條路徑的需求點的組成并且限制每個需求點僅能由一輛汽車送貨；式（5）表明當第K輛汽車服務的客戶數大于或等于1時。該車參加了配送，此時取sign(nk)=1，當第K輛汽車服務的客戶數小于1時，表示未使用該車，取sign(nk)=0。

上述數學模型的最終優化目標就是：在滿足以上各種約束條件的情況下，使得所有車輛路徑之和Z最小。

2 粒子群優化算法

2.1 標準粒子群算法

設在一個n維的搜索空間中，由m個粒子組成的種群X={x1，…x2，…xm}，其中第i個粒子位置為xi=(xi1，xi2，…，xim)T，其速度為vi=(vi1，vi2，…，vin)T。它的個體極值為pi=(pi1，pi2，…，pin)T，種群的全局極值為pg=(pg1，pg2，…，pgn)T。按追隨當前最優粒子的原理，粒子xi將按(6)、(7)式改變速度和位置。

vik+1=vik+c1r1(pik-xik)+c2r2(pgk-xik)（6）

xik+1=xik+vik+1（7）

其中，k為迭代次數，vik及xik分別為粒子i在第k次迭代的速度與位置，而pik則是粒子i在第k次迭代的自身最佳解，pgk為第k次迭代的整體最佳解，其更新后粒子i在第k+1次迭代的速度為vik+1，xik+1則是粒子i在第k+1次迭代的位置，r1、r2為介于0~1之間的隨機數，c1和c2為學習因子，建議將c1和c2取值為2。在上式中的第二部分被稱為粒子本身的認知模式，而第三部分是粒子群中的群體模式。每個粒子的速度以及移動的位置，均受最大速度vmax和最大位置xmax的限制。一旦粒子更新后的速度和位置超出所限定的最大極限時，則需將其分別設定為vmax和xmax。

主要針對速度更新公式(6)中的第一部分，期望給予vik一個慣性權重w，測量出粒子本身搜索最佳解的能力，加入慣性權重w之后速度更新公式如下所示：

vik+1=wvik+c1r1pik-xik+c2r2(pgk-xik)（8）

式中w為一常數，為提供各粒子速度vik的一個移動比例，對于各粒子而言，該權重可以調整速度vik的移動速度大小。當慣性權重w較大時，決定粒子下一次搜索方向的主要影響因素為vik，所以粒子會呈現較穩定的搜索路徑，進而表現出較好的全局搜索特性。反之，如果慣性權重w較小時，則會受到vik、自身最佳解pbest與整體最佳解gbest等三種因素的影響，出現搜索路徑不穩定的現象，僅能發揮出局部搜索的能力。

2.2 改進的粒子群算法

為了解決不易選取合理的慣性權重的困難，本文提出將慣性權重以線性遞減方式加以考慮的方法，即將式(8)中的w由下列式子決定：

w=wmax-wmax-wminkmax×k(9)

式中wmax為使用者設定的慣性權重上限值，wmin為慣性權重下限值，一般慣性權重w的范圍為0.8~1.4。通過添加線性慣性權重使得初始搜索階段具有較高的慣性權重值，從而保證搜索初期全局搜索的靈活性，隨著迭代過程的進行逐漸降低慣性權重，轉入局部搜索，加強粒子局部搜索能力。

為了避免各粒子在使用式(7)后產生過大移動步幅，給各粒子最大移動速度進行限制，其最大速度計算公式如下所示：

vmaxγ(xub-xlb)(10)

式中xub及xlb分別為搜索空間中變量的上、下限值，γ式用于取決搜索空間中最大速度的移動距離。采用最大速度限制加以約束后，使得粒子的搜索效果更好，并且可以減少不必要的計算時間。

2.3 改進粒子群算法流程

第一步：設定初始值：最大迭代次數kmax，學習因子c1、c2，動態周期遞減周期h，慣性權重以及最大速度動態系數α、β，初始最大速度vmax0，γ，慣性權重上限值wmax，慣性權重下限值wmin，以及其它初始值。在搜索空間中，隨機產生初始粒子群的速度v0及位置x0。

第二步：對各粒子進行分析計算，根據所設定的目標函數與限制，進一步計算各粒子的適應值。初始階段的自身最佳解pi0即為各粒子的初始解xi0，而所有粒子自身最佳解中適應值最好的解即為整體最佳解pg0。

第三步：利用自身最佳解pik以及整體最佳解pgk修正各粒子下一次搜索的速度，速度更新公式如式（8），其中慣性權重采用動態調整策略。并根據該調整策略更新搜索速度，進一步更新各粒子的所處位置，其位置更新公式如式（7）所示。

第四步：將更新后各粒子的適應值與自身最佳解的適應值進行比較，產生下一次迭代的自身最佳解pik+1。將整體最佳解與自身最佳解中適應值最佳的解進行比較，一旦自身最佳解中適應值最好的解優于整體最佳解，則需將下一次迭代的整體最佳解pgk+1加以更新。

第五步：若經過h次迭代后，整體最佳解的適應值仍然無法改善，則需根據將慣性權重和最大速度調整策略進行調整，如式（9）、（10）所示。

第六步：若是滿足終止條件則迭代停止，否則重復第三步，終止條件則是取決于最大迭代次數kmax。



3 實驗分析

引用一個常用的運輸調度問題為例來測試算法。有8個需求點和一個供應點的系統，各個需求點對應供應點的需求量為qi(i=1，2，…，8)（單位為t）。供應點只有兩輛車用于配送，每輛車的載重均為8噸，已知供應點與各個需求點之間的距離（單位為km）。算法由Matlab 7.1仿真，運行環境為Pentium 4，2.0GHZ，內存為2G的微機上進行。用文獻的遺傳算法與本文的改進粒子群算法相比較，兩種算法在結論上的差異是很明顯的，另外達到最優路徑的迭代時間，改進粒子群算法為4.52S ；遺傳算法為5.68S。實驗證明本算法的可行性。