Full Text:   <254>

Summary:  <10>

CLC number: TP18

On-line Access: 2020-09-09

Received: 2019-08-26

Revision Accepted: 2019-12-02

Crosschecked: 2020-04-10

Cited: 0

Clicked: 341

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Hu-sheng Wu

https://orcid.org/0000-0003-0692-7467

Ren-bin Xiao

https://orcid.org/0000-0003-0951-2734

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2020 Vol.21 No.9 P.1356-1368

http://doi.org/10.1631/FITEE.1900437


Uncertain bilevel knapsack problem based on an improved binary wolf pack algorithm


Author(s):  Hu-sheng Wu, Jun-jie Xue, Ren-bin Xiao, Jin-qiang Hu

Affiliation(s):  School of Equipment Management and Support, Armed Police Force Engineering University, Xi’an 710086, China; more

Corresponding email(s):   wuhusheng0421@163.com, 1019609875@qq.com, rbxiao@hust.edu.cn, hujinqiang002@163.com

Key Words:  Bilevel knapsack problem, Uncertainty, Improved binary wolf pack algorithm


Hu-sheng Wu, Jun-jie Xue, Ren-bin Xiao, Jin-qiang Hu. Uncertain bilevel knapsack problem based on an improved binary wolf pack algorithm[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(9): 1356-1368.

@article{title="Uncertain bilevel knapsack problem based on an improved binary wolf pack algorithm",
author="Hu-sheng Wu, Jun-jie Xue, Ren-bin Xiao, Jin-qiang Hu",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="21",
number="9",
pages="1356-1368",
year="2020",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.1900437"
}

%0 Journal Article
%T Uncertain bilevel knapsack problem based on an improved binary wolf pack algorithm
%A Hu-sheng Wu
%A Jun-jie Xue
%A Ren-bin Xiao
%A Jin-qiang Hu
%J Frontiers of Information Technology & Electronic Engineering
%V 21
%N 9
%P 1356-1368
%@ 2095-9184
%D 2020
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1900437

TY - JOUR
T1 - Uncertain bilevel knapsack problem based on an improved binary wolf pack algorithm
A1 - Hu-sheng Wu
A1 - Jun-jie Xue
A1 - Ren-bin Xiao
A1 - Jin-qiang Hu
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 21
IS - 9
SP - 1356
EP - 1368
%@ 2095-9184
Y1 - 2020
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1900437


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 PE Nash equilibrium and PE 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 PE uncertain solution are applied to an armament transportation problem as a case study.

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

吴虎胜1,薛俊杰2,肖人彬3,胡锦强1
1武警工程大学装备管理与保障学院,中国西安市,710086
2空军工程大学空管领航学院,中国西安市,710051
3华中科技大学人工智能与自动化学院,中国武汉市,430074

摘要:为解决双层背包问题中的不确定性,提出一种不确定双层背包问题(uncertain bilevel knapsack problem, UBKP)模型。通过定义期望值纳什均衡(PE Nash equilibrium)和期望值斯塔克尔伯格-纳什均衡(PE Stackelberg-Nashe quilibrium),给出UBKP问题的不确定解。为提高不确定解的计算效率,构造一种改进的二进制狼群算法。该算法由一个规则(头狼规则)、两个算子(反向算子和移动算子)和三种智能行为(游走、智能猎杀和种群更新行为)组成。以某装备运输问题为实例,验证了UBKP模型及/不确定解的有效性。

关键词:双层背包问题;不确定性;改进的二进制狼群算法

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1]Bai T, Wei J, Yang WW, et al., 2018. Multi-objective parameter estimation of improved Muskingum model by wolf pack algorithm and its application in upper Hanjiang River, China. Water, 10(10):1415.

[2]Brotcorne L, Hanafi S, Mansi R, 2013. One-level reformulation of the bilevel knapsack problem using dynamic programming. Dis Optim, 10(1):1-10.

[3]Caprara A, Carvalho M, Lodi A, et al., 2014. A study on the computational complexity of the bilevel knapsack problem. SIAM J Optim, 24(2):823-838.

[4]Carvalho M, Lodi A, Marcotte P, 2018. A polynomial algorithm for a continuous bilevel knapsack problem. Oper Res Lett, 46(2):185-188.

[5]Chih M, Lin CJ, Chern MS, et al., 2014. Particle swarm optimization with time-varying acceleration coefficients for the multidimensional knapsack problem. Appl Math Model, 38(4):1338-1350.

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

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

[8]Gao F, Cui G, Wu ZB, et al., 2009. Virus-evolutionary particle swarm optimization algorithm for knapsack problem. J Harbin Inst Technol, 41(6):103-107 (in Chinese).

[9]Gao YJ, Zhang FM, Zhao Y, et al., 2019. A novel quantum- inspired binary wolf pack algorithm for difficult knapsack problem. Int J Wirel Mob Comput, 16(3):222-232.

[10]Gherboudj A, Layeb A, Chikhi S, 2012. Solving 0-1 knapsack problems by a discrete binary version of cuckoo search algorithm. Int J Bio-Inspir Comput, 4(4):229-236.

[11]Han ZH, Tian XT, Ma XF, et al., 2018. Scheduling for re-entrant hybrid flowshop based on wolf pack algorithm. IOP Conf Ser Mater Sci Eng, 382(3):032007.

[12]Li H, Zhang L, Jiao YC, 2014. Solution for integer linear bilevel programming problems using orthogonal genetic algorithm. J Syst Eng Electron, 25(3):443-451.

[13]Li H, Xiao RB, Wu HS, 2016. Modelling for combat task allocation problem of aerial swarm and its solution using wolf pack algorithm. Int J Innov Comput Appl, 7(1): 50-59.

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

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

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

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

[18]Liu JQ, He YC, Gu QQ, 2007. Solving knapsack problem based on discrete particle swarm optimization. Comput Eng Des, 28(13):3189-3191, 3204 (in Chinese).

[19]Özaltın OY, Prokopyev OA, Schaefer AJ, 2010. The bilevel knapsack problem with stochastic right-hand sides. Oper Res Lett, 38(4):328-333.

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

[21]Qiu X, Kern W, 2015. Improved approximation algorithms for a bilevel knapsack problem. Theor Comput Sci, 595(30): 120-129.

[22]Wang R, Guo N, Xiang FH, et al., 2012. An improved quantum genetic algorithm with mutation and its application to 0-1 knapsack problem. Proc Int Conf on Measurement, Information and Control, p.484-488.

[23]Wang ZT, Guo JS, Zheng MF, et al., 2015. A new approach for uncertain multiobjective programming problem based on E principle. J Ind Manag Optim, 11(1):13-26.

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

[25]Xue JJ, Wang Y, Li H, et al., 2016. A smart wolf pack algorithm and its convergence analysis. Contr Dec, 31(12):2131-2139 (in Chinese).

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE