论文部分内容阅读
双层规划是一种具有嵌套性的优化问题,具有非常重要的现实意义和应用价值。由于双层规划问题的非凸非可微性,使得其求解特别困难,最简单的线性双层规划已被证明是 NP-难问题,传统算法对于这类问题的求解效果并不好。由于遗传算法、蚁群算法、粒子群算法等进化算法不需要目标函数可微及其梯度信息等原因,进化算法在求解双层规划问题中受到了广泛的关注。分布估计算法(EDA)是一种结合进化算法和统计学习的新型进化算法,此算法既继承了进化算法的优点,又能通过统计学习改善进化算法本身的一些缺点,是求解复杂不可微问题的一种重要方法。到目前为止,分布估计算法很少用于求解双层规划问题。 本文在原始的分布估计算法基础上,引入均匀设计思想、交叉算子以及正交交叉算子,提出两类改进的EDA方法,研究了求解两类特殊形式的双层规划问题。本文主要工作包括以下几个方面: 第一,对于二次—线性的双层规划问题,首先,利用单纯形最优性等价条件将问题转化成单层规划问题。然后,基于原始EDA,采用均匀设计思想产生初始种群,引入一种利用种群最优个体进行交叉的交叉算子,设计了改进的 EDA方法,并且证明了该算法的收敛性。利用均匀设计产生初始种群,保证了种群的多样性;加入交叉算子,增强了算法的局部收敛性,保证了种群向好的方向进化,加快了算法收敛速度;对新产生的个体进行越界处理,保证了个体的质量。最后,数值实验结果表明该算法是有效的,与原始 EDA相比,该算法更稳定且收敛速度更快。 第二,对于分式—分式形式的双层规划问题,首先,利用等价变形将下层为分式规划的问题转化成下层为线性规划的问题。然后,利用均匀设计思想产生初始种群,引入正交交叉算子,对新个体使用越界处理技术,设计一种新改进的EDA方法。克服了原始EDA局部收敛性较弱的缺点,增强了EDA方法的局部搜索能力,加快了算法收敛速度。进一步,对该算法进行了收敛性证明。最后,数值实验结果表明该算法是有效的,与原始EDA相比,该方法更稳定且收敛速度更快。