Deep Reinforcement Learning for Combinatorial Optimization

Deep reinforcement learning proves its success in solving complicated combinatorial problems. This work studies essential issues of DRL and its applications in the disassembly planning problem for 4D-printed products and energy-aware task planning problems. From the aspect of the methodology, this work utilizes experimental results and theoretical analysis to prove the existence of compatible issues in the deep deterministic policy gradient algorithm. This work is the first to estimate the compatibility in quantity with the Centred Kernel Alignment index and the Normalized Bures Similarity index. To solve this found compatibility issue, a new algorithm is proposed with a modified energy function. The convergence and the satisfaction of the compatible theorem are proved. This work observes that when overestimation happens, the overestimated Q values are much more than the maximum accessible discounted return. Different from the true Q value, the maximum accessible discounted return can be evaluated without biases. This work proposes a light-computation overestimation solver by limiting the outputs of the target critic network with the maximum accessible discounted return. After studying the disadvantages of existing asynchronous parallel learning architecture and experience replay buffer, this work introduces contrastive learning to DRL to propose a new parallel learning architecture, which provides a way for offline policy algorithms to utilize the most recent experienced trajectories. Motivated by the success of using Hebbian learning to solve Markov Decision Process problems, this work proposes a transfer learning architecture to combine Hebbian learning algorithms and DRL. From the aspect of applications, this work is the first to study complete disassembly planning problems for 4D-printed products. Disassembly planning problems for 4D-printed products introduce extra decision variables and model complexity for shape morphing and energy absorbing. This work proposes mathematical models, a product representation model, and a new DRL method for solving the multi-objective problem with DRL. Several uncertainties are considered. Besides, this work is the first to study partial disassembly planning problems for 4D-printed products considering uncertain component qualities. The partial disassembly planning problem adds another complexity in determining the depth of the disassembly work. To solve multi-objective problems, this work proposes a new Hebbian learning algorithm with the mechanism of the non-Dominating sorting and the crowding-distance sorting algorithms. Moreover, this work extends simultaneous task and energy planning problems with multiple scenarios. A modified deep reinforcement learning with an attention-based link information filter is developed to solve the uncertainties in the STEP problem.