冯艳红 王改革 李明亮 李 晰

组合优化问题(Combinatorial Optimization Pro-blem, COP)的求解一直是运筹学领域重要的研究主题之一.典型的组合优化问题包括:作业车间调度问题(Job Shop Scheduling Problem, JSSP)[1-2],图着色问题(Graph Coloring Problem, GCP)[3],车辆路径规划问题(Vehicle Routing Problem, VRP)[4],旅行商问题(Travelling Salesman Problem, TSP)[5],多维背包问题(Multidimensional Knapsack Problem, MKP)[6].

多需求多维背包问题(Multidemand MKP, MDMKP)[7]是MKP的一个重要扩展,也被证明是一类复杂的NP-hard问题.相比MKP,MDMKP包含一组与背包约束冲突的需求约束,是一类更难求解的多约束0-1规划问题.现实生活中的很多问题可以建模为MDMKP,包括设备配置、选址方案设计、投资预算、证券选择等,但是,MDMKP并未引起广大学者更多的关注.

目前,针对MDMKP问题的求解分为两类:确切性算法(Exact Algorithm)和启发式算法(Heuristic Algorithm).Cappanera等[7]提出嵌套禁忌搜索启发式算法,在标准禁忌搜索算法中增加扰动策略.Gortázar等[8]介绍一种黑盒分散搜索算法,特别提出一种静态罚函数法,处理MDMKP问题的约束.Arntzen等[9]提出交替控制树搜索框架,交替使用确切性算法和启发式算法求解问题.Lai等[10]提出高效的基于两阶段解的禁忌搜索算法.Al-Shihabi[11]提出基于核思想的优化框架,更新28个已知最优解.因此,寻找有效的方法解决MDMKP问题是有意义的.

群智能算法[12-13]是利用群体智能高效求解优化问题的方法,具有不依赖梯度信息、对待求解问题无需连续、可导等特点,已被广泛应用于求解各类优化问题,特别是组合优化问题.受蛾子趋光性和莱维飞行的启发,Wang[14]提出蛾子搜索算法(Moth Search, MS),基于莱维飞行算子(Lévy Flight Ope-rator, LFO)和直接飞行算子(Straight Flight Ope- rator, SFO)实现种群中个体的更新.目前,MS已在数值优化、约束优化、多目标……