Researches On Combinatorial Optimization Methods In Basis Of Deep Reinforcement Learning

Combinatorial optimization problems widely exist in various fields such as national defense,transportation,industry and communication.For decades,traditional operations research optimization methods,such as branch and bound method,heuristic search algorithm and neighborhood search algorithm,are the main means to solve combinatorial optimization problems.However,in practical applications,such as military operation scheduling,network resource allocation and online car hailing,the scale of optimization problems is expanding,and the demand for online optimization is higher and higher.The traditional combinatorial optimization algorithm is facing great computational pressure,which is difficult to realize online solution and rapid decision-making of combinatorial optimization problems.It is urgent to propose new breakthrough methods to overcome the limitations of traditional combinatorial optimization methods.In recent years,with the rapid development of deep learning technology,the remarkable achievements of deep reinforcement learning in the fields of go and robot show its strong learning ability and sequential decision-making ability.Through the characteristics of off-line training and on-line optimization of deep neural network model,it can effectively learn the characteristics of the problem and realize the rapid decision-making of the problem,Thus,it provides a new possibility for the rapid solution of combinatorial optimization problems.Based on this,this paper studies the combinatorial optimization method based on deep reinforcement learning,puts forward the combinatorial optimization framework based on deep reinforcement learning,and carries out research from the aspects of single objective method,multi-objective method and branch and bound method of combinatorial optimization.The main contributions are as follows:(1)A combinatorial optimization framework based on deep reinforcement learning is proposed.In this paper,the process of solving combinatorial optimization problems by deep reinforcement learning method is divided into three steps: model selection according to the type of problem;The deep neural network is designed to model the combinatorial optimization problem;Reinforcement learning method is used to learn the parameters of deep neural network.For each step,the related theories of deep neural network model and deep reinforcement learning method are described,the modeling method of combinatorial optimization problem based on deep neural network is studied in detail,the scientific principle of solving combinatorial optimization problem based on deep reinforcement learning is clarified,and the combinatorial optimization framework and solution paradigm based on deep reinforcement learning are proposed.(2)Aiming at the complex single objective combinatorial optimization problem,a covering traveling salesman combinatorial optimization method based on deep reinforcement learning is proposed.At present,the combinatorial optimization methods based on artificial intelligence are mostly applied to relatively simple combinatorial optimization problems,and there is little research on complex large-scale combinatorial optimization problems.In this paper,the covering traveling salesman problem with complex dynamic characteristics is studied,and a solution method of covering traveling salesman problem based on deep reinforcement learning is proposed,An attention model based on dynamic embedding is designed,which overcomes the limitations of the current artificial intelligence model in dealing with large-scale and dynamic complex problems.Compared with the traditional heuristic methods,the proposed method can improve the solution speed by more than 10 times on the premise of reaching the same optimization level,And the model can be generalized to different types of covering traveling salesman problems.(3)Aiming at the multi-objective combinatorial optimization problem,a multi-objective traveling salesman combinatorial optimization method based on deep reinforcement learning is proposed.At present,the combinatorial optimization methods based on artificial intelligence are studied for single objective problems,and there is still a gap in multiobjective problems.In this paper,the deep reinforcement learning method is used to study the multi-objective combinatorial optimization problem for the first time,a decomposition strategy and a parameter transfer strategy based on neighborhood are designed,and the deep neural network is used to model the problem,The Pareto frontier of the problem is directly output in an end-to-end manner,so as to realize the efficient solution of the multi-objective combinatorial optimization problem.The proposed method outperforms the traditional methods on the multi-objective traveling salesman problem with up to 500 nodes and up to 5 optimization objectives,and has the ability of fast solution and generalization.(4)Aiming at the exact algorithms for combinatorial optimization,a branch and bound combinatorial optimization method based on deep reinforcement learning is proposed.The branch and bound method can obtain the theoretical optimal solution of the combinatorial optimization problem,but the core defect of the traditional branch and bound method is its extremely slow solution speed.This paper uses artificial intelligence technology to improve the traditional branch and bound method,designs a graph pointer neural network model to model the branch strategy,and extracts the global and historical features of the problem,A training method based on the imitation learning is designed,which realizes the optimization performance 40 % faster than the professional optimization solver.Its performance on three different combinatorial optimization problems exceeds the current branch and bound method based on machine learning,and realizes the effective improvement of the solution speed.(5)Finally,the practical application problems are studied based on the deep reinforcement learning optimization method.A UAV path planning task scenario based on wireless energy transmission is considered.The UAV is charged wirelessly through wireless energy transmission technology.The UAV power consumption model,wireless energy transmission model and deep neural network model are established respectively through off-line training The online optimization mode realizes the online optimization of UAV path.Compared with traditional optimization methods such as particle swarm optimization and Google or tools,it improves the solution speed by 5 to 500 times on different scale problems.