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

doi:10.11772/j.issn.1001-9081.2021061079

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

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

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

青海师范大学数学与统计学院，西宁 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

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)

摘要/Abstract

摘要：

双层规划涉及上层和下层两个最优化问题，上层规划问题的约束域由下层规划问题隐式确定，双层优化以上层目标为主，而下层目标在下层变量方面必须达到最优。双层规划问题的递阶结构使其具有很高的计算复杂度，特别是频繁计算下层问题会累计很大的计算量。为了有效求解这类问题，提出一种基于近似技术的进化算法。首先，采取多种群协同进化，分别利用交叉和变异算子平衡算法的开采和勘探能力；其次，基于灵敏度分析理论，设计了新个体的近似评价方式以减少算法的下层求解次数。一个算例的近似效果演示结果表明，由近似技术得到的近似后代个体与精确后代个体的位置大部分是重合的。除此之外，在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

中图分类号:

TP301.6

沈瑜, 李和成, 陈黎娟. 基于近似技术的双层规划进化算法[J]. 计算机应用, 2022, 42(8): 2511-2518.

Yu SHEN, Hecheng LI, Lijuan CHEN. Evolutionary algorithm based on approximation technique for solving bilevel programming problems[J]. Journal of Computer Applications, 2022, 42(8): 2511-2518.

图/表 13

图1 交叉操作和变异操作示意图

Fig. 1 Schematic diagrams of crossover operation and mutation operation

图2 本文算法的流程

Fig. 2 Flowchart of the proposed algorithm

图3 式（10）的诱导域

Fig. 3 Inducible region of Equation（10）

表1 近似下层解和精确下层解

Tab. 1 Approximate and precise follower solutions

父代个体 $x 1, y 1, x 2, y 2$	近似后代个体 $x, y$	精确后代个体 $x, y *$
（0.00，2.00），（1.00，4.00）	（0.70，3.40）	（0.70，3.40）
（0.10，2.20），（0.80，3.60）	（0.24，2.48）	（0.24，2.48）
（0.40，2.80），（0.90，3.80）	（0.55，3.10）	（0.55，3.10）
（1.20，3.90），（1.60，3.70）	（1.40，3.80）	（1.40，3.80）
（1.80，3.60），（2.40，3.30）	（2.20，3.40）	（2.20，3.40）
（2.00，3.50），（2.60，3.20）	（2.40，3.30）	（2.40，3.30）
（3.00，3.00），（3.50，2.50）	（3.20，2.80）	（3.20，2.80）
（3.60，2.40），（4.10，1.90）	（3.90，2.10）	（3.90，2.10）
（4.50，1.50），（4.90，1.10）	（4.70，1.30）	（4.70，1.30）
（1.75，3.63），（3.25，2.75）	（2.50，3.19）	（2.50，3.25）

表1 近似下层解和精确下层解

Tab. 1 Approximate and precise follower solutions

父代个体 $x 1, y 1, x 2, y 2$	近似后代个体 $x, y$	精确后代个体 $x, y *$
（0.00，2.00），（1.00，4.00）	（0.70，3.40）	（0.70，3.40）
（0.10，2.20），（0.80，3.60）	（0.24，2.48）	（0.24，2.48）
（0.40，2.80），（0.90，3.80）	（0.55，3.10）	（0.55，3.10）
（1.20，3.90），（1.60，3.70）	（1.40，3.80）	（1.40，3.80）
（1.80，3.60），（2.40，3.30）	（2.20，3.40）	（2.20，3.40）
（2.00，3.50），（2.60，3.20）	（2.40，3.30）	（2.40，3.30）
（3.00，3.00），（3.50，2.50）	（3.20，2.80）	（3.20，2.80）
（3.60，2.40），（4.10，1.90）	（3.90，2.10）	（3.90，2.10）
（4.50，1.50），（4.90，1.10）	（4.70，1.30）	（4.70，1.30）
（1.75，3.63），（3.25，2.75）	（2.50，3.19）	（2.50，3.25）

表2 目标函数值的误差

Tab. 2 Errors of objective function values

$F x, y$	$F x, y *$	$F - F *$	$α$
4.80	4.80	0.00	0.048
2.96	2.96	0.00	0.030
4.20	4.20	0.00	0.042
6.60	6.60	0.00	0.066
7.80	7.80	0.00	0.078
8.10	8.10	0.00	0.081
9.20	9.20	0.00	0.092
9.90	9.90	0.00	0.099
9.40	9.40	0.00	0.094
8.19	8.25	0.06	0.082

表2 目标函数值的误差

Tab. 2 Errors of objective function values

$F x, y$	$F x, y *$	$F - F *$	$α$
4.80	4.80	0.00	0.048
2.96	2.96	0.00	0.030
4.20	4.20	0.00	0.042
6.60	6.60	0.00	0.066
7.80	7.80	0.00	0.078
8.10	8.10	0.00	0.081
9.20	9.20	0.00	0.092
9.90	9.90	0.00	0.099
9.40	9.40	0.00	0.094
8.19	8.25	0.06	0.082

图4 下层解的散点图

Fig. 4 Scatter diagram of follower solutions

图5 目标函数曲线图

Fig. 5 Curves of objective functions

图6 道路网络拓扑

Fig. 6 Road network topology

表3 相关参数及取值

Tab. 3 Related parameter and their values

参数	含义	取值
$M$ $K$	种群规模种群聚类组数	50 5
$M 1$	好个体数	5
$P c$	交叉概率	0.8
$P m$	变异概率	0.2
$γ$	拟合精度系数	1/100
Max_gen	运行的最大代数	20

表3 相关参数及取值

Tab. 3 Related parameter and their values

参数	含义	取值
$M$ $K$	种群规模种群聚类组数	50 5
$M 1$	好个体数	5
$P c$	交叉概率	0.8
$P m$	变异概率	0.2
$γ$	拟合精度系数	1/100
Max_gen	运行的最大代数	20

表4 上层目标函数值的最好值、最差值和均值

Tab. 4 Best values， worst values and mean values of leader objective functions

算法	上层目标函数	算例1	算例2	算例3	算例4	算例5	算例6	算例8	算例9	算例11
本文算法	$F b e s t$	49	-1 011.666 7	-22	-20	-243.5	225	-18.679 9	-29.2	748.89
	$F w o r s t$	49	-1 011.666 7	-22	-20	-243.5	225	-18.679 9	-29.2	748.89
	$F m e a n$	49	-1 011.666 7	-22	-20	-243.5	225	-18.679 9	-29.2	748.89
文献［31-32，29，33］算法	$F b e s t$	49	-1 011.666 7	-22	-20	-243.5	225	-18.678 7	-29.2	741.56

表4 上层目标函数值的最好值、最差值和均值

Tab. 4 Best values， worst values and mean values of leader objective functions

算法	上层目标函数	算例1	算例2	算例3	算例4	算例5	算例6	算例8	算例9	算例11
本文算法	$F b e s t$	49	-1 011.666 7	-22	-20	-243.5	225	-18.679 9	-29.2	748.89
	$F w o r s t$	49	-1 011.666 7	-22	-20	-243.5	225	-18.679 9	-29.2	748.89
	$F m e a n$	49	-1 011.666 7	-22	-20	-243.5	225	-18.679 9	-29.2	748.89
文献［31-32，29，33］算法	$F b e s t$	49	-1 011.666 7	-22	-20	-243.5	225	-18.678 7	-29.2	741.56

表5 本文算法和比较算法的最优解对比

Tab. 5 Best solutions comparison of the proposed algorithm and compared algorithms

（0，1，0，1，0.00，75.00，21.67）

（2，2）

（8，6）

（3，8，

0.5，0）

（20，5，

10，5）

（0，30，

-10，10）

（0，2，1.877 0，0.910 0）

（0.000 1，0.899 9，0，0.599 9，0.400 1）

（0，30，

-10，10）

文献［31-32，29］

算法

（3，4，2，0，3，0）

（0，1，0，1，0.00，75.00，21.67）

（2，2）

（8，6）

（3，8，

0.5，0）

（20，5，

10，5）

（0，30，

-10，10）

（0，2，1.876 8，0.907 6）

（0.000 1，0.899 9，0，0.599 9，0.400 1）

（0，30，

-10，10）

表6 最优解对应的下层目标函数值

Tab. 6 Follower objective function values corresponding to best solutions

算法	算例1	算例2	算例3	算例4	算例5	算例6	算例7	算例8	算例9	算例10
本文算法	-27	-4 673.36	2	-6	-19.5	100	100	-1.026 8	3.2	100
文献［31-32，29］算法	-27	-4 673.36	2	-6	-19.5	100	100	-1.015 6	3.2	100

表7 本文算法的CPU时间和UACPU时间比较

Tab. 7 Comparison of CPU time and UACPU time of the proposed algorithm

算例	CPU/s	UACPU/s	算例	CPU/s	UACPU/s
1	0.4	0.7	7	0.5	0.9
2	0.3	0.8	8	0.5	0.9
3	0.5	0.9	9	0.4	0.9
4	0.3	0.7	10	0.6	1.0
5	0.5	0.9	11	200.0	310.0
6	0.4	0.8

参考文献 33

1	DEMPE S. Foundations of Bilevel Programming［M］. New York： Springer， 2002 ：7-10.
2	DEMPE S. Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints［J］. Optimization， 2003， 52（3）： 333-359. 10.1080/0233193031000149894
3	BARD J F. Practical Bilevel Optimization： Algorithms and Applications［M］. New York： Springer， 1998 ：8-20. 10.1007/978-1-4757-2836-1_7
4	WHITTAKER G， FÄRE R， GROSSKOPF S， et al. Spatial targeting of agri-environmental policy using bilevel evolutionary optimization［J］. Omega， 2017， 66（Pt A）： 15-27. 10.1016/j.omega.2016.01.007
5	AN B， ORDÓÑEZ F， TAMBE M， et al. A deployed quantal response-based patrol planning system for the U.S. Coast Guard［J］. Interfaces， 2013， 43（5）： 400-420. 10.1287/inte.2013.0700
6	NASROLAHPOUR E， KAZEMPOUR J， ZAREIPOUR H， et al. A bilevel model for participation of a storage system in energy and reserve markets［J］. IEEE Transaction on Sustainable Energy， 2018， 9（2）： 582-598. 10.1109/tste.2017.2749434
7	李丽滢，付寒梅. 考虑多种运输方式的整车物流服务供应链订单分配问题［J］. 计算机应用， 2019， 39（6）： 1836-1841. 10.11772/j.issn.1001-9081.2018122461
	LI L Y， FU H M. Order allocation problem of vehicle logistics service supply chain considering multiple modes of transportation［J］. Journal of Computer Applications， 2019， 39（6）： 1836-1841. 10.11772/j.issn.1001-9081.2018122461
8	尹胜男，李引珍，张长泽. 基于客流分配的高铁票价调整策略［J］. 计算机应用， 2020， 40（1）： 278-283.
	YIN S N， LI Y Z， ZHANG C Z. High-speed railway fare adjustment strategy based on passenger flow assignment［J］. Journal of Computer Applications， 2020， 40（1）： 278-283.
9	SINHA A， MALO P， DED K. A review on bilevel optimization： from classical to evolutionary approaches and applications［J］. IEEE Transactions on Evolutionary Computation， 2018， 22（2）： 276-295. 10.1109/tevc.2017.2712906
10	JENSEN T V， KAZEMPOUR J， PINSON P. Cost-optimal ATCs in zonal electricity markets［J］. IEEE Transactions on Power Systems， 2018， 33（4）： 3624-3633. 10.1109/tpwrs.2017.2786940
11	DUPIN R， MICHIORRI A， KARINIOTAKIS G. Optimal dynamic line rating forecasts selection based on ampacity probabilistic forecasting and network operators’ risk aversion［J］. IEEE Transactions on Power Systems， 2019， 34（4）： 2836-2845. 10.1109/tpwrs.2018.2889973
12	SINHA A， SOUN T， DEB K. Using Karush-Kuhn-Tucker proximity measure for solving bilevel optimization problems［J］. Swarm and Evolutionary Computation， 2019， 44： 496-510. 10.1016/j.swevo.2018.06.004
13	SINHA A， SOUN T， DEB K. Evolutionary bilevel optimisation using KKT proximity measure ［C］// Proceedings of 2017 IEEE Congress on Evolutionary Computation. Piscataway： IEEE， 2017： 2412-2419. 10.1109/cec.2017.7969597
14	LIU S N， WANG M Z， KONG N， et al. An enhanced branch-and-bound algorithm for bilevel integer linear programming［J］. European Journal of Operational Research， 2021， 291（1）： 661-679. 10.1016/j.ejor.2020.10.002
15	FRANK S， MEHLITZ P， PILECKA M. Optimality conditions for the simple convex bilevel programming problem in Banach spaces［J］. Optimization， 2017， 67（2）： 237-268. 10.1080/02331934.2017.1394296
16	LIU J E， HONG Y F， ZHENG Y. A new variant of penalty method for weak linear bilevel programming problems［J］. Wuhan University Journal of Natural Sciences， 2018， 23（4）： 328-332. 10.1007/s11859-018-1330-1
17	TUO Q， LAN H Y. New exact penalty function methods with ϵ-approximation and perturbation convergence for solving nonlinear bilevel programming problems［J］. Journal of Computational Analysis and Applications， 2019， 5（1）： 449-458.
18	AGOR J， ÖZALTIN O Y. Feature selection for classification models via bilevel optimization［J］. Computers and Operations Research， 2019， 106： 156-168. 10.1016/j.cor.2018.05.005
19	LI H C. A genetic algorithm using a finite search space for solving nonlinear/linear fractional bilevel programming problems［J］. Annals of Operations Research， 2015， 235（1）： 543-558. 10.1007/s10479-015-1878-5
20	LI H C， WANG Z C. An evolutionary algorithm using parameter space searching for interval linear fractional bilevel programming problems［J］. International Journal of Pattern Recognition and Artificial Intelligence， 2016， 30（4）： No.1659011. 10.1142/s0218001416590114
21	LI H C， FANG L. Co-evolutionary algorithm： an efficient approach for bilevel programming problems［J］. Engineering Optimization， 2014， 46（3）： 361-376. 10.1080/0305215x.2013.772601
22	ABO-ELNAGA Y， NASR S. Modified evolutionary algorithm and chaotic search for bilevel programming problems［J］. Symmetry， 2020， 12（5）： No.767. 10.3390/sym12050767
23	GOSHU N N， KASSA S M. A Systematic Sampling Evolutionary （SSE） method for stochastic bilevel programming problems［J］. Computers and Operations Research， 2020， 120： No.104942. 10.1016/j.cor.2020.104942
24	曾明华，全轲. 双层规划的改进混合布谷鸟搜索量子行为粒子群优化算法［J］. 计算机应用， 2020， 40（7）： 1908-1912.
	ZENG M H， QUAN K. Improved hybrid cuckoo search-based quantum-behaved particle swarm optimization algorithm for bi-level programming［J］. Journal of Computer Applications， 2020， 40（7）： 1908-1912.
