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

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

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

1 背景知識介紹

　　1.1 PSO算法

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

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

　　1.2 差分進化算法（DE）

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

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

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

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

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

　　1.3 可行規(guī)則

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

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

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

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

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

2 微粒群差分算法(CPSODE)

　　2.1 CPSODE算法的原理

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

　　2.2 CPSODE算法的流程

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

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

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

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

　　針對約束優(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ù)量級，n表示任意一個數(shù)。

3 實驗仿真與分析

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

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

　　對每個測試函數(shù)獨立運行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，對函數(shù)g11取 ε值為0.000 01。加速常量c1=c2=2.05。表2總結(jié)了在以上參數(shù)設(shè)置下約束測試函數(shù)的結(jié)果，給出了最好值，平均值，最差值和標(biāo)準(zhǔn)方差?？梢钥吹紺PSODE算法均能找到測試函數(shù)的全局最優(yōu)值，而且函數(shù)g06、g08能夠保持收斂到全局最優(yōu)值。每個測試函數(shù)獨立運行100次的標(biāo)準(zhǔn)方差也比較小。

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

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

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

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

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

　　3.3 CPSODE搜索效率分析

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

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

參考文獻

　　[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.