Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
A modified artificial bee colony approach for the 0-1 knapsack problem
Cao J., Yin B., Lu X., Kang Y., Chen X. Applied Intelligence48 (6):1582-1595,2018.Type:Article
Date Reviewed: Aug 22 2018

Many would consider the search for the optimal evolutionary computation (the collective noun for the multitude of search algorithms based on nature) algorithm by researchers the world over as evolutionary in itself. Not only do we search for new algorithms, but we also try and combine existing algorithms in new and novel ways. In this paper, to solve the knapsack problem, the authors combine the artificial bee colony algorithm (ABC) together with differential evolution and a methodology to repair infeasible solutions into valid trials.

The knapsack problem starts with a set of items. Each item has a weight and a value. The aim is to fit the most value into a knapsack that can only contain a limited weight. Although of direct practical interest to the backpacking student, the applications are much wider and include virtually any problem that involves the allocation of limited resources. One can view the problem as finding the optimal Boolean vector, where each element corresponds to an item and the value of the Boolean indicates whether that item is included.

Starting with ABC, the employed bees are each initialized with a random choice of items. During the employed bee phase, each bee selects a target solution by modifying each element based on its inclusion status among two randomly chosen neighbors. In the onlooker bee phase, a bee chooses a food source using a probability based on how close that solution is to the best fit discovered. Once selected, the bee will apply mutation and crossover operations (this is the differential evolution component) to the solution. The final scout bee phase will reinitialize a solution to a random set if no improvement has been found over some predefined number of trials. The repair operation is then applied, which unloads low-value items from overfilled knapsacks and tops up underfilled knapsacks. Simulation results show that this new approach is better than its predecessors.

Reviewer:  Bernard Kuc Review #: CR146214 (1811-0583)
Bookmark and Share
  Featured Reviewer  
 
Discrete Mathematics (G.2 )
 
 
Combinatorial Algorithms (G.2.1 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Discrete Mathematics": Date
 Discrete mathematics and its applications
Rosen K., McGraw-Hill Higher Education, Columbus, OH, 2002.  928, Type: Book (9780072424348)
May 7 2003
Derandomization of auctions
Aggarwal G., Fiat A., Goldberg A., Hartline J., Immorlica N., Sudan M.  Theory of computing (Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, Baltimore, MD, May 22-24, 2005)619-625, 2005. Type: Proceedings
Jul 31 2006
Algorithms on strings
Crochemore M., Hancart C., Lecroq T., Cambridge University Press, New York, NY, 2007.  392, Type: Book (9780521848992)
Apr 8 2008
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy