求解不确定双层背包问题的改进二进制狼群算法

吴虎胜; 薛俊杰; 肖人彬; 胡锦强

doi:10.1631/FITEE.1900437

Your Location：

Home >

Browse articles >

求解不确定双层背包问题的改进二进制狼群算法

常规文章 | Updated：2022-05-19

- 求解不确定双层背包问题的改进二进制狼群算法
- Uncertain bilevel knapsack problem based on an improved binary wolf pack algorithm
- 信息与电子工程前沿（英文） 2020年21卷第9期页码：1356-1368
- Affiliations：
  
  School of Equipment Management and Support, Armed Police Force Engineering University, Xi'an 710086, China
  Air Traffic Control and Navigation College, Air Force Engineering University, Xi'an 710051, China
  School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China
- Author bio：
  
  [ "Hu-sheng WU, E-mail: wuhusheng0421@163.com" ]
  [ "Jun-jie XUE, E-mail:1019609875@qq.com" ]
  Ren-bin XIAO, E-mail: rbxiao@hust.edu.cn
  [ "Jin-qiang HU, E-mail:hujinqiang002@163.com" ]
- Funds：
  
  Project supported by the National Science and Technology Innovation 2030 Major Project of the Ministry of Science and Technology of China (No. 2018AAA0101200), the National Natural Science Foundation of China (No. 61502534), the Natural Science Foundation of Shaanxi Province, China (No. 2020JQ-493), and the Domain Foundation of China (No. 61400010304)
- DOI：10.1631/FITEE.1900437
  中图分类号： TP18
- 收稿：2019-08-26，
  
  修回：2020-;4-10，
  
  网络出版：2020-06-09，
  
  纸质出版：2020-09
- Accepted：
Scan QR Code
吴虎胜, 薛俊杰, 肖人彬, 等. 求解不确定双层背包问题的改进二进制狼群算法[J]. 信息与电子工程前沿（英文）, 2020,21(9):1356-1368.

Hu-sheng WU, Jun-jie XUE, Ren-bin XIAO, et al. Uncertain bilevel knapsack problem based on an improved binary wolf pack algorithm[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(9): 1356-1368.
吴虎胜, 薛俊杰, 肖人彬, 等. 求解不确定双层背包问题的改进二进制狼群算法[J]. 信息与电子工程前沿（英文）, 2020,21(9):1356-1368. DOI： 10.1631/FITEE.1900437.

Hu-sheng WU, Jun-jie XUE, Ren-bin XIAO, et al. Uncertain bilevel knapsack problem based on an improved binary wolf pack algorithm[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(9): 1356-1368. DOI： 10.1631/FITEE.1900437.

摘要

为解决双层背包问题中的不确定性，提出一种不确定双层背包问题（uncertain bilevel knapsack problem

UBKP）模型。通过定义期望值纳什均衡（

Nash equilibrium）和期望值斯塔克尔伯格-纳什均衡（

Stackelberg-Nashe quilibrium），给出UBKP问题的不确定解。为提高不确定解的计算效率，构造一种改进的二进制狼群算法。该算法由一个规则（头狼规则）、两个算子（反向算子和移动算子）和三种智能行为（游走、智能猎杀和种群更新行为）组成。以某装备运输问题为实例，验证了UBKP模型及/不确定解的有效性。

Abstract

To address indeterminism in the bilevel knapsack problem

an uncertain bilevel knapsack problem (UBKP) model is proposed. Then

an uncertain solution for UBKP is proposed by defining the

$$\mathcal{P}$$

Nash equilibrium and

$$\mathcal{P}$$

Stackelberg–Nash equilibrium. To improve the computational efficiency of the uncertain solution

an evolutionary algorithm

the improved binary wolf pack algorithm

is constructed with one rule (wolf leader regulation)

two operators (invert operator and move operator)

and three intelligent behaviors (scouting behavior

intelligent hunting behavior

and upgrading). The UBKP model and the

$$\mathcal{P}$$

uncertain solution are applied to an armament transportation problem as a case study.

关键词

Keywords

references

T Bai , , , J Wei , , , WW Yang , , , 等 . . Multi-objective parameter estimation of improved Muskingum model by wolf pack algorithm and its application in upper Hanjiang River, China . . Water , , 2018 . . 10 ( ( 10 ): ): 1415 DOI: 10.3390/w10101415 http://doi.org/10.3390/w10101415 . .

L Brotcorne , , , S Hanafi , , , R Mansi . . One-level reformulation of the bilevel knapsack problem using dynamic programming . . Dis Optim , , 2013 . . 10 ( ( 1 ): ): 1 - - 10 . . DOI: 10.1016/j.disopt.2012.09.001 http://doi.org/10.1016/j.disopt.2012.09.001 . .

A Caprara , , , M Carvalho , , , A Lodi , , , 等 . . A study on the computational complexity of the bilevel knapsack problem . . SIAM J Optim , , 2014 . . 24 ( ( 2 ): ): 823 - - 838 . . DOI: 10.1137/130906593 http://doi.org/10.1137/130906593 . .

M Carvalho , , , A Lodi , , , P Marcotte . . A polynomial algorithm for a continuous bilevel knapsack problem . . Oper Res Lett , , 2018 . . 46 ( ( 2 ): ): 185 - - 188 . . DOI: 10.1016/j.orl.2017.12.009 http://doi.org/10.1016/j.orl.2017.12.009 . .

M Chih , , , CJ Lin , , , MS Chern , , , 等 . . Particle swarm optimization with time-varying acceleration coefficients for the multidimensional knapsack problem . . Appl Math Model , , 2014 . . 38 ( ( 4 ): ): 1338 - - 1350 . . DOI: 10.1016/j.apm.2013.08.009 http://doi.org/10.1016/j.apm.2013.08.009 . .

AM Cohn , , , C Barnhart . . The stochastic knapsack problem with random weights: a heuristic approach to robust transportation planning . . Proc Triennial Symp on Transportation Analysis , , 1998 . . p.1 - - 13 . . . .

S Dempe , , , K Richter . . Bilevel programming with knapsack constraints . . Centr Eur J Oper Res , , 2000 . . 8 ( ( 2 ): ): 93 - - 107 . . . .

F Gao , , , G Cui , , , ZB Wu , , , 等 . . Virus-evolutionary particle swarm optimization algorithm for knapsack problem . . J Harbin Inst Technol , , 2009 . . 41 ( ( 6 ): ): 103 - - 107 . . . .

YJ Gao , , , FM Zhang , , , Y Zhao , , , 等 . . A novel quantum-inspired binary wolf pack algorithm for difficult knapsack problem . . Int J Wirel Mob Comput , , 2019 . . 16 ( ( 3 ): ): 222 - - 232 . . DOI: 10.1504/IJWMC.2019.099861 http://doi.org/10.1504/IJWMC.2019.099861 . .

A Gherboudj , , , A Layeb , , , S Chikhi . . Solving 0-1 knapsack problems by a discrete binary version of cuckoo search algorithm . . Int J Bio-Inspir Comput , , 2012 . . 4 ( ( 4 ): ): 229 - - 236 . . DOI: 10.1504/IJBIC.2012.048063 http://doi.org/10.1504/IJBIC.2012.048063 . .

ZH Han , , , XT Tian , , , XF Ma , , , 等 . . Scheduling for re-entrant hybrid flowshop based on wolf pack algorithm . . IOP Conf Ser Mater Sci Eng , , 2018 . . 382 ( ( 3 ): ): 032007 DOI: 10.1088/1757-899X/382/3/032007 http://doi.org/10.1088/1757-899X/382/3/032007 . .

H Li , , , L Zhang , , , YC Jiao . . Solution for integer linear bilevel programming problems using orthogonal genetic algorithm . . J Syst Eng Electron , , 2014 . . 25 ( ( 3 ): ): 443 - - 451 . . DOI: 10.1109/JSEE.2014.00051 http://doi.org/10.1109/JSEE.2014.00051 . .

H Li , , , RB Xiao , , , HS Wu . . Modelling for combat task allocation problem of aerial swarm and its solution using wolf pack algorithm . . Int J Innov Comput Appl , , 2016 . . 7 ( ( 1 ): ): 50 - - 59 . . DOI: 10.1504/IJICA.2016.075473 http://doi.org/10.1504/IJICA.2016.075473 . .

B Liu . . Some research problems in uncertainty theory . . J Uncert Syst , , 2009a . . 3 ( ( 1 ): ): 3 - - 10 . . . .

B Liu . . Theory and Practice of Uncertain Programming , , : : Berlin, Germany Springer Verlag , , 2009b . . .

B Liu . . Uncertainty Theory: a Branch of Mathematics for Modeling Human Uncertainty , , : : Berlin, Germany Springer Verlag , , 2010 . . .

B Liu . . Uncertainty Theory (5 th Ed.) , , : : Berlin, Germany Springer Verlag , , 2016 . . .

JQ Liu , , , YC He , , , QQ Gu . . Solving knapsack problem based on discrete particle swarm optimization . . Comput Eng Des , , 2007 . . 28 ( ( 13 ): ): 3189 - - 3191, 3204 . . DOI: 10.3969/j.issn.1000-7024.2007.13.052 http://doi.org/10.3969/j.issn.1000-7024.2007.13.052 . .

OY Özaltın , , , OA Prokopyev , , , AJ Schaefer . . The bilevel knapsack problem with stochastic right-hand sides . . Oper Res Lett , , 2010 . . 38 ( ( 4 ): ): 328 - - 333 . . DOI: 10.1016/j.orl.2010.04.005 http://doi.org/10.1016/j.orl.2010.04.005 . .

J Qian , , , JG Zheng . . Greedy quantum-inspired evolutionary algorithm for quadratic knapsack problem . . Comput Integr Manuf Syst , , 2012 . . 18 ( ( 9 ): ): 2003 - - 2011 . . . .

X Qiu , , , W Kern . . Improved approximation algorithms for a bilevel knapsack problem . . Theor Comput Sci , , 2015 . . 595 ( ( 30 ): ): 120 - - 129 . . DOI: 10.1016/j.tcs.2015.06.027 http://doi.org/10.1016/j.tcs.2015.06.027 . .

R Wang , , , N Guo , , , FH Xiang , , , 等 . . An improved quantum genetic algorithm with mutation and its application to 0-1 knapsack problem . . Proc Int Conf on Measurement, Information and Control , , 2012 . . p.484 - - 488 . . DOI: 10.1109/MIC.2012.6273347 http://doi.org/10.1109/MIC.2012.6273347 . .

ZT Wang , , , JS Guo , , , MF Zheng , , , 等 . . A new approach for uncertain multiobjective programming problem based on $\mathcal{P}$ E principle . . J Ind Manag Optim , , 2015 . . 11 ( ( 1 ): ): 13 - - 26 . . DOI: 10.3934/jimo.2015.11.13 http://doi.org/10.3934/jimo.2015.11.13 . .

HS Wu , , , FM Zhang , , , LS Wu . . New swarm intelligence algorithm―wolf pack algorithm . . Syst Eng Electron , , 2013 . . 35 ( ( 11 ): ): 2430 - - 2438 . . . .

JJ Xue , , , Y Wang , , , H Li , , , 等 . . A smart wolf pack algorithm and its convergence analysis . . Contr Dec , , 2016 . . 31 ( ( 12 ): ): 2131 - - 2139 . . DOI: 10.13195/j.kzyjc.2015.1202 http://doi.org/10.13195/j.kzyjc.2015.1202 . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

On robustness of an AMB suspended energy storage flywheel platform under characteristic model based all-coefficient adaptive control laws

Supply chain network design under uncertainty with new insights from contracts