Combinatorial optimization using Recurrent Neural Network and Reinforcement Learning

The Combinatorial optimization problems are traditionally solved with handcrafted heuristics. Finding these heuristics for an unseen or a poorly solved problem can be a challenge and the engineer cost can be high. On the other hand, Machine Learning models yield incredible results in many fields like text categorization, image processing, speech recognition and many others. The recent idea of using Machine Learning models to learn heuristics for Combinatorial optimization problem can save human engineer cost. In this thesis, we explain in more depth the framework introduced by Bello et al. in Neural Combinatorial Optimization with Reinforcement Learning. Their work uses Recurrent Neural Networks and Reinforcement Learning to learn heuristics. The model uses LSTM encoder and decoder, along with Neural Attention mechanisms. The model is trained using the REINFORCE algorithm with a Critic Network as baseline. To obtain better results, some search strategies are also used. Since their paper is made for experienced people, we give a more complete description of the components of the model, such that someone without knowledge about Recurrent Neural Network could understand it. We also try to reproduce their results on the famous Traveling Salesman Problem but with three simple modifications of their model and one more search strategy, 2opt. This strategy is used to improve the performances since the model doesn’t necessarily produce local optima solutions. As Bello et al., we compare our results against the OR Tools and Concorde solvers but we also add simpler baselines with Nearest Neighbor and 2opt. We also test if the model is able to generalize to variable problem sizes.