混合差分粒子群優化算法及其應用

【摘要】基于差分進化算法在收斂快速性及粒子群算法在種群多樣性保持上的優勢，提出一種新的混合啟發式優化算法，其基本思路是將粒子群種群作為輔助變異算子，與差分進化算法種群進行交叉操作，產生的新子代繼承了父代和母代的優勢特性，從而避免了單一算法的早熟收斂和收斂速度過慢的問題. 通過在測試函數上的仿真實驗印證了該算法思想的可行性，并將其應用到物流配送路徑優化問題的解決中。

【關鍵詞】差分進化;粒子群;定向變異;物流配送優化

1.引言

優化問題普遍存在于科學研究、經濟管理和工程技術等諸多領域，近年來以遺傳算法、粒子群算法和差分進化算法為代表的群智能優化算法得到了迅速的發展和廣泛應用，與傳統優化方法相比，這些智能優化算法的優勢在于能夠保證收斂的前提下，對所求優化問題動力學信息不苛求，具有全局優化能力。

差分進化算法（Differential Evolution， 簡稱DE）是一種新的進化計算技術，它其實是一種基于實數編碼的具有保優思想的貪婪遺傳算法。同遺傳算法一樣，差分進化算法包含變異和交叉操作，但同時相較于遺傳算法的選擇操作，差分進化算法采用一對一的淘汰機制來更新種群。它的特點是具有良好的優化性能，但是對于多峰值函數以及搜索空間較大時，算法收斂速度較慢，且易早熟。粒子群優化算法（Particle Swarm Optimization， 簡稱PSO）也是一種典型的群智能算法，它源于對鳥群、魚群覓食行為的研究和模擬。PSO算法簡單易于實現，并且在保持種群多樣性上具有一定優勢，且具有相對較快的收斂速度。在PSO算法中，群體中所有的粒子具有相同的搜索行為，并表現出相同的全局或局部搜索能力。

2.研究現狀

PSO和DE算法都是一種基于群體進化的智能優化算法，他們有自身的特點和優勢，同樣也都存在缺陷和不足。具體講就是DE是一種基于隨機種群搜索的算法，它通過特有的變異、交叉和選擇操作使種群能夠快速進化到最優值附近，算法簡單，控制參數少，易于實現。DE算法在具有簡易和快速收斂性的同時，其在種群多樣性方面優勢不明顯，算法易陷入局部極小。PSO算法也比較簡單，便于實現，并且在種群多樣性保持上具有一定優勢，收斂速度相對較快。

國內外很多學者對DE和PSO算法進行了深入研究，文獻[2]在基本差分進化算法的基礎上，把自適應變空間思想融入提出了自適應變空間差分進化算法，在進化代數達到預設周期整數倍時，按變空間算法自動擴展或收縮搜索空間，實現了自動尋找合適搜索空間、提高收斂速度和精度的目的;文獻提出了兩種新的改進算法：DERL和DELB，并進行了大量對比仿真，驗證了改進算法的有效性;文獻改進了粒子速度的更新公式，引入了慣性權因子，并提出了自適應調整的策略，使算法在搜索初期有較大的搜索能力，而在后期又能得到較精確的結果。文獻[9]提出了算法模型，PSO模型是基于繁殖和子種群的雜交，在子群的繁殖過程中，PSO算法引入繁殖概率，每次迭代可產生相同數目的后代微粒，父代微粒可用后代微粒取代，實現保持不變的種群的微粒數目，對于后代的微粒位置由父母位置的算術“交叉”得到，達到了防止早熟和加快收斂速度的效果。

另一方面，為突破單一算法的局限，繼承和發揚算法各自的優點，國內外學者對混合種群智能優化算法進行了很多研究和探討。文獻[1]根據遺傳算法和粒子群算法各自的特點，設計了一種遺傳算法和粒子群優化的多子群分層混合算法，底層由遺傳算法組成，貢獻算法的全局搜索能力，上層由各子群的最有個體組成精英群，采用粒子群加速收斂。文獻[10]結合混沌差分進化思想，提出混沌差分進化的粒子群優化算法，利用信息交換機制，引入混沌變異操作，用差分進化算法和粒子群算法將兩組種群分別進行協同進化，提高了算法的局部搜索能力和收斂速度。文獻[11]提出一種差分進化與粒子群雙種群協同進化算法（DEPSO），仿真結果顯示了有效性。基于上述思想，本文對差分進化和粒子群算法以及兩者的混合算法進行了深入研究，提出了一種新的混合差分粒子群優化算法（New hybrid differential evolution and particle swarm optimization algorithm，簡稱NHDEPSO），仿真驗證其有效性，并應用到物流配送問題研究中。

