Research On The Maximum Weight Matching Problem Based On Deep Reinforcement Learnin

Maximum weighted matching problem,i.e.,finding a matching in any weighted graph to maximize the sum of the weights of the edges of that matching,is a fundamental problem in graph theory and combinatorial optimization,and has a wide range of applications in various fields,such as biotechnology,web services,and social analytics.The current fastest exact algorithm can find the optimal solution in polynomial time,but still cannot satisfy large-scale graph scenarios.Approximate-based and heuristic-based algorithms strive to find a balance between accuracy and efficiency,however,they are fixed strategies that cannot learn from experience to self-optimize during the solution process and usually lack the ability to generalize.To overcome these limitations,more research attempts to introduce machine learning techniques into the solution of combinatorial optimization,using data-driven methods to learn effective decision rules or optimize strategies,thus improving the performance and generalization ability of the algorithms.Reinforcement learning as one of the machine learning techniques excels in solving decision problems because it can continuously update its own behavioral strategies by interacting with the environment to achieve the goal of maximizing the cumulative reward.Also,reinforcement learning techniques can be combined with deep learning techniques to extract feature information in the graph structure,thus enhancing the expressiveness and generalization of the model.Inspired by this,this paper aims at solving the maximum weighted matching problem and uses deep reinforcement learning to learn solving strategies to achieve a balance between accuracy and efficiency.The main findings of this paper are as follows:(1)In this paper,a reinforcement learning-based framework for solving the maximum weighted matching problem,L2M(Learn to Match),is proposed for the first time.The key idea is to map the maximum weighted matching solution process to a Markov Decision Process to find the optimal matching by multi-step decision making.To improve the efficiency of the solution,we design action patterns that support simultaneous selection of multiple edges.In addition,we propose a state transfer function with a rollback mechanism,which enables to effectively eliminate the conflict problem caused by selecting multiple edges at one time.Extensive experiments on synthetic and realworld datasets demonstrate that the L2 M framework achieves a better balance between accuracy and efficiency than traditional approximation-based and heuristic-based algorithms.And the reinforcement learning based design effectively overcomes the challenge of difficulty in obtaining high-quality training data by self-supervised learning methods.(2)We propose a maximum weighted matching algorithm based on edge embedding network,which captures graph structure information and outputs it as an edge feature vector,enabling end-to-end solution of the edge selection problem.The edge embedding network uses nodes as a transmission channel for feature information as well as a temporary storage area,and edges update features based on the set of neighboring feature information on the endpoints.The edge embedding network effectively overcomes the challenge that current machine learning solvers cannot be directly applied to the edge selection problem,and effectively avoids the large time overhead of line graph transformation operations.Theoretical proofs and experimental results show that the L2 M framework augmented by the edge embedding network can solve the maximum weighted matching problem with()time complexity and has excellent scalability and generalization,and the decision model can be directly applied to unknown graphs of larger size for solution.