吳華偉，陳特放

中南大學(xué) 信息科學(xué)與工程學(xué)院，長沙 410083

動態(tài)分級中心引力約束優(yōu)化算法及工程應(yīng)用

吳華偉，陳特放

中南大學(xué) 信息科學(xué)與工程學(xué)院，長沙 410083

1 引言

約束優(yōu)化問題是科學(xué)研究與應(yīng)用領(lǐng)域經(jīng)常會遇到的一類數(shù)學(xué)規(guī)劃問題，一個非線性約束優(yōu)化問題通?？擅枋鰹椋?/p>

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

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

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

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

2 中心引力優(yōu)化算法

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

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

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

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

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

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

CFO算法的實現(xiàn)步驟如下：

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

步驟2計算每個粒子的適應(yīng)度值。

步驟3判斷算法是否滿足終止條件，若滿足，則算法結(jié)束，輸出最優(yōu)解；否則執(zhí)行步驟4。

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

3 動態(tài)分級約束優(yōu)化CFO算法

3.1 算法思想

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

3.2 種群初始化

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

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

圖1 佳點集方法產(chǎn)生的80個初始種群分布

3.3 模式搜索法

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

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

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

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

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

3.4 多樣性變異算子

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

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

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

3.5 約束處理技術(shù)

如何處理好約束條件是利用進(jìn)化算法求解約束優(yōu)化問題的關(guān)鍵。

對于如式（1）所示的約束優(yōu)化問題，通常所構(gòu)造的廣義目標(biāo)函數(shù)具有如下形式：

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

Parsopoulos等[11]提出了一種基于非固定多段映射罰函數(shù)法的約束優(yōu)化粒子群算法。本文也采用非固定多段映射罰函數(shù)法處理約束條件，在文獻(xiàn)[11]的基礎(chǔ)上，并對其進(jìn)行適當(dāng)修正。設(shè)

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

3.6 算法步驟

步驟1設(shè)置算法參數(shù)。初始化種群規(guī)模，在每個變量的定義域內(nèi)，利用佳點集方法產(chǎn)生初始種群。

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

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

步驟4根據(jù)式（9）計算出每個粒子的適應(yīng)度值，求出最優(yōu)適應(yīng)度值及最優(yōu)粒子。

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

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

4 數(shù)值實驗

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

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

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

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

圖2 測試函數(shù)g01、g02、g06和g11的尋優(yōu)曲線

5 DHCFO在焊接梁優(yōu)化中的應(yīng)用

為了進(jìn)一步驗證DHCFO算法的有效性，將其應(yīng)用到焊接梁優(yōu)化設(shè)計問題中。

圖3 焊接梁優(yōu)化設(shè)計問題

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

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

表2 幾種算法對焊接梁優(yōu)化設(shè)計問題的結(jié)果比較

6 結(jié)論

提出一種動態(tài)分級中心引力優(yōu)化算法用于求解約束優(yōu)化問題。針對中心引力優(yōu)化算法存在的問題，該算法利用佳點集方法構(gòu)造初始種群以保證粒子的多樣性，將種群分為兩個子種群，分別進(jìn)行局部搜索和全局搜索，并動態(tài)調(diào)整子種群粒子的數(shù)目。幾個標(biāo)準(zhǔn)測試函數(shù)和工程應(yīng)用的實驗結(jié)果表明該算法具有較好的尋優(yōu)效果。

[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]錢偉懿，張桐桐.自適應(yīng)中心引力優(yōu)化算法[J].計算機科學(xué)，2012，39（6）：207-209.

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

[7]謝麗萍，曾建潮.受擬態(tài)物理學(xué)啟發(fā)的全局優(yōu)化算法[J].系統(tǒng)工程理論與實踐，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]龍文，梁昔明，徐松金，等.聚類佳點集交叉的約束優(yōu)化混合進(jìn)化算法[J].計算機研究與發(fā)展，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

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

約束優(yōu)化問題；中心引力優(yōu)化算法；非固定多段罰函數(shù)；工程優(yōu)化

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—），男，博士研究生，主要研究領(lǐng)域為進(jìn)化計算、智能控制等；陳特放（1957—），男，教授，博士生導(dǎo)師，主要研究領(lǐng)域為機車車輛故障診斷、智能交通系統(tǒng)等。

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