Take a Step and Reconsider: Sequence Decoding for Self-Improved Neural Combinatorial Optimization
This work addresses the challenge of improving solution diversity and quality in combinatorial optimization for researchers and practitioners, representing an incremental advancement in decoding techniques.
The paper tackles the problem of generating high-quality pseudo-labels for self-improved learning in Neural Combinatorial Optimization by proposing a sequence decoding method that samples without replacement and revisits intermediate solutions, resulting in strong performance on problems like the Traveling Salesman Problem and outperforming previous methods on the Job Shop Scheduling Problem.
The constructive approach within Neural Combinatorial Optimization (NCO) treats a combinatorial optimization problem as a finite Markov decision process, where solutions are built incrementally through a sequence of decisions guided by a neural policy network. To train the policy, recent research is shifting toward a 'self-improved' learning methodology that addresses the limitations of reinforcement learning and supervised approaches. Here, the policy is iteratively trained in a supervised manner, with solutions derived from the current policy serving as pseudo-labels. The way these solutions are obtained from the policy determines the quality of the pseudo-labels. In this paper, we present a simple and problem-independent sequence decoding method for self-improved learning based on sampling sequences without replacement. We incrementally follow the best solution found and repeat the sampling process from intermediate partial solutions. By modifying the policy to ignore previously sampled sequences, we force it to consider only unseen alternatives, thereby increasing solution diversity. Experimental results for the Traveling Salesman and Capacitated Vehicle Routing Problem demonstrate its strong performance. Furthermore, our method outperforms previous NCO approaches on the Job Shop Scheduling Problem.