3.NHDEPSO算法

3.1 基本DE算法

DE算法是一種基于群體進化的算法，通過種群內個體間的合作與競爭來優化問題的解，具有記憶最優個體和共享種群內信息的特點，其本質就是一種用實數編碼具有保優思想的貪婪遺傳算法[19]。

算法首先要取得一組在搜索空間上隨機初始化的種群：

（1）

Np是種群規模，經過一系列規定的操作，第t代個體進化為：

（2）

式中，D為所優化問題的維數。

為防止陷于局部極值，可采用變異進化，有多種變異的方式，本文列出其中DE/rand/1和DE/best/2：兩種基本的變異方式。

（3）

（4）

式（1）和（2）中，當前種群中隨機個體是各不相同的;為適應度最好的個體;為縮放因子。

交叉策略為：在種群中假設個體與進行交叉操作，產成試驗個體，為了確證個體的進化，首先通過隨機選擇，使試驗個體xT至少有一位由貢獻。其他位則利用交叉概率因子CR，交叉操作方程為：

（5）

選擇策略：采用“貪婪”的搜索策略，誰的適應值高，就選擇誰作為子代：

（6）

上述算法中，父代兩個不相同的隨機個體相減得到差分矢量，隨機選取第3個個體把差分矢量加到其上，產生一個變異的個體，依據一定的概率，將父代個體同變異個體之間進行交叉操作，得到試驗的個體，然后按照應度函數值的大小在父代個體與試驗個體之間進行選擇，擇優的個體作為子代，保證了最優的進化方向。

3.2 標準粒子群算法

標準PSO算法，是由m個粒子組成的群體在n維搜索空間中以一定的速度飛行，每個粒子在搜索時，考慮到了自己搜索到的歷史最好點和群體內其他粒子的歷史最好點，在此基礎上進行位置的變化，直到滿足條件時停止并輸出最優解：

（6）

式中，上標i對應于第i個個體（，N為種群規模），下標j對應于粒子的第j維，t表示當前迭代代數;和分別表示第i個粒子的位置和速度，其中;是慣性因子;c1、c2分別是個體歷史最優和全體最優的加速因子;r1、r2為[0，1]內隨機數。

3.3 算法改進

對于DE算法和粒子群算法的改進，已有很多學者進行了研究，這里采用兩種簡單的改進方式，來提高算法的性能。文獻[12]提出一種新的差分變異方式，該變異方式能有效地提高算法的收斂速度，同時也在一定程度上還能保持較高的種群的多樣性。在種群中新的差分變異方案是隨機選取不同的四個個體，來生成差分矢量對每代個體進行變異操作。其變異的方程為：

（7）

在（7）式的變異中，對于第t代的種群的第i個個體，基向量仍然采用，表示在的基礎上進行變異，這種變異方式使初始種群的多樣性得到了很好保持，種群進化的方向同時也得到了兼顧。后面一項是作為“擾動項”引入的，經過這種方式處理后，使變異后的個體可以保持盡可能大的差異，從而使種群的多樣性得到很好的保持。

文獻[13]認為以往的粒子群算法都是基于“位置”和“速度”兩個概念，并且改進算法也都是圍繞這兩個參數增加操作算子，如雜交、變異等，使得算法描述越來越復雜。對此作者經過研究分析相關文獻資料，提出一種簡化的不含速度項的粒子群位置變換公式：

（8）

式中，右邊的第1項為“歷史（history）”部分，表示過去對現在的影響，通過調節影響程度;第2項為“認知（cognition）”部分，表示粒子對自身的思考;第3項為“社會（social）”部分，表示與鄰居粒子的比較和模仿，實現粒子間的信息共享與合作。

3.4 NHDEPSO算法步驟

Step1：設定參數Np、D、D、CR、xmin、xmax、c1、c2等參數;設置進化代數計數器t=0;設置變空間次數最大值T。

Step2：初始化.在搜索空間[xmin，xmax]中隨機產生Np個個體作為初始種群P（0）。

Step3：個體評價.計算群體P（t）中每一個體的評價函數值f（i），并根據評價值對和進行賦值。

