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

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

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

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

3、后給出一個例子，說明算法的可行性。．關鍵詞：雙層規(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