非線性雙層規(guī)劃問(wèn)題的遺傳算法研究.pdf

1、雙層規(guī)劃問(wèn)題是一類(lèi)具有遞階結(jié)構(gòu)的非凸優(yōu)化問(wèn)題.目前，對(duì)于這類(lèi)問(wèn)題的討論往往局限于線性情形、上下層函數(shù)均凸可微等，對(duì)于含不可微非凸函數(shù)的雙層規(guī)劃問(wèn)題，存在的有效算法極少.本文針對(duì)幾類(lèi)非線性雙層規(guī)劃問(wèn)題，利用問(wèn)題的特點(diǎn)設(shè)計(jì)了相應(yīng)的遺傳算法，并證明了算法的收斂性，提出的大部分算法突破了基于梯度的傳統(tǒng)優(yōu)化方法對(duì)函數(shù)可微性和凸性的限制；另外，為了提高遺傳算法的效率，利用單純形法、指數(shù)分布等設(shè)計(jì)了一些新的遺傳算子。主要工作包括如下幾個(gè)方面：

2、 1.對(duì)于下層問(wèn)題為線性規(guī)劃的情形，本文討論了上層問(wèn)題為凸可微規(guī)劃和上層函數(shù)非凸不可微兩種情況。首先，對(duì)于上層凸可微的問(wèn)題，利用下層基進(jìn)行個(gè)體編碼，并運(yùn)用最優(yōu)性條件，將問(wèn)題轉(zhuǎn)化為一個(gè)單層規(guī)劃，以該單層規(guī)劃的最優(yōu)值作為相應(yīng)個(gè)體的適應(yīng)度值.該算法的優(yōu)點(diǎn)是適合求解大規(guī)模問(wèn)題。其次，針對(duì)上層函數(shù)非凸不可微的問(wèn)題，基于下層規(guī)劃的對(duì)偶問(wèn)題及對(duì)偶定理，將上層變量的取值域進(jìn)行剖分，使得每一個(gè)剖分區(qū)域內(nèi)的所有點(diǎn)對(duì)應(yīng)同一個(gè)下層最優(yōu)解表達(dá)式.而對(duì)上層采用遺傳

3、算法求解，并基于單純形法設(shè)計(jì)了新的雜交算子.算法的優(yōu)勢(shì)是對(duì)每一個(gè)上層變量值，無(wú)需求解下層問(wèn)題即可得到下層最優(yōu)解，因而提高了算法的效率。 2.討論了下層為凸二次規(guī)劃和一般凸規(guī)劃，而上層含非凸不可微函數(shù)的兩個(gè)問(wèn)題，分別提出了求解這兩類(lèi)問(wèn)題的遺傳算法。首先利用下層凸規(guī)劃的K-K-T條件，將問(wèn)題轉(zhuǎn)化為一個(gè)等價(jià)的單層規(guī)劃；其次為了提高種群個(gè)體的可行性，對(duì)下層為凸二次規(guī)劃的情形，利用Lemke算法獲得下層最優(yōu)解；對(duì)于下層為一般凸規(guī)劃的情形，

4、給出了新的約束處理方法，它能將種群中的不可行點(diǎn)轉(zhuǎn)化為約束域內(nèi)的點(diǎn)，且給出了一個(gè)判斷個(gè)體是否滿(mǎn)足下層最優(yōu)性的方法。 3.研究了三類(lèi)下層含非凸函數(shù)的雙層規(guī)劃問(wèn)題，包括下層函數(shù)可分、下層目標(biāo)為一類(lèi)非凸復(fù)合函數(shù)和下層函數(shù)為廣義凹函數(shù)三種情形.首先針對(duì)下層問(wèn)題特點(diǎn)，分別給出了下層求解方法.對(duì)下層可分的情形，將問(wèn)題分為單變量函數(shù)的極值問(wèn)題求解；對(duì)于第二類(lèi)問(wèn)題，利用下層目標(biāo)函數(shù)，將問(wèn)題分解為多個(gè)凸規(guī)劃，通過(guò)求解其中兩個(gè)而獲得最優(yōu)解；對(duì)于第三類(lèi)

5、問(wèn)題，利用凹規(guī)劃的最優(yōu)解能在極點(diǎn)上達(dá)到的性質(zhì)求解，其次利用種群最好個(gè)體設(shè)計(jì)了新的雜交算子，并用遺傳算法求解上層問(wèn)題。 4.針對(duì)下層問(wèn)題可解的非線性雙層規(guī)劃問(wèn)題，提出了一個(gè)基于插值的遺傳算法，該算法的特點(diǎn)是利用插值函數(shù)估計(jì)下層最優(yōu)解函數(shù)，以插值函數(shù)的值近似下層最優(yōu)解，這省去了大量求解下層問(wèn)題的過(guò)程，能有效節(jié)約計(jì)算量。 5.研究了下層函數(shù)關(guān)于整數(shù)變量可分、下層松弛問(wèn)題為凸規(guī)劃和下層函數(shù)關(guān)于整數(shù)變量為多項(xiàng)式的混合整數(shù)雙層規(guī)劃問(wèn)