《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (8): 2511-2518.DOI: 10.11772/j.issn.1001-9081.2021061079

• 先进计算 • 上一篇    

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

沈瑜, 李和成(), 陈黎娟   

  1. 青海师范大学 数学与统计学院,西宁 810008
  • 收稿日期:2021-06-25 修回日期:2022-02-25 接受日期:2022-03-04 发布日期:2022-03-17 出版日期:2022-08-10
  • 通讯作者: 李和成
  • 作者简介:沈瑜(1995—),女,重庆人,硕士研究生,主要研究方向:最优化;
    李和成(1973—),男,青海西宁人,教授,博士生导师,博士,主要研究方向:智能计算、最优化;
    陈黎娟(1997—),女,甘肃兰州人,硕士研究生,主要研究方向:最优化。
  • 基金资助:
    国家自然科学基金资助项目(61966030);青海省自然科学基金资助项目(2018-ZJ-901)

Evolutionary algorithm based on approximation technique for solving bilevel programming problems

Yu SHEN, Hecheng LI(), Lijuan CHEN   

  1. College of Mathematics and Statistics,Qinghai Normal University,Xining Qinghai 810008,China
  • Received:2021-06-25 Revised:2022-02-25 Accepted:2022-03-04 Online:2022-03-17 Published:2022-08-10
  • Contact: Hecheng LI
  • About author:SHEN Yu, born in 1995, M. S. candidate. Her research interests include optimization.
    LI Hecheng, born in 1973, Ph. D., professor. His research interests include intelligent computing, optimization.
    CHEN Lijuan, born in 1997, M. S. candidate. Her research interests include optimization.
  • Supported by:
    National Natural Science Foundation of China(61966030);Natural Science Foundation of Qinghai Province(2018-ZJ-901)

摘要:

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

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

Abstract:

Bilevel programming involves two optimization problems located at upper-level (leader) and lower-level (follower). The constraint domain of the leader is determined by the follower implicitly, the leader objective dominates in a bilevel optimization procedure, and the follower objective must be optimized with respect of the follower variables. The hierarchical structure of the bilevel optimization problem causes large computational complexity. Especially, the frequent computations of the follower can accumulate a large amount of computational cost. In order to solve this kind of problem effectively, an evolutionary algorithm based on approximation technique was developed. Firstly, a multi-population co-evolution approach was applied, and the crossover and the mutation operators were used respectively to balance the exploitation and exploration capabilities of the algorithm. Secondly, based on the sensitivity analysis theory, an approximation evaluation method for new individuals was designed to reduce the computation frequency of the follower carried out by the algorithm. The demonstration results of the approximate effect of a numerical example show that most positions of the approximate offspring individuals and the exact offspring individual are mostly coincident. In addition, the results on 10 common examples show that the proposed algorithm can find better optimal solutions than the multi-valued mapping algorithm. CPU time comparison shows that the approximate technique improves the speed of finding the optimal solution effectively, thereby reducing the running time. Therefore, the effectiveness of the approximate technique adopted by the algorithm is demonstrated.

Key words: bilevel programming, evolutionary algorithm, approximation technique, approximate solution, optimal solution

中图分类号: