计算机应用

作者：徐小平, 徐丽, 王峰, 刘龙

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

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

基金：国家自然科学基金资助项目（61773016）；陕西省创新能力支撑计划项目（2020PT-023）；陕西省自然科学基础研究计划项目（2018JQ1089）。

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

来源：2020年第11期

《计算机应用》期刊编辑部

查看计算机应用杂志2020年第11期