Evolutionary algorithm based on approximation technique for solving bilevel programming problems

doi:10.11772/j.issn.1001-9081.2021061079

Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (8): 2511-2518.DOI: 10.11772/j.issn.1001-9081.2021061079

• Advanced computing • Previous Articles

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)

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

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

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

通讯作者: 李和成
作者简介:沈瑜（1995—），女，重庆人，硕士研究生，主要研究方向：最优化；
李和成（1973—），男，青海西宁人，教授，博士生导师，博士，主要研究方向：智能计算、最优化；
陈黎娟（1997—），女，甘肃兰州人，硕士研究生，主要研究方向：最优化。
基金资助:
国家自然科学基金资助项目(61966030);青海省自然科学基金资助项目(2018-ZJ-901)

Abstract

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

摘要：

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

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

CLC Number:

TP301.6

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.

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

Figures/Tables 13

Fig. 1 Schematic diagrams of crossover operation and mutation operation

Fig. 2 Flowchart of the proposed algorithm

Fig. 3 Inducible region of Equation（10）

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）

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）

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

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

Fig. 4 Scatter diagram of follower solutions

Fig. 5 Curves of objective functions

Fig. 6 Road network topology

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

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

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

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

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）

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

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

References 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]	Feifan SHI, Xuhua SHI. Adaptive reference vector based constrained multi-objective evolutionary algorithm [J]. Journal of Computer Applications, 2022, 42(2): 542-549.
[2]	Wei LI, Yaochi FAN, Qiaoyong JIANG, Lei WANG, Qingzheng XU. Variable convolutional autoencoder method based on teaching-learning-based optimization for medical image classification [J]. Journal of Computer Applications, 2022, 42(2): 592-598.
[3]	Erchao LI, Yuyan MAO. Constrained multi-objective evolutionary algorithm based on space shrinking technique [J]. Journal of Computer Applications, 2021, 41(12): 3419-3425.
[4]	YAN Huajian, ZHANG Guofu, SU Zhaopin, LIU Yang. Modeling and solving of high-dimensional multi-objective adaptive allocation for emergency relief supplies [J]. Journal of Computer Applications, 2020, 40(8): 2410-2419.
[5]	YIN Shengnan, LI Yinzhen, ZHANG Changze. High-speed railway fare adjustment strategy based on passenger flow assignment [J]. Journal of Computer Applications, 2020, 40(1): 278-283.
[6]	GUO Houqian, WANG Weiwei, SHANG Ying, ZHAO Ruilian. Weak mutation test case set generation based on dynamic set evolutionary algorithm [J]. Journal of Computer Applications, 2017, 37(9): 2659-2664.
[7]	XIONG Ruiqi, MA Changxi. Robust vehicle route optimization for multi-depot hazardous materials transportation [J]. Journal of Computer Applications, 2017, 37(5): 1485-1490.
[8]	LYU Hongwu, GU Lei, WANG Huiqiang, ZOU Shichen, FENG Guangsheng. Quasi-optimal period computation model for hierarchical checkpoint protocol [J]. Journal of Computer Applications, 2017, 37(1): 103-107.
[9]	ZHANG Wenqiang, LU Jiaming, ZHANG Hongmei. Fast multi-objective hybrid evolutionary algorithm for flow shop scheduling problem [J]. Journal of Computer Applications, 2016, 36(4): 1015-1021.
[10]	SONG Yuezhen, PEI Tengda, PEI Bingnan. Improved artificial bee colony algorithm based on central solution [J]. Journal of Computer Applications, 2016, 36(4): 1022-1026.
[11]	TAN Yang, NING Ke, CHEN Lin. Chromosomal translocation-based Dynamic evolutionary algorithm [J]. Journal of Computer Applications, 2015, 35(9): 2584-2589.
[12]	NI Zhiwei, FANG Qinghua, LI Rongrong, LI Yiming. Improved ant colony optimization for QoS-based Web service composition optimization [J]. Journal of Computer Applications, 2015, 35(8): 2238-2243.
[13]	QI Xuemei, WANG Hongtao, CHEN Fulong, TANG Qimei, SUN Yunxiang. Novel quantum differential evolutionary algorithm for blocking flowshop scheduling [J]. Journal of Computer Applications, 2015, 35(3): 663-667.
[14]	LIU Xiaohong, QU Zhijian, CAO Yanfeng, ZHANG Xianwei, FENG Gang. Multi-universe parallel quantum-inspired evolutionary algorithm based on adaptive mechanism [J]. Journal of Computer Applications, 2015, 35(2): 369-373.
[15]	HUANG Xiangdong, XIA Shixiong, NIU Qiang, ZHAO Zhijun. Improved teaching-learning-based optimization algorithm based on K-means [J]. Journal of Computer Applications, 2015, 35(11): 3126-3129.

Evolutionary algorithm based on approximation technique for solving bilevel programming problems

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 33

Related Articles 15

Recommended Articles

Metrics