An ABC Algorithm Inspired by Boolean Operators for Knapsack and Lot Sizing Problems

Abstract

This paper proposes a logically inspired artificial bee colony algorithm (ABCLO) to deal with the knapsack and lot sizing problems shown in many forms such as in economics, engineering and business. The proposed ABC-LO algorithm aims to find fitter solutions using the search mechanism designed through the basic Boolean operators. To verify the effectiveness of the ABC-LO algorithm, it is analyzed and compared with the recent variants of particle swarm optimization, artificial bee colony and genetic algorithms. The results indicate that the proposed ABC-LO algorithm performs well in knapsack and lot sizing problem sets compared to the others.

Keywords

• Boolean logic,knapsack,artificial bee colony,lot sizing

References

1. [1] Karaboga, D., Basturk, B. 2011. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. Journal of Global Optimization, 39 (3), 459-471.
2. [2] Das, S., Biswas, S., Kundu S. 2013. Synergizing fitness learning with proximity-based food source selection in artificial bee colony algorithm for numerical optimization. Applied Soft Computing, 13 (12), 4676 - 4694.
3. [3] Kashan, M. H., Nahavandi, N., Kashan, A. H. 2012. DisABC: A new artificial bee colony algorithm for binary optimization. Applied Soft Computing, 12 (1), 342- 352.
4. [4] Kiran M. S., Gunduz M. 2013. XOR-based artificial bee colony algorithm for binary optimization. Turkish Journal of Electrical Engineering & Computer Sciences, 21 (Sup.2), 2307-2328.
5. [5] Pampara, G., Engelbrecht, A. P. 2011. Binary artificial bee colony optimization IEEE Symposium on Swarm Intelligence (SIS), 11-15 April, Paris, 1-8
6. [6] Ozturk, C., Hancer, E., Karaboga, D. 2015. Dynamic Clustering with Improved Binary Artificial Bee Colony Algorithm, Applied Soft Computing, 28, 69-80.
7. [7] Ozturk, C., Hancer, E., Karaboga, D. 2015. A Novel Binary Artificial Bee Colony Algorithm Based on Genetic Operators, 297, 154-170.
8. [8] Hancer, E., Xue B., Karaboga, D., Zhang, M. 2015. A binary ABC algorithm based on advanced similarity scheme for feature selection, Applied Soft Computing, 36, 334-348.

9. [9] Andonov, R., Poirriez, V., Rajopadhye, S. 2000. Unbounded knapsack problem: Dynamic programming revisited. European Journal of Operational Research, 123 (2), 394-407.
10. [10] Martello, S., Toth, P. 1990. Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc. New York, NY, USA.
11. [11] Martello, S., Toth, P. 1999. Dynamic programming and strong bounds for the 0-1 knapsack problem. Management Science, 45 (3), 414–424.
12. [12] Martello, S., Toth, P. 1984. A mixture of dynamic programming and branch-and-bound for the subset-sum problem. Management Science, 30 (6), 765–771.
13. [13] Singh, R. P. 2011. Solving 0-1 Knapsack problem using Genetic Algorithms, 3rd IEEE International Conference on Communication Software and Networks (ICCSN), 27-29 May, Xi’an, 591-595.
14. [14] Chu, P. C., Beasley, J. E. 1998. A Genetic Algorithm for the Multidimensional Knapsack Problem. Journal of Heuristics, 4 (1), 63-86.
15. [15] AbdulHalim, M.F., Attea, B.A., Hameed, S.M. 2008. A binary Particle Swarm Optimization for attacking knapsacks Cipher Algorithm. International Conference on Computer and Communication Engineering (ICCCE), 13-15 May, Kuala Lumpur, 77-81.
16. [16] Fangguo, H. 2009. An Improved Particle Swarm Optimization for Knapsack Problem. International Conference on Computational Intelligence and Software Engineering (CISE), 11-13 December, Wuhan, 1-4.
17. [17] Changshou, D., Bingyan, Z., Yanling, Y., Anyuan, D. 2009. Modified Dynamic Differential Evolution for 0-1 Knapsack Problems. International Conference on Computational Intelligence and Software Engineering (CISE), 11-13 December, Wuhan, 1-4.
18. [18] Jun, S., Jian, L. 2009. Solving 0-1 Knapsack Problems via a Hybrid Differential Evolution. Third International Symposium on Intelligent Information Technology Application (IITA), 21-22 November, Nanchang, 134-137.
19. [19] Pulikanti, S., Singh, A. 2009. An Artificial Bee Colony Algorithm for the Quadratic Knapsack Problem. 16th International Conference on Neural Information Processing (ICONIP), December 1-5, Bangkok, 196-205.
20. [20] Sabet, S., Farokhi, F., Shokouhifar, M. 2012. A novel artificial bee colony algorithm for the knapsack problem. International Symposium on Innovations in Intelligent Systems and Applications (INISTA), 2-4 July, Trabzon, 1-5.
21. [21] Wagner, H. M., Whitin, T. M. 1958. Dynamic Version of the Economic Lot Size Model, Management Science, 50 (12), 1770-1774.
22. [22] Tasgetiren, M. F., Liang, Y-C. 2003. A Binary Particle Swarm Optimization Algorithm for Lot Sizing Problem. Journal of Economic and Social Research, 5 (2), 1-20.
23. [23] Deorussi, L., Lemoine, D. 2011. Discrete Particle Swarm Optimization for the Multi-Level Lot-Sizing Problem. Trends in Developing Metaheuristics, Algorithms, and Optimization Approaches, IGI Publishing Hershey, PA, USA.
24. [24] Brahimi, N., Dauzere-Peres, S., Najid, N. M., Nordli, A. 2006. Single item lot sizing problems. European Journal of Operational Research, 168 (1), 1-16.
25. [25] Van den Heuvel, W. 2006. The Economic Lot-Sizing Problem: New Results and Extensions. Erasmus School of Economics (ESE), Erasmus University of Rotterdam, PhD Thesis.
26. [26] Dorigo, M., Stutzle T. 2004. Ant Colony Optimization. Bradford Company Scituate, MA, USA.
27. [27] Kennedy, J., Eberhart, R. 1995. Particle swarm optimization, IEEE International Conference on Neural Networks, 1942-1948.
28. [28] Das, S., Biswas, A., Dasgupta, S., Abraham, A. 2009. Bacterial Foraging Optimization Algorithm: Theoretical Foundations, Analysis, and Applications pp 23-55. Abraham, A., Hassanien, A.-E., Siarry, P., Engelbrecht, A., ed. 2009. Foundations of Computational Intelligence, Springer Berlin Heidelberg.
29. [29] Akay, B., Karaboga, D. 2012. A modified Artificial Bee Colony algorithm for real-parameter optimization. Information Sciences, 192, 120-142.
30. [30] Hancer, E., Karaboga, D. 2017. A comprehensive survey of traditional, merge-split and evolutionary approaches proposed for determination of cluster number. Swarm and Evolutionary Computation, 32, 49-67.
31. [31] Hancer, E., Ozturk, C., Karaboga, D. 2012. Artificial Bee Colony Based Image Clustering Method. IEEE Congress on Evolutionary Computation (CEC), 10-12 June, Brisbane, 1-5.
32. [32] Kennedy, J., Eberhart, R. C. 1997. A discrete binary version of the particle swarm algorithm. IEEE International Conference on Computational Cybernetics and Simulation, 12-15 October, Orlando, 4104-4108.
33. [33] Yuan, X., Nie, H., Su, A., Wang, L., Yuan, Y. 2009. An improved binary particle swarm optimization for unit commitment problem. Expert Systems with Applications, 36 (4), 8049-8055.
34. [34] Holland, J. 2012. Genetic algorithms. Scholarpedia, 7, 1482.
35. [35] Zitzler, E., Laumans, M. 2012. Test Problems and Test Data for Multiobjective Optimizers. http://www.tik.ee.ethz.ch/sop/ (Access Date: 05/05/2016).
36. [36] Mirjalili S., Lewis, A. 2013. S-shaped versus V-shaped transfer functions for binary Particle Swarm Optimization. Swarm and Evolutionary Computation, 9, 1-14.