Estratégias de Busca Reativa Utilizando Aprendizagem por Reforço e Algoritmos de Busca Local
Aprendizagem por reforço
Busca Reativa
Busca Local
Busca em Vizinhança Variável
Otimização Combinatória
Técnicas de otimização conhecidas como as metaheurísticas tem conseguido resolver
satisfatoriamente problemas conhecidos, mas desenvolvimento das metaheurísticas é
caracterizado por escolha de parâmetros para sua execução, na qual a opção apropriada
destes parâmetros (valores). Onde o ajuste de parâmetro é essencial testa-se os parâmetros
até que resultados viáveis sejam obtidos, normalmente feita pelo desenvolvedor que esta
implementando a metaheuristica. A qualidade dos resultados de uma instância1 de teste
não será transferida para outras instâncias a serem testadas e seu feedback pode requerer
um processo lento de “tentativa e erro” onde o algoritmo têm que ser ajustado para uma
aplicação especifica. Diante deste contexto das metaheurísticas surgiu a Busca Reativa
que defende a integração entre o aprendizado de máquina dentro de buscas heurísticas
para solucionar problemas de otimização complexos. A partir da integração que a Busca
Reativa propõe entre o aprendizado de máquina e as metaheurísticas, surgiu a ideia de
se colocar a Aprendizagem por Reforço mais especificamente o algoritmo Q-learning de
forma reativa, para selecionar qual busca local é a mais indicada em determinado instante
da busca, para suceder uma outra busca local que não pode mais melhorar a solução
corrente na metaheurística VNS. Assim, neste trabalho propomos uma implementação reativa,
utilizando aprendizado por reforço para o auto-tuning do algoritmo implementado,
aplicado ao problema do caixeiro viajante simétrico e ao problema escalonamento sondas
para manutenção de poços.