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

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

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

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

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

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