计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (35): 39-41.DOI: 10.3778/j.issn.1002-8331.2010.35.011

• 研究、探讨 • 上一篇    下一篇

二进制混合蛙跳算法求解0-1背包问题

赵 洋1,单 娟2   

  1. 1.石家庄经济学院 信息工程系,石家庄 050031
    2.河北省大中专院校学生信息咨询与就业指导中心,石家庄 050061
  • 收稿日期:2010-06-03 修回日期:2010-09-06 出版日期:2010-12-11 发布日期:2010-12-11
  • 通讯作者: 赵 洋

Solving Knapsack problem based on binary shuffled frog-leaping algorithm

ZHAO Yang1,SHAN Juan2   

  1. 1.Information Engineering School,Shijiazhuang University of Economics,Shijiazhuang 050031,China
    2.Student Information and Employment Center for Colleges of Hebei Province,Shijiazhuang 050061,China
  • Received:2010-06-03 Revised:2010-09-06 Online:2010-12-11 Published:2010-12-11
  • Contact: ZHAO Yang

摘要: 为利用混合蛙跳算法(SFLA)求解具有二进制编码特点的组合优化问题,基于双重编码机制,提出了一种二进制混合蛙跳算法(记为BSFLA)。基于罚函数法和贪心变换策略,探讨了利用BSFLA求解背包问题(KP)的可行性与有效性。计算结果表明BSFLA与贪心策略相结合是求解KP问题的一种有效的新方法。

关键词: 混合蛙跳算法, 背包问题, 双重编码机制, 罚函数法, 贪心策略

Abstract: For solving combinatorial optimization problem with binary code using shuffled frog-leaping algorithm,propose a binary shuffled frog-leaping algorithm(for short BSFLA) based on double coding method.Then,combine BSFLA with penalty function method and greedy strategy,analyse the feasibility and validity of solving knapsack problem(KP) based on BSFLA.Computing results indicate that BSFLA combined greedy strategy is a new efficient method for KP.

Key words: shuffled frog-leaping algorithm, knapsack problem, double coding method, penalty function method, greedy strategy

中图分类号: