摘 要： 提出了一個全新的混合算法并命名為微粒群差分算法，該算法在標準微粒群算法的基礎上結合了差分進化算法用于求解約束的數值和工程優化問題。傳統的標準微粒群算法由于其種群單一性容易陷入局部最優值，針對這一缺點利用差分進化算法中的變異、交叉、選擇3個算子來更新每次迭代每個粒子新生產的位置以使粒子跳出局部優值。融合了標準微粒群算法和差分進化算法優點的混合算法加速了粒子的收斂速度。為了避免懲罰因子的選擇對實驗結果的影響，采取了可行規則法來處理約束優化問題。最后將微粒群差分算法用于5個基準函數和兩個工程問題，并與其他算法作了比較，試驗結果表明，微粒群差分算法算法具有很好的精準性、魯棒性和有效性。
關鍵詞： 混合算法；約束優化問題；微粒群算法；差分進化；可行規則
進化算法由于其通用性、可靠性、穩定性、簡單性、所需要的信息少等一系列的優點，被廣泛地用來解決并且成功地解決了很多約束優化問題。因此，提出了很多基于進化算法的約束處理方法[1-3]。由Kennedy和Eberhart [4] 提出的標準微粒群算法(PSO)便是其中一種應用廣泛的仿生算法，它模擬鳥類群體覓食行為來尋求最優解，是一種基于群體智能的隨機尋優算法，依賴于個體之間和種群之間的信息共享交換。然而PSO算法由于其種群的單一性容易導致早熟現象，使得優化問題陷入局部最優解。利用其他算法的全局搜索能力來改善PSO算法的缺點，這一混合算法的思想受到很多人的認同，本文正是在此基礎上融合了差分進化算法(DE)的進化策略，提出了一種新的PSO、DE混合算法。算法的前半部分同粒子群算法，只是在粒子進行速度、位置更新后，借鑒DE算法的變異、交叉、選擇算子以增強粒子群的多樣性。
1 背景知識介紹
1.1 PSO算法
如上所述，PSO是受鳥類覓食行為啟發而來的隨機全局優化算法。基本PSO的速度和位置更新方程如下：
其中，
為第i個粒子在第t次迭代時的自身歷史最優位置，gbestt是第t次迭代時的種群最優位置。
是慣性權重，c1，c2是常量，r1，r2是服從U(0,1)的兩個相互獨立的隨機數。然而這個基本的PSO算法，速度是受到限制的。Clerc和Kennedy[5]引入了收縮因子
修改了標準的微粒群模型，速度更新公式變為：
1.2 差分進化算法（DE）
差分進化算法是由Storn和Price[6]于1995年提出的解決全局優化問題的隨機進化算法。算法通過變異、交叉、選擇3種操作來領導種群找到最優解。DE算法的主要流程如下：
變異操作：本文中采用的是rand/1變異策略即vi=xr1+F×(xr2-xr3)，{xr1, xr2, xr3}， 是在父代種群中隨機選擇的3個不同個體，并且
。F是一個介于[0,2]間的實型常量因子，稱為放縮因子。
交叉操作：交叉操作的目的是通過變異個體Vi=(vi,1,vi,2,…,viD)和目標個體Xi=(xi,1,xi,2,…,xiD)各維分量的隨機重組以提高種群個體的多樣性。算法通過下面的公式產生交叉向量Ui=(ui,1,ui,2,…,uiD)：
其中，rand是[0,1]間的隨機數；CR是范圍在[0,1]間的常數稱為交叉變量。
選擇操作：在貪婪準則的指導下，交叉向量Ui與目標個體Vi競爭。假設待求問題為minf(x),則選擇操作可由下式確定：
1.3 可行規則
本文對于約束的處理采用的是可行規則法，可行規則[7]包含3個方面的內容。
⑴任意可行解總是優于不可行解；
⑵兩個不可行解之間，適應值好的要優于適應值差的；
⑶兩個不可行解之間，約束沖突值小的要優于約束沖突值大的。
總而言之，可行規則法就是找一個離可行域最近的解，即使這個解不在可行域內。
2 微粒群差分算法(CPSODE)
2.1 CPSODE算法的原理
如上所述，基本PSO算法盡管操作簡單但并不是完美的。在本文中，在PSO的基本框架中加入了DE進化策略。基本PSO算法中的粒子在每次迭代中通過學習自身的歷史最優位置和全局最優位置來更新自己的速度和位置,從而慢慢靠近優化問題的最優解。換句話說，PSO算法以全局最優位置為中心，吸引所有其他粒子靠近，但是如果最優位置粒子得不到更新，將出現早熟現象。這就是PSO算法陷入局部優值最本質的原因。眾所周知，DE算法有著高效的全局搜索能力，其進化策略不僅參數少而且收斂速度快。如果考慮在PSO的位置更新后，對位置矢量進行DE的變異、交叉、選擇操作，在這里變異選取了rand/1策略，這樣位置矢量就得到更新，使得粒子的運動軌跡偏離既定的軌道，從而全局最優位置得到更新，增強了種群多樣性。對DE進化策略的采納不但加強了算法的搜索能力使算法能夠更快的收斂到最優值，而且使算法跳出局部最優值的概率很大，可以有效地避免早熟早收斂。
2.2 CPSODE算法的流程
為了處理約束，首先在搜索空間隨機初始化種群規模為M的粒子群的位置和速度，并計算每個粒子的適應值和約束沖突值，令每個粒子的歷史最優位置(記作pbest)為初始化位置，適應值最優的歷史最優位置為種群最優位置(記作gbest)；其次根據式⑵、式⑶更新每個粒子的位置和速度，接著對更新的位置進行DE算法的變異、交叉、選擇操作，并重新計算各個粒子的適應值和約束沖突值；然后，在可行規則法的指導下，每個粒子更新pbest,并與gbest的適應值進行比較，若較好，則更新gbest，否則保持gbest原始位置。最后循環條件判斷，若不滿足算法會一次次迭代，直到滿足終止條件。程序的結構流圖如圖1所示。
本文對于兩處位置更新也做了細節的處理。搜索在搜索范圍內才是有效的，因此CPSODE算法為了避免對速度的限制，使用了帶收縮因子的速度更新公式即式（3），這樣就保證粒子每次迭代的速度都不會致使粒子偏離搜索范圍。其次，每次迭代新生產的位置若超出了邊界，則超出邊界的變量將用如下的法則處理[8]：
對每次迭代中DE交叉操作產生的交叉個體Uit，如果交叉個體Uit中任意一維向量Uti,j超出搜索空間，那么將會根據參考文獻[9]處理：
2.3 CPSODE算法時間復雜度分析
針對約束優化問題，設n為種群的粒子數，d為目標函數的維數，T為最大迭代次數。根據圖1所示的CPSODE算法程序結構流程來分析其復雜度。分析結果如表1所示。
由上表可以看出，CPSODE算法的復雜度是O(T×n)數量級，n表示任意一個數。
3 實驗仿真與分析
為了驗證CPSODE算法的有效性，證明其相對于其他算法的優點，這一部分用了5 個典型約束測試函數和兩個實際的工程問題來驗證本文所提出的混合算法，這些測試函數包括非線性和二次函數。
3.1 典型約束測試函數優化
對每個測試函數獨立運行100次，CPSODE算法參數設置如下：粒子數N=200，F和CR分別為0.4、0.9，g01,g04,g11最大迭代次數設置為500，g04和g08分別設置為300和250。收縮因子missing image file，對函數g11取 ε值為0.000 01。加速常量c1=c2=2.05。表2總結了在以上參數設置下約束測試函數的結果，給出了最好值，平均值，最差值和標準方差。可以看到CPSODE算法均能找到測試函數的全局最優值，而且函數g06、g08能夠保持收斂到全局最優值。每個測試函數獨立運行100次的標準方差也比較小。
CPSODE算法同時也跟CRGA、SAPF、CDE、CLUDE和CPSO算法作了比較。結果如表3、表4、表5所示，NA表示不可求。從表格中可以看出，CPSODE算法要優于CRGA、SAPF、CDE算法，且可與性能很好的CLUDE和ABC算法相比較。就CLUDE算法而言，本文所提出的算法對g11尋找到更好的最好值、平均值和最差值；針對g01函數的平均值和最差值，CPSODE算法結果比其結果要好；對剩下的函數CPSODE、CLUDE算法都可以找到相同的最好值，對g04、g06、g08這3個函數的平均值也相同，最差值方面兩種算法對g06、g08的最差值相同，只是對g04函數的最差值，CPSODE要略遜色一些。對于CPSO算法，CPSODE算法對g11函數求得的最好值、平均值、最差值都要優于CPSO算法。總而言之，CPSODE算法具有較好的尋優能力。
3.2 工程問題優化
為了研究CPSODE算法解決現實生活中工程問題的性能，用兩個典型的實際工程問題對算法做了測試，分別是焊接條和伸縮繩問題。每個問題獨立運行100次，粒子數N=200，F和CR分別為0.4、0.9，最大迭代次數設置為500。
從表6可以看出，CPSODE找到的最優解比參考文獻[15]、參考文獻[16]結果要好。而且CPSODE算法的平均值比其他算法都好，不僅如此，最差值和方差都是最優的。甚至CPSODE的最差值也要比參考文獻[16]最優值好。表明CPSODE對于實際工程問題的求解有其明顯的優勢。
從表7中，可以得出CPSODE算法找到的最優值比參考文獻[16]、參考文獻[17]結果好，不僅如此，本文所提出算法對伸縮繩問題求解的平均值和方差均優于其他算法，最差值也同樣優于除了參考文獻[18]之外的其他算法，甚至要比參考文獻[17]最優值要好。
3.3 CPSODE搜索效率分析
圖2和圖3 分別說明了g01、g04這兩個函數收斂到目標函數最優值的迭代過程，從兩幅圖中可以看出CPSODE比PSO、DE能更快地找到最優適應值。由于混合了DE算法，不僅找到全局最優值而且加快了收斂速度。因此，證實了本文所提出的算法具有良好的全局搜索能力。
本文提出了一種新的算法，并命名為CPSODE算法，該算法通過嵌入DE算法提高了單一PSO算法的性能。算法通過局部最優值pbest和全局最優值gbest引導粒子最終收斂到全局最優位置，并在可行規則的指導下[7]來比較粒子更新的位置和其相對應的歷史最優位置，然后優勝者更新pbest。在本文的后部分進一步的運用了CPSODE算法對5個典型的約束測試函數和兩個典型的約束優化工程問題進行了實驗仿真，并對其收斂性和復雜度進行了分析。從比較的研究中可以看出CPSODE展現了其對約束優化問題良好的求解性能。新提出的算法改善了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.