Research On Membrane Evolutionary Algorithm For Solving The 3-Satisfiability Problem

Membrane evolutionary algorithm is an evolutionary algorithm abstracted from the structure and activity of cells.As the application of membrane computing,the natural parallel framework is the main feature of membrane evolutionary algorithm.In recent years,it has been widely used to solve all kinds of NP hard problems and obtains better application results.SAT problem is one of the core problems in computer science,and it is also the first NP complete problem proved,which has attracted the attention of many researchers.3-SAT problem is a representative category of SAT problem,which is widely related to many fields of computer science,and plays an important role in the development of computer theory and artificial intelligence.The methods used to solve 3-SAT problems are mainly divided into the accurate algorithms and the approximate algorithms.As one of the best approximate algorithms,the local search algorithms based on configuration check strategy can effectively solve random 3-SAT instances,but the efficiency is limited by the random initialization.In this thesis,the stochastic local search algorithms for solving 3-SAT problem are analyzed.ISSATA is proposed by three improved strategies,which improve the efficiency for solving 3-SAT problem.In addition,considering the framework of membrane evolution algorithm and the 3-SAT problem,MEASAT algorithm is also proposed by designing various operators of membrane evolution algorithm.This algorithm has better efficiency in the larger instances.At the same time,the related experimental results also show the effectiveness of ISSATA and MEASAT.The main research work of this thesis includes:1.Analyze the local search algorithms for solving the 3-SAT problem,and propose some improved strategies.The main improvements are described as follow: first,the information of variables and clauses is used to assign the variables at the beginning rather than the random initialization strategy,so that the initial assignment can satisfy more clauses as much as possible.Second,the variable with largest score is not always selected because of the randomness of variable selection,which also avoid the algorithm falling into the local optimum.Third,when the scores of the candidates are the same,the clause information of the variable will be used to break ties.The results show that ISSATA has better performance in the random 3-SAT instances and it is still effective in the crafted instances because it does reduce the running time of some instances.2.MEASAT is proposed to improve the performance of the ISSATA on the larger instances.By combining different operators and changing the execution sequence,the Evolution Between Membranes strategy and the Evolution In Membrance strategy are designed to accelerate the convergence of the algorithm,and the efficiency of the algorithm on the larger instances is improved.