Research On Solving Method Of Constraint Satisfaction Problem Combined With Reinforcement Learning

The Constraint Satisfaction Problem(CSP)is an important area of research in fields such as computer science and operations research for modeling and simulating many real-world problems,including problems such as task scheduling and resource allocation.In addition,CSP is applied to artificial intelligence to help solve problems in natural language processing,image recognition,and other areas.Unlike machine learning,constraint satisfaction problems focus more on the constraints of the problem itself,i.e.,constraints,and thus CSP is also a problem of efficient allocation of variable values under satisfying constraints.There are many classical algorithms available for solving CSP,including search algorithms,constraint propagation,and local search.The Traveling Salesman Problem(TSP)is a special class of constraint satisfaction problems that have been successfully applied in areas such as grid layout,circuit design,and logistics distribution.In recent years,a series of new neural network-based approaches have been proposed in academia for the Traveling Salesman Problem,which can be summarized into two categories: one using a sequence-to-sequence based modeling-to-solution idea;and the other using node features and edge features of Graph Neural Network to learn the constraints.Although the problems proposed today are more mature in solving specific problems,there are still some problems and challenges,such as difficulty in generalizing to larger-scale problems,difficulty in solving problems with heterogeneous distributions,and poor solution quality.To address the problem of poor solution quality,this paper makes improvements and innovations based on previous research,as follows:(1)A global regret pre-training model for learning the TSP problem is proposed,which addresses the existing heuristic solvers with long time consuming and insufficient accuracy in the prediction phase.The pre-training model efficiently learns node-to-node correlation information through the message passing mechanism of the graph neural network,capturing the gap between each edge and the optimal policy.In the solution process,the global regret of each edge is first predicted by the practical pre-training model,and then a better initial solution is obtained by the greedy search strategy,which reduces the number of rounds of heuristic iterations and improves the performance of model prediction.(2)A neural network model with learning 2-Opt heuristic is proposed to combine the proposed pre-trained model with the neural network model with learning 2-Opt heuristic.Since the prediction results of the pre-training deviate from the optimal solution,the initial solution obtained from the pre-training model is optimized iteratively by the 2-Opt heuristic,so as to further improve the solution solving efficiency.Experimental results show that the model approach proposed in this paper successfully learns a powerful 2-Opt selection strategy that can solve TSP problems of sizes 20,50,and 100 well,and outperforms classical exact algorithms,heuristics,and other learning heuristics,especially on larger scale problems.