混合猴群算法求解折扣{0-1}背包问题  

Mixed Monkey Algorithm for Solving Discount Knapsack Problem

作　　者：肖颜 潘大志[1,2] 冯世强[1] XIAO Yan;PAN Dazhi;FENG Shiqiang(College of Mathematics and Information,China West Normal University,Nanchong 637009;Institute of Computing Method and Application Software,China West Normal University,Nanchong 637009)

机构地区：[1]西华师范大学数学与信息学院,南充637009 [2]西华师范大学计算方法与应用研究所,南充637009

出　　处：《计算机与数字工程》2021年第2期231-237,241,共8页Computer & Digital Engineering

基　　金：国家自然科学基金项目(编号:11871059);四川省教育厅自然科学基金项目(编号:18ZA0469);西华师范大学英才科研基金项目(编号:17YC385);西华师范大学校级科研团队(编号:CXTD2015-4)资助。

摘　　要：针对折扣{0-1}背包问题(D{0-1}KP),当问题规模较大时,精确算法求解比较困难。基于此,将贪心核加速算子与猴群算法融合提出一种混合猴群算法(MMA)用于求解D{0-1}KP问题。同时在MMA算法的爬过程中引入诱导因子,避免爬过程陷入局部最优,再利用修复策略对不可行解进行修复。通过仿真实验,结果表明MMA算法求解大规模D{0-1}KP问题的计算性能有效,求解结果可行。For the discount{0-1}knapsack problem(D{0-1}KP),when the problem size is large,the exact algorithm is dif⁃ficult to solve.Based on this problem,this paper combines the greedy kernel acceleration operator with the monkey algorithm,and proposes a mixed monkey algorithm(MMA)to solve the D{0-1}KP problem.At the same time,the inductive factor is introduced in the process of climbing the MMA algorithm to avoid the localization of the climbing process,and then the repair strategy is used to repair the infeasible solution.Through simulation experiments,the results show that the MMA algorithm is effective in solving the computational performance of the large-scale D{0-1}KP problem,and the solution result is feasible.

关 键 词：猴群算法 折扣{0-1}问题背包 诱导因子 编码修复 贪心核加速算子 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]