双层规划问题的EDA算法研究.pdf

《双层规划问题的EDA算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号密级公开UDC学号20150713016青海师范大学硕士学位论文双层规划问题的EDA算法研究研究生姓名陈华飞导师姓名（职称）李和成，教授申请学位名称理学硕士学科专业名称运筹学与控制论研究方向名称最优化理论、方法及应用论文提交日期2018年3月论文答辩日期2018年5月学位授予单位青海师范大学学位授予日期2018年6月答辩委员会主席评阅人，青海师范大学学位论文独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果

2、，也不包含为获得青海师范大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。研究生签名：日期：青海师范大学学位论文使用授权声明青海师范大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布（包括刊登）论文的全部或部分内容。论文的公布（包括刊登）授权由青海师范大学研究生部办理。研究生签名：导师签名

3、：日期：双层规划问题的EDA算法研究中文摘要双层规划是一种嵌套上下层问题的递阶优化模型.在该模型中，上下层问题有各自的目标函数和约束条件.在优化过程中，上层首先给出一个决策，下层根据上层决策通过优化自己的目标做出反应.一方面，上层决策影响下层问题的优化；另一方面，下层的反应也制约着上层的优化过程.由于双层规划问题在工程领域中的广泛应用，使得该领域的研究成果比较丰富.但由于该类问题本身非凸和不可微的特征，使得这类问题的求解异常困难.目前的研究主要限于一些特殊函数的小规模问题，能用于较大规模问题的算法极少.分布估计算法在求解优化问题时充分考

4、虑了已有点的分布信息，计算效率高，特别是在离散优化问题上操作方便.本文通过最优性条件离散化搜索空间，设计了求解线性双层规划和线性分式双层规划的EDA算法.线性双层规划是上下层问题均为线性规划的双层规划问题，是双层规划问题中较简单的一类，但就上层变量而言也是非凸不可微问题，因而对大规模问题求解依然缺乏有效的算法.本文利用线性规划的最优性条件和EDA算法框架，给出了求解该问题的一个EDA算法.首先，利用下层线性规划的特点，将下层基作为个体进行搜索，使问题的搜索空间变为有限集；其次，针对每一个个体（基），利用最优可行性条件获得下层解函数并代入

5、上层，得到只包含上层变量的一个线性规划；然后，求解该线性规划，得到对个体的评价；最后，通过扰动概率给出了产生后代个体的概率分布.在一些常见算例和较大规模问题上的数值仿真结果表明，提出的算法是可行且有效的.线性分式双层规划是上下层目标函数都是线性分式规划的一类非线性双层规划问题，结合下层分式规划的最优性特征，设计了求解该类问题的EDA算法.首先，将下层规划的基作为种群个体进行搜索，此时，搜索空间是一个有限集；其次，针对每个固定的基，利用线性分式规划的最优可行性条件获得下层变量的表达式.将该表达式代入上层问题，得到一个线性分式规划.然后，求

6、解这个分式规划问题，并将求得的目标函数值作为相应个体的适应度值；最后，通过概率扰动方法确定分布函数,在产生新个体时，给出了一个局部搜索方法.数值实验验证了算法的有效性.关键词：双层规划，线性分式规划，EDA，最优解IResearchonestimationofdistributionalgorithmsforbilevelprogrammingproblemsAbstractBilevelprogrammingproblems(BLPPs)areaclassofhierarchyoptimizationmodelswithnestedu

7、pperandlowerlevelproblems.Inthismodel,bothlevelshavetheirownobjectivefunctionsandconstraintconditions.Intheprocessofoptimization,theleaderfirstmakesitsdecisionsandthenthefollowerreactsunderthedecisionsgivenbytheleader.Ononehand,thedecisionsmadebytheleaderinfluencetheopti

8、mizationofthefollower;Ontheotherhand,thelower’sresponseaffectstheupper’sdecisioninreturn.Plentifulappli