Genetic Optimization Design Of 3-SAT Problem Cell-Like Membrane Computing Models

Membrane computing, a vital research highlight of nature-inspired computation, has achieved fruitful research results with the great efforts of domestic and foreign researchers. Automatic design of membrane computing model is a new and challenging research topic in the field of membrane computing. Aiming to reduce complexity of design and improve efficiency of design, it could automatically manufacture a necessary membrane system by means of the algorithm or program.Currently, the latest research has promoted the development of monomial and polynomial calculation in automatic design of membrane computing, however little research of these design has focused on NP-hard problem. Known as a vital NP-hard problem, the SAT problem has been widely used in the fields of artificial intelligence, calculation-aided manufacturing etc. In this case, this paper proposed an automatic design method of cell-like membrane computing model to solve 3-SAT problem by using genetic algorithm. The research work was based on cell-like membrane system, and the main work and research results are as follows:1.Two methods for design of the 3-SAT problem cell-like membrane computing model with charge by using genetic optimization was proposed. After elaborating the design ideas and specific design goal, two methods of membrane system design are respectively proposed for unchanged and changeable membrane structure according to the characteristics of membrane structure of cell-like membrane system. And then, three elements of P system encoding, the method to judge a P system, and selection of genetic operator and genetic parameter setting, etc were showed. The simulation results showed the feasibility and effectiveness of the proposed two design methods, and the comparison results showed that the design method based on membrane structure variable performed better;2.A method for the 3-SAT problem catalytic cell-like membrane computing model by using genetic optimization was proposed. On the basis of elaborating the advantages of catalytic cell-like membrane system, a clear design ideas and goals was confirmed by introducing the group catalyst and improved three elements of P system encoding and method to judge a P system with penalty. The experimental results eventually showed the feasibility and effectiveness of this proposed method. And the comparative analysis with the charged cell-like membrane system showed that automatic design method of the 3-SAT problem catalytic cell-like membrane computing model by using genetic optimization performed better.