Skip to main content
SpringerLink
Log in

Hyper-Heuristic Based NSGA-III for the Many-Objective Quadratic Assignment Problem

  • Conference paper
  • First Online:
Intelligent Systems (BRACIS 2021)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 13073))

Included in the following conference series:

Abstract

The Quadratic Assignment Problem (QAP) can be subdivided into different versions, being present in several real-world applications. In this work, it is used a version that considers many objectives. QAP is an NP-hard problem, so approximate algorithms are used to address it. This work analyzes a Hyper-Heuristic (HH) that selects genetic operators to be applied during the evolutionary process. HH is based on the NSGA-III framework and on the Thompson Sampling approach. Our main contribution is the analysis of the use of a many objective algorithm using HH for QAP, as this problem was still under-explored in the context of many objective optimization. Furthermore, we analyze the behavior of operators forward the changes related to HH (TS). The proposal was tested considering 42 instances with 5, 7 and 10 objectives. The results, interpreted using the Friedman statistical test, were satisfactory when compared to the original algorithm (without HH), as well as when compared to algorithms in the literature: MOEA/DD, MOEA/D, SPEA2, NSGA-II and MOEA/D-DRA.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 79.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 99.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. Abdel-Basset, M., Manogaran, G., Rashad, H., Zaied, A.N.: A comprehensive review of quadratic assignment problem: variants, hybrids and applications. In: Journal of Ambient Intelligence and Humanized Computing, pp. 1–24 (2018)

    Google Scholar 

  2. Koopmans, T.C., Beckmann, M.: Assignment problems and the location of economic activities. Econometrica 25(1), 53–76 (1957)

    Article  MathSciNet  Google Scholar 

  3. Uluel, M., Ozturk, Z.K.: Solution approaches to multiobjective quadratic assignment problems. In: European Conference on Operational Research (2016)

    Google Scholar 

  4. Fritsche, G.: The cooperation of multi-objective evolutionary algorithms for many-objective optimization. Ph.D. dissertation, Universidade Federal do Paraná, Curitiba, PR, BR (2020)

    Google Scholar 

  5. Deb, K., Jain, H.: An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: Solving problems with box constraints. IEEE Trans. Evol. Comput. 18(4), 577–601 (2014)

    Article  Google Scholar 

  6. Burke, E., et al.: Hyper-heuristics: a survey of the state of the art. J. Oper. Res. Soc. 64, 1695–1724 (2013)

    Google Scholar 

  7. Thompson, W.R.: On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25(3–4), 285–294 (1933)

    Google Scholar 

  8. Li, K., Deb, K., Zhang, Q., Kwong, S.: An evolutionary many-objective optimization algorithm based on dominance and decomposition. IEEE Trans. Evol. Comput. 19(5), 694–716 (2015)

    Article  Google Scholar 

  9. Zhang, Q., Li, H.: MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 11(6), 712–731 (2007)

    Article  Google Scholar 

  10. Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: Improving the strength pareto evolutionary algorithm for multiobjective optimization, vol. 3242 (2001)

    Google Scholar 

  11. Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)

    Article  Google Scholar 

  12. Zhang, Q., Liu, W., Li, H.: The performance of a new version of moea/d on cec09 unconstrained mop test instances. In: Congress on Evolutionary Computation, pp. 203–208. IEEE Press (2009)

    Google Scholar 

  13. Çela, E.: The Quadratic Assignment Problem: Theory and Algorithms, ser. Combinatorial Optimization. Springer, US (2013)

    Google Scholar 

  14. Sabar, N., Ayob, M., Kendall, G., Qu, R.: A dynamic multiarmed bandit-gene expression programming hyper-heuristic for combinatorial optimization problems. IEEE Trans. Cybern. 45, 06 (2014)

    Google Scholar 

  15. Pillay, N., Qu, R.: Hyper-heuristics: theory and applications, 1st ed. Springer Nature (2018). https://doi.org/10.1007/978-3-319-96514-7

  16. Drake, J.H., Kheiri, A., Özcan, E., Burke, E.K.: Recent advances in selection hyper-heuristics. Eur. J. Oper. Res. 285(2), 405–428 (2020)

    Article  MathSciNet  Google Scholar 

  17. Talbi, E.-G.: Metaheuristics: From Design to Implementation. Wiley, Hoboken (2009)

    Google Scholar 

  18. Oliver, I., Smith, D., Holland, J.R.: Study of permutation crossover operators on the traveling salesman problem. In: Genetic Algorithms and Their Applications: Proceedings of the Second International Conference on Genetic Algorithms: July 28–31, at the Massachusetts Institute of Technology, Cambridge, MA. Hillsdale, NJ: L. Erlhaum Associates. (1987)

    Google Scholar 

  19. Larranaga, P., Kuijpers, C., Murga, R., Inza, I., Dizdarevic, S.: Genetic algorithms for the travelling salesman problem: a review of representations and operators. Artif. Intell. Rev. 13, 129–170 (1999)

    Google Scholar 

  20. Russo, D.J., Roy, B.V., Kazerouni, A., Osband, I., Wen, Z.: A tutorial on thompson sampling. Found. Trends Mach. Learn. 11, 1–96 (2018)

    Article  Google Scholar 

  21. Zitzler, E., Laumanns, M., Bleuler, S.: A tutorial on evolutionary multiobjective optimization. In: Gandibleux, X., Sevaux, M., Sörensen, K., T’kindt, V. (Eds.) Metaheuristics for Multiobjective Optimisation, Springer, Berlin Heidelberg, pp. 3–37 (2004). https://doi.org/10.1007/978-3-642-17144-4_1

  22. Dokeroglu, T., Cosar, A.: A novel multistart hyper-heuristic algorithm on the grid for the quadratic assignment problem. Eng. Appl. Artif. Intell. 52, 10–25 (2016)

    Article  Google Scholar 

  23. Dokeroglu, T., Cosar, A.: A novel multistart hyper-heuristic algorithm on the grid for the quadratic assignment problem. Eng. Appl. Artif. Intell. 52, 10–25 (2016)

    Google Scholar 

  24. Senzaki, B.N.K., Venske, S.M., Almeida, C.P.: Multi-objective quadratic assignment problem: an approach using a hyper-heuristic based on the choice function. In: Cerri, R., Prati, R.C. (eds.) Intelligent Systems, pp. 136–150. Springer International Publishing, Cham (2020). https://doi.org/10.1007/978-3-030-61377-8_10

    Chapter  Google Scholar 

  25. Drugan, M.M.: Stochastic pareto local search for many objective quadratic assignment problem instances. In: 2015 IEEE Congress on Evolutionary Computation (CEC), pp. 1754–1761, May 2015

    Google Scholar 

  26. Rahimi, I., Gandomi, A.: Evolutionary many-objective algorithms for combinatorial optimization problems: A comparative study. Arch. Comput. Methods Eng. 28, 03 (2020)

    MathSciNet  Google Scholar 

  27. de Almeida, C.P.: Transgenética computacional aplicada a problemas de otimização combinatória com múltiplos objetivos. Ph.D. dissertation, Federal University of Technology - Paraná, Brazil (2013)

    Google Scholar 

  28. Castro, O.R., Pozo, A.: A mopso based on hyper-heuristic to optimize many-objective problems. In: 2014 IEEE Symposium on Swarm Intelligence, pp. 1–8 (2014)

    Google Scholar 

  29. Walker, D.J., Keedwell, E.: Towards many-objective optimisation with hyper-heuristics: identifying good heuristics with indicators. In: Handl, J., Hart, E., Lewis, P.R., López-Ibáñez, M., Ochoa, G., Paechter, B. (eds.) PPSN 2016. LNCS, vol. 9921, pp. 493–502. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45823-6_46

    Chapter  Google Scholar 

  30. Kuk, J., Gonçalves, R., Almeida, C., Venske, S., Pozo, A.: A new adaptive operator selection for nsga-iii applied to cec 2018 many-objective benchmark. In: 2018 7th Brazilian Conference on Intelligent Systems (BRACIS), pp. 7–12 (2018)

    Google Scholar 

  31. Fritsche, G., Pozo, A.: The analysis of a cooperative hyper-heuristic on a constrained real-world many-objective continuous problem. In: 2020 IEEE Congress on Evolutionary Computation (CEC), pp. 1–8 (2020)

    Google Scholar 

  32. Friesche, G., Pozo, A.: Cooperative based hyper-heuristic for many-objective optimization. In: Genetic and Evolutionary Computation Conference, ser. GECCO ’19. New York, NY, USA: Association for Computing Machinery, pp. 550–558 (2019)

    Google Scholar 

  33. Knowles, J., Corne, D.: Instance generators and test suites for the multiobjective quadratic assignment problem. In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Thiele, L., Deb, K. (eds.) EMO 2003. LNCS, vol. 2632, pp. 295–310. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36970-8_21

    Chapter  Google Scholar 

  34. Ishibuchi, H., Masuda, H., Tanigaki, Y., Nojima, Y.: Modified distance calculation in generational distance and inverted generational distance. In: Gaspar-Cunha, A., Henggeler Antunes, C., Coello, C.C. (eds.) EMO 2015. LNCS, vol. 9019, pp. 110–125. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-15892-1_8

    Chapter  Google Scholar 

  35. Nebro, A.J., Durillo, J.J., Vergne, M.: Redesigning the jmetal multi-objective optimization framework. In: Conference on Genetic and Evolutionary Computation, ser. GECCO Companion ’15. New York, NY, USA: Association for Computing Machinery, pp. 1093–100 (2015)

    Google Scholar 

  36. Conover, W.: Practical nonparametric statistics, 3rd ed., ser. Wiley series in probability and statistics. New York, NY [u.a.]: Wiley (1999)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Midwestern Paraná State University - UNICENTRO, Paraná, Brazil

    Bianca N. K. Senzaki, Sandra M. Venske & Carolina P. Almeida

Authors
  1. Bianca N. K. Senzaki
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sandra M. Venske
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Carolina P. Almeida
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Universidade Federal de Sergipe, São Cristóvão, Brazil

    André Britto

  2. Universidade de São Paulo, São Paulo, Brazil

    Karina Valdivia Delgado

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Senzaki, B.N.K., Venske, S.M., Almeida, C.P. (2021). Hyper-Heuristic Based NSGA-III for the Many-Objective Quadratic Assignment Problem. In: Britto, A., Valdivia Delgado, K. (eds) Intelligent Systems. BRACIS 2021. Lecture Notes in Computer Science(), vol 13073. Springer, Cham. https://doi.org/10.1007/978-3-030-91702-9_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-91702-9_12

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-91701-2

  • Online ISBN: 978-3-030-91702-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation