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

doi:10.3778/j.issn.1002-8331.2010.35.011

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

二进制混合蛙跳算法求解0-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 Yang¹，SHAN Juan²

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

摘要/Abstract

摘要： 为利用混合蛙跳算法（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

中图分类号:

TP18

赵洋¹，单娟². 二进制混合蛙跳算法求解0-1背包问题[J]. 计算机工程与应用, 2010, 46(35): 39-41.

ZHAO Yang¹，SHAN Juan². Solving Knapsack problem based on binary shuffled frog-leaping algorithm[J]. Computer Engineering and Applications, 2010, 46(35): 39-41.

[1]	郝翔，贺毅朝，朱晓斌，翟庆雷. 基于离散混合多宇宙算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(18): 103-113.
[2]	张铭，邓文瀚，林娟，钟一文. 改进蚁群优化算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(13): 85-95.
[3]	吴聪聪，贺毅朝，赵建立. 求解折扣{0-1}背包问题的新遗传算法[J]. 计算机工程与应用, 2020, 56(7): 57-66.
[4]	陈长倩，慕晓冬，牛犇，王立志. 结合高斯分布的改进二进制灰狼优化算法[J]. 计算机工程与应用, 2019, 55(13): 145-150.
[5]	李志强1，朱望纯1，张伟昆1，2. 区域停车诱导信息发布板的选址优化算法[J]. 计算机工程与应用, 2018, 54(8): 242-246.
[6]	杨洋1，潘大志1，贺毅朝2. 改进修复策略遗传算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2018, 54(21): 37-42.
[7]	张健，郭星，李炜. 改进果蝇优化算法在多目标搜索的应用[J]. 计算机工程与应用, 2018, 54(2): 131-136.
[8]	刘雪静，贺毅朝，吴聪聪，才秀凤. 基于细菌觅食算法求解折扣{0-1}背包问题的研究[J]. 计算机工程与应用, 2018, 54(2): 155-162.
[9]	刘雪静1，贺毅朝1，吴聪聪1，李靓2. 自适应细菌觅食算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2018, 54(18): 139-146.
[10]	林诗洁1，2，董晨1，2，陈明志1，2，张凡1，2，陈景辉1，2. 新型群智能优化算法综述[J]. 计算机工程与应用, 2018, 54(12): 1-9.
[11]	刘雪静1，贺毅朝1，吴聪聪1，李靓2. 求解0-1背包问题的混沌二进制乌鸦算法[J]. 计算机工程与应用, 2018, 54(10): 173-179.
[12]	刘宏，王其涛，夏未君. 优化混合蛙跳算法的WSN三维定位方法[J]. 计算机工程与应用, 2017, 53(2): 129-133.
[13]	赵玖玲，张文海. 降低固体推进剂特征信号的改进粒子群算法[J]. 计算机工程与应用, 2017, 53(19): 136-141.
[14]	钱汐，曾承，王甜. 时序范围最具稳定性服务集推荐算法[J]. 计算机工程与应用, 2017, 53(10): 73-78.
[15]	苟杰，马自堂. 基于MapReduce的并行SFLA-FCM聚类算法[J]. 计算机工程与应用, 2016, 52(1): 66-70.

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

Solving Knapsack problem based on binary shuffled frog-leaping algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics