Solving Knapsack problem based on binary shuffled frog-leaping algorithm

doi:10.3778/j.issn.1002-8331.2010.35.011

Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (35): 39-41.DOI: 10.3778/j.issn.1002-8331.2010.35.011

• 研究、探讨 • Previous Articles Next Articles

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

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

赵洋¹，单娟²

1.石家庄经济学院信息工程系，石家庄 050031
2.河北省大中专院校学生信息咨询与就业指导中心，石家庄 050061

通讯作者: 赵洋

Abstract

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

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

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

CLC Number:

TP18

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

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

[1]	WANG Keyin, SHI Zhen, YANG Zhengcai, YANG Yahui, WANG Sishan. Path Planning for Mobile Robot Using Improved Reinforcement Learning Algorithm [J]. Computer Engineering and Applications, 2021, 57(18): 270-274.
[2]	HAO Xiang, HE Yichao, ZHU Xiaobin, ZHAI Qinglei. Discrete Hybrid Multi-verse Optimization Algorithm for Solving Discounted {0-1} Knapsack Problem [J]. Computer Engineering and Applications, 2021, 57(18): 103-113.
[3]	ZHANG Ming, DENG Wenhan, LIN Juan, ZHONG Yiwen. Modified Ant Colony Optimization Algorithm for Discounted {0-1} Knapsack Problem [J]. Computer Engineering and Applications, 2021, 57(13): 85-95.
[4]	YANG Tong, QIN Jin. Adaptive ε-greedy Strategy Based on Average Episodic Cumulative Reward [J]. Computer Engineering and Applications, 2021, 57(11): 148-155.
[5]	WU Congcong, HE Yichao, ZHAO Jianli. New Genetic Algorithm for Discounted {0-1} Knapsack Problem [J]. Computer Engineering and Applications, 2020, 56(7): 57-66.
[6]	CHEN Changqian, MU Xiaodong, NIU Ben, WANG Lizhi. Improved Binary Grey Wolves Optimization Algorithm Combined with Gaussian Distribution [J]. Computer Engineering and Applications, 2019, 55(13): 145-150.
[7]	YANG Yang1, PAN Dazhi1, HE Yichao2. Improved repair strategy genetic algorithm solve discount {0-1} knapsack problem [J]. Computer Engineering and Applications, 2018, 54(21): 37-42.
[8]	ZHANG Jian, GUO Xing, LI Wei. Application of improved?fruit fly optimization?algorithm on multi object search [J]. Computer Engineering and Applications, 2018, 54(2): 131-136.
[9]	LIU Xuejing, HE Yichao, WU Congcong, CAI Xiufeng. Research on bacterial foraging optimization algorithm for discounted {0-1} knapsack problem [J]. Computer Engineering and Applications, 2018, 54(2): 155-162.
[10]	LIU Xuejing1, HE Yichao1, WU Congcong1, LI Liang2. Adaptive bacterial foraging optimization algorithm for discounted {0-1} knapsack problem [J]. Computer Engineering and Applications, 2018, 54(18): 139-146.
[11]	LIU Xuejing1, HE Yichao1, WU Congcong1, LI Liang2. Chaotic binary crow search algorithm for 0-1 knapsack problem [J]. Computer Engineering and Applications, 2018, 54(10): 173-179.
[12]	WU Weimin, WU Wangyang, LIN Zhiyi, LI Zexiong, FANG Dianyu. Dragonfly algorithm based on enhancing exchange of individuals’ information [J]. Computer Engineering and Applications, 2017, 53(4): 10-14.
[13]	ZHAO Jiuling, ZHANG Wenhai. Improved particle swarm algorithm to lower characteristic signal of solid propellant [J]. Computer Engineering and Applications, 2017, 53(19): 136-141.
[14]	QIAN Xi, ZENG Cheng, WANG Tian. Most stably continuous service set recommend algorithm in changing time [J]. Computer Engineering and Applications, 2017, 53(10): 73-78.
[15]	CUI Jianshuang, WANG Chongjing. Solving multiple knapsack problem with speed limit particle swarm algorithm [J]. Computer Engineering and Applications, 2015, 51(9): 244-247.

Solving Knapsack problem based on binary shuffled frog-leaping algorithm

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics