基于Lagrange插值的学习猴群算法求解折扣｛0-1｝背包问题

doi:10.11772/j.issn.1001-9081.2020040482

计算机应用 ›› 2020, Vol. 40 ›› Issue (11): 3113-3118.DOI: 10.11772/j.issn.1001-9081.2020040482

基于Lagrange插值的学习猴群算法求解折扣｛0-1｝背包问题

徐小平¹, 徐丽¹, 王峰², 刘龙³

1. 西安理工大学理学院, 西安 710054;
2. 西安交通大学数学与统计学院, 西安 710049;
3. 西安理工大学自动化与信息工程学院, 西安 710048

收稿日期:2020-04-20 修回日期:2020-06-26 出版日期:2020-11-10 发布日期:2020-07-20
通讯作者: 徐丽(1995-),女,陕西安康人,硕士研究生,主要研究方向:智能算法;1396580639@qq.com
作者简介:徐小平(1973-),男,陕西蓝田人,教授,博士,主要研究方向:智能算法;王峰(1972-),女,河南兰考人,教授,博士,主要研究方向:智能算法;刘龙(1975-),男,陕西西安人,教授,博士,主要研究方向:机器学习
基金资助:
国家自然科学基金资助项目（61773016）；陕西省创新能力支撑计划项目（2020PT-023）；陕西省自然科学基础研究计划项目（2018JQ1089）。

Learning monkey algorithm based on Lagrange interpolation to solve discounted ｛0-1｝ knapsack problem

XU Xiaoping¹, XU Li¹, WANG Feng², LIU Long³

1. School of Sciences, Xi'an University of Technology, Xi'an Shaanxi 710054, China;
2. School of Mathematics and Statistics, Xi'an Jiaotong University, Xi'an Shaanxi 710049, China;
3. School of Automation and Information Engineering, Xi'an University of Technology, Xi'an Shaanxi 710048, China

Received:2020-04-20 Revised:2020-06-26 Online:2020-11-10 Published:2020-07-20
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61773016), the Shaanxi Provincial Innovation Capability Support Program (2020PT-023), the Shaanxi Natural Science Basic Research Program (2018JQ1089).

摘要/Abstract

摘要： 折扣｛0-1｝背包问题（D｛0-1｝KP）的目的是在不超过背包载重的前提下，使得装入背包的所有物品价值系数之和为最大。针对已有算法在求解规模大、复杂度高的D｛0-1｝KP时的求解精度低的问题，提出了Lagrange插值的学习猴群算法（LSTMA）。首先，在基本猴群算法的望过程中重新定义了视野长度；其次，在跳过程中引入了种群中最优的个体作为第二个支点，并调整搜索机制；最后，在跳过程之后引入Lagrange插值操作来提高算法的搜索性能。对四类实例的仿真结果表明：LSTMA在求解D｛0-1｝KP时的求解精度高于对比算法，并且具有良好的鲁棒性。

关键词: 折扣｛0-1｝背包问题, Lagrange插值, 猴群算法, 学习因子

Abstract: The purpose of the Discounted {0-1} Knapsack Problem (D{0-1}KP) is to maximize the sum of the value coefficients of all items loaded into the knapsack without exceeding the weight limit of the knapsack. In order to solve the problem of low accuracy when the existing algorithms solve the D{0-1}KP with large scale and high complexity, the Lagrange Interpolation based Learning Monkey Algorithm (LSTMA) was proposed. Firstly, the length of the visual field was redefined during the look process of the basic monkey algorithm. Then, the best individual in the population was introduced as the second pivot point and the search mechanism was adjusted during the jump process. Finally, the Lagrange interpolation operation was introduced after the jump process to improve the search performance of the algorithm. The simulation results on four types of examples show that LSMTA solves the D{0-1}KP with higher accuracy than the comparison algorithms, and it has good robustness.

Key words: Discounted {0-1} Knapsack Problem (D{0-1}KP), Lagrange interpolation, Monkey Algorithm (MA), learning factor

中图分类号:

TP301.6

徐小平, 徐丽, 王峰, 刘龙. 基于Lagrange插值的学习猴群算法求解折扣｛0-1｝背包问题[J]. 计算机应用, 2020, 40(11): 3113-3118.

XU Xiaoping, XU Li, WANG Feng, LIU Long. Learning monkey algorithm based on Lagrange interpolation to solve discounted ｛0-1｝ knapsack problem[J]. Journal of Computer Applications, 2020, 40(11): 3113-3118.

参考文献

[1] FENG Y,WANG G,LI W,et al. Multi-strategy monarch butterfly optimization algorithm for discounted{0-1}knapsack problem[J]. Neural Computing and Applications,2018,30(10):3019-3036.
[2] RONG A Y, FIGUEIRA J R, KLAMROTH K. Dynamic programming based algorithms for the discounted {0-1} knapsack problem[J]. Applied Mathematics and Computation,2012,218(12):6921-6933.
[3] HE Y,WANG X,HE Y,et al. Exact and approximate algorithms for discounted{0-1}knapsack problem[J]. Information Sciences, 2016,369:634-647.
[4] 贺毅朝, 王熙照, 李文斌, 等. 基于遗传算法求解折扣{0-1}背包问题的研究[J]. 计算机学报,2016,39(12):2614-2630.(HE Y C,WANG X Z,LI W B,et al. Research on genetic algorithms for the discounted {0-1} knapsack problem[J]. Chinese Journal of Computers,2016,39(12):2614-2630.)
[5] ZHU H,HE Y,WANG X,et al. Discrete differential evolutions for the discounted{0-1}knapsack problem[J]. International Journal of Bio-Inspired Computation,2017,10(4):219-238.
[6] ZHAO R, TANG W. Monkey algorithm for global numerical optimization[J]. Journal of Uncertain Systems,2008,2(3):165-176.
[7] LIANG Z. An improved monkey algorithm with dynamic adaptation[J]. Applied Mathematics and Computation,2013,222:645-657.
[8] 辛景舟, 周建庭, 杨俊, 等. 基于混沌猴群算法的结构有限元模型修正[J]. 科学技术与工程,2017,17(34):80-85.(XIN J Z, ZHOU J T,YANG J,et al. Finite element model updating based on chaotic monkey algorithm[J]. Science Technology and Engineering,2017,17(34):80-85.)
[9] 殷红, 杜国璋, 彭珍瑞, 等. 野草猴群算法的传感器优化布置方法研究[J]. 计算机工程与科学,2018,40(4):626-635.(YIN H,DU G Z,PENG Z R,et al. A weed monkey algorithm for optimal sensor placement[J]. Computer Engineering and Science, 2018,40(4):626-635.)
[10] ZHOU Y,CHEN X,ZHOU G. An improved monkey algorithm for a 0-1 knapsack problem[J]. Applied Soft Computing,2016,38:817-830.
[11] FENG Y,WANG G. Binary moth search algorithm for discounted {0-1} knapsack problem[J]. IEEE Access,2018,6:10708-10719.
[12] ABIYEV R H, TUNAY M. Experimental study of specific benchmarking functions for modified monkey algorithm[J]. Procedia Computer Science,2016,102:595-602.
[13] ZHANG K,HUANG Q,ZHANG Y,et al. Hybrid Lagrange interpolation differential evolution algorithm for path synthesis[J]. Mechanism and Machine Theory,2019,134:512-540.
[14] 吴聪聪, 贺毅朝, 陈嶷瑛, 等. 变异蝙蝠算法求解折扣{0-1}背包问题[J]. 计算机应用,2017,37(5):1292-1299.(WU C C,HE Y C,CHEN Y Y,et al. Mutated bat algorithm for solving discounted {0-1} knapsack problem[J]. Journal of Computer Applications,2017,37(5):1292-1299.)
[15] 杨澜, 惠飞, 侯俊, 等. 基于免疫进化的野草优化随机搜索算法[J]. 计算机技术与发展,2018,28(2):36-39,44.(YANG L, HUI F,HOU J,et al. An invasive weed optimization algorithm based on immune evolution[J]. Computer Technology and Development,2018,28(2):36-39,44.)
[16] 徐小平, 张东洁. 一种改进的猴群算法[J]. 计算机系统应用, 2017,26(6):193-197. (XU X P,ZHANG D J. Improved monkey algorithm[J]. Computer Systems and Applications, 2017,26(6):193-197.)
[17] OZCAN S,SIMSIR F. A new model based on artificial bee colony algorithm for preventive maintenance with replacement scheduling in continuous production lines[J]. Engineering Science and Technology,an International Journal,2019,22(6):1175-1186.
[18] LI J,DONG P. Global maximum power point tracking for solar power systems using the hybrid artificial fish swarm algorithm[J]. Global Energy Interconnection,2019,2(4):351-360.

基于Lagrange插值的学习猴群算法求解折扣｛0-1｝背包问题

Learning monkey algorithm based on Lagrange interpolation to solve discounted ｛0-1｝ knapsack problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

编辑推荐

Metrics

[1]	史文旭, 杨洋, 鲍胜利. 贪心核加速动态规划算法求解折扣{0-1}背包问题[J]. 计算机应用, 2019, 39(7): 1912-1917.
[2]	杨洋, 潘大志, 刘益, 谭代伦. 折扣{0-1}背包问题的简化新模型及遗传算法求解[J]. 计算机应用, 2019, 39(3): 656-662.
[3]	刘雪静, 贺毅朝, 路凤佳, 吴聪聪, 才秀凤. 基于Lévy飞行的差分乌鸦算法求解折扣{0-1}背包问题[J]. 计算机应用, 2018, 38(2): 433-442.
[4]	刘雪静, 贺毅朝, 路凤佳, 吴聪聪, 才秀凤. 基于差分演化策略的混沌乌鸦算法求解折扣{0-1}背包问题[J]. 计算机应用, 2018, 38(1): 137-145.
[5]	吴聪聪, 贺毅朝, 陈嶷瑛, 刘雪静, 才秀凤. 变异蝙蝠算法求解折扣{0-1}背包问题[J]. 计算机应用, 2017, 37(5): 1292-1299.
[6]	赵远东方正华. 带有权重函数学习因子的粒子群算法[J]. 计算机应用, 2013, 33(08): 2265-2268.
[7]	张敏黄强许周钊姜柏庄. 基于余弦函数改进的PSO算法及其仿真[J]. 计算机应用, 2013, 33(02): 319-322.
[8]	欧旭梁京章罗德相张新华. 利用前两代信息的改进粒子群优化算法[J]. 计算机应用, 2010, 30(2): 472-475.
[9]	殷凤梅侯整风. 可选子密钥的门限多秘密共享方案[J]. 计算机应用, 2007, 27(9): 2187-2188.
[10]	侯整风段笑言昂东宇. 基于(t,n)门限的代理签名方案[J]. 计算机应用, 2007, 27(3): 614-615.