資源描述:
《約束優(yōu)化問題的改進混合遺傳算法.pdf》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、過程控制化工自動化及儀表,2010,37(7):13—16ControlandInstrumentsinChemicalIndustry約束優(yōu)化問題的改進混合遺傳算法范小勤8,汪小紅6,尹潔8(廣州番禺職業(yè)技術(shù)學(xué)院a.基礎(chǔ)課部.b.機械與電子系,廣州511483)摘要:提出了罰函數(shù)與修復(fù)的混合策略,改進了罰函數(shù),給出了種群早熟度評價指標(biāo),對遺傳算法的交叉算子進行了改進,解決了單一使用罰函數(shù)方法求約束優(yōu)化問題所遇到的困難,方便了遺傳算法在約束優(yōu)化問題中的應(yīng)用,提高了遺傳算法在機械及工程中應(yīng)用的適應(yīng)性。數(shù)值實驗證明,該方法比傳統(tǒng)的遺傳算法處理約束優(yōu)化問題效率高
2、。關(guān)鍵詞:約束優(yōu)化;罰函數(shù);修復(fù);遺傳算法中圖分類號:0221文獻標(biāo)識碼:A文章編號:1000-3932(2010)07-0013..041引言在機械、化工及其它工程等應(yīng)用中,常涉及到優(yōu)化問題。對很多問題進行數(shù)學(xué)建模后,都可以抽象為一個數(shù)值約束函數(shù)的優(yōu)化問題。一般而言,約束函數(shù)的優(yōu)化問題可以描述為下列數(shù)學(xué)模型:Minf(z)S.t.hi(z)=0(i=1,2。?,&)既x)90(,:1,2,?,m)(1)算=(善,,z2,?,at:。)Ⅳ?≤≈≤Z實踐表明,遺傳算法求解約束優(yōu)化問題的計算效率很高。在使用遺傳算法優(yōu)化時,必須對這些約束條件進行處理。目前還沒有
3、處理約束問題的一般方法,需要根據(jù)具體問題具體分析,常用如下策略:罰函數(shù)策略、改進遺傳算子策略、修復(fù)策略,等等?。罰函數(shù)策略是通過對不可行解施加某種懲罰,使目標(biāo)懲罰值增大(求極小值問題),經(jīng)過不斷迭代,種群逐漸收斂于可行解。但這類算法中懲罰函數(shù)及懲罰系數(shù)的選取較困難,如靜態(tài)罰函數(shù)法、動態(tài)罰函數(shù)法等。改進遺傳算子策略是設(shè)計針對問題的表達方式以及專門的遺傳算子來維持染色體的可行性,從而解決可行性問題的一個合理辦法。許多領(lǐng)域中的實際工作者采用這一策略構(gòu)成了非常成功的遺傳算法,這已經(jīng)是一個十分普遍的趨勢。但是該方法遺傳搜索受到了可行域的限制。修復(fù)策略是通過一些修復(fù)法
4、將隨機產(chǎn)生的不可行解及遺傳算子作用后的不可行解修復(fù)成可行解,或?qū)⒁欢ū壤牟豢尚薪獍茨撤N原則用可行解取代。與改變算子法類似,這類算法的缺點是修復(fù)法依賴于所求解的問題,對于具有復(fù)雜約束的優(yōu)化問題,設(shè)計修復(fù)算法較困難。如上所述,處理約束優(yōu)化問題的方法眾多,各有優(yōu)缺點??傮w上來說,就通用性而言,罰函數(shù)法是處理約束優(yōu)化問題最常用的方法,本質(zhì)上它是通過懲罰不可行解約束問題轉(zhuǎn)化為無約束問題。在約束算法中,懲罰技術(shù)用來在每一代的種群中保持部分不可行解,使遺傳搜索可以從可行域和不可行域兩邊來達到最優(yōu)解。懲罰策略的關(guān)鍵問題是如何設(shè)計一個懲罰函數(shù)P(算),從而能有效地引導(dǎo)遺傳
5、搜索達到解空間的最好區(qū)域。2罰函數(shù)的構(gòu)造罰函數(shù)的基本思想:對在解空間中無對應(yīng)可行解的個體,計算其適應(yīng)值時,給一罰函數(shù),以降低該個體的適應(yīng)值,使該個體遺傳到下一代的機會減少‘2
6、。2.1外點罰函數(shù)法外點罰函數(shù)是通過一系列的罰因子,求罰函數(shù)的極值點來逼近原約束問題的最優(yōu)點。因為它是從可行域外部向約束邊界靠攏的,所以稱外點罰函數(shù)法。外點罰函數(shù)法既可以求含等式約束優(yōu)化問題,還可以求混合約束優(yōu)化問題。對于模型(1)通過引入罰函數(shù),可轉(zhuǎn)化為如下無約束優(yōu)化問題:‘“Minfix)+肘∑
7、jl:(x)+肘∑[min(O,g;(z))]2(2)2.2內(nèi)點罰函數(shù)法內(nèi)點罰函數(shù)法
8、的基本思想是用可行域內(nèi)的點來逼近最優(yōu)解,要求初始點位于可行域內(nèi),這樣即使經(jīng)過有限步后沒有求得最優(yōu)解,但可以將其作為近似最優(yōu)解。對于約束優(yōu)化模型(1),用內(nèi)點罰函數(shù)法,先處理約束等式。收稿日期:2010-06-01(修改稿)·14·化工自動化及儀表第37卷h。(石)=0可以表達為h.(z)+占≥0(i=1,2,?,t)(3)一h,(*)+占≥0(i=1,2,?,^)(4)式中:占——一個很小的實數(shù)。將上述不等式與模型(1)中的gJ(戈)≥0結(jié)合起來,還記為g,(茗)≥0,此時i=1,2,?,k,?,m+2后,則用內(nèi)點罰函數(shù)法,模型(1)轉(zhuǎn)化為如下無約束優(yōu)化問
9、題:肘iIlf(z)+盧m善+2i麗12.3混合罰函數(shù)法㈦(5)混合罰函數(shù)法綜合了外點罰函數(shù)的初始點可以任取和內(nèi)點罰函數(shù)法的可以求近似最優(yōu)解的優(yōu)點,將約束問題轉(zhuǎn)化為無約束問題。模型(1)采用此法,轉(zhuǎn)化為如下無約束優(yōu)化問題:,^m川甜@)+.壽薈卟小)]2+rj;1南~fr.}=li‘8I、冉’2.4罰函數(shù)的改進為了很好地解決罰因子的確定,將罰因子選為變量戈的函數(shù)。為了加快收斂速度,不僅采用外插法,并借鑒“多級懲罰”思想口1,對違反約束較大的給予較大的懲罰而違反約束較小的給予較小的懲罰,改進懲罰函數(shù)為:p(x)=∑Mihi(z)1+∑Njmax{o,一gJ(
10、石)}其中,Mi:T———掣旦L—一(i:1,2,?,^)∑Ihi