求解約束優(yōu)化問題的海豚算法

陳建華　陳建榮

摘要：針對廣泛存在于實際工程等領(lǐng)域，但使用傳統(tǒng)方法難于求解的約束優(yōu)化問題，提出了一種求解約束優(yōu)化問題的海豚算法。海豚算法主要通過模仿海豚利用超聲波在大海中追逐和捕食獵物的行為進(jìn)行尋優(yōu)。對三個經(jīng)典工程實例的優(yōu)化結(jié)果表明，該算法具有收斂速度快、求解精度高、穩(wěn)定性好且不易陷入局部極值等優(yōu)點(diǎn)，非常適合解決約束優(yōu)化問題。

關(guān)鍵詞：約束優(yōu)化；海豚算法；群智能；優(yōu)化；算法

中圖分類號：TP18 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）11-0235-05

Dolphin Swarm Optimization Algorithm for Constrained Optimization Problems

CHEN Jian-hua1，CHEN Jian-rong2，3

（1.You Jiang District Social Insurance Bureau， Baise 533000， China；2. Sun Yat-sen University， School of Data and Computer Science， Guangzhou 510275， China； 3. You Jiang Medical University for Nationalities， Baise 533000， China）

Abstract： The constrained optimization problems are widely present in the practical engineering and other fields， and very difficult to solve by using traditional methods. Dolphin swarm optimization algorithm for constrained optimization problems was proposed. Dolphin swarm optimization algorithm is based on mimicking the behavior of dolphins using ultrasound to chase and prey in the ocean. The experimental results of the three typical engineering design problems shows that the algorithm has the advantages of fast convergence， high accuracy， good stability and is not easy to fall into local extremum， so it is very suitable for solving constrained optimization problems.

Key words： constrained optimization； dolphin swarm optimization algorithm （DSOA）； swarm intelligence； optimization； algorithm

約束優(yōu)化問題（constrained optimization problems， COPs）是在科學(xué)、工程和商業(yè)等諸多領(lǐng)域中經(jīng)常出現(xiàn)但又較難求解的一類數(shù)學(xué)規(guī)劃問題，對其進(jìn)行研究具有非常重要的理論和實際意義[1]。海豚算法[2]（dolphin swarm optimization algorithm， DSOA）是2016年由王勇等通過觀察并模擬海豚在海洋中尋找和捕食沙丁魚群的行為特點(diǎn)而提出的一種新型的群智能算法。對于多維函數(shù)的優(yōu)化問題，與粒子群算法（PSO）、人工蜂群算法（ABC）和蝙蝠算法（BA）相比，海豚算法在全局搜索能力、收斂率、求解精度、有效性和魯棒性等方面有明顯優(yōu)勢。

基于海豚算法的優(yōu)秀性能，將該算法用于求解約束優(yōu)化問題。并使用工程實例對算法性能進(jìn)行驗證。

1 海豚算法[2]介紹

1.1海豚的自然特征

海豚是一種非常聰明的海洋生物，它們通常被認(rèn)為是地球上最智能的物種之一。海豚流線型的體態(tài)使得它們非常適合在水中快速游動，因此大多數(shù)海豚擁有高超的游泳技巧和非同尋常的潛水能力。當(dāng)海豚捕食沙丁魚、攻擊鯊魚、逃避天敵、躲避障礙物、避免陷入死胡同時，海豚能夠動態(tài)地改變游泳模式和前進(jìn)方向，并使用例如翻轉(zhuǎn)劃水和旋轉(zhuǎn)劃水等各種各樣的游泳技巧。

海豚是聲學(xué)生物，超聲波是它們的語言。每只海豚頭部有“額隆”，它能夠產(chǎn)生超聲波并接收回聲?！邦~隆”是一種高靈敏度的生物聲吶系統(tǒng)。依靠“額隆”，海豚能夠快速和精確地探測物體的距離、方向、位置和形狀。

海豚平時喜歡群居。特別是當(dāng)它們追逐或捕食一大群沙丁魚或攻擊鯊魚時，多達(dá)數(shù)十只的海豚會生活在一起。

1.2算法的基本假設(shè)

為了模擬海豚攻擊和捕食的行為，海豚算法給出如下基本假設(shè)：1）海豚僅在自己的搜索空間里搜尋、攻擊和捕食；2）在海洋里攻擊或捕食一大群沙丁魚的時候，海豚只使用翻轉(zhuǎn)劃水模式或旋轉(zhuǎn)劃水模式；3）每只海豚僅使用自己的聲吶來產(chǎn)生超聲波、接收回聲、探測物體的狀態(tài)、與伙伴交流；4）整個搜索過程劃分為三個情景：探測目標(biāo)位置（一群沙丁魚）；追逐和接近目標(biāo)；最終捕食或攻擊目標(biāo)；5）海豚根據(jù)需要能夠動態(tài)地改變自身的游泳模式和使用不同的搜索策略。

1.3算法基本規(guī)則及搜索方法

給定閉區(qū)間[a，b]，使用線性變換[φx=x-b+a2]將其映射到區(qū)間[-b-a2，b-a2]。為不失一般性，假設(shè)海豚搜索空間為[S=-a1，a1×-a2，a2×…×-an，an?Rn]，其中[ak>0]，[k=1，…，n]。

對于每一個屬于[S]的區(qū)間[-ak，ak]，首先在復(fù)平面內(nèi)構(gòu)造方域[F=hR+ihI|hR，hI∈-ak，ak]，其中[i]為虛部。那么，點(diǎn)[hR+ihI∈Fk]可以表示為[hR=ρkcosθk]，[hI=ρksinθk]，[ρk=h2R+h2I]，其中[0≤ρk≤ak]，[θk∈0，2π]。

第[j]只海豚的初始速度表示為[VjR1+iVjI1]，其中[VjR1=vjR，1，…，vjR，n]，[VjI1=vjI，1，…，vjI，n]。

1.3.1探測目標(biāo)位置

假設(shè)在開始時，第[j]只海豚探測到有一群沙丁魚位于[ρjk（cosθjk+isinθjk）]。則第[j]只海豚獲得坐標(biāo)如下：

[xjR，k（1）=ρjkcosθjk]，[xjI，k（1）=ρjksinθjk]， and[XjR（1）+iXjI（1）]. （1）

其中，[ρjk]是[[0，ak]]內(nèi)的隨機(jī)數(shù)，[θjk]是區(qū)間[[0，2π]]內(nèi)的隨機(jī)角度，[i]為虛部，[XjR（1）=（xjR，1（1），…，xjR，n（1））]，[XjI（1）=（xjI，1（1），…，xjI，n（1））]， [k=1，…，n]，[j=1，…，M]， [M]為海豚個體的數(shù)量。

1.3.2追逐和接近目標(biāo)

假設(shè)在[t]時刻，第[j]只海豚的位置和移動速度分別為[XjR（t）+iXjI（t）]和[VjR（t）+iVjI（t）]，它找到的最優(yōu)目標(biāo)（一群沙丁魚）位于[PjR（t）+iPjI（t）]，當(dāng)前海豚群體探測到的最優(yōu)目標(biāo)（一群沙丁魚）表示為[GR（t）+iGI（t）]（[GR（t）+iGI（t）]為最優(yōu)目標(biāo)的質(zhì)心），其中[i]為虛部。

則在[t+1]時刻，第[j]只海豚的位置和速度通過如下公式給出：

[VjR（t+1）=w1?VjR（t）+cjR1（t）?（PjR（t）-XjR（t））+cjR2（t）?（GR（t）-XjR（t））+cjR3（t）?（GI（t）-GR（t））] （2）

[VjI（t+1）=w2?VjI（t）+cjI1（t）?（PjI（t）-XjI（t））+cjI2（t）?（GI（t）-XjI（t））+cjI3（t）?（GR（t）-GI（t））] （3）

[XjR（t+1）=XjR（t）+VjR（t+1）] （4）

[XjI（t+1）=XjI（t）+VjI（t+1）] （5）

其中，[XjR（t），XjI（t）]，[GR（t），GI（t）∈Rn]，[βq]是[[0，1]]內(nèi)的[n]維隨機(jī)向量，[w1]和[w2]是慣性權(quán)重，[cjR1（t）]，[cjR2（t）]，[cjR3（t）]，[cjI1（t）]，[cjI2（t）]和[cjI3（t）]是加速控制函數(shù)。[cjR3（t）（GI（t）-GR（t））]和[cjI3（t）（GR（t）-GI（t））]稱為錯誤糾正項。

1.3.3捕食或攻擊目標(biāo)

假設(shè)在[t]時刻，一群海豚已經(jīng)連續(xù)追逐目標(biāo)[ω]步（[ω

[xjR，k（t+1）=rR，l] （6）

[xjI，k（t+1）=rI，l] （7）

其中，[rR，l]是區(qū)間[[gR，l（t）-ε（t），gR，l（t）+ε（t）]]內(nèi)均勻分布的隨機(jī)數(shù)，[rI，l]是區(qū)間[[gI，l（t）-ε（t），gI，l（t）+ε（t）]]內(nèi)均勻分布的隨機(jī)數(shù)，[l]是屬于集合[1，…，n]的隨機(jī)數(shù)，[ε（t）]是滿足[|ε（t）|?1]的遞減正函數(shù)，[t]為時間步長，正整數(shù)[ω]滿足[t≥ω]，[ω

1.3.4搜索模式轉(zhuǎn)換條件

給定海豚個體數(shù)量[M]，優(yōu)化問題（以求最小值為例）的目標(biāo)函數(shù)[fX]，[X=（x1，…，xn）∈S]，[t]時刻第[j]只海豚的位置為[XjR（t）+iXjI（t）]。記

[Yj=12（f（XjR（t））+f（XjI（t）））]，[j=1，…，M] （8）

對[Yj]按升序排序，將[Yj]的順序記為[Oj（t）]。取

[μj（t）=（Oj（t）-1）/M] （9）

稱[μj]為轉(zhuǎn)換因子。容易看出[0≤μj（t）<1]。若[Yj=min{Yl|l=1，…，M}]，則有[Oj（t）=1]。若[Yj=max{Yl|l=1，…，M}]，則[Ol（t）≤Oj（t）=M′≤M]，[l=1，…，M]。

搜索模式的轉(zhuǎn)換根據(jù)下面兩條規(guī)則進(jìn)行：

規(guī)則一：若[t≤ω]或[η<μj]，則第[j]只海豚根據(jù)公式（2）， （3）， （4）和（5）更新自己的位置和速度。

規(guī)則二：若[t>ω]且[μj≤η]，則第[j]只海豚根據(jù)公式（6）和（7）更新自己的位置和速度。

其中，[η]是[[0，1]]內(nèi)的隨機(jī)數(shù)。

1.4算法流程

算法輸入?yún)?shù)：[w1]，[w2]，[cR1]，[cI1]，[β1]，[β2]，[ω]，最大迭代次數(shù)[Gen]，海豚個體數(shù)[M]。

Step1：對[M]只海豚進(jìn)行初始化。[t=0]。

Step2：計算所有海豚個體的適應(yīng)度值。

Step3：若未找到最優(yōu)解或[t

Step4：[t=t+1]。

Step5：若[t≤ω]，則用式（2），（3），（4），（5）對[M]只海豚的位置進(jìn)行更新，轉(zhuǎn)Step2。否則轉(zhuǎn)Step6。

Step6：根據(jù)式（8）計算[Yj]，并對[Yj]排序。根據(jù)式（9）計算[μj]。產(chǎn)生[[0，1]]內(nèi)的隨機(jī)數(shù)[η]。

Step7：依次對[M]只海豚進(jìn)行位置更新。若[μj≤η]，則用式（6），（7）對第[j]只海豚進(jìn)行位置更新，否則用式（2），（3），（4），（5）對第[j]只海豚進(jìn)行位置更新。[j=1，2，…，M]。轉(zhuǎn)Step2。

Step8：算法終止，輸出最優(yōu)解。

2 約束優(yōu)化問題描述

一般的約束優(yōu)化問題可描述為：

[minfX]

[s.t.] [giX≤0]，[i=1，2，…，m]

[hjX=0]，[j=1，2，…，p]

[lk≤xk≤uk]，[k=1，2，…，n]

其中，[X=x1，x2，…，xn∈Ω?S]為決策向量，[Ω]為可行域，[S]為決策空間。[fX]為目標(biāo)函數(shù)，[giX]為[m]個不等式約束，[hjX]為[j]個等式約束。[lk]和[uk]分別為[xk]的上下界。

3 實驗分析

3.1實驗環(huán)境及仿真實例

實驗采用Intel? Core（TM） i7-4790K CPU @4.00 GHz、16GB內(nèi)存、SanDisk SDSSDHII120G硬盤的臺式機(jī)，操作系統(tǒng)為Windows 10 64位專業(yè)版，仿真軟件為Matlab 2015b。

選取的三個仿真實例分別為伸縮繩、焊接條和壓力管的設(shè)計問題[3-5]。

（1）伸縮繩設(shè)計問題。

伸縮繩結(jié)構(gòu)如圖1所示。該問題屬于連續(xù)型約束優(yōu)化問題，優(yōu)化目標(biāo)是尋求滿足對最小偏差、切應(yīng)力、湍振頻率等一系列約束條件的3 個決策變量，即平均卷直徑[Dx1]、線直徑[dx2]和活動卷的數(shù)量[Px3]，使得伸縮繩的重量最小。其目標(biāo)函數(shù)及約束條件如下：

[minfx=x3+2x2x21]

[s.t.] [g1x=1-x32x371785x41≤0]

[g2x=4x22-x1x212566x2x31-x41+15108x21-1≤0]

[g3x=1-140.45x1x22x3≤0]

[g4x=x1+x21.5-1≤0]

其中，[x1∈0.05，2]，[x2∈0.25，1.3]，[x3∈2，15]。

（2）焊接條設(shè)計問題。

焊接條結(jié)構(gòu)如圖2所示。該問題屬于連續(xù)型約束優(yōu)化問題，優(yōu)化目標(biāo)是尋求滿足切應(yīng)力[τ]、彎曲應(yīng)力[σ]、桿條彎曲載荷[Pc]、末端偏差[δ]和邊界條件等約束條件的4個設(shè)計變量[hx1]、[lx2]、[tx3]和[bx4]，使得制造焊接條所需的總費(fèi)用最小。其目標(biāo)函數(shù)及約束條件如下：

[minfx=1.10471x21x2+0.04811x3x414.0+x2]

[s.t.] [g1x=τx-13600≤0]

[g2x=σx-30000≤0]

[g3x=x1-x4≤0]

[g4x=0.10471x21+0.04811x3x414.0+x2-5.0≤0]

[g5x=0.125-x1≤0]

[g6x=δx-0.25≤0]

[g7x=6000-Pcx≤0]

其中，

[τx=τ'2+τ'τ''x2R+τ''2]

[τ'=60002x1x2]

[τ''=MRJ]

[M=600014+x22]

[R=x22+x1+x324]

[J=22x1x2x2212+x1+x324]

[σx=504000x4x23]

[δx=2.1952x33x4]

[Pc=4.013E1-0.0282346x3x3x346L2]

式中，[L=14]，[E=30×106]。決策變量取值范圍：[x1，x4∈0.1，2]，[x2，x3∈0.1，10]。

（3）壓力管設(shè)計問題。

壓力管結(jié)構(gòu)如圖3 所示。該問題屬于混合約束優(yōu)化問題，優(yōu)化目標(biāo)是尋求滿足一系列約束條件的4個設(shè)計變量[Ts]（[x1]，圓柱形管子的厚度）、[Th]（[x2]，半球形蓋子的厚度）、[R]（[x3]，圓柱形管子的內(nèi)徑）和[L]（[x4]，圓柱形管子的長度，不包括兩端的蓋子），使得材料、焊接、鑄造等費(fèi)用在內(nèi)的總費(fèi)用最少。其中，[Ts]和[Th]均為0.0625英寸的整數(shù)倍，[R]和[L]是連續(xù)變量。其目標(biāo)函數(shù)及約束條件如下：

[minfx=0.6224x1x3x4+1.7781x2x23+3.1661x21x4+19.84x21x3]

[s.t.] [g1x=-x1+0.0193x3≤0]

[g2x=-x2+0.00954x3≤0]

[g3x=-πx23x4-4πx333+1296000≤0]

[g4x=x4-240≤0]

其中，[x1，x2∈1，99]，[x3，x4∈10，200]。

3.2參數(shù)設(shè)置及計算結(jié)果

算法參數(shù)統(tǒng)一設(shè)置如下：海豚規(guī)模[M=50]，算法最大迭代次數(shù)[Gen=500]，[w1=w2=0.6]，[cR1=cI1=2]，[β1=β2=2]，[ω=20]，[cR2=cR3=β1Gen-t/Gen]，[cI2=cI3=β2Gen-t/Gen]，[εt=1/1000t100]。

算法連續(xù)獨(dú)立運(yùn)行30次，求解結(jié)果見表1-表6。注：“-”表示文獻(xiàn)未給出計算結(jié)果。

3.3實驗結(jié)論

從表1和表2伸縮繩設(shè)計問題的實驗結(jié)果可知，DSOA算法找到的最優(yōu)解比文獻(xiàn)[6-9]優(yōu)，與文獻(xiàn)[10，11]一致。但在平均解、最差解和標(biāo)準(zhǔn)差三個指標(biāo)上，DSOA算法均優(yōu)于其他方法。

從表3和表4焊接條設(shè)計問題的實驗結(jié)果可知，在最優(yōu)解、平均解、最差解和標(biāo)準(zhǔn)差四個指標(biāo)上看，除文獻(xiàn)[10]算法求解結(jié)果與DSOA算法基本相當(dāng)外，其余均差于DSOA算法。

從表5和表6壓力管設(shè)計問題的實驗結(jié)果可知，僅DSOA算法能找到全局最優(yōu)，其他算法均陷入局部最優(yōu)，說明DSOA算法具有很強(qiáng)的避免陷入局部極值的能力。DSOA算法在標(biāo)準(zhǔn)差指標(biāo)上比文獻(xiàn)[6，9，13]略差，其余指標(biāo)均比其他方法要好。

DSOA算法求解伸縮繩、焊接條和壓力管設(shè)計問題的收斂曲線，如圖4-圖6所示。由圖可知，算法收斂速度是很快的。

4 結(jié)束語

將DSOA算法應(yīng)用于求解約束優(yōu)化問題，并使用三個工程實例對算法性能及有效性進(jìn)行驗證。實驗結(jié)果表明，與對比方法相比，DSOA算法具有收斂速度快、求解精度高、穩(wěn)定性好等優(yōu)點(diǎn)，并且擁有很好的全局搜索能力。因此，DSOA算法對于求解約束優(yōu)化問題是非常適用且有效的。

參考文獻(xiàn)：

[1]王勇， 蔡自興， 周育人，等.約束優(yōu)化進(jìn)化算法[J].軟件學(xué)報，2009，20（1）：11-29

[2]Wang Yong， Wang Tao， Zhang Cheng-zhi， et al. A New Stochastic Optimization Approach： Dolphin Swarm Optimization Algorithm[J]. International Journal of Computational Intelligence and Applications，2016，15（2）

[3] Rao S S.Engineering Optimization[M].3rd ed.New York：Wiley，1996.

[4] Arora J S.Introduction to optimum design[M].New York：Mc-Graw-Hill，1989.

[5] Kannan B K，Kramer S N.An augmented Lagrange multiplierbased method for mixed integer discrete continuous optimization and its applications to mechanical design[J]. Trans of the ASME，Journal of Mechanical Design，1994，116：318-320.

[6] Coello C A C.Use of a self-adaptive penalty approach for engineering optimization problems[J].Computers in Industry，2000，41：113-127.

[7] Coello C A C，Montes E M.Constraint-handling in genetic algorithms through the use of dominance-based tournament selection[J].Advanced Engineering Informatics，2002，16：193-203.

[8] Coello C A C，Becerra R L.Efficient evolutionary optimization through the use of a cultural algorithm[J].Engineering Optimization，2004，36：219-236.

[9] He Q，Wang L.An effective co-evolutionary particle swarm optimization for constrained engineering design problems[J].Engineering Applications of Artificial Intelligence，2007，20：89-99.

[10]龐興，王勇.PSO與捕魚策略相結(jié)合的優(yōu)化方法[J].計算機(jī)工程與應(yīng)用，2011，47（8）：36-40，50.

[11]A.H.Gandomi，X.S.Yang，et al. Bat algorithm for constrained optimization tasks[J]. Neural Comput & Applic，2013，22：1239-1255.

[12] LIU H，CAI Z，WANG Y.Hybridizing particle swarm optimization with differential evolution for constrained numerical and engineering optimization[J].Applied soft computing， 2010，10（2）：629-640.

[13] HUANG F，WANG L，HE Q.An effective co-evolutionary differential evolution for constrained optimization[J]. Applied mathematics and computation，2007，186（1）：340-356.