基于遺傳算法的退火精確罰函數(shù)非線性約束優(yōu)化方法

1、基于遺傳算法的退火精確罰函數(shù)非線性約束優(yōu)化方法吳新余(上海交通大學自動化所,200030)(南京郵電學院)吳志遠邵惠鶴摘要提出一種新的基于遺傳算法求解非線性約束優(yōu)化的方法,通過自適應的退火罰因子和不可微精確罰函數(shù)來處理約束條件,可以使算法逐漸收斂于可行的極值點。仿真結(jié)果表明該方法有較高的求解精度。關鍵詞遺傳算法,模擬退火,精確罰函數(shù),非線性約束優(yōu)化分類號O2241引言在最優(yōu)化問題中,尤其是非線性約束優(yōu)化的求解,。(SQP)、逐次線性規(guī)劃法(SLP),是目前求解非線性。盡管如此,這些方法都是基于梯度尋優(yōu)的方法,它們要求目,且這些方法僅能求得局部極值點。(GA)是由美國Holland教授及其學生和

2、同事發(fā)展起來的1,目前已得到了廣泛的研究和應用。GA是一種通用的求解優(yōu)化問題的方法,它吸取了自然界的自然選擇,適者生存等思想,在每次迭代中都保留一組候選解,并按某種指標從解群中選取較優(yōu)的個體,利用一些遺傳算子(如交叉和變異等)對其進行運算,產(chǎn)生新一代的候選解群,重復此過程,直到滿足某種收斂指標為止。由于遺傳算法無需優(yōu)化問題有連續(xù)性和可微性的限制,只要求被優(yōu)化的問題是可計算的,同時遺傳算法是基于群體進化的算法,且能收斂到全局最優(yōu)解,這樣就克服了傳統(tǒng)的基于梯度優(yōu)化方法的一些缺點。GA已被廣泛應用于各種優(yōu)化問題中,如神經(jīng)網(wǎng)絡訓練算法,調(diào)度問題,機器學習中的分類系統(tǒng),組合優(yōu)化等問題。但這些大多是無約束

3、優(yōu)化問題。對基于遺傳算法的有約束非線性優(yōu)化問題,是近期才逐漸研究和應用的。2基于遺傳算法的非線性約束優(yōu)化方法實際工程中的各種優(yōu)化問題,最終都可化為非線性約束優(yōu)化問題的求解,通?？擅枋鰹橄铝行问絤inimizef(x)subjecttoCi(x)=0,i=1,2,me(1)Ci(x)0,i=me,me+1,m國家“九五”攻關課題1997-05-27收稿,1997-09-14修回第13卷第2期吳志遠等:基于遺傳算法的退火精確罰函數(shù)非線性約束優(yōu)化方法137其中xRn,f(x)是被優(yōu)化的目標函數(shù),me是等式約束的個數(shù),m是整個約束的個數(shù)。用遺傳算法求解約束優(yōu)化問題的難點在于:1)不可行解可能產(chǎn)生偏離可

4、行域的解;2)遺傳因子作用于可行解后,可能產(chǎn)生不可行解2。目前,在遺傳算法中,已有幾種常用處理約束的方法:拋棄不可行解法(rejectionofinfeasibleoffspring),修復不可行解法(repairofinfeasibleoffspring),改變遺傳因子法(modifiedgeneticoperators),懲罰函數(shù)法(penaltyfunctions)3。拋棄不可行解法是將產(chǎn)生的不可行后代完全丟掉。這種方法雖然消除了不可行解,維持了解群的可行性,但其搜索效率較低,尤其當解群中含有較多的不可行解時。修復不可行解法是通過特殊的修復算法將產(chǎn)生的不可行解修復成可行解。該算法的最大缺

5、點是依賴于所要解決的問題。對于不同的問題需要設計不同的修復算法,對于某些復雜的優(yōu)化問題,設計相應的修復算法是較為困難的。改變遺傳因子法是通過特殊的遺傳因子,解。但是該方法僅能處理線性約束的優(yōu)化問題。4,5。以上方法或多或少都與所要解決的問題有關。,它通過對不可行解施加某種懲罰,經(jīng)過不斷迭代后,。目前該方法是遺傳的選取。;而罰函數(shù)取得過小,又可。3311懲罰函數(shù)法懲罰函數(shù)法最早是在最優(yōu)化問題中用來處理非線性約束優(yōu)化的一種方法,它通過對約束條件施加懲罰函數(shù)而使有約束問題變?yōu)闊o約束優(yōu)化問題,從而利用成熟的無約束優(yōu)化方法求解。對于式(1)的求解可以化為下列無約束問題的求解(2)minimizeF(x,

6、k)=f(x)+P(k,x)其中P(k,x)是懲罰函數(shù),k是懲罰因子。針對不同的懲罰函數(shù),形成了不同的方法,主要有外罰函數(shù)法,內(nèi)罰函數(shù)法,乘子法和精確罰函數(shù)法6。外罰函數(shù)法和內(nèi)罰函數(shù)法容易引起求解問題的病態(tài)問題,這是由于它們需要罰因子無限增大而引起的。乘子法通過在罰函數(shù)中引入拉格朗日乘子,使得罰因子k可取某個有限值,因而解決了早期外罰函數(shù)和內(nèi)罰函數(shù)法中出現(xiàn)的病態(tài)問題,但它需要解決一系列無約束極小值問題來逼近最優(yōu)乘子和最優(yōu)解。精確罰函數(shù)法有不可微精確罰函數(shù)和可微精確罰函數(shù)兩種形式。不可微精確罰函數(shù)法的主要缺點是它在約束邊界不可微,因此不能采用無約束優(yōu)化中有效的梯度法?？晌⒕_罰函數(shù)法雖可以利用梯

7、度型算法來求解,但要利用這些函數(shù)的二階導數(shù),這就大大增加了無約束極小化過程的工作量。312基于遺傳算法的退火精確罰函數(shù)法文獻7對基于遺傳算法的約束罰函數(shù)優(yōu)化方法提出了一些指導性建議。已有一些基于遺傳算法來處理約束優(yōu)化的罰函數(shù)方法8,9。文獻8采用多級罰函數(shù)法將每個約束區(qū)域分成幾段,對違反約束大的段給予較大的罰因子,而違反約束小的段的罰因子較小。文獻9則利用了非靜態(tài)罰函數(shù)法,其罰因子是迭代次數(shù)的函數(shù),這樣隨著迭代次數(shù)的增加,算法逐漸收斂于可行解。文獻8的缺點是對不同的約束優(yōu)化問題要設計相應的分段罰因子;文獻9雖然最終保138控制與決策1998年證了算法收斂于可行解,但由于它是迭代次數(shù)的函數(shù),這樣

