Híper-heurísticas com aprendizagem

A otimização nos sistemas de suporte à decisão atuais assume um carácter fortemente interdisciplinar relacionando-se com a necessidade de integração de diferentes técnicas e paradigmas na resolução de problemas reais complexos, sendo que a computação de soluções ótimas em muitos destes problemas é intratável. Os métodos de pesquisa heurística são conhecidos por permitir obter bons resultados num intervalo temporal aceitável. Muitas vezes, necessitam que a parametrização seja ajustada de forma a permitir obter bons resultados. Neste sentido, as estratégias de aprendizagem podem incrementar o desempenho de um sistema, dotando-o com a capacidade de aprendizagem, por exemplo, qual a técnica de otimização mais adequada para a resolução de uma classe particular de problemas, ou qual a parametrização mais adequada de um dado algoritmo num determinado cenário. Alguns dos métodos de otimização mais usados para a resolução de problemas do mundo real resultaram da adaptação de ideias de várias áreas de investigação, principalmente com inspiração na natureza - Meta-heurísticas. O processo de seleção de uma Meta-heurística para a resolução de um dado problema é em si um problema de otimização. As Híper-heurísticas surgem neste contexto como metodologias eficientes para selecionar ou gerar heurísticas (ou Meta-heurísticas) na resolução de problemas de otimização NP-difícil. Nesta dissertação pretende-se dar uma contribuição para o problema de seleção de Metaheurísticas respetiva parametrização. Neste sentido é descrita a especificação de uma Híperheurística para a seleção de técnicas baseadas na natureza, na resolução do problema de escalonamento de tarefas em sistemas de fabrico, com base em experiência anterior. O módulo de Híper-heurística desenvolvido utiliza um algoritmo de aprendizagem por reforço (QLearning), que permite dotar o sistema da capacidade de seleção automática da Metaheurística a usar no processo de otimização, assim como a respetiva parametrização. Finalmente, procede-se à realização de testes computacionais para avaliar a influência da Híper- Heurística no desempenho do sistema de escalonamento AutoDynAgents. Como conclusão genérica, é possível afirmar que, dos resultados obtidos é possível concluir existir vantagem significativa no desempenho do sistema quando introduzida a Híper-heurística baseada em QLearning.

Optimization in current decision support systems has a highly interdisciplinary nature related with the need to integrate different techniques and paradigms in solving real-world complex problems. Computing optimal solutions in many of these problems are unmanageable. Heuristic search methods are known to obtain good results in an acceptable time interval. Often, parameters need to be adjusted to allow good results. In this sense, learning strategies can enhance the performance of a system, providing it with the ability to learn, for instance, the most suitable optimization technique for solving a particular class of problems, or the most suitable parameterization of a given algorithm on a given scenario. Some of the most used optimization methods for solving real world problems resulted from the adaptation of ideas from several areas of research, especially the ones inspired by nature - Metaheuristics. The process of selecting a Metaheuristics for solving a given problem is by itself an optimization problem. The Hyper-heuristics arise in this context as efficient methodologies for selecting or generating heuristics (or Metaheuristics) to solve NP-hard optimization problems. This thesis aims to make a contribution to the problem of selection of Metaheuristics and respective parameterization. In this sense, the specification of a Hyper-heuristic is describes for the selection of techniques based in nature, in solving the problem of scheduling in manufacturing systems, based on previous experience. The developed Hyper-heuristic module uses a reinforcement learning algorithm (Q-Learning), which enables the system with the ability to autonomously select the Metaheuristics to use in optimization process as well as the respective parameters. Finally, a computational study was carried out to evaluate the influence of the Hyper-heuristics on the performance of the AutoDynAgents system. As a general conclusion, we can say from the results obtained that there is significant advantage in using the system with the Q-Learning based Hyper-heuristic.