Thompson Sampling in Heuristic Selection for the Quadratic Assignment Problem
Resumo
Este trabalho propõe uma Hiper-Heurística (HH) de seleção baseada na abordagem Thompson Sampling (TS) para a solução do Problema Quadrático de Alocação (PQA). O PQA tem como objetivo a alocação de instalações em um conjunto de possíveis localidades já conhecidas, a fim de minimizar o custo total de todas as movimentações entre as instalações. A HH proposta é aplicada na configuração automática de um algoritmo memético, atuando na seleção de uma combinação de heurísticas de baixo nível. Cada combinação envolve a seleção de uma heurística de recombinação, de uma estratégia de busca local e de uma heurística de mutação. O algoritmo foi analisado em 15 instâncias do benchmark Nug e o desempenho da HH é superior àquele obtido por qualquer combinação de heurísticas aplicada de forma isolada, demonstrando a sua eficiência na configuração automática do algoritmo. Os experimentos mostram que o desempenho da TS é afetado pela qualidade do conjunto de heurísticas de baixo nível. A melhor versão da HH obtém a solução ótima em 9 instâncias e o desvio médio percentual da solução ótima (gap), considerando todas as 15 instâncias foi de 8,6%, sendo que os maiores gaps foram encontrados para as três maiores instâncias.
Referências
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.
