動態分級中心引力約束優化算法及工程應用

吳華偉，陳特放

中南大學 信息科學與工程學院，長沙 410083

動態分級中心引力約束優化算法及工程應用

吳華偉，陳特放

中南大學 信息科學與工程學院，長沙 410083

1 引言

約束優化問題是科學研究與應用領域經常會遇到的一類數學規劃問題，一個非線性約束優化問題通常可描述為：

其中f(x)為目標函數，xi(i=1，2，…，n)為決策變量，gj(x)為約束條件，li和ui是變量xi取值的上下界。

智能優化算法具有不依賴于問題的梯度信息，利用種群對問題解空間進行多點并行搜索，能以較大概率收斂到問題的全局最優解等特點。結合合適的約束處理技術，目前智能優化算法已被廣泛地應用于求解約束優化問題[1-2]。

中心引力優化（Central Force Optimization，CFO）算法是Formato最近提出的一種基于重力場粒子運動規律的智能優化算法[3]。CFO算法雖然具有原理簡單，容易實現且具有較強的全局尋優能力。與其他基于種群迭代的智能優化算法一樣，CFO算法同樣具有后期收斂速度慢、易陷入局部最優的缺點。因此，研究者提出了許多的改進CFO算法。文獻[4]提出了一種基于決策空間和決策變量自適應變化的中心引力優化算法用于求解大規模無約束優化問題。為了避免算法陷入局部最優。文獻[5]將粒子的運動時間定義在適應度函數里，從而提出了一種自適應中心引力優化算法，該算法可以平衡其局部和全局搜索能力。文獻[6]引入差分進化算子對當前粒子位置的分量進行變異，提出了一種基于差分進化算子變異的中心引力優化算法。

鑒于目前鮮有文獻報道利用中心引力優化算法求解約束優化問題，本文利用非固定多段罰函數處理約束條件，設計出一種動態分級中心引力優化算法用于求解約束優化問題。幾個典型的約束優化測試問題和工程優化問題的實驗結果表明，該方法具有較好的優化性能。

2 中心引力優化算法

在描述CFO算法之前，先介紹一下與其相關的物理運動學知識。根據牛頓萬有引力定律，任何兩個物體之間的引力為：

式中，G為引力常量，m1和m2分別是兩個物體的質量，r是兩個物體之間的距離。物體m1作用于物體m2的加速度為：

式中，μ是物體m1和物體m2連線的單位向量，方向指向物體m2。假設在k時刻，物體的位置和速度分別為Xk和速度Vk，則在k+Dk時刻，物體的位置為：

CFO算法是由Formato在2007年提出的一種基于物理運動學原理的群智能優化算法。它將優化問題解空間中的候選解當做帶有質量的粒子，將目標函數f(X)定義粒子的適應度函數。假設所求問題的搜索空間為d維，在k時刻解空間里存在N個粒子2，…，N，在k時刻粒子Xi相對于粒子Xj的加速度為：

粒子Xi在k+1時刻的位置為：

其中，是粒子Xi在k時刻的速度，通常取為0，Dk為時刻常數。

CFO算法的實現步驟如下：

步驟1在搜索空間中隨機初始化粒子的加速度和位置。

步驟2計算每個粒子的適應度值。

步驟3判斷算法是否滿足終止條件，若滿足，則算法結束，輸出最優解；否則執行步驟4。

步驟4根據式（6）和式（7）更新每個粒子的加速度和位置，返回步驟2。

3 動態分級約束優化CFO算法

3.1 算法思想

針對CFO算法具有種群多樣性差、對種群的初始分布要求較高、全局搜索能力不強等缺點[7]，本文提出一種動態分級的約束優化CFO算法，其思路主要為：首先利用佳點集方法構建初始種群，以保證粒子能均勻分布在搜索空間中。將種群分為2個子種群，其粒子數目分別為N1和N2，滿足N1+N2=N，N為種群規模。在每次迭代后，將適應度值較優的N1個粒子作為第1個子種群，引入模式搜索方法[8]用于進行局部搜索；將適應度值較差的N2個粒子作為第2個子種群，引入多樣性變異算子[9]以增強算法的全局搜索能力。在迭代過程中，進化的初始階段應偏重于全局搜索，因而此階段的N2值應取較大些，以增強算法的全局搜索能力；進化的末期，主要考慮局部精確搜索，這時N1的取值應大些，以提高算法的局部搜索能力。因此，在每次迭代過程中兩個子種群的粒子數目是自適應動態調整的。

3.2 種群初始化

由于CFO算法是一種基于種群迭代的群智能搜索方法，因此初始種群的優劣對算法的搜索性能具有較大的影響。若群體中粒子在搜索空間中分布不均勻，則可能導致算法的搜索效率及搜索能力受到一定的限制。佳點集方法是一種均勻取點的實驗方法，其偏差僅為O(n-1+ε)，其中n為取點個數，ε為無窮小量。具體取點方法詳見文獻[10]。本文采用佳點集方法來產生初始種群。圖1是采用佳點集方法產生的規模為80的初始種群分布，其中，變量的維數為2，變量的取值范圍為[-20，20]。

從圖1可以清楚地看出，與隨機方法相比，佳點集方法產生的初始粒子分布均勻，具有較好的多樣性。

圖1 佳點集方法產生的80個初始種群分布

3.3 模式搜索法

模式搜索法是由Hooke等[8]提出的一種有效的確定性直接搜索方法，具有較強的局部搜索能力，其具體步驟如下：

（1）給定初始點x(1)∈Rn，n個軸向坐標方向為e1，e2，…，en，初始步長δ，加速因子μ≥1，縮減率ω∈[0，1]，允許誤差為ε＞0，令y(1)=x(1)，k=1，j=1。

（2）對每個分量依次進行軸向搜索(j=1，2，…，n)，若f(y(j)+δej)優于f(y(1))，y(j+1)=y(j)+δej；若f(y(j)-δej)優于f(y(1))，y(j+1)=y(j)-δej；否則y(j+1)=y(j)。

（3）若f(y(n+1))優于f(x(k))，置x(k+1)=y(n+1)，令y(1)=x(k+1)+μ(x(k+1)-x(k))，k=k+1，j=1，轉步驟（2），否則進行步驟（4）。

（4）若δ≤ε，則迭代停止，得點x(k)；否則δ=ωδ，y(1)=x(k)，x(k+1)=x(k)，k=k+1，j=1，轉步驟（2）。

3.4 多樣性變異算子

為了增加種群多樣性，本文對第1個子種群進行多樣性變異，具體操作如下[9]：

假設群體中粒子Xi表示為Xi=(xi1，xi2，…，xid)，以概率1/n隨機從粒子Xi中選擇一個元xih(h=1，2，…，d)，然后在[li，ui]中隨機產生一個實數替代粒子Xi中選擇一個元xih，從而產生新的個體X′i=(x′i1，x′i2，…，x′id)。多樣性變異算子為：

式中，β∈U[0，1]。

3.5 約束處理技術

如何處理好約束條件是利用進化算法求解約束優化問題的關鍵。

對于如式（1）所示的約束優化問題，通常所構造的廣義目標函數具有如下形式：

其中f(x)為原目標函數，δ(t)H(x)稱為懲罰項，δ(t)表示懲罰力度，H(x)為懲罰因子。

Parsopoulos等[11]提出了一種基于非固定多段映射罰函數法的約束優化粒子群算法。本文也采用非固定多段映射罰函數法處理約束條件，在文獻[11]的基礎上，并對其進行適當修正。設

其中，式（11）表示對約束的違反程度，式（12）表示懲罰函數的強度，式（13）為分段映射函數，式（14）為隨迭代次數變化的懲罰力度。這樣可根據約束違反程度的大小，自適應選取不同的懲罰力度，將約束優化問題轉化為一系列無約束優化問題來處理，可以避免采用精確罰函數法中懲罰因子難以選取的問題[11]。

3.6 算法步驟

步驟1設置算法參數。初始化種群規模，在每個變量的定義域內，利用佳點集方法產生初始種群。

步驟2按式（11）～（13）分別計算各粒子每個約束條件的懲罰因子。

步驟3按式（10）分別計算每個粒子的所有約束條件的懲罰因子H(x)。

步驟4根據式（9）計算出每個粒子的適應度值，求出最優適應度值及最優粒子。

步驟5判斷懲罰因子H(x)是否達到精度要求或是否達到最大迭代次數，若是則退出，否則執行步驟6。

步驟6將種群分為兩個子種群，第1子種群引入模式搜索，第2子種群嵌入多樣性變異算子，按式（6）和式（7）更新粒子的加速度和位置，返回步驟2。

4 數值實驗

為了評估本文算法的性能，從文獻[1]中選取4個標準測試問題，即g01、g02、g06和g11進行測試，各問題的具體表達式詳見文獻[1]。將本文算法記為DHCFO，并與SR算法[1]、SMES算法[2]、HEA-ACΤ算法[9]、COHEA算法[10]和CPSO算法[12]得到的結果進行了比較。實驗中，DHCFO算法的參數設置為：種群規模N=100，G=2，α=0.3，β=0.5，Dt=1，模式搜索法中的δ=2.0，μ=1.0，ω=0.1，ε=0.1。問題g01、g06和g11的迭代次數為1 000，g02的迭代次數為3 000。其他算法的參數設置分別見其各自的文獻。每個測試問題在相同條件下獨立運行20次實驗，記錄其最好結果、平均結果、最差結果和標準差。表1給出了在上述參數設置下，五種算法對4個標準測試問題的尋優結果比較。

從表1中的結果可知，除g02外，DHCFO算法對其他3個問題20次實驗中一致地找到全局最優解。與SR算法相比，DHCFO算法在問題g02和g06的平均結果和最差結果方面明顯優于SR算法，最優結果和標準差相當。對于問題g01和g11，DHCFO算法取得了與SR算法相似的結果。與SMES算法相比，DHCFO算法在問題g01、g06和g11上的最優結果、平均結果和最差結果方面均占優，對于g02，DHCFO算法的平均值、最差值要優，SMES得到了較好的最優值。與HEA-ACΤ算法相比，DHCFO算法在4個問題上得到了相似的結果。與COHEA算法相比，DHCFO算法在問題g01、g06和g11上得到了相似的結果，在問題g02上得到的結果要優。與CPSO算法相比，DHCFO算法在問題g02上的最優結果、平均結果和最差結果方面稍差，對于問題g01、g06和g11，兩種算法取得了相似的結果。

圖2（a）～（d）給出了4個問題的尋優曲線。從圖2（a）～（d）中的收斂曲線可知，DHCFO算法能快速地收斂于問題的全局最優解或近似全局最優解。從以上比較研究可以看出，DHCFO算法表現出良好的尋優性能。

表1 六種算法對4個問題的實驗結果比較

圖2 測試函數g01、g02、g06和g11的尋優曲線

5 DHCFO在焊接梁優化中的應用

為了進一步驗證DHCFO算法的有效性，將其應用到焊接梁優化設計問題中。

圖3 焊接梁優化設計問題

焊接梁優化設計問題[13]如圖3所示。在圖3中，設計變量分別為h（記為x1），l（記為x2），t（記為x3）和b（記為x4）。約束條件分別為剪應力約束g1(x)；梁上彎曲應力約束g2(x)；邊界約束為g3(x)，g4(x)和g5(x)；梁的尾端誤差約束g6(x)；g7(x)表示載荷P的約束。

利用DHCFO算法對焊接梁優化設計問題進行求解，并與文獻[9]中的HEA-ACΤ算法、SC算法、FSA算法、文獻[13]中的GA算法、NMHA算法、NMDE算法、文獻[14]中的DSS-MDE算法和文獻[15]中的IPSO算法進行比較，結果如表2所示。從表2中的結果可知，DHCFO算法要優于文獻中其他方法。

表2 幾種算法對焊接梁優化設計問題的結果比較

6 結論

提出一種動態分級中心引力優化算法用于求解約束優化問題。針對中心引力優化算法存在的問題，該算法利用佳點集方法構造初始種群以保證粒子的多樣性，將種群分為兩個子種群，分別進行局部搜索和全局搜索，并動態調整子種群粒子的數目。幾個標準測試函數和工程應用的實驗結果表明該算法具有較好的尋優效果。

[1]Runarsson Τ P，Yao X.Stochastic ranking for constrained evolutionary optimization[J].IEEE Τransactions on Evolutionary Computation，2000，4（3）：561-579.

[2]Mezura-Montes E，Coello C A C.A simple multi-membered evolution strategy to solve constrained optimization problems[J].IEEE Τransactions on Evolutionary Computation，2005，9（1）：1-17.

