求解特殊雙層規(guī)劃問題的遺傳算法

《求解特殊雙層規(guī)劃問題的遺傳算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、摘要對(duì)雙層規(guī)劃問題進(jìn)行算法研究具有現(xiàn)實(shí)意義和應(yīng)用前景，近年來受到眾多領(lǐng)域的廣泛關(guān)注。雙層規(guī)劃問題是一類具有遞階結(jié)構(gòu)的非凸優(yōu)化問題，雙層規(guī)劃的非凸性和不可微性給其數(shù)值求解帶來了極大的困難，特別是求解非線性雙層規(guī)劃問題的全局最優(yōu)解更加困難。遺傳算法是一種解決復(fù)雜非線性優(yōu)化問題的新型的有效方法，它不受目標(biāo)函數(shù)的可微性、凸性、連續(xù)性等限制。具有全局優(yōu)化、隱并行性、魯棒性強(qiáng)、操作簡(jiǎn)單等特點(diǎn)。本文主要分析了雙層規(guī)劃的復(fù)雜性和遺傳算法的優(yōu)點(diǎn)，用遺傳算法來求解雙層規(guī)劃問題。主要研究?jī)煞N類型的雙層規(guī)劃問題，一類是下層為凸二次規(guī)劃的雙層規(guī)劃，一類是灰色雙層線性規(guī)劃。首先

2、，對(duì)下層是凸二次規(guī)劃這一特殊結(jié)構(gòu)的非線性雙層規(guī)劃問題，將下層的最優(yōu)解用上層的決策變量或者Lagrange乘子來表示，并將下層的最優(yōu)解帶入到上層，把雙層規(guī)劃問題轉(zhuǎn)化為含上層決策變量和Lagrange乘子的單層規(guī)劃問題，設(shè)計(jì)一個(gè)改進(jìn)的變異算子和一個(gè)局部搜索算子，提出一種混合遺傳算法。大量的數(shù)值實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性。其次，對(duì)灰色雙層線性規(guī)劃進(jìn)行了研究。提出了定位區(qū)間的概念和滿意度計(jì)算的新方法，并對(duì)其性質(zhì)進(jìn)行了研究，根據(jù)灰色雙層線性規(guī)劃的特性，改進(jìn)了種群初始化方法和適應(yīng)度值計(jì)算方法，對(duì)灰色雙層線性規(guī)劃解的情況進(jìn)行了初始判斷，設(shè)計(jì)一個(gè)新的遺傳算法求解。最

3、后給出一個(gè)例子，說明算法的可行性。．關(guān)鍵詞：雙層規(guī)劃遺傳算法全局優(yōu)化灰色雙層線性規(guī)劃求解特殊雙層規(guī)劃問題的遺傳算法AbstractBi—levelprogrammingproblem，brieflydenotedbyBLPP，hasbeenwidelyused，andtheresearchonalgorithmsforBLPPisofrealsignificance．Somuchattentionhasbeenpaidtothisareainrecentyears．Bi—levelprogrammingproblems(BLPPs)arenon-co

4、nvexoptimizationproblemswithhierarchicalstructure．ItisverydifjficulttodetermineitssolutionofBLPPbecauseofitsinherentnon-convexityandnon—differentiability．Inparticular，itismoredifficulttogettheglobaloptimalsolutionofnonlinearBLPP．Geneticalgorithm，brieflydenotedbyGA，isanewkindofe

5、ffectivealgorithmforverycomplexnonlinearprogramming．Itisnotrestrictedbyfunctionsinvolvingrequitingdifferentiability，convexitycontinuationandSOon．IthasSOmeadvantagessuchasglobalsearchability，implicitparallelism，robustness，simpleoperationandSOon．Inthispaper,westudythedifficultyof

6、bi-levelprogrammingandgoodperformanceofgeneticalgorithm．Geneticalgorithmsaleappliedtosolvetwokindsofbi—levelprogramming．Onekindisthelowerforconvexquadraticprogrammingbi—levelprogramming，andtheotherkindisagraybi-levellinearprogramming．Firstly，foraclassofconvexquadraticprogrammin

7、gbi—levelprogramming，theoptimalsolutionofthelower-levelproblemisrepresentedbytheupper-levelvariablesorLagrangemultipliers．Thelower-levelvariablesareafunctionofupper-levelvariables．Thenthebi-levelprogrammingprogramcallbetransformedintoasingle-leveloptimizationprogramcontainingth

8、eupper-levelvariablesorLagrangemultipliersthroughrepla