一种改进的模拟退火萤火虫混合算法求解0/1背包问题  

An Improved Simulated Annealing Firefly Hybrid Algorithm for 0/1 Knapsack Problem

作　　者：任静敏 潘大志[1] REN Jingmin;PAN Dazhi(College of Mathematics and Information,China West Normal University,Nanchong,Sichuan 637009)

机构地区：[1]西华师范大学数学与信息学院

出　　处：《绵阳师范学院学报》2020年第2期93-99,共7页Journal of Mianyang Teachers＇ College

基　　金：国家自然科学基金(11371015);四川省教育厅自然科学基金(18ZA0469);西华师范大学校级科研团队(CXTD2015-4);西华师范大学英才基金(17YC385)

摘　　要：根据萤火虫算法自身特点,本文提出一种基于模拟退火的改进萤火虫算法,并用于求解0-1背包问题.该算法在模拟退火过程中利用萤火虫算法搜索新解,采用贪心修复算子对不可行解进行修正.每一次退火操作完成时,对萤火虫种群实行变异操作,增强萤火虫的全局搜索能力.本算法在求解0-1背包问题时,能及时跳出局部最优,在算法初期增强全局搜索能力,在算法后期加快收敛速度.通过仿真实验表明,该算法可较好的求解0-1背包问题.According to the characteristics of the firefly algorithm,this paper proposes an improved firefly algorithm based on simulated annealing,which is used to solve the 0-1 knapsack problem.In the simulated annealing process,the algorithm used the firefly al-gorithm to spread the new solution in the global search.When solving the 0-1 knapsack problem,the greedy repair operator was used to correct the infeasible solution.When each annealing operation is completed,the firefly population was mutated to enhance the global search ability of the firefly.When solving the 0-1 knapsack problem,the algorithm could jump out of the local optimum in time,enhance the global search ability in the early stage of the algorithm,and accelerate the convergence speed in the later stage of the algorithm.Simulation results showed that the algorithm could better solve the 0-1 knapsack problem.

关 键 词：萤火虫算法 0/1背包问题 模拟退火算法 变异操作 贪心修复算子 

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