Step4：按照（7）式進行變異操作產生群體P1（t）;按照（8）式進行變異操作產生群體P2（t）。

Step5：P1（t）和P2（t）按照（5）式進行交叉操作產生下一代種群P'（t）。

Step6：按照（6）式對種群P1（t）和P'（t）進行選擇操作產生子代種群P（t+1），并對種群P（t+1）個體進行評價。

Step7：如滿足精度則停止進化輸出最優個體;否則，轉步驟3。

4.算法性能分析

算法性能測試參數設置：設置維數D=30;種群規模取維數的5～10倍[4]，這里取NP=200;最大迭代次數8000;差分縮放因子取F=0.6;差分交叉概率取CR=0.6。設置粒子群算法參數=0.729，c1=c2=1.49445[14]，測試函數如表1所示。

對比算法選取標準DE、PSO和DEPSO算法， DE和PSO參數的設置同上，DEPSO參數設置參見文獻[11]中的設置，仿真精度VTR=10-6。仿真結果如圖1～3所示，為方便對比，在圖1～3中取適應值的對數來畫圖。

對文獻[15]測試函數F1-F4、文獻[16]測試函數f 7和f 8進行仿真分析，參數設置同上。為便于比較4種方法計算6個測試函數的收斂情況，參考文獻[15]，若求得的結果與理想最優解的誤差若小于10-4，則視其算法收斂性已實現，最大迭代代數為4000。記錄算法第一次達到收斂的代數和時間，分別稱為收斂代數、收斂時間。采用編程工具MATLAB 2013a，配置計算機的系統為：Pentium4 3.00GHz，4GHz內存，Win7。每個測試的算法分別獨立執行50次，分別平均計算50次的試驗結果如表2所示。

表1 測試函數

函數名 表達式 取值范圍

Dejong

Griewank

Rosenbrock

表2 基準函數的優化結果比較

算法 性能 F1 F2 F3 F4 f7 f8

PSO 收斂率 0.27 0.31 0.21 0.19 0.35 0.3

平均收斂代數 2358 3520 3200 3321 1920 1832

平均收斂時間/ms 45.32 86.22 75.26 82.35 37.25 35.26

DE 收斂率 0.34 0.24 0.33 0.23 0.4 0.38

平均收斂代數 2198 3652 2635 3457 1735 1507

平均收斂時間/ms 41.25 61.23 49.67 58.35 32.48 27.89

DEPSO 收斂率 0.6 0.58 0.73 0.67 0.8 0.9

平均收斂代數 1423 2347 1378 1736 536 796

平均收斂時間/ms 37.25 46.35 35.26 39.57 15.6 23.12

NHDEPSO 收斂率 0.82 0.79 0.92 0.89 0.93 0.97

平均收斂代數 807 1423 652 1576 825 756

平均收斂時間/ms 25.12 37.35 20.14 37.58 22.25 20.35

從圖1～圖3及表2對比數據可以看出，NHDEPSO算法在f1～f3、F1～F4、f7～f8測試函數上的尋優性能普遍好于其他幾種對比算法。例如圖1中，在f1函數上DE、PSO和DEPSO算法均趨向于早熟收斂，但是NHDEPSO卻能夠在保持種群多樣性，防止早熟收斂以及收斂速度上具有明顯優勢。

5.NHDEPSO算法在電子商務物流配送路徑優化問題中的應用

5.1 B2C電子商務物流配送數學模型

文獻[17]給出了B2C電子商務物流配送路徑優化模型：

（9）

滿足如下條件：

（10）

（11）

模型中的符號有兩類：決策變量和模型參數。

決策變量：xijk表示車輛k是否從節點i開往節點j;yij表示顧客j是否由配送中心i配送;zjk表示顧客j是否由車輛k配送。

模型參數：G是配送中心、顧客兩類節點和代表之間配送線路的邊組成的不完全無向圖，，其中：表示配送中心節點集合，表示顧客的節點集合，表示配送中心、顧客間直接線路邊的集合;K配送車輛集合，每輛車僅屬于一個配送中心;L配送商品種類集合;Ap配送中心p的可用車輛數;Bk車輛k的一次性啟動費用;Cij車輛k在路線（i，j）單位路程的運輸費用;qjl顧客j對商品l的需求量;dij顧客（或配送中心）i，j間的距離;Q單個車輛的裝載量;商品l的重量系數;vil配送中心i商品l的供應量。

