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 Intelligence 48 (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
 Essential discrete mathematics for computer science
Lewis H., Zax R.,  PRINCETON UNIVERSITY PRESS, Princeton, NJ, 2019. 388 pp. Type: Book (978-0-691179-29-2)
Jul 18 2022
Discrete mathematics and graph theory: a concise study companion and guide
Erciyes K.,  Springer International Publishing, New York, NY, 2021. 352 pp. Type: Book (978-3-030611-14-9)
Jul 12 2022
Induced minor free graphs: isomorphism and clique-width
Belmonte R., Otachi Y., Schweitzer P.  Algorithmica 80(1): 29-47, 2018. Type: Article
Apr 2 2019
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2022 ThinkLoud, Inc.
Terms of Use
| Privacy Policy