摘 要： 提出了一個(gè)全新的混合算法并命名為微粒群差分算法，該算法在標(biāo)準(zhǔn)微粒群算法的基礎(chǔ)上結(jié)合了差分進(jìn)化算法用于求解約束的數(shù)值和工程優(yōu)化問題。傳統(tǒng)的標(biāo)準(zhǔn)微粒群算法由于其種群?jiǎn)我恍匀菀紫萑刖植孔顑?yōu)值，針對(duì)這一缺點(diǎn)利用差分進(jìn)化算法中的變異、交叉、選擇3個(gè)算子來更新每次迭代每個(gè)粒子新生產(chǎn)的位置以使粒子跳出局部?jī)?yōu)值。融合了標(biāo)準(zhǔn)微粒群算法和差分進(jìn)化算法優(yōu)點(diǎn)的混合算法加速了粒子的收斂速度。為了避免懲罰因子的選擇對(duì)實(shí)驗(yàn)結(jié)果的影響，采取了可行規(guī)則法來處理約束優(yōu)化問題。最后將微粒群差分算法用于5個(gè)基準(zhǔn)函數(shù)和兩個(gè)工程問題，并與其他算法作了比較，試驗(yàn)結(jié)果表明，微粒群差分算法算法具有很好的精準(zhǔn)性、魯棒性和有效性。

　　關(guān)鍵詞： 混合算法；約束優(yōu)化問題；微粒群算法；差分進(jìn)化；可行規(guī)則

　　進(jìn)化算法由于其通用性、可靠性、穩(wěn)定性、簡(jiǎn)單性、所需要的信息少等一系列的優(yōu)點(diǎn)，被廣泛地用來解決并且成功地解決了很多約束優(yōu)化問題。因此，提出了很多基于進(jìn)化算法的約束處理方法[1-3]。由Kennedy和Eberhart [4] 提出的標(biāo)準(zhǔn)微粒群算法(PSO)便是其中一種應(yīng)用廣泛的仿生算法，它模擬鳥類群體覓食行為來尋求最優(yōu)解，是一種基于群體智能的隨機(jī)尋優(yōu)算法，依賴于個(gè)體之間和種群之間的信息共享交換。然而PSO算法由于其種群的單一性容易導(dǎo)致早熟現(xiàn)象，使得優(yōu)化問題陷入局部最優(yōu)解。利用其他算法的全局搜索能力來改善PSO算法的缺點(diǎn)，這一混合算法的思想受到很多人的認(rèn)同，本文正是在此基礎(chǔ)上融合了差分進(jìn)化算法(DE)的進(jìn)化策略，提出了一種新的PSO、DE混合算法。算法的前半部分同粒子群算法，只是在粒子進(jìn)行速度、位置更新后，借鑒DE算法的變異、交叉、選擇算子以增強(qiáng)粒子群的多樣性。

1 背景知識(shí)介紹

　　1.1 PSO算法

　　如上所述，PSO是受鳥類覓食行為啟發(fā)而來的隨機(jī)全局優(yōu)化算法?；綪SO的速度和位置更新方程如下：

　　其中，為第i個(gè)粒子在第t次迭代時(shí)的自身歷史最優(yōu)位置，gbestt是第t次迭代時(shí)的種群最優(yōu)位置。是慣性權(quán)重，c1，c2是常量，r1，r2是服從U(0,1)的兩個(gè)相互獨(dú)立的隨機(jī)數(shù)。然而這個(gè)基本的PSO算法，速度是受到限制的。Clerc和Kennedy[5]引入了收縮因子修改了標(biāo)準(zhǔn)的微粒群模型，速度更新公式變?yōu)椋?/p>

　　1.2 差分進(jìn)化算法（DE）

　　差分進(jìn)化算法是由Storn和Price[6]于1995年提出的解決全局優(yōu)化問題的隨機(jī)進(jìn)化算法。算法通過變異、交叉、選擇3種操作來領(lǐng)導(dǎo)種群找到最優(yōu)解。DE算法的主要流程如下：

　　變異操作：本文中采用的是rand/1變異策略即vi=xr1+F×(xr2-xr3)，{xr1, xr2, xr3}， 是在父代種群中隨機(jī)選擇的3個(gè)不同個(gè)體，并且。F是一個(gè)介于[0,2]間的實(shí)型常量因子，稱為放縮因子。

　　交叉操作：交叉操作的目的是通過變異個(gè)體Vi=(vi,1,vi,2,…,viD)和目標(biāo)個(gè)體Xi=(xi,1,xi,2,…,xiD)各維分量的隨機(jī)重組以提高種群個(gè)體的多樣性。算法通過下面的公式產(chǎn)生交叉向量Ui=(ui,1,ui,2,…,uiD)：

　　其中，rand是[0,1]間的隨機(jī)數(shù)；CR是范圍在[0,1]間的常數(shù)稱為交叉變量。

　　選擇操作：在貪婪準(zhǔn)則的指導(dǎo)下，交叉向量Ui與目標(biāo)個(gè)體Vi競(jìng)爭(zhēng)。假設(shè)待求問題為minf(x),則選擇操作可由下式確定：

　　1.3 可行規(guī)則

　　本文對(duì)于約束的處理采用的是可行規(guī)則法，可行規(guī)則[7]包含3個(gè)方面的內(nèi)容。

　?、湃我饪尚薪饪偸莾?yōu)于不可行解；

　?、苾蓚€(gè)不可行解之間，適應(yīng)值好的要優(yōu)于適應(yīng)值差的；

　?、莾蓚€(gè)不可行解之間，約束沖突值小的要優(yōu)于約束沖突值大的。

　　總而言之，可行規(guī)則法就是找一個(gè)離可行域最近的解，即使這個(gè)解不在可行域內(nèi)。

2 微粒群差分算法(CPSODE)

　　2.1 CPSODE算法的原理

　　如上所述，基本PSO算法盡管操作簡(jiǎn)單但并不是完美的。在本文中，在PSO的基本框架中加入了DE進(jìn)化策略?；綪SO算法中的粒子在每次迭代中通過學(xué)習(xí)自身的歷史最優(yōu)位置和全局最優(yōu)位置來更新自己的速度和位置,從而慢慢靠近優(yōu)化問題的最優(yōu)解。換句話說，PSO算法以全局最優(yōu)位置為中心，吸引所有其他粒子靠近，但是如果最優(yōu)位置粒子得不到更新，將出現(xiàn)早熟現(xiàn)象。這就是PSO算法陷入局部?jī)?yōu)值最本質(zhì)的原因。眾所周知，DE算法有著高效的全局搜索能力，其進(jìn)化策略不僅參數(shù)少而且收斂速度快。如果考慮在PSO的位置更新后，對(duì)位置矢量進(jìn)行DE的變異、交叉、選擇操作，在這里變異選取了rand/1策略，這樣位置矢量就得到更新，使得粒子的運(yùn)動(dòng)軌跡偏離既定的軌道，從而全局最優(yōu)位置得到更新，增強(qiáng)了種群多樣性。對(duì)DE進(jìn)化策略的采納不但加強(qiáng)了算法的搜索能力使算法能夠更快的收斂到最優(yōu)值，而且使算法跳出局部最優(yōu)值的概率很大，可以有效地避免早熟早收斂。

　　2.2 CPSODE算法的流程

　　為了處理約束，首先在搜索空間隨機(jī)初始化種群規(guī)模為M的粒子群的位置和速度，并計(jì)算每個(gè)粒子的適應(yīng)值和約束沖突值，令每個(gè)粒子的歷史最優(yōu)位置(記作pbest)為初始化位置，適應(yīng)值最優(yōu)的歷史最優(yōu)位置為種群最優(yōu)位置(記作gbest)；其次根據(jù)式⑵、式⑶更新每個(gè)粒子的位置和速度，接著對(duì)更新的位置進(jìn)行DE算法的變異、交叉、選擇操作，并重新計(jì)算各個(gè)粒子的適應(yīng)值和約束沖突值；然后，在可行規(guī)則法的指導(dǎo)下，每個(gè)粒子更新pbest,并與gbest的適應(yīng)值進(jìn)行比較，若較好，則更新gbest，否則保持gbest原始位置。最后循環(huán)條件判斷，若不滿足算法會(huì)一次次迭代，直到滿足終止條件。程序的結(jié)構(gòu)流圖如圖1所示。

　　本文對(duì)于兩處位置更新也做了細(xì)節(jié)的處理。搜索在搜索范圍內(nèi)才是有效的，因此CPSODE算法為了避免對(duì)速度的限制，使用了帶收縮因子的速度更新公式即式（3），這樣就保證粒子每次迭代的速度都不會(huì)致使粒子偏離搜索范圍。其次，每次迭代新生產(chǎn)的位置若超出了邊界，則超出邊界的變量將用如下的法則處理[8]：

　　對(duì)每次迭代中DE交叉操作產(chǎn)生的交叉?zhèn)€體Uit，如果交叉?zhèn)€體Uit中任意一維向量Uti,j超出搜索空間，那么將會(huì)根據(jù)參考文獻(xiàn)[9]處理：

　　2.3 CPSODE算法時(shí)間復(fù)雜度分析

　　針對(duì)約束優(yōu)化問題，設(shè)n為種群的粒子數(shù)，d為目標(biāo)函數(shù)的維數(shù)，T為最大迭代次數(shù)。根據(jù)圖1所示的CPSODE算法程序結(jié)構(gòu)流程來分析其復(fù)雜度。分析結(jié)果如表1所示。

　　由上表可以看出，CPSODE算法的復(fù)雜度是O(T×n)數(shù)量級(jí)，n表示任意一個(gè)數(shù)。

3 實(shí)驗(yàn)仿真與分析

　　為了驗(yàn)證CPSODE算法的有效性，證明其相對(duì)于其他算法的優(yōu)點(diǎn)，這一部分用了5 個(gè)典型約束測(cè)試函數(shù)和兩個(gè)實(shí)際的工程問題來驗(yàn)證本文所提出的混合算法，這些測(cè)試函數(shù)包括非線性和二次函數(shù)。

　　3.1 典型約束測(cè)試函數(shù)優(yōu)化

　　對(duì)每個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行100次，CPSODE算法參數(shù)設(shè)置如下：粒子數(shù)N=200，F(xiàn)和CR分別為0.4、0.9，g01,g04,g11最大迭代次數(shù)設(shè)置為500，g04和g08分別設(shè)置為300和250。收縮因子missing image file，對(duì)函數(shù)g11取 ε值為0.000 01。加速常量c1=c2=2.05。表2總結(jié)了在以上參數(shù)設(shè)置下約束測(cè)試函數(shù)的結(jié)果，給出了最好值，平均值，最差值和標(biāo)準(zhǔn)方差?？梢钥吹紺PSODE算法均能找到測(cè)試函數(shù)的全局最優(yōu)值，而且函數(shù)g06、g08能夠保持收斂到全局最優(yōu)值。每個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行100次的標(biāo)準(zhǔn)方差也比較小。

　　CPSODE算法同時(shí)也跟CRGA、SAPF、CDE、CLUDE和CPSO算法作了比較。結(jié)果如表3、表4、表5所示，NA表示不可求。從表格中可以看出，CPSODE算法要優(yōu)于CRGA、SAPF、CDE算法，且可與性能很好的CLUDE和ABC算法相比較。就CLUDE算法而言，本文所提出的算法對(duì)g11尋找到更好的最好值、平均值和最差值；針對(duì)g01函數(shù)的平均值和最差值，CPSODE算法結(jié)果比其結(jié)果要好；對(duì)剩下的函數(shù)CPSODE、CLUDE算法都可以找到相同的最好值，對(duì)g04、g06、g08這3個(gè)函數(shù)的平均值也相同，最差值方面兩種算法對(duì)g06、g08的最差值相同，只是對(duì)g04函數(shù)的最差值，CPSODE要略遜色一些。對(duì)于CPSO算法，CPSODE算法對(duì)g11函數(shù)求得的最好值、平均值、最差值都要優(yōu)于CPSO算法?？偠灾?，CPSODE算法具有較好的尋優(yōu)能力。

　　3.2 工程問題優(yōu)化

　　為了研究CPSODE算法解決現(xiàn)實(shí)生活中工程問題的性能，用兩個(gè)典型的實(shí)際工程問題對(duì)算法做了測(cè)試，分別是焊接條和伸縮繩問題。每個(gè)問題獨(dú)立運(yùn)行100次，粒子數(shù)N=200，F(xiàn)和CR分別為0.4、0.9，最大迭代次數(shù)設(shè)置為500。

　　從表6可以看出，CPSODE找到的最優(yōu)解比參考文獻(xiàn)[15]、參考文獻(xiàn)[16]結(jié)果要好。而且CPSODE算法的平均值比其他算法都好，不僅如此，最差值和方差都是最優(yōu)的。甚至CPSODE的最差值也要比參考文獻(xiàn)[16]最優(yōu)值好。表明CPSODE對(duì)于實(shí)際工程問題的求解有其明顯的優(yōu)勢(shì)。

　　從表7中，可以得出CPSODE算法找到的最優(yōu)值比參考文獻(xiàn)[16]、參考文獻(xiàn)[17]結(jié)果好，不僅如此，本文所提出算法對(duì)伸縮繩問題求解的平均值和方差均優(yōu)于其他算法，最差值也同樣優(yōu)于除了參考文獻(xiàn)[18]之外的其他算法，甚至要比參考文獻(xiàn)[17]最優(yōu)值要好。

　　3.3 CPSODE搜索效率分析

