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: 4659
Citations: Bibtex RefMan EndNote GB/T7714
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,in press.https://doi.org/10.1631/FITEE.1900437 @article{title="Uncertain bilevel knapsack problem based on an improved binary wolf pack algorithm", %0 Journal Article TY - JOUR
求解不确定双层背包问题的改进二进制狼群算法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). Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou
310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn Copyright © 2000 - 2024 Journal of Zhejiang University-SCIENCE |
Open peer comments: Debate/Discuss/Question/Opinion
<1>