Research On Membrane Algorithm With Preprocessing For The Minimum Vertex Cover Problem

Several important applications related to complex network analysis require finding small vertex covers in massive graphs at an acceptable time cost.To fulfill this task,this thesis proposes a general algorithm framework PEAF,which divides the process of obtaining a vertex cover into three stages: preprocessing stage,solution stage,and inverse-processing stage.Based on PEAF,a minimum vertex cover(Min VC)solver PEAVC is developed,which uses a new preprocessor(Pre P)to reduce the graph;for the connected components of bipartite graphs and other connected components,PEAVC uses BGVC and FastVC2 to obtain their vertex cover respectively;finally,this thesis develops an inverse processor matching with Pre P(Inv＿Pre P)to get a minimum vertex cover of the original problem.In recent years,more and more attention has been paid to the membrane evolutionary algorithm framework MEAF inspired by the membrane computing idea in the application of membrane computing.MEAF has its unique evolutionary operators:division,fusion,cytolysis,and selection.Based on MEAF,this thesis implements and improves the operators,and obtains a Min VC solver Q-Mea Meta VC.This thesis takes the minimum vertex cover problem(Min VCP)as the research object to carry out the related theoretical and technology research.The main contents and contributions of this thesis are listed below:(1)This thesis proposes a general algorithm framework PEAF for Min VCP and designs a Min VC solver PEAVC based on PEAF.(2)In PEAVC,we solve the convergence problem of the fold rule and develop a preprocessor Pre P.For 90 instances of massive sparse graphs in the REAL-WORLD benchmark,Pre P can reduce 48 instances(53%)to empty,which means that these instances can be solved accurately.(3)In PEAVC,a solution architecture of Min VCP based on BGVC and FastVC2 is designed,which makes PEAVC gets 7 more exact results.(4)The solver PEAVC obtains 5 best known results which have not been reported in any literature.(5)A solver named Q-Mea Meta VC based on membrane evolutionary algorithm is designed and implemented.We research 35 instances that PEAVC can’t get the exact result.Q-Mea Meta VC can get the best known results of 29 instances,6 of them have never been reported in any literature.In this thesis,we obtain a new algorithm for the Min VCP and verify the feasibility and effectiveness of the membrane evolutionary algorithm in solving the Min VCP.