求解0-1背包问题的萤火虫算法  

Firefly algorithm for solving 0-1 knapsack problem

作　　者：莫愿斌[1,2] 马彦追[1] 郑巧燕[1] 

机构地区：[1]广西民族大学理学院,广西南宁530006 [2]广西民族大学广西混杂计算与集成电路设计分析重点实验室,广西南宁530006

出　　处：《计算机工程与设计》2014年第8期2778-2784,共7页Computer Engineering and Design

基　　金：中国博士后基金项目(2012M511711);广西混杂计算与集成电路设计分析重点实验室开放基金项目(2012HCI08);广西教育厅基金项目(201204LX082);广西民族大学基金项目(2011MDYB030)

摘　　要：将贪心策略和变异策略与萤火虫算法相结合,提出一种求解0-1背包问题的贪心萤火虫算法。通过增加贪心策略和变异策略,在一定程度上能使萤火虫跳出局部极值,提高算法的性能。通过对多个实例的仿真,将该算法与其它算法如贪心遗传算法、贪心微粒群算法进行对比,对比结果表明,该算法在求解0-1背包问题上具有更强约束处理能力和快速收敛效果。By integrating the greedy and mutation strategy into the firefly algorithm, a greedy firefly algorithm was proposed to solve 0-1 knapsack problem. The firefly jumped out of the local optimum to a certain extent through adding the greedy and mutation strategy, thus the optimization performance of the algorithm was improved. Through the simulation of some examples and contrasting with other algorithms, such as greedy genetic algorithm and greedy discrete particle swarm optimization, the results of the experiment show that the proposed algorithm has stronger constraint handing ability and higher rate of convergence in solving 0-1 knapsack problem.

关 键 词：萤火虫算法 贪心策略 变异策略 背包问题 局部极值 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]