Aprendendo Algoritmos de Otimização Combinatória através de Aprendizagem por Reforço Profunda

Aprendendo Algoritmos de Otimização Combinatória através de Aprendizagem por Reforço Profunda

• Autor
• Moésio Wenceslau da Silva Filho
• Co-autores
• Rafael Ferreira Leite de Mello , Péricles Barbosa Cunha de Miranda
• Resumo

• O projeto "Aprendendo Algoritmos de Otimização Combinatória através de Aprendizagem por Reforço Profunda" buscou investigar o desempenho de métodos DRL em diferentes problemas de otimização combinatória e otimização global, para compreender as vantagens, desvantagens e limitações desses métodos. Durante o período de Maio/2021 a Agosto/2021, foi estudado o caso de otimização global.

  Com esse intuito, o projeto foi divido em 4 etapas distintas: (1) Revisão da literatura; (2) Definição do arranjo experimental e escolha dos algoritmos DRL para testes; (3) Criação e organização dos códigos em repositório público; (4) Escrita do artigo e execução dos experimentos. 

  Durante a etapa (1), foram levantados os métodos DRL estado da arte e diferentes problemas clássicos de otimização global. Além disso, foram pontuados diferentes trabalhos que consideraram abordagens DRL para otimização global, demonstrando que esse é um tópico recente, animado e promissor. Todavia, foi-se verificado a existência de um cenário pouco estudado: alta dimensionalidade e os algoritmos de otimização aprendidos são de ordem zero (i. e., não dependem das derivadas da função a ser otimizada). Dessa forma, os experimentos foram realizados considerando esse cenário. 

  Já durante a etapa (2), foram definidos o arranjo experimental e os algoritmos DRL usados para os experimentos. Foram considerados 8 problemas de otimização global e 5 algoritmos DRL Policy Search (REINFORCE, SAC, TD3, PPO e TD3-IG, uma versão modificada do TD3 proposta neste trabalho). Os experimentos consistiam em 2 fases: (i) Uma fase de treinamento, onde os métodos escolhidos são utilizados para se aprender um algoritmo de otimização; (ii) Uma fase de avaliação, onde os algoritmos aprendidos são comparados entre si. Ademais, durante essa etapa também foram escolhidos os hiperparâmetros para cada um dos algoritmos.

  Durante as etapas (3) e (4), foram implementados os algoritmos escolhidos e executados os códigos de treino e avaliação. Os resultados apontam que os métodos DRL Policy Search considerados conseguiram aprender algoritmos de otimização de ordem zero para grandes dimensões. Em especial, as adaptações incorporadas no TD3-IG permitiram aprender, de forma geral, algoritmos de otimização mais rápidos, robustos e precisos quando comparados aos demais. Todavia, são necessárias mais investigações considerando outros algoritmos e adaptações.

• Palavras-chave
• Aprendizado de Máquina, Inteligência Artificial, Aprendizagem por Reforço Profundo, Otimização;
• Área Temática
• Computação (SEDE)