贪心二进制狮群优化算法求解多维背包问题

杨 艳，刘生建，周永权

（1.广州大学华软软件学院，广州510990； 2.广西民族大学信息科学与工程学院，南宁530006）（∗通信作者电子邮箱yangyan_08@yeah.net）

0 引言

多维背包问题（Multidimensional Knapsack Problem,MKP）是一类典型的组合优化问题，有着广泛的实际应用价值，如项目决策与规划、资源分配、资金预算、货物装载等，对其求解方法的研究无论是在理论上还是实践中都具有一定的意义［1］。求解MKP主要有精确算法和启发式算法两大类：精确算法的时间复杂性都是呈指数增长的，主要用于求解规模相对较小的问题，对大规模问题依赖智能优化算法解决，常见的算法有粒子群优化算法、烟花算法、狼群算法、布谷鸟搜索算法、蚁群算法等［2-9］；进化算法多采用精英策略，在具有高进化效率的同时，存在易陷入局部最优解的局限性。文献［2-3］提出将连续的粒子群优化算法通过转换函数生成离散粒子群算法，并用于求解MKP，为求解离散问题提供了一种新方法。二进制反向烟花算法求解MKP具有良好的寻优效果，尤其是在背包维度高、物品数量多的问题中具有良好的寻优能力［6］；二进制狼群算法求解MKP时减小了陷入局部极值的概率［7］；二进制布谷鸟算法求解背包问题时提高了算法求解精度和收敛速度［8］；二进制蚁群算法求解背包问题时提高了算法的全局搜索能力［9］。本文受以上算法思想的启发，通过改进狮群算法求解MKP。

受狮群协作捕猎的启发，文献［10］提出一种新的群智能优化算法——狮群算法，并验证其良好的计算鲁棒性和全局搜索能力，但其主要用于连续函数优化问题。……