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

发布时间：2020-05-10 16:59

【摘要】：双层规划是一种嵌套上下层问题的递阶优化模型.在该模型中,上下层问题有各自的目标函数和约束条件.在优化过程中,上层首先给出一个决策,下层根据上层决策通过优化自己的目标做出反应.一方面,上层决策影响下层问题的优化;另一方面,下层的反应也制约着上层的优化过程.由于双层规划问题在工程领域中的广泛应用,使得该领域的研究成果比较丰富.但由于该类问题本身非凸和不可微的特征,使得这类问题的求解异常困难.目前的研究主要限于一些特殊函数的小规模问题,能用于较大规模问题的算法极少.分布估计算法在求解优化问题时充分考虑了已有点的分布信息,计算效率高,特别是在离散优化问题上操作方便.本文通过最优性条件离散化搜索空间,设计了求解线性双层规划和线性分式双层规划的EDA算法.线性双层规划是上下层问题均为线性规划的双层规划问题,是双层规划问题中较简单的一类,但就上层变量而言也是非凸不可微问题,因而对大规模问题求解依然缺乏有效的算法.本文利用线性规划的最优性条件和EDA算法框架,给出了求解该问题的一个EDA算法.首先,利用下层线性规划的特点,将下层基作为个体进行搜索,使问题的搜索空间变为有限集;其次,针对每一个个体(基),利用最优可行性条件获得下层解函数并代入上层,得到只包含上层变量的一个线性规划;然后,求解该线性规划,得到对个体的评价;最后,通过扰动概率给出了产生后代个体的概率分布.在一些常见算例和较大规模问题上的数值仿真结果表明,提出的算法是可行且有效的.线性分式双层规划是上下层目标函数都是线性分式规划的一类非线性双层规划问题,结合下层分式规划的最优性特征,设计了求解该类问题的EDA算法.首先,将下层规划的基作为种群个体进行搜索,此时,搜索空间是一个有限集;其次,针对每个固定的基,利用线性分式规划的最优可行性条件获得下层变量的表达式.将该表达式代入上层问题,得到一个线性分式规划.然后,求解这个分式规划问题,并将求得的目标函数值作为相应个体的适应度值;最后,通过概率扰动方法确定分布函数,在产生新个体时,给出了一个局部搜索方法.数值实验验证了算法的有效性.
【图文】：

分布估计,经典遗传算法,微观层面

了 EDA 的基本流程并与 GA 做了比较.化的角度来看，GA 通过对种群中的单个个体进行交叉、变进化，是对生物进化微观层面上数学模型的构建；EDA 则图 1-1 经典遗传算法(GA)与分布估计算法(EDA)比较
【学位授予单位】：青海师范大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O221

【参考文献】