混合人工魚群算法在約束非線性優(yōu)化中的應(yīng)用

劉志君，高亞奎，章衛(wèi)國，候 美

（1.西北工業(yè)大學(xué)自動(dòng)化學(xué)院，710129西安；2.中國航空工業(yè)第一集團(tuán)第一飛機(jī)研究院，710000西安；3.日照市工業(yè)學(xué)校，262300山東日照）

混合人工魚群算法在約束非線性優(yōu)化中的應(yīng)用

劉志君1，高亞奎2，章衛(wèi)國1，候 美3

（1.西北工業(yè)大學(xué)自動(dòng)化學(xué)院，710129西安；2.中國航空工業(yè)第一集團(tuán)第一飛機(jī)研究院，710000西安；3.日照市工業(yè)學(xué)校，262300山東日照）

為了解決具有約束的非線性優(yōu)化問題，本文將增廣拉格朗日乘子法和魚群算法相結(jié)合用于非線性問題的全局優(yōu)化，即用人工魚群算法尋找增廣拉格朗日函數(shù)的近似最優(yōu)解，并將該近似解用于拉格朗日乘子和懲罰因子等參數(shù)的更新.同時(shí)，簡要分析了人工魚群算法的隨機(jī)收斂性.仿真結(jié)果證明，與自適應(yīng)懲罰遺傳算法相比，該混合算法在解決約束優(yōu)化問題中具有優(yōu)越性和有效性.

增廣拉格朗日乘子法；增廣拉格朗日函數(shù)；魚群算法；隨機(jī)收斂性

約束優(yōu)化問題是在自變量滿足約束條件的情況下，使目標(biāo)函數(shù)最?。ù螅┑膯栴}，其中約束條件可以是等式約束，也可以是不等式約束，全局優(yōu)化在科學(xué)工程和應(yīng)用科學(xué)中的應(yīng)用無處不在.過去數(shù)年，已有很多學(xué)者對全局優(yōu)化理論和應(yīng)用做了大量研究［1-6］.經(jīng)典的解決優(yōu)化問題的方法是傳統(tǒng)解析法中的罰函數(shù)法，但傳統(tǒng)的罰函數(shù)法存在病態(tài)性質(zhì)，如數(shù)值不穩(wěn)定和收斂慢等缺陷［7-9］.而乘子法很好地解決了這一問題，增廣拉格朗日乘子法作為一種精確罰函數(shù)法目前得到了廣泛關(guān)注與應(yīng)用.

增廣拉格朗日乘子法最初是由Hestenes［8］和Powell［9］提出，用于消除等式約束和其Lagrangian對偶問題中的對偶間隙.后來，有學(xué)者將該方法推廣應(yīng)用于解決不等式約束的優(yōu)化問題［10-11］.文獻(xiàn)［12］對增廣拉格朗日乘子法的全局收斂性做了詳細(xì)證明分析.

約束優(yōu)化已成為非線性優(yōu)化面臨的一個(gè)挑戰(zhàn)性課題，因?yàn)橛糜诩s束優(yōu)化的可行性方法僅針對具體問題具有良好的優(yōu)化效果.Birgin等［13］將增廣的拉格朗日乘子法和確定性全局優(yōu)化方法（αBB）相結(jié)合解決約束優(yōu)化問題，Jansen等［14］利用粒子群優(yōu)化算法的全局收斂性用于結(jié)構(gòu)設(shè)計(jì)優(yōu)化問題，同時(shí)引入增廣的拉格朗日乘子強(qiáng)化可行性約束條件.

增廣拉格朗日乘子法是目前用于解決等式／不等式約束函數(shù)優(yōu)化的常用方法，該方法將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題進(jìn)行求解，而魚群算法作為一種新型的群體智能優(yōu)化方法和粒子群算法有著類似的全局收斂性，借鑒文獻(xiàn)［13-14］的理論思想，本文嘗試將增廣的拉格朗日乘子法和魚群算法相結(jié)合用于解決約束非線性的全局優(yōu)化問題.

1 增廣拉格朗日乘子法

最優(yōu)化問題的數(shù)學(xué)模型一般為