25	CASAS-RAMÍREZ M S， CAMACHO-VALLEJO J F. Solving the p-median bilevel problem with order through a hybrid Heuristic［J］. Applied Soft Computing， 2017， 60： 73-86. 10.1016/j.asoc.2017.06.026
26	ISLAM M M， SINGH H K， RAY T， et al. An enhanced memetic algorithm for single-objective bilevel optimization problems［J］. Evolutionary Computation， 2017， 25（4）： 607-642. 10.1162/evco_a_00198
27	ABO-ELNAGA Y， EI-SHORBAGY M A. Multi-sine cosine algorithm for solving nonlinear bilevel programming problems［J］. International Journal of Computational Intelligence Systems， 2020， 13（1）： 421-432. 10.2991/ijcis.d.200411.001
28	WANG G M， MA L M. The estimation of particle swarm distribution algorithm with sensitivity analysis for solving nonlinear bilevel programming problems［J］. IEEE Access， 2020， 8： 137133-137149. 10.1109/access.2020.3011017
29	SINHA A， MALO P， DEB K. Evolutionary algorithm for bilevel optimization using approximations of the lower level optimal solution mapping［J］. European Journal of Operational Research， 2017， 257（2）： 395-411. 10.1016/j.ejor.2016.08.027
30	LIU Y H， LI H C， CHEN H F. A genetic algorithm for solving linear bilevel programming problems ［C］// Proceedings of the 14th International Conference on Computational Intelligence and Security. Piscataway： IEEE， 2018： 40-44. 10.1109/cis2018.2018.00017
31	LI H， ZHANG L， JIAO Y C. Solution for integer linear bilevel programming problems using orthogonal genetic algorithm［J］. Journal of Systems Engineering and Electronics， 2014， 25（3）： 443-451. 10.1109/jsee.2014.00051
32	YUE D J， GAO J Y， ZENG B， al at. A projection-based reformulation and decomposition algorithm for global optimization of a class of mixed integer bilevel linear programs［J］. Journal of Global Optimization， 2019， 73（1）： 27-57. 10.1007/s10898-018-0679-1
33	KALASHNIKOV V， FLORES MUÑIZ J G， KALASHNYKOVA N. Bilevel optimal tolls problems with non linear costs： a heuristic solution method［M］// KOSHELEVA O， SHARY S P， XIANG G， et al. Beyond Traditional Probabilistic Data Processing Techniques： Interval， Fuzzy etc. Methods and Their Applications， SCI 835. Cham： Springer， 2020： 481-516.

[1]	魏凤凤, 陈伟能. 分布式数据驱动的多约束进化优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1393-1400.
[2]	田野, 陈津津, 张兴义. 面向约束多目标优化的进化计算与梯度下降联合优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1386-1392.
[3]	田茂江, 陈鸣科, 堵威, 杜文莉. 面向大规模重叠问题的两阶段差分分组方法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1348-1354.
[4]	张莞婷, 杜文莉, 堵威. 基于多时间尺度协同的大规模原油调度进化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1355-1363.
[5]	赵佳伟, 陈雪峰, 冯亮, 候亚庆, 朱泽轩, Yew‑Soon Ong. 优化场景视角下的进化多任务优化综述[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1325-1337.
[6]	赵楷文, 王鹏, 童向荣. 基于双阶段搜索的约束进化多任务优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1415-1422.
[7]	黄亚伟, 钱雪忠, 宋威. 基于双档案种群大小自适应方法的改进差分进化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3844-3853.
[8]	黄杰, 武瑞梓, 李均利. 高效的自适应复杂网络鲁棒性优化算法[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3530-3539.
[9]	郭茂祖, 张雅喆, 赵玲玲. 基于空间语义和个体活动的电动汽车充电站选址方法[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2819-2827.
[10]	徐赛娟, 裴镇宇, 林佳炜, 刘耿耿. 基于多阶段搜索的约束多目标进化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2345-2351.
[11]	李二超, 程艳丽. 基于权重向量聚类的动态多目标进化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2226-2236.
[12]	高智慧, 韩萌, 刘淑娟, 李昂, 穆栋梁. 基于智能优化算法的高效用项集挖掘方法综述[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1676-1686.
[13]	王彬, 向甜, 吕艺东, 王晓帆. 基于NSGA‑Ⅱ的自适应多尺度特征通道分组优化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1401-1408.
[14]	高乾顺, 范纯龙, 李炎达, 滕一平. 基于差分进化的神经网络通用扰动生成方法[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3436-3442.
[15]	李二超, 张生辉. 基于新评价指标自适应预测的动态多目标优化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3178-3187.

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

Evolutionary algorithm based on approximation technique for solving bilevel programming problems

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 33

相关文章 15

编辑推荐

Metrics