Abstract
The knapsack problem is a fundamental problem that has been extensively studied in combinatorial optimization. The reason is that such a problem has many practical applications. Several solution techniques have been proposed in the past, but their performance is usually limited by the complexity of the problem. Hence, this paper studies a novel hyper-heuristic approach based on the ant colony optimization algorithm to solve the knapsack problem. The hyper-heuristic is used to produce rules that decide which heuristic to apply given the current problem state of the instance being solved. We test the hyper-heuristic model on sets with a variety of knapsack problem instances. Our resulting data seems promising.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Schiff, K.: Ant colony optimization algorithm for the 0–1 knapsack problem. Technical Transactions. Autom. Control R 110(AC-3), 39–52 (2013)
Sahni, S.: Approximate algorithms for the 0/1 knapsack problem. J. ACM 22(1), 115–124 (1975)
Burke, E.K., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., Qu, R.: Hyper-heuristics: a survey of the state of the art. J. Oper. Res. Soc. 64(12), 1695–1724 (2013)
Dorigo, M., Stützle, T.: Ant Colony Optimization. Bradford Company, Scituate (2004)
Zhang, J.: Comparative study of several intelligent algorithms for knapsack problem. Procedia Environ. Sci. 11, 163–168 (2011)
Ke, L., Feng, Z., Ren, Z., Wei, X.: An ant colony optimization approach for the multidimensional knapsack problem. J. Heuristics 16(1), 65–83 (2010)
Ren, Z., Feng, Z.: An ant colony optimization approach to the multiple-choice multidimensional knapsack problem. In: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, GECCO 2010, pp. 281–288. ACM (2010)
Du, D., Zu, Y.: Greedy strategy based self-adaption ant colony algorithm for 0/1 knapsack problem. In: Park, J.J.J.H., Pan, Y., Chao, H.-C., Yi, G. (eds.) Ubiquitous Computing Application and Wireless Sensor. LNEE, vol. 331, pp. 663–670. Springer, Dordrecht (2015). https://doi.org/10.1007/978-94-017-9618-7_70
He, L., Huang, Y.: Research of ant colony algorithm and the application of 0/1 knapsack. In: 2011 6th International Conference on Computer Science Education (ICCSE), pp. 464–467 (2011)
Changdar, C., Mahapatra, G.S., Pal, R.K.: An ant colony optimization approach for binary knapsack problem under fuzziness. Appl. Math. Comput. 223, 243–253 (2013)
Aziz, Z.A.: Ant colony hyper-heuristics for travelling salesman problem. Procedia Comput. Sci. 76, 534–538 (2015)
Chen, P.C., Kendall, G., Berghe, G.V.: An ant based hyper-heuristic for the travelling tournament problem. In: 2007 IEEE Symposium on Computational Intelligence in Scheduling, pp. 19–26 (2007)
Ferreira, A.S., Pozo, A., Gonçalves, R.A.: An ant colony based hyper-heuristic approach for the set covering problem. Adv. Distrib. Comput. Artif. Intell. J. 4, 1–21 (2015)
Cuesta-Cañada, A., Garrido, L., Terashima-Marín, H.: Building hyper-heuristics through ant colony optimization for the 2D bin packing problem. In: Khosla, R., Howlett, R.J., Jain, L.C. (eds.) KES 2005. LNCS (LNAI), vol. 3684, pp. 654–660. Springer, Heidelberg (2005). https://doi.org/10.1007/11554028_91
López-Camacho, E., Terashima-Marin, H., Ross, P., Ochoa, G.: A unified hyper-heuristic framework for solving bin packing problems. Expert Syst. Appl. 41(15), 6876–6889 (2014)
Gaertner, D., Clark, K.: On optimal parameters for ant colony optimization algorithms. In: Proceedings of the International Conference on Artificial Intelligence 2005, pp. 83–89. CSREA Press (2005)
Wei, X.: Parameters analysis for basic ant colony optimization algorithm in TSP. Int. J. u- e-Serv. Sci. Technol. 7(4), 159–170 (2014)
Pisinger, D.: Where are the hard knapsack problems? Comput. Opera. Res. 32(9), 2271–2284 (2005)
Acknowledgements
This research was partially supported by CONACyT Basic Science Projects under grants 241461, 221551 and 287479, and ITESM Research Group with Strategic Focus in Intelligent Systems.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Duhart, B., Camarena, F., Ortiz-Bayliss, J.C., Amaya, I., Terashima-Marín, H. (2018). An Experimental Study on Ant Colony Optimization Hyper-Heuristics for Solving the Knapsack Problem. In: Martínez-Trinidad, J., Carrasco-Ochoa, J., Olvera-López, J., Sarkar, S. (eds) Pattern Recognition. MCPR 2018. Lecture Notes in Computer Science(), vol 10880. Springer, Cham. https://doi.org/10.1007/978-3-319-92198-3_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-92198-3_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-92197-6
Online ISBN: 978-3-319-92198-3
eBook Packages: Computer ScienceComputer Science (R0)