Approximating meta-heuristics with homotopic recurrent neural networks

Abstract

Much combinatorial optimisation problems constitute a non-polynomial (NP) hard optimisation problem, i.e., they can not be solved in polynomial time. One such problem is finding the shortest route between two nodes on a graph. Meta-heuristic algorithms such as $A^{\ast }$ along with mixed-integer programming (MIP) methods are often employed for these problems. Our work demonstrates that it is possible to approximate solutions generated by a meta-heuristic algorithm using a deep recurrent neural network. We compare different methodologies based on reinforcement learning (RL) and recurrent neural networks (RNN) to gauge their respective quality of approximation. We show the viability of recurrent neural network solutions on a graph that has over 300 nodes and argue that a sequence-to-sequence network rather than other recurrent networks has improved approximation quality. Additionally, we argue that homotopy continuation -- that increases chances of hitting an extremum -- further improves the estimate generated by a vanilla RNN.

References in corpus (7)

• Adam: A Method for Stochastic Optimization
• Neural Machine Translation by Jointly Learning to Align and Translate
• A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning
• Dueling Network Architectures for Deep Reinforcement Learning
• A Neural Conversational Model
• Training Recurrent Neural Networks by Diffusion
• Bayesian Belief Updating of Spatiotemporal Seizure Dynamics

Cited by in corpus (3)

• Learning to Perform Local Rewriting for Combinatorial Optimization
• How Robust are Deep Neural Networks?
• StackSeq2Seq: Dual Encoder Seq2Seq Recurrent Networks