International Journal of Intelligent Systems and Applications (IJISA)
IJISA Vol. 11, No. 2, 8 Feb. 2019
Cover page and Table of Contents: PDF (size: 570KB)
Ant Colony System Algorithm with Dynamic Pheromone Updating for 0/1 Knapsack Problem
Full Text (PDF, 570KB), PP.9-17
Views: 0 Downloads: 0
Author(s)
Index Terms
Ant Colony System, Heuristic Optimization, Combinatorial Optimization, Knapsack Problem, 0/1 Knapsack Problem
Abstract
The 0/1 Knapsack (KP) is a combinatorial optimization problem that can be solved using various optimization algorithms. Ant Colony System (ACS) is one of these algorithms that is operated iteratively and converged emphatically to a matured solution. The convergence of the ACS depends mainly on the heuristic patterns that are used to update the pheromone trails throughout the optimization cycles. Although, ACS has significant advantages, it suffers from a slow convergence, as the pheromones, which are used to initiate the searching process are initialized randomly at the beginning. In this paper, a new heuristic pattern is proposed to speed up the convergence of ACS with 0/1 KP. The proposed heuristic enforces an order-critical item selection. As such, the proposed heuristic depends on considering the profit added by each item, as similar to the existing heuristics, besides the order of item selection. Accordingly, the proposed heuristic allows the items that are added at the end to get more value in order to be considered in the beginning of the next round. As such, with each cycle, the selected items are varied substantially and the pheromones are vastly updated in order to avoid long trapping with the initial values that are initialized randomly. The experiments showed that the proposed heuristic is converged more rapidly compared to the existing heuristics by reducing up to 30% of the cycles required to reach the optimal solution using difficult 0/1 KP datasets. Accordingly, the times required for convergence have been reduced significantly in the proposed work compared to the time required by the existing algorithms.
Cite This Paper
Abdullah Alzaqebah, Ahmad Adel Abu-Shareha, "Ant Colony System Algorithm with Dynamic Pheromone Updating for 0/1 Knapsack Problem", International Journal of Intelligent Systems and Applications(IJISA), Vol.11, No.2, pp.9-17, 2019. DOI:10.5815/ijisa.2019.02.02
Reference
[1]Shareha, A.A.A., M. Rajeswari, and D. Ramachandram, “Textured Renyi Entropy for Image Thresholding”, in Computer Graphics, Imaging and Visualisation, 2008. CGIV'08. Fifth International Conference on. 2008. IEEE.
[2]Shehab, M., A.T. Khader, and M.A. Al-Betar, “A survey on applications and variants of the cuckoo search algorithm”, Applied Soft Computing, vol. 61, p. 1041-1059, 2017.
[3]Bazgan, C., H. Hugot, and D. Vanderpooten, “Solving efficiently the 0–1 multi-objective knapsack problem”, Computers & Operations Research, vol. 36, no. 1, p. 260-279, 2009.
[4]Wang, L., et al., “A human learning optimization algorithm and its application to multi-dimensional knapsack problems”, Applied Soft Computing, vol. 34, p. 736-7432, 015.
[5]García-Martínez, C., F.J. Rodriguez, and M. Lozano, “Tabu-enhanced iterated greedy algorithm: a case study in the quadratic multiple knapsack problem”, European Journal of Operational Research, vol. 232, no. 3, p. 454-463, 2014.
[6]Gimadi, E. and I. Rykov. “Efficient Randomized Algorithm for a Vector Subset Problem”, in International Conference on Discrete Optimization and Operations Research. 2016. Springer.
[7]Jacobson, L. and B. Kanber, Introduction, in Genetic Algorithms in Java Basics. 2015, Springer. p. 1-19.
[8]Liu, A., et al. “Improved simulated annealing algorithm solving for 0/1 knapsack problem”, in Intelligent Systems Design and Applications, 2006. ISDA'06. Sixth International Conference on. 2006. IEEE.
[9]Egeblad, J. and D. Pisinger, “Heuristic approaches for the two-and three-dimensional knapsack packing problem”, Computers & Operations Research, vol. 36, no. 4, p. 1026-1049, 2009.
[10]Thiel, J. and S. Voss, “Some experiences on solving multiconstraint zero-one knapsack problems with genetic algorithms”, INFOR: Information Systems and Operational Research, vol. 32, no. 4, p. 226-242, 1994.
[11]Hua, Z. and F. Huang, “A variable-grouping based genetic algorithm for large-scale integer programming”, Information Sciences, vol. 176, no. 19, p. 2869-2885, 2006.
[12]Ye, B., J. Sun, and W.-B. Xu, “Solving the hard knapsack problems with a binary particle swarm approach”, in Computational Intelligence and Bioinformatics, 2006: p. 155-163, Kunming, China.
[13]Tan, R.R., “Hybrid evolutionary computation for the development of pollution prevention and control strategies”, Journal of Cleaner Production, vol. 15, no. 10, p. 902-906, 2007.
[14]Zhao, P., P. Zhao, and X. Zhang, “A new ant colony optimization for the knapsack problem”, in Computer-Aided Industrial Design and Conceptual Design, 2006. CAIDCD'06. 7th International Conference on. 2006. IEEE.
[15]Dorigo, M., M. Birattari, and T. Stutzle, “Ant colony optimization”, IEEE computational intelligence magazine,vol. 1, no. 4, p. 28-39, 2006.
[16]Sim, K.M. and W.H. Sun, “Ant colony optimization for routing and load-balancing: survey and new directions”, IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, vol. 33, no. 5, p. 560-572, 2003.
[17]Blum, C., “Ant colony optimization: Introduction and recent trends”, Physics of Life reviews, vol. 2, no. 4, p. 353-373, 2005.
[18]Dorigo, M., V. Maniezzo, and A. Colorni, “Ant system: optimization by a colony of cooperating agents”, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 26, no. 1, p. 29-41,1996..
[19]Bullnheimer, B., R.F. Hartl, and C. Strauss, “A new rank based version of the Ant System”, A computational study, 1997.
[20]Stützle, T. and H.H. Hoos, “MAX–MIN ant system”, Future generation computer systems, vol. 16, no. 8, p. 889-914, 2000.
[21]Dorigo, M. and L.M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem”, IEEE Transactions on evolutionary computation, vol.1, no. 1, p. 53-66, 1997.
[22]Zhang, Y.D. and L.N. Wu., “Bankruptcy prediction by genetic ant colony algorithm”, in Advanced Materials Research, 2011.
[23]Leguizamon, G. and Z. Michalewicz, “A new version of ant system for subset problems”, in Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on. 1999. IEEE.
[24]Schiff, K., “Ant colony optimization algorithm for the 0-1 knapsack problem”, Technical Transaction, Automatic Control, vol. 52, p. 39-52, 2013.
[25]Pisinger, D., “Where are the hard knapsack problems?” Computers & Operations Research, vol. 32, no. 9, p. 2271-2284, 2005.