式中:Ω=｛x∈Rn｜l＜x＜u｝為優(yōu)化向量或決策變量；f:Rn→R為目標(biāo)函數(shù)；gi:Rn→R（i∈I）；hj:Rn→R（j∈E）為約束函數(shù)；gi≤0（i∈I）；hj=0（j∈E）分別稱為不等式約束和等式約束，對給定的任意一個(gè)足夠小的數(shù)ε＞0，任何等式約束hj（x）=0都可以轉(zhuǎn)化為不等式約束｜hj（x）｜-εj≤0．

采用增廣拉格朗日乘子法對問題（1）進(jìn)行優(yōu)化求解，定義增廣拉氏函數(shù)為［8，15］

式中:x∈Ω；λ∈Rm+；ρ＞0為懲罰參數(shù)．約束優(yōu)化問題（1）轉(zhuǎn)化為無約束優(yōu)化問題（2），即對固定的λk和ρk，有

定義懲罰參數(shù)的初值為［13］

式中:x0為決策變量的任意隨機(jī)初始值；［g（x）］+∈Rm，［g（x）］+=max（0，gi（x））；同時(shí)定義懲罰參數(shù)ρ范圍ρ∈［ρ-，ρ+］．更新拉格朗日乘子λk∈［0，λ+］，且

其中i=1，2，…，m．給定運(yùn)算精度ε?，迭代終止條件更新公式為

增廣拉格朗日乘子法的算法流程如圖1所示.

圖1 拉格朗日乘子法算法流程

在上述增廣拉格朗乘子法的實(shí)現(xiàn)程序中，內(nèi)部算法采用基于群體智能的魚群算法，并將第k次迭代式（3）的近似最小解xk，作為第k+1次迭代的一條人工魚，其余的人工魚在可行域中隨機(jī)產(chǎn)生．

2 魚群算法

魚群算法是李曉磊等［16］于2003年提出的一種基于動(dòng)物自治體的群體智能優(yōu)化方法，基本魚群算法通過模擬魚類的覓食、聚群、追尾、隨機(jī)等行為在搜索域中進(jìn)行尋優(yōu)，是群體智能在優(yōu)化領(lǐng)域的一個(gè)典型應(yīng)用.且魚群算法具有較強(qiáng)的克服局部極值，并取得全局極值的能力［17］.同時(shí)在算法中引入公告板，用于記錄最優(yōu)人工魚的狀態(tài)，人工魚在每次尋優(yōu)結(jié)束后均檢測對比尋優(yōu)結(jié)果與公告板的記錄狀態(tài)，如果尋優(yōu)結(jié)果優(yōu)于公告板值，則更新公告板值，否則公告板保持不變.

2.1 魚群算法與實(shí)現(xiàn)程序

魚群算法是目前比較流行的一種新型群體智能優(yōu)化方法，該方法的實(shí)現(xiàn)流程主要包括:魚群初始化、覓食行為、聚群行為、追尾行為和隨機(jī)行為［18］.在魚群初始化中，需要設(shè)置的主要參數(shù)有最大迭代次數(shù)Gmax、種群規(guī)模Psize、視距v、移動(dòng)步長s、隨機(jī)數(shù)r、擁擠度因子δ以及覓食行為中的最大遍歷次數(shù)t等．各參數(shù)對算法收斂性的影響在文獻(xiàn)［16］中有詳細(xì)分析．

本文中的移動(dòng)步長s=βmax（Xmax-Xmin），視距參數(shù)采用自適應(yīng)調(diào)整策略，即隨著迭代次數(shù)的增加而自適應(yīng)的改變，v=ηmax（Xmax-Xmin），η= max｛ηmin，kηη｝，其中，ηmin＞0，0＜kη＜1．算法主要流程如下［18］:

1）覓食行為的實(shí)現(xiàn):選擇人工魚的當(dāng)前狀態(tài)為Xi（k），在其視距范圍內(nèi)隨機(jī)選取1個(gè)狀態(tài)Xj（k）=Xi（k）+r?v，如果滿足f（Xj（k））＜f（Xi（k）），則

否則重新選擇Xj（k）．若達(dá)到最大遍歷次數(shù)t后，仍不滿足覓食更新條件，則Xprey（k）=Xi（k）+ r?s．其中k為迭代次數(shù)．

2）聚群行為的實(shí)現(xiàn):選取魚群當(dāng)前狀態(tài)為Xi（k），尋找di，j＜v范圍內(nèi)的魚群數(shù)目nf及魚群中心位置Xc，如果滿足f（Xc）＜f（Xi）＆（nf／Psize）≤δ，說明魚群中心位置有較多的食物，且人工魚較少，則向中心位置移動(dòng)，

否則進(jìn)行覓食行為操作．

3）追尾行為的實(shí)現(xiàn):選取魚群當(dāng)前狀態(tài)為Xi（k），尋找di，j＜v范圍內(nèi)的魚群數(shù)目nf以及魚群中適應(yīng)度值最小的人工魚Xmin（k），如果滿足f（Xmin）＜f（Xi）＆（nf／Psize）≤δ，說明Xmin（k）處具有較多的食物，并且周圍的人工魚較少，則向Xmin（k）處移動(dòng)，

否則進(jìn)行覓食行為操作．

4）隨機(jī)行為:不滿足覓食行為的更新條件時(shí)，進(jìn)行隨機(jī)行為操作.

圖2說明了魚群算法實(shí)現(xiàn)的大致流程.需要指出的是，魚群行為中的人工魚所處狀態(tài)的適應(yīng)值Y是由式（3）的增廣拉格朗日函數(shù)計(jì)算得到的，另外，di，j是指第i條人工魚和第j條人工魚的距離．當(dāng)滿足g≥Gmax或L-Lk（Xb）≤εk時(shí)，魚群算法終止．L為種群中所有人工魚的平均適應(yīng)值．

圖2 魚群算法的實(shí)現(xiàn)程序

2.2 魚群算法的收斂性分析

因?yàn)轸~群行為中有隨機(jī)性行為的參與，因此不可避免地會(huì)出現(xiàn)隨機(jī)性優(yōu)化結(jié)果，對此借鑒文獻(xiàn)［19-20］對粒子群算法收斂性分析的思想理論，對魚群算法進(jìn)行簡要的均方收斂性分析，為方便分析，并不失一般性，假設(shè)決策變量為一維變量，且對目標(biāo)函數(shù)進(jìn)行最小值優(yōu)化.

魚群算法的收斂性特性定義為:?i∈｛1，2，…，Psize｝，Xi（t）均方收斂于P，即

式中:Xi（t）表示第i條人工魚在t時(shí)刻的位置，P表示搜索空間的1個(gè)位置點(diǎn)．定義E（Xi（t））和D（Xi（t））分別表示Xi（t）的期望和方差．因?yàn)镋（Xi（t）-P）2=（E（Xi（t））-P）2+D（Xi（t）），所以式（4）中的均方收斂等價(jià)于:tlim∝E（Xi（t）-→P）=（Xi（t）=0．整個(gè)魚群算法的迭代表達(dá)

式為

式中Y（t）=a1（Xmin（t）-Xi（t））+a2（Xc（t）-Xi（t））+a3（Xprey（t）-Xi（t））+a4v（t）．其中t表示迭代次數(shù)，aj∈｛0，1｝，j=1，2，3，4，且滿足=1，整個(gè)迭代過程Xmin（t），Xc（t），Xprey（t），v（t）都是變化的，但在某特定的迭代過程中，它們保持不變．為了分析方便，在此假定它們?yōu)槌Ｖ担虼怂悬c(diǎn)（即人工魚）的移動(dòng)是獨(dú)立的，由于X0和r（t）均是隨機(jī)數(shù)，所以迭代過程｛X（t）｝是一個(gè)隨機(jī)過程．式（5）可以表示為

其中a=a1+a2+a3，Z=a1Xmin+a2Xc+a3Xprey+ a4v．由于X（t）和r（t）相互獨(dú)立，且E［r（t）］= 1／2，因此有

所以迭代過程的特征方程為

定理1 給定aj∈｛0，1｝，j=1，2，3，4，且滿足=1，當(dāng)且僅當(dāng)a1+a2+a3=1時(shí)，迭代過程的數(shù)學(xué)期望｛E［X（t）］｝收斂到

證明 由于jaj=1，所以a1+a2+a3只能取0或1，E［X（t）］收斂，特征值需滿足｜λ｜＜1，即｜1-（a1+a2+a3）／2＜1｜，所以a1+a2+a3=1，由式（6）可以得到

令ω=（a1Xmin+a2Xc+a3Xprey+a4v）／（a1+ a2+a3），定義一個(gè)新的變量Z（t），并令Z（t）= X（t）-ω，則

定理2 給定aj∈｛0，1｝，j=1，2，3，4，且j=1，當(dāng)且僅當(dāng)a1+a2+a3=1，D（X（t））=0．

證明 由于D（XY）=D（X）D（Y）+ D（X）E2（Y）+D（Y）E2（X），且D（r（t））=1／12，利用定理1的證明結(jié)論，則從方程（7）可以得到

從前面的定義可以得出

所以，特征方程為

同定理1中E［X（t）］的收斂條件一樣，D（X（t））收斂需滿足特征根

所以a1+a2+a3=1，則從方程（8）可以得出D（X（t））=0．

3 仿真測試

用文中提出的混合魚群算法（AFS-aL）對文獻(xiàn)［21］中的G01、G02、G03、G04、G06和G10函數(shù)進(jìn)行優(yōu)化求解．基于魚群的尋優(yōu)算法依賴于一些隨機(jī)參數(shù)和變量，favg表示平均值，fbest表示得到的最優(yōu)結(jié)果，st．dev表示標(biāo)準(zhǔn)偏差，kavg表示外部平均迭代次數(shù)．

n（n=13，20，10，5，2，8）表示決策變量的維數(shù)．參考文獻(xiàn)［13］中拉格朗日乘子法的參數(shù)設(shè)置，本文仿真參數(shù)設(shè)置如下:λ+=1012，ρ-=10-12，ρ+=1012，ε?=10-12，γ=10，α=0.5，Kmax=20．魚群算法中的參數(shù):η0=1，kη=0.9，ηmin=10-8，β= 0.001，t=50，Gmax=20 n，40 n；Psize=10 n，20 n，30 n．對測試函數(shù)分別進(jìn)行10次仿真，取其中的5次仿真結(jié)果，并和文獻(xiàn)［22］中的優(yōu)化算法進(jìn)行對比，優(yōu)化結(jié)果如表1所示.

通過和文獻(xiàn)［22］的優(yōu)化算法比較可以看出，文中提出的算法能夠較好的解決非線性函數(shù)的優(yōu)化問題，優(yōu)化得到的可行解具有較高的計(jì)算精度，且算法具有較好的穩(wěn)定性，甚至對于較高維的優(yōu)化函數(shù)也可以得到比較滿意的可行解，如測試函數(shù)G02，維數(shù)為20．但對于決策變量優(yōu)化范圍比較大的優(yōu)化函數(shù)，得到可行解的質(zhì)量相對較低，如測試函數(shù)G06和G10．

3.1 種群規(guī)模對算法的影響

以測試函數(shù)G01、G03、G04和G06的仿真結(jié)果說明魚群種群規(guī)模不同對算法優(yōu)化結(jié)果的影響，每個(gè)測試函數(shù)仿真10次，取其中5次的結(jié)果，并對其取均值和標(biāo)準(zhǔn)偏差值．內(nèi)部迭代次數(shù)為Gmax= max（50，10n），其他參數(shù)不變．仿真結(jié)果如表2所示．

從表2可以看出，種群規(guī)模的增大提高了優(yōu)化解的質(zhì)量，除了G03中Psize=20n的優(yōu)化均值和標(biāo)準(zhǔn)偏差出現(xiàn)特異外，其他函數(shù)的優(yōu)化均值和偏差均隨著種群規(guī)模的增大而明顯減小，說明可行解的分布趨于均勻，同時(shí)，從kavg可以看出外部迭代次數(shù)對優(yōu)化結(jié)果的影響不大．

表1 測試函數(shù)優(yōu)化結(jié)果

表2 種群規(guī)模不同對算法的影響

3.2 內(nèi)部迭代次數(shù)對算法的影響

選取G02、G03、G04和G06作為測試函數(shù)，進(jìn)行10次仿真，選取其中5次的仿真結(jié)果說明內(nèi)部迭代次數(shù)對算法的影響．其中G02的種群規(guī)模為Psize=10n，其他測試函數(shù)的種群為Psize=20n，Gmax=10n，30n，其他參數(shù)不變．結(jié)果如表3所示．

表3 內(nèi)部迭代次數(shù)對算法的影響

除G02外，表中數(shù)據(jù)說明隨著內(nèi)部迭代次數(shù)的增加，優(yōu)化可行解的質(zhì)量得到了顯著改善，且隨著Gmax的增大，優(yōu)化均值favg和標(biāo)準(zhǔn)偏差st．dev明顯減小，說明可行解越來越趨于均勻化．

4 結(jié) 論

增廣拉格朗日乘子法是求解約束非線性優(yōu)化問題的常用方法，和群體智能算法的融合進(jìn)一步拓寬了該方法的應(yīng)用領(lǐng)域.魚群算法和其他智能算法一樣，屬于一種隨機(jī)搜索算法，文中簡要分析了該算法的隨機(jī)收斂性，并給出了扼要的證明，所得結(jié)論如下:

1）文中選取了6個(gè)測試函數(shù)，通過和自適應(yīng)懲罰遺傳算法的結(jié)果相比，本文的仿真結(jié)果優(yōu)于文獻(xiàn)［22］的結(jié)果，尤其對于較高維函數(shù)的計(jì)算優(yōu)勢更明顯，證明本文提出的混合魚群算法在求解約束非線性優(yōu)化問題時(shí)是可行、有效的，且通過多次仿真分析了外部迭代次數(shù)、內(nèi)部迭代次數(shù)以及魚群規(guī)模對優(yōu)化結(jié)果的影響.

2）經(jīng)多次仿真發(fā)現(xiàn)，對于決策變量尋優(yōu)范圍比較大的優(yōu)化函數(shù)，得到的可行解的精度相對較低，所以為了得到較高質(zhì)量的可行解，在進(jìn)行種群初始化時(shí)，可以采取適當(dāng)?shù)牟呗砸蕴岣叻N群初始化質(zhì)量，如采用基于Tent映射的混沌方法進(jìn)行種群初始化等.

3）基本魚群算法的計(jì)算精度相對較低，要用于解決較高精度的約束優(yōu)化問題，可以對基本魚群算法進(jìn)行改進(jìn)，然后和增廣拉格朗日乘子法相結(jié)合進(jìn)行問題的優(yōu)化分析.

［1］BARD JF.Practical bilevel optimization:algorithms and applications［M］.Dordrecht:Kluwer Academic Publishers，1998.

［2］FLOUDASCA.Deterministic global optimization:theory，methods and application［M］.Dordrecht:Kluwer Academic Publishers，1999.

［3］SHERALIH D，ADAMSW P.A reformulation-linearization technique for solving discrete and continuous nonconvex problems［M］.Dordrecht:Kluwer Academic Publishers，1999.

［4］TAWARMALANIM，SAHINIDISN V.Convexification and global optimization in continuous and mixed-integer nonlinear programming［M］.Dordrecht:Kluwer Academic Publishers，2002.

［5］TUY H.Convex analysis and global optimization［M］. Dordrecht:Kluwer Academic Publishers，1998.

［6］ZABINSKY Z B.Stochastic adaptive search for global optimization［M］.Dordrecht:Kluwer Academic Publishers，2003.

［7］杜學(xué)武，靳禎.不等式約束優(yōu)化問題的一個(gè)精確增廣拉格朗日函數(shù)［J］.上海交通大學(xué)學(xué)報(bào):自然科學(xué)版，2006，40（9）:1636-1640.

［8］HESTENESM R.Multiplier and gradientmethods［J］. Optimization Theory and Applications，1969，4（5）: 303-320.

［9］POWELLM JD.A method for nonlinear constraints in minimization problems optimization［M］.New York: Academic Press，1969:283-298.

［10］ROCKAFELLAR R T.The multiplier method of Hestenes and Powell applied to convex programming［J］. Optimization Theory and Applications，1973，12（6）:555-562.

［11］ROCKAFELLAR R T.Augmented Lagrange multiplier functions and duality in nonconvex programming［J］. SIAM Journal on Control，1974，12（2）:268-285.

［12］萬仲平，費(fèi)浦生.優(yōu)化理論與方法［M］.武漢:武漢大學(xué)出版社，2006.

［13］BIRGIN EG，F(xiàn)LOUDASCA，MARTINEZ JM.Global minimization using an augmented Lagrangian method with variable lower-level constraints［J］.Mathematical Programming，2010，125（1）:139-162.

［14］JANSEN PW，PEREZR E.Constrained structural design optimization via a parallel augmented Lagrangian particle swarm optimization approach［J］.Computers and Structures，2011，89（13）:1352-1366.

［15］ROCKAFELLAR R T.Augmented Lagrange multiplier functions and duality in nonconvex programming［J］. Control Optimization，1974，12（2）:268-285.

［16］李曉磊.一種新型的智能優(yōu)化方法——人工魚群算法［D］.杭州:浙江大學(xué)，2003:17-39.

［17］李曉磊，錢積新.基于分解協(xié)調(diào)的人工魚群優(yōu)化算法研究［J］.電路與系統(tǒng)學(xué)報(bào)，2003，8（1）:1-6.

［18］史峰，王輝，郁磊，等.Matlab智能算法30個(gè)案例分析［M］.北京:北京航空航天大學(xué)出版社，2011:162-177.

［19］JIANG Ming，LUO Yupin，YANG Shiyuan.Stochastic convergence analysis and parameter selection of the standard particle swarm optimization algorithm［J］. Information Processing Letters，2007，102（1）:8-16.

［20］IOAN C T.The particle swarm optimization algorithm: convergence analysis and parameter selection［J］. Information Processing Letters，2003，85（6）:317-325.

［21］THOMASPR，YAOXin.Stochastic ranking for constrained evolutionary optimization［J］.IEEE Transcations on Evolutionary Computation，2000，4（3）:284-294.

［22］BARBOSA H JC，LEMONGEACC.An adaptive penalty method for genetic algorithms in constrained optimization problems［M］.Vienna:INTECH，2008:9-34.

（編輯張 宏）

The app lication of hybrid fish swarm algorithm for constrained nonlinear optim ization

LIU Zhijun1，GAO Yakui2，ZHANGWeiguo1，HOU Mei3

（1.School of Automation，Northwestern Polytechnical University，710129 Xi’an，China；2.The First Aircraft Institute of China Aviation Industry Corporation I，710000 Xi’an，China；3.Rizhao Industry School，262300 Shandong Rizhao，China）

A hybrid algorithm which combines the augmented Lagrangian multiplier method with the fish swarm algorithm is presented to solve the problem of constrained nonlinear optimization.The method approximately solves the optimal solution of the augmented Lagrangian function with the fish swarm algorithm，and the solution is applied to update the Lagrangianmultipliers and penalty parameters.Stochastic convergence of the artificial fish swarm is analyzed.Compared with an adaptive penalty method for genetic algorithms，simulation results verify the superiority and validity of the proposed hybrid algorithm.

augmented Lagrangian multipliermethod；augmented Lagrangian function；fish swarm algorithm；stochastic convergence

TP301.6

A

0367-6234（2014）09-0055-06

2013-06-19.

國家重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃資助項(xiàng)目（20126131890302）；航空科學(xué)基金資助項(xiàng)目（20125853035）.

劉志君（1982—）女，博士研究生；高亞奎（1959—）男，兼職教授，博士生導(dǎo)師；章衛(wèi)國（1956—）男，教授，博士生導(dǎo)師.

章衛(wèi)國，zhangwg＠nwpu.edu.cn.