基于近似技术的双层规划进化算法

来源：计算机应用杂志2022年第8期北京时间：

作者：沈瑜, 李和成, 陈黎娟

单位：青海师范大学 数学与统计学院，西宁 810008

摘要：双层规划涉及上层和下层两个最优化问题，上层规划问题的约束域由下层规划问题隐式确定，双层优化以上层目标为主，而下层目标在下层变量方面必须达到最优。双层规划问题的递阶结构使其具有很高的计算复杂度，特别是频繁计算下层问题会累计很大的计算量。为了有效求解这类问题，提出一种基于近似技术的进化算法。首先，采取多种群协同进化，分别利用交叉和变异算子平衡算法的开采和勘探能力；其次，基于灵敏度分析理论，设计了新个体的近似评价方式以减少算法的下层求解次数。一个算例的近似效果演示结果表明，由近似技术得到的近似后代个体与精确后代个体的位置大部分是重合的。除此之外，在10个常用算例上的结果显示，所提算法比多值映射算法获得了更好的最优解；并且根据CPU时间比较，说明近似技术有效地提高了找到最优解的速度，减少了运行时间，验证了所提算法采取的近似技术的有效性。

关键词：双层规划,进化算法,近似技术,近似解,最优解

基金资助：国家自然科学基金资助项目(61966030);青海省自然科学基金资助项目(2018-ZJ-901)