Thompson Sampling in Heuristic Selection for the Quadratic Assignment Problem
Abstract
In this work we propose a selection Hyper-Heuristic (HH) based on the Thompson Sampling (TS) approach to the solution of Quadratic Assignment Problem (QAP). The QAP aims to allocate facilities in a set of possible known locations, in order to minimize the total cost of all movements between facilities. The proposed HH is applied in the automatic configuration of a memetic algorithm, acting on the selection of a combination of low-level heuristics. Each combination involves the selection of a recombination heuristic, a local search strategy and a mutation heuristic. The algorithm was tested in 15 instances of Nug benchmark and the performance of HH is superior to that obtained by any combination of heuristics applied in isolation, demonstrating its efficiency in the automatic configuration of the algorithm. Experiments show that TS performance is affected by the quality of the set of low-level heuristics. The best version of HH obtains the optimal solution in 9 instances and the mean percentage deviation of the optimal solution (gap), considering all 15 instances, was 8.6%, with the largest gaps found for the three largest instances.
References
Burke, E., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., ¨Ozcan, E., and Qu, R. (2013). Hyper-heuristics: A survey of the state of the art. Journal of the Operational Research Society, 64:1695–1724.
de Oliveira Neto, L. G. (2017). Um algoritmo imuno-inspirado para o problema quadrático de alocação. Master’s thesis, Faculdade de Engenharia Elétrica e de Computação/UNICAMP.
Drake, J. H., Kheiri, A., Özcan, E., and Burke, E. K. (2020). Recent advances in selection hyper-heuristics. European Journal of Operational Research, 285(2):405 – 428.
Engelbrecht, A. P. (2007). Computational Intelligence: An Introduction. John Wiley & Sons Inc, 2 edition.
Knowles, J. and Corne, D. (2003). Instance generators and test suites for the multiobjective quadratic assignment problem. In Fonseca, C., Fleming, P., Zitzler, E., Deb, K., and Thiele, L., editors, Evolutionary Multi-Criterion Optimization, Second International Conference, EMO 2003, Faro, Portugal, April 2003, Proceedings, number 2632 in LNCS, pages 295–310. Springer.
Loiola, E. M., de Abreu, N. M. M., and Netto, P. O. B. (2004). Uma revisão comentada das abordagens do problema quadrático de alocação. Pesquisa Operacional, pages 73 – 109.
Moreira, D. A. (2011). Pesquisa operacional: curso introdutório. Cengage Learning, 2 edition.
Nugent, C. E., Vollmann, T. E., and Ruml, J. (1968). An experimental comparison of techniques for the assignment of facilities to locations. Oper. Res., 16(1):150–173.
Pillay, N. and Qu, R. (2018). Hyper-heuristics: theory and applications. Springer Nature, 1 edition.
Rodrigues, O. A. M. (2017). Aprendizado por reforço baseado em agrupamentos para recomendação na ausência de informação prévia. Master’s thesis, Programa de PósGraduação em Modelagem Matemática e Computacional/CEFET-MG.
Russo, D. J., Roy, B. V., Kazerouni, A., Osband, I., and Wen, Z. (2021). A tutorial on thompson sampling.
Sabar, N. R., Ayob, M., Kendall, G., and Qu, R. (2015). A dynamic multiarmed bandit-gene expression programming hyper-heuristic for combinatorial optimization problems. IEEE Transactions on Cybernetics, 45(2):217–228.
Sahni, S. and Gonzales, T. (1976). P-complete approximation problems. Journal of the Association for Computing Machinery, 23(3):555–565.
Sucupira, I. R. (2007). Um estudo empírico de hiper-heurísticas. Master’s thesis, Instituto de Matemática e Estatística/USP.
Thompson, W. R. (1933). On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285–294.
Çela, E. (2013). The Quadratic Assignment Problem: Theory and Algorithms. Combinatorial Optimization. Springer US.
