Research Article
BibTex RIS Cite

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

Year 2018, Volume: 6 Issue: 2, 142 - 152, 03.08.2018
https://doi.org/10.21541/apjes.337415

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.

References

  • [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] 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] 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] 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] Pampara, G., Engelbrecht, A. P. 2011. Binary artificial bee colony optimization IEEE Symposium on Swarm Intelligence (SIS), 11-15 April, Paris, 1-8
  • [6] Ozturk, C., Hancer, E., Karaboga, D. 2015. Dynamic Clustering with Improved Binary Artificial Bee Colony Algorithm, Applied Soft Computing, 28, 69-80.
  • [7] Ozturk, C., Hancer, E., Karaboga, D. 2015. A Novel Binary Artificial Bee Colony Algorithm Based on Genetic Operators, 297, 154-170.
  • [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] Andonov, R., Poirriez, V., Rajopadhye, S. 2000. Unbounded knapsack problem: Dynamic programming revisited. European Journal of Operational Research, 123 (2), 394-407.
  • [10] Martello, S., Toth, P. 1990. Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc. New York, NY, USA.
  • [11] Martello, S., Toth, P. 1999. Dynamic programming and strong bounds for the 0-1 knapsack problem. Management Science, 45 (3), 414–424.
  • [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] 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] Chu, P. C., Beasley, J. E. 1998. A Genetic Algorithm for the Multidimensional Knapsack Problem. Journal of Heuristics, 4 (1), 63-86.
  • [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] 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] 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] 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] 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] 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] Wagner, H. M., Whitin, T. M. 1958. Dynamic Version of the Economic Lot Size Model, Management Science, 50 (12), 1770-1774.
  • [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] 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] 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] 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] Dorigo, M., Stutzle T. 2004. Ant Colony Optimization. Bradford Company Scituate, MA, USA.
  • [27] Kennedy, J., Eberhart, R. 1995. Particle swarm optimization, IEEE International Conference on Neural Networks, 1942-1948.
  • [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] Akay, B., Karaboga, D. 2012. A modified Artificial Bee Colony algorithm for real-parameter optimization. Information Sciences, 192, 120-142.
  • [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] 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] 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] 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] Holland, J. 2012. Genetic algorithms. Scholarpedia, 7, 1482.
  • [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] Mirjalili S., Lewis, A. 2013. S-shaped versus V-shaped transfer functions for binary Particle Swarm Optimization. Swarm and Evolutionary Computation, 9, 1-14.

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

Year 2018, Volume: 6 Issue: 2, 142 - 152, 03.08.2018
https://doi.org/10.21541/apjes.337415

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.

References

  • [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] 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] 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] 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] Pampara, G., Engelbrecht, A. P. 2011. Binary artificial bee colony optimization IEEE Symposium on Swarm Intelligence (SIS), 11-15 April, Paris, 1-8
  • [6] Ozturk, C., Hancer, E., Karaboga, D. 2015. Dynamic Clustering with Improved Binary Artificial Bee Colony Algorithm, Applied Soft Computing, 28, 69-80.
  • [7] Ozturk, C., Hancer, E., Karaboga, D. 2015. A Novel Binary Artificial Bee Colony Algorithm Based on Genetic Operators, 297, 154-170.
  • [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] Andonov, R., Poirriez, V., Rajopadhye, S. 2000. Unbounded knapsack problem: Dynamic programming revisited. European Journal of Operational Research, 123 (2), 394-407.
  • [10] Martello, S., Toth, P. 1990. Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc. New York, NY, USA.
  • [11] Martello, S., Toth, P. 1999. Dynamic programming and strong bounds for the 0-1 knapsack problem. Management Science, 45 (3), 414–424.
  • [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] 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] Chu, P. C., Beasley, J. E. 1998. A Genetic Algorithm for the Multidimensional Knapsack Problem. Journal of Heuristics, 4 (1), 63-86.
  • [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] 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] 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] 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] 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] 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] Wagner, H. M., Whitin, T. M. 1958. Dynamic Version of the Economic Lot Size Model, Management Science, 50 (12), 1770-1774.
  • [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] 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] 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] 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] Dorigo, M., Stutzle T. 2004. Ant Colony Optimization. Bradford Company Scituate, MA, USA.
  • [27] Kennedy, J., Eberhart, R. 1995. Particle swarm optimization, IEEE International Conference on Neural Networks, 1942-1948.
  • [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] Akay, B., Karaboga, D. 2012. A modified Artificial Bee Colony algorithm for real-parameter optimization. Information Sciences, 192, 120-142.
  • [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] 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] 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] 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] Holland, J. 2012. Genetic algorithms. Scholarpedia, 7, 1482.
  • [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] Mirjalili S., Lewis, A. 2013. S-shaped versus V-shaped transfer functions for binary Particle Swarm Optimization. Swarm and Evolutionary Computation, 9, 1-14.
There are 36 citations in total.

Details

Primary Language English
Subjects Engineering
Journal Section Articles
Authors

Emrah Hançer

Publication Date August 3, 2018
Submission Date September 10, 2017
Published in Issue Year 2018 Volume: 6 Issue: 2

Cite

IEEE E. Hançer, “An ABC Algorithm Inspired by Boolean Operators for Knapsack and Lot Sizing Problems”, APJES, vol. 6, no. 2, pp. 142–152, 2018, doi: 10.21541/apjes.337415.