Implementation and Evaluation of a Deep Reinforcement Learning Model for Combinatorial Optimization Problems
Autores
|
7555 |
753,3264
|
|
|
7556 |
753,3264
|
Informações:
Publicações do PESC
Problemas de Otimização Combinatória (CO) são muito importantes em diversas aplicações do mundo real, mas resolvê-los pode ser frequentemente desafiador. Neste trabalho, exploramos técnicas de Aprendizado por Reforço Profundo (DRL) para treinar agentes para resolver problemas de otimização combinatória, com foco no Structure2Vec Deep Q-Network (S2V-DQN), um dos primeiros modelos que utilizam DRL para aprender representações de vértices e construir boas soluções para esses problemas.
Apresentamos nossa própria implementação, desenvolvida inteiramente do zero, e a avaliamos em dois problemas: o Problema do Caixeiro Viajante (TSP) e o Problema da Cobertura de Vértices Mínima (MVC). Além disso, analisamos como certos hiperparâmetros impactam o aprendizado e discutimos os desafios encontrados durante a fase experimental.
Combinatorial Optimization (CO) problems are very important in many real-world applications, but solving them can often be very challenging. In this work, we explore Deep Reinforcement Learning (DRL) techniques to train agents to solve CO problems, focusing on Structure2Vec Deep Q-Network (S2V-DQN), a foundational model that uses DRL to learn node embeddings and construct good solutions for these problems.
We provide our own implementation, developed entirely from scratch, and evaluate it on two CO problems: the Traveling Salesman Problem (TSP) and the Minimum Vertex Cover (MVC) problem. Moreover, we analyze how certain hyperparameters impact learning and discuss the challenges encountered during the experimental phase.
