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

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

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

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

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

4、,調(diào)度問(wèn)題,機(jī)器學(xué)習(xí)中的分類(lèi)系統(tǒng),組合優(yōu)化等問(wèn)題。但這些大多是無(wú)約束優(yōu)化問(wèn)題。對(duì)基于遺傳算法的有約束非線性?xún)?yōu)化問(wèn)題,是近期才逐漸研究和應(yīng)用的。2基于遺傳算法的非線性約束優(yōu)化方法實(shí)際工程中的各種優(yōu)化問(wèn)題,最終都可化為非線性約束優(yōu)化問(wèn)題的求解,通?？擅枋鰹橄铝行问絤inimizef(x)(1)subjecttoCi(x)=0,i=1,2,?,meCi(x)≥0,i=me,me+1,?,mX國(guó)家“九·五”攻關(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是等式約束的個(gè)數(shù),m是整個(gè)約束的個(gè)數(shù)。用遺傳算法求解約束優(yōu)化問(wèn)題的難點(diǎn)在于:1)不可行解可能產(chǎn)生偏離可行域的解;2)遺[2]傳因子作用于可行解后,可能產(chǎn)生不可行解。目前,在遺傳算法中,已有幾種常用處理約束的方法:拋棄不可行解法(rejectionofinfeasibleoffspring),修復(fù)不可行解法(repairofinfeasible[3]offspring),改變遺傳因子法(modifiedgenetico

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

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

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