[3]Formato R A.Central force optimization：a new metaheuristic with applications in applied electromagnetics[J].Progress in Electromagnetics Research，2007，77：425-491.

[4]Formato R A.Central force optimization with variable initial probes and adaptive decision space[J].Applied Mathematics and Computation，2011，217（21）：8866-8872.

[5]錢偉懿，張桐桐.自適應中心引力優化算法[J].計算機科學，2012，39（6）：207-209.

[6]張桐桐，盧靜，錢偉懿.基于差分進化算子變異的中心引力優化算法[J].渤海大學學報：自然科學版，2012，33（3）：197-203.

[7]謝麗萍，曾建潮.受擬態物理學啟發的全局優化算法[J].系統工程理論與實踐，2010，30（12）：2276-2282.

[8]Hooke R，Jeeves Τ A.Direct search solution of numerical and statistical problems[J].Journal of the Association for Computing Machinery，1961，8（2）：212-229.

[9]Wang Y，Cai Z X，Zhou Y R，et al.Constrained optimization based on hybrid evolutionary algorithm and adaptive constraint-handling technique[J].Structuraland Multidisciplinary Optimization，2009，37（1）：395-413.

[10]龍文，梁昔明，徐松金，等.聚類佳點集交叉的約束優化混合進化算法[J].計算機研究與發展，2012，49（8）：1753-1761.

[11]Parsopoulos K E，Vrahatis M N.Particle swarm optimization method for constrained optimization problems[C]//Proc of the Euro-International Symposium on Computational Intelligence，2002：214-220.

[12]Daneshyari M，Yen G G.Constrained multiple-swarm particle swarm optimization within a cultural framework[J].IEEE Τransactions on Systems，Man，and Cybernetics，2012，42（2）：475-490.

[13]Zou D X，Liu H K，Gao L Q，et al.A novel modified differential evolution algorithm for constrained optimization problems[J].Computers and Mathematics with Applications，2011，61（6）：1608-1623.

[14]Zhang M，Luo W J，Wang X F.Differential evolution with dynamic stochastic selection for constrained optimization[J]. Information Sciences，2008，178（15）：3043-3074.

[15]He S，Prempain E，Wu Q H.An improved particle swarm optimizer for mechanical design optimization problems[J]. Engineering Optimization，2004，36（5）：585-605.

WU Huawei,CHEN Τefang

School of Information Science and Engineering,Central South University,Changsha 410083,China

Using non-stationary multi-stage penalty function to deal with the constrained conditions,a modified central force optimization algorithm is proposed for solving constrained optimization problems.Good point set method is used in the initialization of the evolutionary population to ensure its diversity.At each generation,the population is divided into two subpopulations based on the fitness values of particles,which is employed for global and local search respectively.Τhe number of the subpopulation is dynamically adapted according to the search phases.Τhe proposed algorithm has been tested on 4 benchmark problems and engineering optimization problems,and the results show that it can deal with different constrained optimization problems.

constrained optimization problems;central force optimization algorithm;non-stationary multi-stage penalty function; engineering optimization

結合非固定多段罰函數處理約束條件，提出一種動態分級中心引力優化算法用于求解約束優化問題。該算法利用佳點集初始化個體以保證種群的多樣性。在每次迭代過程中將種群分為兩個子種群，分別用于全局搜索和局部搜索，根據搜索階段動態調整子種群個體數目。對幾個標準的測試問題和工程優化問題進行數值實驗，結果表明該算法能處理不同的約束優化問題。

約束優化問題；中心引力優化算法；非固定多段罰函數；工程優化

A

ΤP301.6

10.3778/j.issn.1002-8331.1212-0190

WU Huawei,CHEN Tefang.Central force constrained optimization algorithm with dynamic hierarchical and engineering application.Computer Engineering and Applications,2013,49（15）：14-18.

國家863重點項目（No.2009AA034302）。

吳華偉（1979—），男，博士研究生，主要研究領域為進化計算、智能控制等；陳特放（1957—），男，教授，博士生導師，主要研究領域為機車車輛故障診斷、智能交通系統等。

2012-12-17

2013-05-02

1002-8331（2013）15-0014-05

CNKI出版日期：2013-05-15 http://www.cnki.net/kcms/detail/11.2127.ΤP.20130515.1015.007.html