Application of the Bee Swarm Optimization BSO to the Knapsack Problem

• Autorzy: Sotelo-Figueroa M. A. , Baltazar B. , Carpio J. M.
• Konferencja: International Seminar on Computational Intelligence held at Tijuana, Mexico on January of 2010
• Języki publikacji: EN

Abstrakty

EN

Swarm Intelligence is the part of Artificial Intelligence based on study of actions of individuals in various decentralized systems. The optimization algorithms which are inspired from intelligent behavior of honey bees are among the most recently introduced population based techniques. In this paper, a novel hybrid algorithm based in Bees Algorithm and Particle Swarm Optimization is applied to the Knapsack Problem. The Bee Algorithm is a new population-based search algorithm inspired by the natural foraging behavior of honey bees, it performs a kind of exploitative neighborhood search combined with random explorative search to scan the solution, but the results obtained with this algorithm in the Knapsack Problem are not very good. Although the combination of BA and PSO is given by BSO, Bee Swarm Optimization, this algorithm uses the velocity vector and the collective memories of PSO and the search based on the BA and the results are much better. We use the Greedy Algorithm, which it's an approximate algorithm, to compare the results from these metaheuristics and thus be able to tell which is which gives better results.

Słowa kluczowe

EN

swarm optimization; PSO; BA; BSO; knapsack problem

• Wydawca: Łukasiewicz Industrial Research Institute for Automation and Measurements PIAP
• Czasopismo: Journal of Automation Mobile Robotics and Intelligent Systems
• Rocznik: 2011
• Tom: Vol. 5, No. 1
• Strony: 101--114
• Opis fizyczny: Bibliogr. 17 poz., rys.

Twórcy

autor

Sotelo-Figueroa M. A.

autor

Baltazar B.

autor

Carpio J. M.

• Instituto Tecnológico de León, Av. Tecnológico S/N, 37290, León, Guanajuato, México,

Bibliografia

• [1] Forrest J.J.H., Kalagnanam J., Ladanyi L., “A Column-GenerationApproach to the Multiple Knapsack Problem with Color Constraints”, INFORMS Journal on Computing, 2006, pp. 129-134.
• [2] Garey Michael R., David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-CompletenessI, 1979.
• [3] Kellerer H., Pferschy U., Pisinger D., Knapsack Problems, Stringer, Berlin, 2004.
• [4] Kennedy J., Eberhart R.C., “Particle Swarm Optimization”. In:, IEEE International Conference Neural Networks, vol. 4, 1995, pp. 1942-1948.
• [5] Kennedy J., Eberhart R.C., Swarm Intelligence , Academic Press, EUA, 2001.
• [6] Kiwiel K. C., “Breakpoint searching algorithms for the continuous quadratic knapsack problem”, Math. Program, Spriger-Verlag, 2008, pp. 473-491.
• [7] Maurice C., Particle Swarm Optimization , ISTE Ldt, USA, 2006.
• [8] McDuff-Spears W., Using neural networks and genetic algorithms as Heuristics for NP-complete problems , Thesis of Master of Science in Computer Science, George Mason University,Virginia, 1989.
• [9] Parsopoulus K.E., Vrahatis M.N., Initializing the particle swarm optimizer using nonlinear simplex method, ,,Advances in Intelligent Systems Fuzzy Systems Evolutionary Computation , 2002, pp. 216-221.
• [10] Pham D., Ghanbarzadeh A., Koç E., Otris S., Rahim S., Zaidi M., “The bee algorithm -a novel tool for complex optimizationproblems” , Intelligent Production Machines and Systems , 2006.
• [11] Pisinger D., “Core Problems in Knapsack Algorithms”, Operation Research , vol. 47, 1999, pp. 570-575.
• [12] Pisinger D., “Where Are The Hard Knapsack problems?”, Computers & Operation Research , vol. 32, 2005, pp. 2271-2282.
• [13] Pisinger D., Rasmussen, A. Sandvik R., “Solution of Large Quadratic Knapsack Problems Through Aggressive Reduction, INFORMS Journal on Computing, INFORMS, 2007, pp. 280-290.
• [14] Shahriar A. Z. M. et al ., “A multiprocessor based heuristic for multi-dimensional multiple-choice knapsack problem”, J. Supercomput , 2008, pp. 257-280.
• [15] Silvano M., Toth P., Knapsack Problem, Algorithms and Computer Implementations , John Wiley and Sons , New York USA, 1990.
• [16] Yamada, T., Watanabe K., and Kataoka, S., Algorithms to solve the knapsack constrained maximum spanning tree problem, International Journal of Computer Mathematics,Taylor & Francis Ltd, 2005, pp. 23-34.
• [17] Zemel E., “An O(n) Algorithm for the linear multiple choice Knapsack problem and related problems”, Information Processing Problems , North Holland, 1984, pp. 123-128.