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

吳華偉，陳特放

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

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

吳華偉，陳特放

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

1 引言

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

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

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

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

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

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

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

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

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

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

粒子X(jué)i在k+1時(shí)刻的位置為：

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

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

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

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

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

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

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

3.1 算法思想

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

3.2 種群初始化

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

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

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

3.3 模式搜索法

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

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

（2）對(duì)每個(gè)分量依次進(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）若δ≤ε，則迭代停止，得點(diǎn)x(k)；否則δ=ωδ，y(1)=x(k)，x(k+1)=x(k)，k=k+1，j=1，轉(zhuǎn)步驟（2）。

3.4 多樣性變異算子

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

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

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

3.5 約束處理技術(shù)

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

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

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

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

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

3.6 算法步驟

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

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

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

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

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

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

4 數(shù)值實(shí)驗(yàn)

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

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

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

表1 六種算法對(duì)4個(gè)問(wèn)題的實(shí)驗(yàn)結(jié)果比較

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

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

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

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

焊接梁優(yōu)化設(shè)計(jì)問(wèn)題[13]如圖3所示。在圖3中，設(shè)計(jì)變量分別為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算法對(duì)焊接梁優(yōu)化設(shè)計(jì)問(wèn)題進(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 幾種算法對(duì)焊接梁優(yōu)化設(shè)計(jì)問(wèn)題的結(jié)果比較

6 結(jié)論

提出一種動(dòng)態(tài)分級(jí)中心引力優(yōu)化算法用于求解約束優(yōu)化問(wèn)題。針對(duì)中心引力優(yōu)化算法存在的問(wèn)題，該算法利用佳點(diǎn)集方法構(gòu)造初始種群以保證粒子的多樣性，將種群分為兩個(gè)子種群，分別進(jìn)行局部搜索和全局搜索，并動(dòng)態(tài)調(diào)整子種群粒子的數(shù)目。幾個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)和工程應(yīng)用的實(shí)驗(yàn)結(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]錢(qián)偉懿，張桐桐.自適應(yīng)中心引力優(yōu)化算法[J].計(jì)算機(jī)科學(xué)，2012，39（6）：207-209.

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

[7]謝麗萍，曾建潮.受擬態(tài)物理學(xué)啟發(fā)的全局優(yōu)化算法[J].系統(tǒng)工程理論與實(shí)踐，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]龍文，梁昔明，徐松金，等.聚類佳點(diǎn)集交叉的約束優(yōu)化混合進(jìn)化算法[J].計(jì)算機(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ù)處理約束條件，提出一種動(dòng)態(tài)分級(jí)中心引力優(yōu)化算法用于求解約束優(yōu)化問(wèn)題。該算法利用佳點(diǎn)集初始化個(gè)體以保證種群的多樣性。在每次迭代過(guò)程中將種群分為兩個(gè)子種群，分別用于全局搜索和局部搜索，根據(jù)搜索階段動(dòng)態(tài)調(diào)整子種群個(gè)體數(shù)目。對(duì)幾個(gè)標(biāo)準(zhǔn)的測(cè)試問(wèn)題和工程優(yōu)化問(wèn)題進(jìn)行數(shù)值實(shí)驗(yàn)，結(jié)果表明該算法能處理不同的約束優(yōu)化問(wèn)題。

約束優(yōu)化問(wèn)題；中心引力優(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.

國(guó)家863重點(diǎn)項(xiàng)目（No.2009AA034302）。

吳華偉（1979—），男，博士研究生，主要研究領(lǐng)域?yàn)檫M(jìn)化計(jì)算、智能控制等；陳特放（1957—），男，教授，博士生導(dǎo)師，主要研究領(lǐng)域?yàn)闄C(jī)車車輛故障診斷、智能交通系統(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