8、罰因子變化的連續(xù)性較差。以前用遺傳算法求解約束優(yōu)化問題時,采用的罰函數(shù)形式大都是二次型的,即memP(k,x)=k3(Ci=12i(x)+Ci=me2i(x)(3)但文獻9的數(shù)值結(jié)果表明它在某些優(yōu)化問題中的求解性能并不好。為了改變上述方法的缺陷,本文提出了一種新的退火精確罰函數(shù)法,即罰函數(shù)的選取為如下形式memiP(k,x)=k3( Ci=1(x) + Ci=mei(x) )(4)其中k=1 T,T=3T,0,1。罰因子k吸取了模擬退火的思想,使T逐漸下降,即k逐漸增大,參數(shù)來控制。這樣隨著進化的不斷進行,k逐漸增大,了不可微精確罰函數(shù)。,能處理不可微函數(shù)的缺陷,4仿真研究,8中選取兩個測試函

9、數(shù)(限于篇幅,這里僅給出),8的結(jié)果進行對比。同時,為了,將它和二次型函數(shù)形式的罰函數(shù)也進行了對比。仿真中對每個求解問題都獨立地運行10次,每次運行100代,通過它們的目標函數(shù)值和滿足的約束條件來綜合評價。由于是求極小值優(yōu)化問題,傳統(tǒng)的輪轉(zhuǎn)選擇方法不再適用。本文采用區(qū)域競爭選擇方法,它類似于遺傳規(guī)劃(EP)中的tournament選擇方法,同時對最優(yōu)個體進行了保存。遺傳算法的編碼用二進制方式,個體的串長、交叉概率和變異概率的選取同文獻8中的一樣,而群體規(guī)模則是8中的1 3。問題1minimizef(x)=(x1-2)2+(x2-1)2subjecttox1-2x2+1=0,-x24-x21 2

10、+10withC1(x)=x1-2x2+1,C2(x)=-x24-x21 2+1其中x1-1.82,0.82,x2-0.41,0.92。本文的退火罰函數(shù)遺傳算法的參數(shù)為(包括精確罰函數(shù)法和二次型罰函數(shù)法):群體規(guī)模為130,染色體長度為38,交叉概率為0185,變異概率為0102,溫度冷卻參數(shù)=0.99。用退火精確罰函數(shù)法求解結(jié)果見表1,用退火二次型罰函數(shù)法求解結(jié)果見表2,文獻8的求解結(jié)果見表3。退火精確罰函數(shù)法求得的平均目標函數(shù)值f(x)=1.401217,等式約束值C1(x)=0.0002552,不等式約束C2(x)=0.0044055>0,滿足不等式約束條件。退火二次罰函數(shù)法求得的

11、平均目標函數(shù)值f(x)=1.3995894,等式約束值C1(x)=-0.0156819,不等式約束C2(x)=-0.0102975。通過對比可知,用退火罰函數(shù)法求解的結(jié)果無論是所求得的目標函數(shù)值還是最終所滿足第13卷第2期吳志遠等:基于遺傳算法的退火精確罰函數(shù)非線性約束優(yōu)化方法139的約束精度都要比8的效果好。雖然二次型罰函數(shù)所求的目標函數(shù)值比精確罰函數(shù)的值小,但是它滿足的約束精度比精確罰函數(shù)法要差得多,而在許多實際工程的優(yōu)化問題中,對可行解的要求(即對約束的滿足)是更為重要的。表1退火精確罰函數(shù)法求解問題1的結(jié)果f(x)x1x2C1(x)C2(x)Trial1Trial2Trial3Tria

12、l4Trial5Trial6Trial7Trial8Trial9Trial10average表2退火二次型罰函數(shù)法求解問題1的結(jié)果f(x)x1x2C1(x)C2(x)Trial1Trial2Trial3Trial4Trial5Trial6Trial7Trial8Trial9Trial10average-0.017234-0.015956-0.018894-0.013237-0.019325-0.017904-0.017980-0.013475-0.008735-0.014079-0.015682-0.011877-0.010784-0.013469-0.008289-0.013873-0.01

13、2526-0.011599-0.008501-0.002995-0.009062-0.010298表3文獻8求解問題的結(jié)果f(x)x1x2C1(x)C2(x)5結(jié)語遺傳算法不要求所求解問題的連續(xù)可微性,因此可以利用基于梯度法不能求解的不可微精確罰函數(shù)法來解決非線性約束優(yōu)化問題。仿真結(jié)果表明它比基于遺傳算法的傳統(tǒng)二次型罰140控制與決策1998年函數(shù)法的求解精度高。參考文獻4MichalewiczZ.Geneticalgorithms+datastructures=evolutionprograms.NewYork:Springer-Verlag,AISeries,19925樊重俊,等1一類約束

14、優(yōu)化問題的改進遺傳算法1控制與決策,1996,11(5):6096126席少霖1非線性最優(yōu)化方法1北京:高等教育出版社,19929JoinesJA,HouckCR.Ontheuseofnon-statilvenonlinearconstrainedoptimizationprob2lemswithGAs.In:PFEvolutionaryComputation.NJ:IEEEPress,Piscat2away,2:579_584lAccuracyPenaltyFunctionBasedNonlinearinedOptimizationMethodwithGeneticAlgorithmsWuZhiyuan,ShaoHuihe(ShanghaiJiaotongUniversity)(NanjingWuXinyuInstituteofPostsandTelecommunications)Keywordsgeneticalgorithms,simulatedannealing,accuracypenltyfunction,nonlinearconstrainedopti2mization作者簡介吳志遠1970年生。分別于1992、1995年獲哈爾濱船舶工程學