　　圖2和圖3 分別說明了g01、g04這兩個(gè)函數(shù)收斂到目標(biāo)函數(shù)最優(yōu)值的迭代過程，從兩幅圖中可以看出CPSODE比PSO、DE能更快地找到最優(yōu)適應(yīng)值。由于混合了DE算法，不僅找到全局最優(yōu)值而且加快了收斂速度。因此，證實(shí)了本文所提出的算法具有良好的全局搜索能力。

　　本文提出了一種新的算法，并命名為CPSODE算法，該算法通過嵌入DE算法提高了單一PSO算法的性能。算法通過局部最優(yōu)值pbest和全局最優(yōu)值gbest引導(dǎo)粒子最終收斂到全局最優(yōu)位置，并在可行規(guī)則的指導(dǎo)下[7]來比較粒子更新的位置和其相對(duì)應(yīng)的歷史最優(yōu)位置，然后優(yōu)勝者更新pbest。在本文的后部分進(jìn)一步的運(yùn)用了CPSODE算法對(duì)5個(gè)典型的約束測(cè)試函數(shù)和兩個(gè)典型的約束優(yōu)化工程問題進(jìn)行了實(shí)驗(yàn)仿真，并對(duì)其收斂性和復(fù)雜度進(jìn)行了分析。從比較的研究中可以看出CPSODE展現(xiàn)了其對(duì)約束優(yōu)化問題良好的求解性能。新提出的算法改善了PSO算法的魯棒性。

參考文獻(xiàn)

　　[1] Mohamed A W, Sabry H Z. Constrained optimization based on modified differential evolution algorithm[J].Information Science,2012（194）:171-208.

　　[2] Daneshyari, M, Yen, G.G. Constrained multiple-swarm particle swarm optimization within a cultural framenwork[J].Transactions on Systems,Man and Cybernetics,Part A: Systems and Humans,2012,42(2):475-490.

　　[3] Gandomi A H,Yang Xinshe, Alavi A H. Cuckoo search algorithm: a metaheuristic approach to solve structural optimization problems[J].Engineering with Computers,2013,29(1):17-35.

　　[4] Eberhart R, Kennedy J.A new optimizer using particle swarm theory[C].Sixth International Symposium on Micro machine and Human Science, Nagoya,1995:39-43.

　　[5] Clerc M . Kennedy J. The particle swarm- explosion,stability,and convergence in amultidimensional complex space[J]. IEEE Transactions on Evolutionary Computation ,2002,6(1) :58-73.

　　[6] Rainer S, Kenneth P.Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J].Journal of global optimization ,1997,11(4) :341-359.

　　[7] Kalyanmoy D.An efficient constraint handling method for genetic algorithms[J].Computer Methods in Applied Mechanics and Engineering ,2000,186(2-4): 311-338.

　　[8] Zielinski K, Laur R. Constrained single-objective optimization using differential evolution [C].IEEE Congress on Evolutionary Computation,Vancouver,BC:IEEE, 2006:223-230.

　　[9] Kukkonen S, Lampinen J. Constrained real-parameter optimization with generalized differential evolution [C].IEEE Congress on Evolutionary Computation, Vancouver, BC:IEEE,2006:207-214.

　　[10] Amirjanov A.The development of a changing range genetic algorithm[J]. Computer Methods in Applied Mechanics and Engineering ,2006,195(19-22):2495-2508.

　　[11] Tessema B,Yen G.G A self-adaptive penalty function based algorithm for constrained optimization[C]. IEEE Congress on Evolutionary Computation,Vancouver, BC:IEEE,2006:246-253.

　　[12] Huang Fuzhuo, Wang Ling, He Qie.An efficient co-evolutionary differential evolution for constrained optimization[J]. Applied Mathematics and Computation, 2007,186(1):340-356.

　　[13] Becerra R L,Carlos A. Coello Coello.Cultured differential evolution for constrained optimization[J].Computer Methods in Applied Mechanics and Engineering, 2006,195(33-36): 4303-4322.

　　[14] Akay B, Karaboga D.Artificial bee colony algorithm for large-scale problems and engineering design optimization[J].Journal of Intelligent Manufacturing, 2012,23(4): 1001-1014.

　　[15] Eskandar H,Sadollah A,Bahreininejad A,et al.Water cycle algorithm-A novel metaheuristic optimization method for solving constrained engineering optimization problems[J].Computer and Structures.,2012（110-111）:151-166.

　　[16] He Qie, Wang Ling.An effective co-evolutionary particle swarm optimization for constrained engineering design problems[J].Engineering Applications of Artificial Intelligence,2007,20(1):89-99.

　　[17] Coello C C, Becerra RL. Efficient evolutionary optimization through the use of a culture algorithm[J]. Engineering Optimizaiton,2004,36(2): 219-236.