Uma abordagem hiper-heurística para problemas de otimização (Atena Editora)

Abstract

Existe, no mundo hoje, uma comunidade empenhada em descobrir novas formas de resolver problemas NP-hard. Tais problemas não admitem soluções em tempo de execução polinomial. Por isso, investem-se enormes esforços no estudo de alternativas que tornem possível a obtenção de soluções aproximadas através de algoritmos heurísticos. Neste cenário, surgem hiper-heurísticas, como um framework capaz de recomendar heurísticas de baixo nível específicas, bem como os ajustes de parâmetros necessários para um desempenho eficiente. A hiper-heurística usa um conjunto de heurísticas organizadas em um bloco separado do domínio do problema. Hiper-heurísticas competitivas, em geral, não estão totalmente emancipadas de ajustes de parâmetros, existindo quase sempre rudimentares mecanismos determinísticos de mudança de comportamento algorítmico. Esta dissertação propõe um mecanismo de controle adaptativo para equipar uma hiper-heurística aplicada ao problema de roteamento de veículos. Para tanto, foram realizados experimentos computacionais e análise dos resultados que dão evidências de notória melhora no desempenho para instâncias desafiadoras encontradas na literatura.