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

《基于遺傳算法的退火精確罰函數(shù)非線性約束優(yōu)化方法new》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、控制與決策1998年3月Vol.13No.2CONTROLANDDECISIONMar.1998X基于遺傳算法的退火精確罰函數(shù)非線性約束優(yōu)化方法吳志遠(yuǎn)邵惠鶴吳新余(上海交通大學(xué)自動化所,200030)(南京郵電學(xué)院)摘要提出一種新的基于遺傳算法求解非線性約束優(yōu)化的方法,通過自適應(yīng)的退火罰因子和不可微精確罰函數(shù)來處理約束條件,可以使算法逐漸收斂于可行的極值點。仿真結(jié)果表明該方法有較高的求解精度。關(guān)鍵詞遺傳算法,模擬退火,精確罰函數(shù),非線性約束優(yōu)化分類號O2241引言在最優(yōu)化問題中,無約束優(yōu)化問題的求解已有

2、許多成熟的方法,但對于約束優(yōu)化問題,尤其是非線性約束優(yōu)化的求解,仍在不斷發(fā)展完善中。早期的非線性約束優(yōu)化問題求解是通過罰函數(shù)法將其化為無約束問題來求解。近期發(fā)展的逐次二次規(guī)劃法(SQP)、逐次線性規(guī)劃法(SLP)以及廣義簡約梯度法(GRG),已經(jīng)脫離了對無約束優(yōu)化方法的依賴,是目前求解非線性約束最優(yōu)化問題較為有效的方法。盡管如此,這些方法都是基于梯度尋優(yōu)的方法,它們要求目標(biāo)函數(shù)和約束連續(xù)、可微,且這些方法僅能求得局部極值點。[1]遺傳算法(GA)是由美國Holland教授及其學(xué)生和同事發(fā)展起來的,目前已

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

4、,調(diào)度問題,機(jī)器學(xué)習(xí)中的分類系統(tǒng),組合優(yōu)化等問題。但這些大多是無約束優(yōu)化問題。對基于遺傳算法的有約束非線性優(yōu)化問題,是近期才逐漸研究和應(yīng)用的。2基于遺傳算法的非線性約束優(yōu)化方法實際工程中的各種優(yōu)化問題,最終都可化為非線性約束優(yōu)化問題的求解,通?？擅枋鰹橄铝行问絤inimizef(x)(1)subjecttoCi(x)=0,i=1,2,?,meCi(x)≥0,i=me,me+1,?,mX國家“九·五”攻關(guān)課題1997-05-27收稿,1997-09-14修回第13卷第2期第13卷第2期吳志遠(yuǎn)等:基于遺傳算

5、法的退火精確罰函數(shù)非線性約束優(yōu)化方法137n其中x∈R,f(x)是被優(yōu)化的目標(biāo)函數(shù),me是等式約束的個數(shù),m是整個約束的個數(shù)。用遺傳算法求解約束優(yōu)化問題的難點在于:1)不可行解可能產(chǎn)生偏離可行域的解;2)遺[2]傳因子作用于可行解后,可能產(chǎn)生不可行解。目前,在遺傳算法中,已有幾種常用處理約束的方法:拋棄不可行解法(rejectionofinfeasibleoffspring),修復(fù)不可行解法(repairofinfeasible[3]offspring),改變遺傳因子法(modifiedgenetico

6、perators),懲罰函數(shù)法(penaltyfunctions)。拋棄不可行解法是將產(chǎn)生的不可行后代完全丟掉。這種方法雖然消除了不可行解,維持了解群的可行性,但其搜索效率較低,尤其當(dāng)解群中含有較多的不可行解時。修復(fù)不可行解法是通過特殊的修復(fù)算法將產(chǎn)生的不可行解修復(fù)成可行解。該算法的最大缺點是依賴于所要解決的問題。對于不同的問題需要設(shè)計不同的修復(fù)算法,對于某些復(fù)雜的優(yōu)化問題,設(shè)計相應(yīng)的修復(fù)算法是較為困難的。改變遺傳因子法是通過特殊的遺傳因子,在這些遺傳因子作用之后產(chǎn)生的后代均為可行[4,5]解。但是該方

7、法僅能處理線性約束的優(yōu)化問題。對于非線性的約束問題則無能為力。以上方法或多或少都與所要解決的問題有關(guān)。懲罰函數(shù)法則克服了這種缺陷,它通過對不可行解施加某種懲罰,經(jīng)過不斷迭代后,使解群逐漸收斂于可行的極值點。目前該方法是遺傳算法中求解約束優(yōu)化問題的一種常用的方法。懲罰函數(shù)法的關(guān)鍵問題是對不可行解的罰函數(shù)的選取。如果罰函數(shù)取得過大,有可能使算法過早地收斂于非極值點;而罰函數(shù)取得過小,又可能使算法的收斂性能很差。3基于遺傳算法的退火精確罰函數(shù)算法311懲罰函數(shù)法懲罰函數(shù)法最早是在最優(yōu)化問題中用來處理非線性約束

8、優(yōu)化的一種方法,它通過對約束條件施加懲罰函數(shù)而使有約束問題變?yōu)闊o約束優(yōu)化問題,從而利用成熟的無約束優(yōu)化方法求解。對于式(1)的求解可以化為下列無約束問題的求解minimizeF(x,Rk)=f(x)+P(Rk,x)(2)其中P(Rk,x)是懲罰函數(shù),Rk是懲罰因子。針對不同的懲罰函數(shù),形成了不同的方法,主要有外[6]罰函數(shù)法,內(nèi)罰函數(shù)法,乘子法和精確罰函數(shù)法。外罰函數(shù)法和內(nèi)罰函數(shù)法容易引起求解問題的病態(tài)問題,這是由于它們需要罰因子無限增大而