Application Research On Membrane Computing

According to Moore's Law, the traditional computer transistor circuit is gradually approaching to the performance limits, and the traditional computer has some other limitations in, among others, the capabilities of calculation. Scientists have been seeking for new computing mediums which can outperform the traditional computers. Molecular computer based on biological hardware has become one of the most favored of the scientific community because of its high parallelism and low energy consumption. New ideas and computing models are proposed at the inspiration of biological phenomenon which can be considered as spcial computing activities.Natural computing is a field of research in which efforts are made to imitate the nature in the way it computes, and abstracts new computing models and computing paradigms. As a promising research area, it includes evolutionary computing, neural computing, DNA computing, etc.. Membrane computing (also called P systems) is an emerging branch of nature computing, which can be seen as a kind of distributed parallel computing model. It is aiming to abstract computing ideas and models from the structure and the function of living cells and from their interactions in tissues or higher order biological structures. Membrane computing not only introduces new distributed and parallel method and technology into computer science, but also provides new modeling and simulation tool for systems biology. It has become an active research area with the expectation of playing a key role in the new generation of computing and information processing system.The research on membrane can be organized in three main categories: theoretic research, application research and software/hardware implementation. Theoretic researches focus on the construction of different computing models and analysis on their computation power. According to the essential features genuinely relevant to membrane computing and the definitions of the models, application researches search for efficient methods to solve the practical problems in various fields such as biology, computer science, and linguistics.Moreover, it has turned out, especially in recent years, that membrane computing has significant potential in the application to various problems of biology as well as to linguistics, theoretical computer science (sorting and ranking, 2D languages) and applied computer science (computer graphics, cryptography, approximate algorithms for optimization problems). This thesis researches the application of membrane computing on computer science by constructing several P systems to solve Hamiltonian path problem (HPP for short), arithmetic operations and design optimization algorithms. The main research topics and contributions of this thesis are as follows:Firstly, spiking neural P systems (SN P systems for short) are constructed for the implementation of signed integer arithmetic operations with the inputs and outputs encoded as appropriate sequences of spikes. There are several SN P systems being constructed during the whole computation. The present work may be considered as the theoretical basis for constructing computing system based on P systems.Secondly, a P system with active membrane is presented to solve HPP problem, which is a well-known NP-complete problem. It is a uniform polynomial time solution and some formal details of this solution are proved in respect of complexity classes. This work extends the researches on resolving computationally hard problems by P systems and presents a new uniform method for NP-complete problem.Thirdly, a constrained optimization evolutionary algorithm based on membrane computing (MCCOP for short) is proposed with the evolutionary operations and strategies designed. In MCCOP, a membrane associates a constraint and the tentative solutions evolve according to the rules in the membrane and are evaluated by the constraint function value as the fitness. The sub-populations can communicate efficiently during the evolution process by making use of the structure of P systems and the communication mechanism among the membranes. The computational experiments show that MCCOP can converge to optimal or close to optimal solutions efficiently and that MCCOP outperforms or performs similarly to the other techniques referred to in terms of the quality of the resulting solutions.Finally, an approximate algorithm based on membrane computing for traveling salesman problems (MCTSP for short) is presented combining 2-Opt (as the local search strategy) and genetic operators (as the global search strategy). In MCTSP, some objects are included in a membrane and the excellent ones can be sent to skin membrane after they evolve according to the rule in the membrane. In the skin membrane, better objects searched by 2-Opt are sent to the membranes stochastically. These objects sent back by the skin membrane will replace the bad objects in the object membrane. This evolution is repeated until the terminate condition is satisfied. After parameters being determined by the experimental statistics data, experiments are performed on benchmarks in TSPLIB. Computer experiments show that MCTSP solves the traveling salesman problem very well, in contrast with three other algorithms.The works on membrane computing focus on the construction of mathematics models and theoretical researches wihle the application researches of membrane computing are much less compared to fruitful theoretical researches on computing models. The work of this thesis contributes to and motivates future research in membrane computing with the belief that membrane computing can offer a useful variety of tools, techniques, and models for a wide spectrum of applications.