混合差分粒子群優(yōu)化算法及其應(yīng)用

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

【關(guān)鍵詞】差分進(jìn)化;粒子群;定向變異;物流配送優(yōu)化

1.引言

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

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

2.研究現(xiàn)狀

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

國內(nèi)外很多學(xué)者對DE和PSO算法進(jìn)行了深入研究，文獻(xiàn)[2]在基本差分進(jìn)化算法的基礎(chǔ)上，把自適應(yīng)變空間思想融入提出了自適應(yīng)變空間差分進(jìn)化算法，在進(jìn)化代數(shù)達(dá)到預(yù)設(shè)周期整數(shù)倍時，按變空間算法自動擴(kuò)展或收縮搜索空間，實現(xiàn)了自動尋找合適搜索空間、提高收斂速度和精度的目的;文獻(xiàn)提出了兩種新的改進(jìn)算法：DERL和DELB，并進(jìn)行了大量對比仿真，驗證了改進(jìn)算法的有效性;文獻(xiàn)改進(jìn)了粒子速度的更新公式，引入了慣性權(quán)因子，并提出了自適應(yīng)調(diào)整的策略，使算法在搜索初期有較大的搜索能力，而在后期又能得到較精確的結(jié)果。文獻(xiàn)[9]提出了算法模型，PSO模型是基于繁殖和子種群的雜交，在子群的繁殖過程中，PSO算法引入繁殖概率，每次迭代可產(chǎn)生相同數(shù)目的后代微粒，父代微?？捎煤蟠⒘Ｈ〈瑢崿F(xiàn)保持不變的種群的微粒數(shù)目，對于后代的微粒位置由父母位置的算術(shù)“交叉”得到，達(dá)到了防止早熟和加快收斂速度的效果。

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

3.NHDEPSO算法

3.1 基本DE算法

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

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

（1）

Np是種群規(guī)模，經(jīng)過一系列規(guī)定的操作，第t代個體進(jìn)化為：

（2）

式中，D為所優(yōu)化問題的維數(shù)。

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

（3）

（4）

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

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

（5）

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

（6）

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

3.2 標(biāo)準(zhǔn)粒子群算法

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

（6）

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

3.3 算法改進(jìn)

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

（7）

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

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

（8）

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

3.4 NHDEPSO算法步驟

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

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

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

Step4：按照（7）式進(jìn)行變異操作產(chǎn)生群體P1（t）;按照（8）式進(jìn)行變異操作產(chǎn)生群體P2（t）。

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

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

Step7：如滿足精度則停止進(jìn)化輸出最優(yōu)個體;否則，轉(zhuǎn)步驟3。

4.算法性能分析

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

對比算法選取標(biāo)準(zhǔn)DE、PSO和DEPSO算法， DE和PSO參數(shù)的設(shè)置同上，DEPSO參數(shù)設(shè)置參見文獻(xiàn)[11]中的設(shè)置，仿真精度VTR=10-6。仿真結(jié)果如圖1～3所示，為方便對比，在圖1～3中取適應(yīng)值的對數(shù)來畫圖。

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

表1 測試函數(shù)

函數(shù)名 表達(dá)式 取值范圍

Dejong

Griewank

Rosenbrock

表2 基準(zhǔn)函數(shù)的優(yōu)化結(jié)果比較

算法 性能 F1 F2 F3 F4 f7 f8

PSO 收斂率 0.27 0.31 0.21 0.19 0.35 0.3

平均收斂代數(shù) 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

平均收斂代數(shù) 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

平均收斂代數(shù) 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

平均收斂代數(shù) 807 1423 652 1576 825 756

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

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

5.NHDEPSO算法在電子商務(wù)物流配送路徑優(yōu)化問題中的應(yīng)用

5.1 B2C電子商務(wù)物流配送數(shù)學(xué)模型

文獻(xiàn)[17]給出了B2C電子商務(wù)物流配送路徑優(yōu)化模型：

（9）

滿足如下條件：

（10）

（11）

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

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

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

圖1 目標(biāo)函數(shù)f1的收斂曲線

圖2 目標(biāo)函數(shù)f2的收斂曲線

圖3 目標(biāo)函數(shù)f3的收斂曲線

圖4 實際配送網(wǎng)絡(luò)圖

5.2 基于NHDEPSO算法的配送路線優(yōu)化仿真

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

圖5 基于NHDEPSO算法的車輛最優(yōu)配送路徑

圖6 目標(biāo)函數(shù)收斂曲線

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

表3 仿真結(jié)果對比

計算次數(shù) 目標(biāo)值/元 計算時間/秒

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

標(biāo)準(zhǔn)差 113.95 39.58 3.79 0.133 0.070 0.085

6.結(jié)論

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

參考文獻(xiàn)

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

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

[3]張潔，裴芳.多策略協(xié)同進(jìn)行粒子群優(yōu)化算法[J].計算機(jī)應(yīng)用研究，2013，30（10）：2965-2967.

[4]陽春華，錢小山，桂衛(wèi)華.一種混沌差分粒子群優(yōu)化混合算法[J].計算機(jī)應(yīng)用研究，2011，28（2）：32-35.

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

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

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

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

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

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