摘要
背包问题是一种典型的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.
作者
刘陆洲
张晓霞
钟江文
LIU Luzhou;ZHANG Xiaoxia;ZHONG Jiangwen(School of Computer Science and Software Engineering,University of Science and Technology Liaoning,Anshan 114051,China)
出处
《辽宁科技大学学报》
CAS
2020年第4期294-298,共5页
Journal of University of Science and Technology Liaoning
基金
辽宁省大学生创新创业训练计划(101462019070)。
关键词
多维背包
蛙跳算法
遗传算法
multidimensional backpack
frog leaping algorithm
genetic algorithm
