Research On Gragh Pattern Discovery Algorithm And Optimization Application

The accurate algorithm of frequent sub-graph pattern discovery mainly focuses on sub-graph isomorphism test,but sub-graph isomorphism has been proved to be NP complete problem;and approximation algorithm avoids sub-graph isomorphism test,but the accuracy is lower.Capacitated arc routing problem is a kind of combinatorial optimization problem evolved from graph.When solving combinatorial optimization problems related to graph structure,there are a lot of pattern information related to solution characteristics,which have an important impact on the solution.In view of the above problems,the main work of this thesis includes:(1)An improved frequent sub-graph discovery algorithm is studied.In the proposed algorithm,the fixed size sampler is used to discovery frequent patterns.In the early stage of the algorithm,the non-frequent edge pruning strategy is introduced to reduce the sampling space of Markov Chain Monte Carlo,thus reducing the complexity of the computation time,and the pruned edges are re-coded.In the algorithm,the target distribution function is improved to avoid oversampling,thus improving the accuracy of frequent sub-graph pattern discovery.Finally,the proposed algorithm is applied to the data sets of graph and S_CARP;and the experimental results are compared with the literature algorithm.And the algorithm is applied to the data set of S_CARP to analyze the process of frequent sub-graph discovery,and proposes the concept of similar pattern and optimal pattern.(2)A memetic algorithm based on pattern discovery is studied to solve the capacitated arc routing problem.The algorithm is based on the framework of memetic algorithm,and the global search algorithm adopts the evolutionary model of genetic algorithm,and constructs the pattern information base for the better individuals through the improved frequent sub-graph discovery algorithm after the global search.Local search algorithm contains two stages according to the different search operators.In the first stage,three basic search operators for the solutions in a larger neighborhood.Finally,the proposed algorithm is applied to the benchmark test instance of capacitated arc routing problem,and the experimental results are compared with the literature algorithms.In conclusion,by analyzing the existing problems of frequent subgraph pattern discovery algorithms,this thesis studies an effective frequent subgraph pattern learning algorithm.According to the characteristics of the capacitated arc routing problem,we use the pattern information of the optimal solutions to guide the operator operations,so as to improve the search performance of the memetic algorithm.The feasibility and effectiveness of the algorithm are analyzed and verified by experiments.