基于混合蛙跳算法求解多维背包问题  

Solving multidimensional knapsack problem based on shuffled frog leaping algorithm

作　　者：刘陆洲 张晓霞 钟江文 LIU Luzhou;ZHANG Xiaoxia;ZHONG Jiangwen(School of Computer Science and Software Engineering,University of Science and Technology Liaoning,Anshan 114051,China)

机构地区：[1]辽宁科技大学计算机与软件工程学院,辽宁鞍山114051

出　　处：《辽宁科技大学学报》2020年第4期294-298,共5页Journal of University of Science and Technology Liaoning

基　　金：辽宁省大学生创新创业训练计划(101462019070)。

摘　　要：背包问题是一种典型的NP问题。混合蛙跳算法是一种生物仿真模拟的进化算法,利用该算法高效的搜索性能,建立基于MKP的数学理论模型。通过在局部搜索中加入遗传算法的基因交换和变异的方法,提出了一种计算性能更好的SFLA算法,把该算法应用于求解MKP问题。实验结果证明了基于混合蛙跳算法在解决多维背包问题时的有效性。The knapsack problem is a typical NP problem.The shuffled frog leaping algorithm is an evolutionary algorithm for biological simulation.A mathematical model based on MKP is built by utilizing the excellent search performance of the shuffled frog leaping algorithm.By adding gene exchange and variation of genetic algorithm into local search,a hybrid SFLA algorithm with better performance is proposed and applied to solve the MKP problem.Experimental results show that the hybrid algorithm is very effective and competitive in solving the multidimensional knapsack problem.

关 键 词：多维背包 蛙跳算法 遗传算法 

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