融合核搜索的演化算法求解多维背包问题  

Improved Heuristic Algorithm with Kernel Search for Solving Multidimensional Knapsack Problem

作　　者：罗金炎[1] LUO Jinyan(Department of Mathematics and Data Science,Minjiang University,Fuzhou,Fujian 350108,China)

机构地区：[1]闽江学院数学与数据科学学院,福建福州350108

出　　处：《闽江学院学报》2018年第5期40-47,共8页Journal of Minjiang University

基　　金：福建省自然科学基金项目(2017J01769)

摘　　要：多维背包问题(MKP)具NP难、约束强的特点,特别是高维MKP的求解比较困难.核问题的引入可以降低问题的维度,减少算法的搜索空间,提高效率.依据定标效用指标运用贪婪方法确定MKP的核问题,避免了使用收敛速度慢的优化算法.此外,在求解MKP的核问题阶段基于粒子群算法的寻优模式改进算法的位取值方式,减小了在进化过程中停滞于局部解的概率;并在算法中引入了局部搜索策略,以提高解决方案的质量.通过对高维MKP实例的测试,验证了算法在求解质量和效率方面的优势.Multidimensional knapsack problem （MKP） is characterized by NP difficulty and strong constraint, especially the solution of high-dimensional MKP. The introduction of the core problem can reduce the dimension of the problem, reduce the search space of the algorithm and improve efficiency. According to the utility index, the greedy method is used to detemine the core problem of MKP, avoiding the use of slow convergence optimization algorithm. In addition, the bit value method is used to reduce the probability of local solution in the evolution process, and the local search strategy is introduced in the algorithm to improve the quality of the solution. Simulation results on benchmark instances show that the proposed algorithm is highly competitive in terms of solution quality and efficiency.

关 键 词：多维背包问题 核搜索 改进二进制粒子群算法 局部搜索 

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