Logo PTI Logo FedCSIS

Proceedings of the 16th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 25

InterCriteria Analyzis of Hybrid Ant Colony Optimization Algorithm for Multiple Knapsack Problem

, ,

DOI: http://dx.doi.org/10.15439/2021F22

Citation: Proceedings of the 16th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 25, pages 173–180 ()

Full text

Abstract. The local search procedure is a method for hybridization and improvement of the main algorithm, when complex  problems are solved. It helps to avoid local optimums and to find faster the global one.  In this paper we apply InterCriteria analysis (ICrA) on hybrid Ant Colony Optimization (ACO) algorithm for Multiple Knapsack Problem (MKP). The aim is to study the algorithm behavior comparing with traditional ACO algorithm. Based on the obtained numerical results and on the ICrA approach the efficiency and effectiveness of the proposed local search procedure are confirmed.

References

  1. M. Angelova, O. Roeva and T. Pencheva. InterCriteria Analysis of Crossover and Mutation Rates Relations in Simple Genetic Algorithm. In Proceedings of the 2015 Federated Conference on Computer Science and Information Systems, Vol. 5, pages 419–424, 2015.
  2. Antonov A., Dependencies Between Model Indicators of the Basic and the Specialized Speed in Hockey Players Aged 13-14, Trakia Journal of Sciences, Vol. 18, Suppl. 1, pp 647-657, 2020.
  3. Idil Arsik, Pinar Keskinocak, Jennifer Coppola, Kirthana Hampapur, Yitong He, Haozheng Jiang,Dani Regala, Nick Tailhardat, and Kristin Goin. Effective and equitable appointment scheduling in rehabilitation centers.INFORMS Annual Meeting 2017, Oct. 22-25 2017.
  4. K. Atanassov. Index matrices: Towards an augmented matrix calculus. Springer International Publishing Switzerland, 2014.
  5. K. Atanassov. Intuitionistic Fuzzy Sets. VII ITKR Session, Sofia, 20-23 June 1983, Reprinted: International Journal Bioautomation, 20(S1):S1–S6, 2016.
  6. K. Atanassov. Generalized index matrices. Comptes rendus de l’Academie bulgare des Sciences, 40(11):15–18, 1987.
  7. K. Atanassov. On intuitionistic fuzzy sets theory. Springer, Berlin, 2012.
  8. K. Atanassov. On index matrices, Part 1: Standard cases. Advanced Studies in Contemporary Mathematics, 20(2):291–302, 2010).
  9. K. Atanassov. On index matrices, Part 2: Intuitionistic fuzzy case. Proceedings of the Jangjeon Mathematical Society, 13(2):121–126, 2010.
  10. K. Atanassov. Review and New Results on Intuitionistic Fuzzy Sets, Mathematical Foundations of Artificial Intelligence Seminar, Sofia, 1988, Preprint IM-MFAIS-1-88. Reprinted: International Journal Bioautomation, 20(S1):S7–S16, 2016.
  11. K. Atanassov, D. Mavrov and V. Atanassova. Intercriteria decision making: A new approach for multicriteria decision making, based on index matrices and intuitionistic fuzzy sets. Issues in on Intuitionistic Fuzzy Sets and Generalized Nets, 11:1–8, 2014.
  12. K. Atanassov, E. Szmidt and J. Kacprzyk. On intuitionistic fuzzy pairs. Notes on Intuitionistic Fuzzy Sets, 19(3):1–13, 2013.
  13. K. Atanassov, V. Atanassova and G. Gluhchev. InterCriteria Analysis: ideas and problems. Notes on Intuitionistic Fuzzy Sets, 21(1):81–88, 2015.
  14. V. Atanassova, D. Mavrov, L. Doukovska and K. Atanassov. Discussion on the Threshold Values in the InterCriteria Decision Making Approach. Notes on Intuitionistic Fuzzy Sets, 20(2): 94–99, 2014.
  15. M. Birattari, T. Stutzle, L.Paquete, K. Varrentrapp, A racing algorithm for configuring metaheuristics, Proceedings of the Genetic and Evolutionary Computation Conference, pp. 11–18, 2002.
  16. Bonabeau E., Dorigo M. and Theraulaz G., Swarm Intelligence: From Natural to Artificial Systems, New York,Oxford University Press, 1999.
  17. M. Dorigo, L. Gambardella, Ant colony system : A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation vol. 1, 53–66, 1996.
  18. Dorigo M, Stutzle T., Ant Colony Optimization, MIT Press, 2004.
  19. S. Fidanova, I. Lirkov, 3d protein structure prediction, Analele Universitatii de Vest Timisoara, vol. XLVII, pp. 33–46, 2009.
  20. S. Fidanova, An improvement of the grid-based hydrophobic-hydrophilic model, Int. J. Bioautomation, vol. 14, pp. 147–156, 2010.
  21. S. Fidanova, ACO algorithm with additional reinforcement, Int Conf. from Ant Colonies to Artificial Ants, Lecture Notes in Computer Science 2463, 292–293, 2003.
  22. S. Fidanova,K. Atanassov, P. Marinov, Generalized nets and ant colony optimization, Bulg. Academy of Sciences Pub. House, 2011.
  23. S. Fidanova, K. Atanassov, P. Marinov, Start strategies of ACO applied on subset problems, Numerical Methods and Applications, Lecture Notes in Computer Science, 6046, 248–255, 2011.
  24. S.Fidanova, K. Atanassov, P. Marinov, Intuitionistic fuzzy estimation of the ant colony optimization starting points, Large Scale Scientific Computing, Lecture Notes in Computer Science 7116, 219–226, 2012.
  25. S. Fidanova, O. Roeva and M. Paprzycki. InterCriteria Analysis of ACO Start Strategies, In Proceedings of the 2016 Federated Conference on Computer Science and Information Systems, Vol. 8, pages 547–550, 2016.
  26. Fidanova S. Hybrid Ant Colony Optimization Algorithm for Multiple Knapsack Problem. 5th IEEE International Conference on Recent Advances and Innovations in Engineering (ICRAIE), IEEE, 2021, http://dx.doi.org/10.1109/ICRAIE51050.2020.9358351, 1-5.
  27. Feuerman, Martin; Weiss, Harvey (April 1973). “A Mathematical Programming Model for Test Construction and Scoring”. Management Science. 19 (8): 961966
  28. D.E. Goldberg, B. Korb, K. Deb, Messy Genetic Algorithms: Motivation Analysis and First Results, Complex Systems, vol. 5(3), pp. 493 – 530, 1989.
  29. D. Karaboga, B. Basturk, Artificial bee colony (ABC) optimization algorithm for solving constrained optimization problems, Advances in Soft Computing: Foundations of Fuzzy Logic and Soft Computing, LNCS 4529, 789-798, 2007.
  30. Kellerer H., Pferschy U., Pisinger D. (2004) Multiple Knapsack Problems. In: Knapsack Problems. Springer, Berlin,
  31. J. Kennedy, R. Eberhart, Particle Swarm Optimization. Proceedings of IEEE International Conference on Neural Networks. IV. pp. 1942–1948, 1995.
  32. S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi, Optimization by simulated annealing Science (New York, N.Y.) (New York, N.Y.), 13 (220) (1983), pp. 671-680
  33. G.Kochenberger, G.McCarl, F.Wymann, An heuristic for general integer programming, Decision Sciences vol. 5, 34–44, 1974.
  34. Jonas Krause, Jelson Cordeiro, Rafael Stubs Parpinelli, and Heitor Silverio Lopes. A survey ofswarm algorithms applied to discrete optimization problems. InSwarm Intelligence and Bio-Inspired Computation, pages 169191. Elsevier, 2013
  35. E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys. Sequencing and scheduling:algorithms and complexity. In S. C. Graves et al. , editor,Handbooks in OR and MS, volume 4, pages445522. Elsevier Science Publishers, 1993
  36. G.Leguizamon, Z.Michalevich, A new version of ant system for subset problems, Int. Conf. on Evolutionary Computations vol. 2, 1459–1464, 1999.
  37. Qing Liu, Tomohiro Odaka, Jousuke Kuroiwa, Haruhiko Shirai, and Hisakazu Ogura. A newartificial fish swarm algorithm for the multiple knapsack problem. IEICE Transactions on Information and Systems, 97(3):455468, 2014
  38. S. Mirjalili, S. M. Mirjalili, A. Lewis, Grey Wolf Optimizer, Advances in Engineering Software, vol. 69, pp. 46–61, 2014.
  39. M.R. Mosavi, M. Khishe, G.R. Parvizi, M.J. Naseri, M. Ayat, Training multi-layer perceptron utilizing adaptive best-mass gravitational search algorithm to classify sonar dataset Archive of Acoustics, 44 (1) (2019), pp. 137-151
  40. F. D. Murgolo. An efficient approximation scheme for variable-sized bin packing.SIAM Journal onComputing, 16(1):149161, 1987.
  41. Schaffer, A. A., Yannakakis, M.: Simple Local Search Problems that are Hard to Solve. Society for Industrial Applied Mathematics Journal on Computing, Vol 20 (1991) 56–87.
  42. I.H. Osman, Metastrategy simulated annealing and tabue search algorithms for the vehicle routing problem, Annals of Operations Research, 41 (4) (1993), pp. 421-451
  43. S. Ravakhah, M. Khishe, M. Aghababaee, E. Hashemzadeh, Sonar false alarm rate suppression using classification methods based on interior search algorithm, International Journal of Computer Science and Network Security, 17 (7) (2017), pp. 58-65
  44. T. Stutzle, H. Hoos, Max min ant system, Future Generation Computer Systems, vol. 16, 889–914, 2000.
  45. P.A. Vikhar, Evolutionary algorithms: A critical review and its future prospects, Proceedings of the 2016 International Conference on Global Trends in Signal Processing, Information Computing and Communication (ICGTSPICC). Jalgaon, pp. 261–265, 2016.
  46. X.S. Yang, A New Metaheuristic Bat-Inspired Algorithm, Nature Inspired Cooperative Strategies for Optimization, Studies in Computational Intelligence, 284: 65–74, 2010.
  47. X.S. Yang, Nature-Inspired Metaheuristic Algorithms, Luniver Press, 2008.
  48. Andrew J Woodcock and John M Wilson. A hybrid tabue search/branch and bound approach tosolving the generalized assignment problem.European journal of operational research, 207(2):566578, 2010