Research On Membrane Evolutionary Algorithm For Solving The Maximum Clique Problem

The integration limit of core devices limits the further improvement of the computing performance of traditional electronic computers.In order to break the restrictions of traditional computing power,it is particularly important to construct a new set of computing theories.Membrane computing,which belongs to one of the branches of natural computing,is a new computing model that is abstracted based on the biological characteristics and functions of cells.It has the advantages of great parallelism and uncertainty,and can effectively solve the NP-hard problem.At present,membrane computing is currently widely used in computer graphics,automatic control,combinatorial optimization,and graph theory.Solving the maximum clique problem is to find a complete subgraph with the largest number of vertices in a given graph.As a classic combinatorial optimization problem,it not only has a close relationship with other NP-hard problems,but also is widely used in research fields such as fault detection,coding theory,social network analysis,and economic analysis.For example,finding the maximum clique in a real social network can effectively mine hidden social organizations and their behavior patterns.At present,many algorithm theories have been used to solve the maximum clique problem,but there are few related researches based on the membrane computing model to solve the maximum clique problem.After relevant research on the membrane computing model and the maximum clique problem,based on the cell-like P system and membrane algorithm,this thesis proposes a new Membrane Evolutionary Algorithm called MEA.Then,the corresponding membrane evolutionary operators are designed for the maximum clique problem,and a Membrane Evolutionary for Algorithm Maximum Clique Problem named MEAMCP is proposed.Aiming at the shortcomings of the MEAMCP algorithm in some data instances,the MEAMCP related operators were further optimized and improved,and a Phased Membrane Evolutionary Algorithm for Maximum Clique Problem called P?MEAMCP was proposed.Experimental results show that MEAMCP and P?MEAMCP both have better solution accuracy and stability.The main research work of this thesis is as follows:(1)Based on the proposed Membrane Evolutionary Algorithm named MEA,a Membrane Evolutionary Algorithm called MEAMCP capable of solving the maximum clique problem is designed.Experimental results on the DIAMCS data set show that MEAMCP is feasible and has good stability and accuracy.(2)A Phased Membrane Evolutionary Algorithm called P?MEAMCP was designed.The algorithm further improves the performance of the algorithm through redesigned vertex selection strategy and improved membrane evolutionary operators.Experimental results on the DIMACS data set and classic social network examples show that P?MEAMCP has better accuracy.Membrane Evolutionary Algorithm and membrane operators proposed in this thesis are of certain reference value for related research on solving the maximum clique problem based on membrane computing theory.