圖1 目標函數f1的收斂曲線

圖2 目標函數f2的收斂曲線

圖3 目標函數f3的收斂曲線

圖4 實際配送網絡圖

5.2 基于NHDEPSO算法的配送路線優化仿真

設某B2C電子商務企業在某時段由3個配送中心為17個顧客配送3類商品，配送網絡節點（站點和客戶）及他們之間的相互距離如圖4所示。設三個配送中心可用車輛數均為Ap=3輛，最大載重量均為Q=10t，車輛啟動費用元，單位距離費用元，3類商品的重量系數分別為噸/件、噸/件，其他相關參數見文獻[18]。為了驗證基于NHDEPSO算法的物流分配方案的有效性，將基于該算法與基于DE算法和PSO算法所得到的目標函數優化值進行對比（各隨機計算10次，求平均值），如表3所示，基于NHDEPSO算法的B2C物流配送最優配送路徑如圖5所示，隨機各選取其中一次目標函數收斂曲線對比如圖6所示（為方便對比，選取同一初始種群）。

圖5 基于NHDEPSO算法的車輛最優配送路徑

圖6 目標函數收斂曲線

從表3對比數據可以看出，雖然在程序運算時間上基于NHDEPSO的物流配送優化算法略長于基于DE算法的優化算法，但是在目標函數的優化值上基于NHDEPSO算法的優化值要具有明顯優勢，10次優化計算的最優值的平均值和標準值均小于基于其他兩種基本算法的物流配送方案。因此，基于NHDEPSO算法的B2C物流配送路線方案是可行和高效的。

表3 仿真結果對比

計算次數 目標值/元 計算時間/秒

PSO DE NHDEPSO PSO DE NHDEPSO

1 2352 2148 2085 0.952 0.756 0.658

2 2248 2096 2085 1.253 0.563 0.547

3 2153 2085 2085 1.123 0.624 0.589

4 2458 2085 2085 1.258 0.524 0.668

5 2247 2124 2085 1.145 0.468 0.758

6 2189 2085 2085 0.975 0.587 0.987

7 2315 2178 2085 1.365 0.652 0.752

8 2478 2085 2097 1.287 0.498 0.675

9 2185 2179 2085 0.976 0.513 0.694

10 2368 2085 2085 0.953 0.487 0.587

平均值 2299.3 2115.0 2086.2 1.129 0.567 0.692

標準差 113.95 39.58 3.79 0.133 0.070 0.085

6.結論

本文基于生物遺傳思想，設計了一種新的差分進化粒子群混合算法，該算法能夠繼承差分進化和粒子群算法的優勢，提高算法的性能，通過仿真對比顯示該算法在保持種群多樣性和收斂性能上要優于所對比算法。最后將該算法應用到B2C電子商務物流配送中，仿真結果顯示該算法要優于基于差分進化和粒子群算法的物流配送優化方案。

參考文獻

[1]金敏，魯華祥.一種遺傳算法與粒子群優化的多子群分層混合算法[J].控制理論與應用，2013，30（10）：1231-1238.

[2]姚峰，楊衛東，張明，李仲德.改進自適應變空間差分進化算法[J].控制理論與應用，2010，27（1）：32-35.

[3]張潔，裴芳.多策略協同進行粒子群優化算法[J].計算機應用研究，2013，30（10）：2965-2967.

[4]陽春華，錢小山，桂衛華.一種混沌差分粒子群優化混合算法[J].計算機應用研究，2011，28（2）：32-35.

[5]楊衛東，姚峰，張明.基于自適應交叉概率因子的差分進化算法及其應用[J].信息與控制，2010，39（2）：187-193.

[6]胡旺，李志蜀.一種更簡化而高效的粒子群優化算法[J].軟件學報，2007，18（4）：861-868.

[7]蔣忠中，汪定偉.B2C電子商務中物流配送路徑優化的模型與算法[J].信息與控制，2005，34（1）：481-485.

[8]汪定偉，王俊偉，王洪峰等.智能優化算法[M].北京：高等教育出版社，2007.

[9]劉波，干凌，金以慧.差分進化算法研究進展[J].控制與決策.2007，22（7）：721-729.

作者簡介：楊智博（1992—），男，山西榆社人，現就讀于太原理工大學信息工程學院，主要從事自動化和信息工程研究。