求解特殊双层规划问题的遗传算法

《求解特殊双层规划问题的遗传算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要对双层规划问题进行算法研究具有现实意义和应用前景，近年来受到众多领域的广泛关注。双层规划问题是一类具有递阶结构的非凸优化问题，双层规划的非凸性和不可微性给其数值求解带来了极大的困难，特别是求解非线性双层规划问题的全局最优解更加困难。遗传算法是一种解决复杂非线性优化问题的新型的有效方法，它不受目标函数的可微性、凸性、连续性等限制。具有全局优化、隐并行性、鲁棒性强、操作简单等特点。本文主要分析了双层规划的复杂性和遗传算法的优点，用遗传算法来求解双层规划问题。主要研究两种类型的双层规划问题，一类是下层为凸二次规划的双层规划，一类是灰色双层线性规划。首先

2、，对下层是凸二次规划这一特殊结构的非线性双层规划问题，将下层的最优解用上层的决策变量或者Lagrange乘子来表示，并将下层的最优解带入到上层，把双层规划问题转化为含上层决策变量和Lagrange乘子的单层规划问题，设计一个改进的变异算子和一个局部搜索算子，提出一种混合遗传算法。大量的数值实验结果验证了算法的有效性。其次，对灰色双层线性规划进行了研究。提出了定位区间的概念和满意度计算的新方法，并对其性质进行了研究，根据灰色双层线性规划的特性，改进了种群初始化方法和适应度值计算方法，对灰色双层线性规划解的情况进行了初始判断，设计一个新的遗传算法求解。最

3、后给出一个例子，说明算法的可行性。．关键词：双层规划遗传算法全局优化灰色双层线性规划求解特殊双层规划问题的遗传算法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