Encyclopedia of Complexity and Systems Science

Living Edition
| Editors: Robert A. Meyers

Applications of P Systems

  • Marian GheorgheEmail author
  • Andrei Păun
  • Sergey Verlan
  • Gexiang Zhang
Living reference work entry
DOI: https://doi.org/10.1007/978-3-642-27737-5_698-1
  • 127 Downloads

Glossary

Computational model

A computational model is a concept introduced in computer science with the aim of defining an algorithm that is executed on an abstract machine. It is built for different purposes and makes use of various notations and formalisms. Some of the most widely used computational models are finite state machines, Turing machines, formal grammars, Boolean networks, Petri nets, cellular automata, and process calculi.

Execution strategy of a P system

Every P system is executed in steps. In each step and each compartment, a number of rules are selected to be applied to the multiset contained in the compartment. The most utilized execution strategies are maximal parallelism (in each compartment after the rules are selected, no more objects are available to be processed by the existing rules), sequential execution (only one rule per compartment is applied), and stochastic behavior (the rules are selected in accordance with the probabilities associated to them). In most of the cases, maximal parallelism leads to nondeterministic behavior as there might be different ways of selecting the rules applied to the multisets contained in compartments. One of the most used stochastic behavior is based on Gillespie algorithm.

Fuzzy reasoning spiking neural P system (FRSNP system)

This is a special type of P system combining the features of a spiking neural P system (SNP system) and some fuzzy theory concepts. The SNP system consists of an alphabet with only one element, called spike, neurons – each of them with its multiset and rules; a set of links between neurons, called synapses; and designated input and output neurons. Fuzzy values are associated with rules defining the potential values of spikes and fuzzy truth values for rules. These values control both the amount of spikes consumed and the rules selected to be executed.

Membrane algorithms

A distributed evolutionary approach using the regions defined by the membranes to host instances of specific meta-heuristic search algorithms. It makes use of different topologies of the membrane structure and the types of rules involved in the meta-heuristic search algorithms. A broad spectrum of meta-heuristic search algorithms have been used in defining new membrane algorithms.

Model checking

Model checking is a method for automatically verifying the correctness of properties of a system. Given a model of a system and a specification, both formulated in a precise mathematical language, model checking automatically checks in an exhaustive manner that the model meets the specification. The model is a state machine, and the specification is given by a temporal logic formula.

P system model

A P system consists of a set of compartments. The most common P system models have their compartments linked in such a way that they form a network (tissue P systems) or a tree – a hierarchical structure (cell P systems). Each compartment consists of a multiset of elements which are transformed through various rules.

Rules

The most basic rules used by a P system are rewriting (evolution or transformation) and communication between neighbor compartments (those directly connected). For stochastic P systems, each rule has a probability or a kinetic constant associated with. The kinetic constants are utilized in computing the rule probabilities.

Standard membrane controller (MeC)

A construct based on the concept of numerical P system. It uses a membrane structure; a set of variables (replacing the usual multisets), with some initial values; and a set of programs (instead of usual rewriting and communication rules) associated to compartments. The programs in each compartment define polynomial production functions, stating the values consumed from the local variables, and repartition protocols, indicating the values distributed to variables from the same compartment and its neighbors.

Introduction

Membrane computing was initiated in Păun (2000) as a new research topic investigating computing models inspired by the architecture and the functioning of the living cells, as individual biological entities as well as parts of higher-order structures, such as tissues or more complex organs. The models are called membrane systems or P systems. Membrane computing is a branch of natural computing, and the main developments in this area are summarized in the handbook of natural computing (see Păun (2012)). A thorough account of the main theoretical topics and significant applications is provided in Păun et al. (2010a).

Membrane computing models have been used in various applications in linguistics, computer graphics, economics, approximate optimizations, cryptography, and other computer science areas, in Ciobanu et al. (2006). The most prominent applications are related to systems and synthetic biology (see Frisco et al. (2014)) and, more recently, to real-life complex problems, presented in Zhang et al. (2017).

Simple or more complex biological systems have been modeled for a long time using mathematical approaches, such as differential equations and statistical models. In recent years, especially after launching the concept of “executable biology” in Fisher and Henzinger (2007 Nov), computational models have started being used more often in applications in biology. These are attractive modeling approaches as they provide a plethora of formal methods from computer science that allow not only to efficiently simulate the systems, but they also provide tools that are able to investigate the behavior of the systems for various scenarios and input conditions and check properties of the associated models. More well-established computational models, such as process algebras, Petri nets, Boolean networks, statecharts, or newly developed nature-inspired models – brane calculi, membrane systems, and kappa rule-based system – are utilized, according to Bartocci and Lió (2016 Jan), in applications in biology. In Bartocci and Lió (2016 Jan), it is shown that these computational models come with formal analysis methods such as static analysis, runtime verification and monitoring, model checking, and tools supporting them.

P systems, as presented in Ciobanu et al. (2006), have been used initially as computational models for various applications primarily in biology. However, the applicability area has been expanded due to the power and flexibility of the computational devices introduced and studied. A relatively new and very promising application, the controller design for mobile robots, using the characteristics of numerical P systems, was introduced in Buiu et al. (2012) and Wang et al. (2015c). P system concepts have been also combined with methods and principles developed in the area of soft computing, especially evolutionary algorithms and fuzzy systems, with the aim of solving a broad spectrum of optimization problems. In Zhang et al. (2014b) and Zhang et al. (2017), a comprehensive survey was presented on the combination of P systems with meta-heuristic algorithms, such as local search approaches, evolutionary algorithms, and swarm intelligence algorithms giving rise to membrane algorithms or membrane-inspired evolutionary algorithms, involved in solving optimization problems. In Zhang et al. (2014c), a novel way of designing a P system for directly obtaining the approximate solutions of combinatorial optimization problems and discrete engineering optimization problems without the aid of meta-heuristic algorithms was presented. In Wang et al. (2015a) and Zhang et al. (2017), the combination of P systems with fuzzy logic theory to solve fault diagnosis problems was reviewed in a systematic manner.

In the sequel we show how various instances of the membrane computing models are used in applications. We start with applications of membrane systems in modeling systems and synthetic biology problems, then continue presenting the use of membrane algorithms for solving optimization problems, and finally describe briefly the use of membrane systems in modeling problems from computer science, graphics, and economy and mention some of the tools developed to support the simulation of various P system models.

Applications in Systems in Synthetic Biology

There are many features of membrane computing models which make them attractive for applications in several disciplines, especially biology. Membrane computing uses a set of concepts derived directly from cell biology: compartments, which are independent entities; their objects, corresponding to simpler or more complex biochemical elements, such as simple molecules or complex proteins and DNA molecules, interacting locally via evolution (or transformation or rewriting); and communication rules, corresponding to various biochemical interactions – complex formation or its reverse transformation, membrane interaction, or transport. The behavior of such systems may be quite complex, nonlinear, and emerging from local interactions within compartments or inter-compartments. Both qualitative and quantitative aspects of their behavior are expressed with nondeterministic and stochastic models, respectively. Such models are presented in Ciobanu et al. (2006) and Frisco et al. (2014) covering a broad spectrum of applications.

In the early monograph on applications of membrane computing (Ciobanu et al. (2006)), there are chapters dedicated to modeling problems in biology. In these applications membrane computing is used as a formal language allowing to describe in a rigorous and precise way the biochemical entities and their interactions. I. I. Ardelean, D. Besozzi, M. H. Garzon, G. Mauri, and S. Roy present a P system model for mechanosensitive channels; L. Bianco, F. Fontana, G. Franco, and V. Manca discuss P systems for biological dynamics; M. Cavaliere and I. I. Ardelean introduce a P system model to simulate respiration and photosynthesis interaction in cyanobacteria; G. Cioban models cell-mediated immunity and T. Y. Nishida photosynthesis; a multiset processing model of p53 signaling pathway is presented by Y. Suzuki and H. Tanaka.

Most of the membrane systems presented in Frisco et al. (2014) and used for systems and synthetic biology applications are stochastic, each rule having associated a kinetic constant based on which a probability is calculated. The execution strategy, the model semantics, is based on Gillespie algorithm. In accordance with this semantics, the probabilities of the rules are evaluated at every step of execution as these are computed taking into account the kinetic constants and the current concentrations of the reactants involved.

Firstly, we present a stochastic P system model for a pulse generator example following Frisco et al. (2014), and then we introduce a formal verification approach for this system. Finally, we describe some other P system models used for various systems and synthetic biology problems, presented in Frisco et al. (2014).

The pulse generator (by J. Blakes, J. Twycross, S. Konur, F. J. Romero-Campero, N. Krasnogor, and M. Gheorghe, in Frisco et al. (2014)), a synthetic bacterial colony, consists of two different bacterial strains, sender cells and pulsing cells:
  • Sender cells contain the gene luxI from Vibrio fischeri, codifying the enzyme LuxI which synthesizes the molecular signal 3OC6–HSL (AHL). The luxI gene is expressed by the promoter PLtetO1 from the tetracycline resistance transposon.

  • Pulsing cells contain the lux R gene from the same organism, Vibrio fischeri, that codifies the 3OC6–HSL receptor protein LuxR. This gene is regulated by the promoter PluxL. These cells also contain the gene c I from lambda phage codifying the repressor C I under the regulation of the promoter PluxR, activated by the binding of the transcription factor LuxR_3OC6_2. These bacterial strains carry the gene g f p that codifies the green fluorescent protein under the regulation of the synthetic promoter PluxPR combining the Plux promoter (activated by the transcription factor Lux R_3OC6_2) and the PR promoter from lambda phage (repressed by the transcription factor CI).

The rules describing the interactions within sending cells are:
  • r 1: [PLtetO1;luxI k1 PLtetO1;luxI + LuxI] s

  • r 2: [LuxI k2] s

  • r 3: [LuxI k3 AHL] s

  • r 4: [AHL] s k4 AHL[] s

The rules appear within a compartment, denoted s, expressing interactions within the compartment: luxI gene expressed by the promoter PLtetO1 produces the enzyme LuxI (r 1); LuxI might degrade (r 2); LuxI synthesizes the signal 3OC6–HSL (AHL) (r 3); and this signal is communicated to a neighbor (r 4). Following the description of a pulsing cell, one can derive in a similar manner the rules for such a cell.

The pulse generator system consists of a lattice of cells distributed in accordance with a specific spatial arrangement. At one end there are located the sender cells and the rest are pulsing cells. The sender cells will start producing the molecular signal 3OC6–HSL (AHL). This will get initially accumulated in sending cells and then through the communication rules, r 4, will start propagating 3OC6–HSL toward the pulsing cells. These in turn, in the presence of 3OC6–HSL, will start producing the green fluorescent protein, GFP. The model, described in chapter 1 of Frisco et al. (2014), consists of a two-dimensional lattice, each cell being a stochastic P system, corresponding to either a sending cell or a pulsing cell. A simulation has been made for a lattice with 341 compartments (11 × 31) and 28 molecular species.

Figure 1 shows the signal molecule 3OC6–HSL amount over time. The figure, initially presented in chapter 1 of Frisco et al. (2014), suggests that the further away the pulsing cells are from the sender cells, the less likely they are to produce a pulse, the green fluorescent protein.
Fig. 1

Signal 3OC6–HSL level over time (From Frisco et al. (2014))

Figure 1 shows the result of one single simulation. As this is a stochastic system, then several simulations need to be performed in order to compute an average behavior. By using some of the analysis methods associated with computational models, in the case of stochastic P systems, the model checking tool, PRISM, one can get more precise information regarding the behavior of the pulse generator. Let us consider the concentration of GFP at row 3 within 50 s. This can be formulated as “probability that GFP concentration at row 3 exceeds 100 within 50 s,” and in PRISM language, this becomes
$$ {\mathrm{P}}_{=?}\left[ true\ {\mathrm{U}}^{\le 50}{GFP}_{-}{pulsing}_{-}3\ge 100\right]. $$

This confirms the behavior shown in Fig. 1, but it also returns a high probability of this event, 0.87, as presented in Frisco et al. (2014).

This example from synthetic biology shows the capabilities of membrane systems to model biological systems using features such as compartments, biochemical interactions, and inter-compartment communications, a direct way of writing biochemical reactions through evolution and communication rules. The stochastic behavior of the system is studied through simulations. Properties of the system can be systematically investigated and emergent behavior predicted. Other applications have been considered in Frisco et al. (2014) and adequate membrane system models developed in this respect.
  • A biological system linked to breast cancer is modeled as a membrane system with peripheral proteins (M. Cavaliere, T. Mazza and S. Sedwards). This model allows to simulate the behavior of the system, revealing the role of estrogen in cellular mitosis and DNA damage. The use of a stochastic model checker facilitates the investigation of the appropriate time-dependent dosage of antagonist that is meant to be used to minimize the random replication of abnormal cells.

  • An application of membrane systems to the study of intracellular diffusive processes is presented by P. Cazzaniga, D. Besozzi, D. Pescini, and G. Mauri. A signal transduction pathway of bacterial chemotaxis is investigated by considering first a single-volume module revealing the effects of different perturbations on the system dynamics and then a multivolume module, extending the former, that looks at diffusive processes leading to the formation of concentration gradients within the bacterial cytoplasm. The membrane computing model is also a stochastic one, called τ-DPP model. The simulation of the model helps analyzing the bacterial chemotaxis by showing the stochastic fluctuations of various proteins and the distribution of flagellar motors over the cell surface.

  • A stochastic membrane computing model suitable for real ecosystem applications, called population dynamics P systems (PDP systems, for short) is considered by M. A. Colomer-Cugat, M. García-Quismondo, L. F. Macías-Ramos, M. A. Martínez-del-Amor, I. Pérez-Hurtado, M. J. Pérez-Jiménez, A. Riscos-Núñez, and L. Valencia-Cabrera. The formal definition of the syntax and semantics of the PDP systems together with a simulation platform, MeCoSim (standing for membrane computing simulator), are provided. The PDP systems are applied to modeling pandemic dynamics of three populations.

  • T. Hinze, J. Behre, C. Bodenstein, G. Escuela, G. Grünert, P. Hofstedt, P. Sauer, S. Hayat, and P. Dittrich present three chronobiological studies modeled with different types of membrane systems capturing spatiotemporal aspects of the biological systems. Using a KaiABC core oscillator, a cell signaling network representing a posttranslational prototype for generation of circadian rhythms is investigated. The second study is dedicated to the circadian clockwork able to adapt its oscillation to an external stimulus. The third system investigated is a bistable toggle switch resulting from mutual gene regulation. The P systems used as models of these systems are specified and analyzed with a software package, called SRSim. The software package allows the use of spatial interaction rules and provides powerful visualization capabilities.

  • A membrane system using an execution strategy for its rules based on a new algorithm, called nondeterministic waiting time method, is introduced by J. Jack, A. Păun, and M. Păun. Some case studies from system biology are used to compare the method with stochastic membrane systems and ordinary differential equations. A FAS-induced apoptosis is then modeled and studied with these membrane systems.

  • The class of MP systems is introduced together with a method based on regression analysis that synthesizes a MP model from time series of observed dynamics (L. Marchetti, V. Manca, R. Pagliarini, and A. Bollig-Fischer). This model is applied to two systems biology case studies. The first case study is about the glucose/insulin interactions related to the intravenous glucose tolerance test. The second one presents gene expression networks involved in breast cancer.

  • The behavior of E. coli bacterium with respect to different levels of oxygen in the environment is investigated using an agent-based approach (A. Turcanu, L. Mierlă, F. Ipate, A. Stefănescu, H. Bai, M. Holcombe, and S. Coakley). The behavior of the system is not only studied through simulations of the agent-based model, but certain properties, formulated in a temporal logic formalism, are investigated through two model checkers, Rodin and Spin. The translation of the agent-based system is not directly into these model checkers, but it comes via a specific class of membrane systems, called kernel P systems. These membrane systems allow a direct translation of their transformation rules into transitions of the model checkers.

Applications to Real-Life Complex Problems

The real-life complex problems discussed in this section are of three types: engineering optimizations, fault diagnosis, and robot control.

Membrane Algorithms

Until now two kinds of membrane algorithms, also called membrane-inspired evolutionary algorithms, have been discussed. One is a proper hybridization of P system features – the hierarchical or network membrane structures, evolution rules and computational procedures, and various well-established meta-heuristic methods such as local search approaches, evolutionary algorithms, and swarm intelligence algorithms. The other type includes optimization spiking neural P systems (OSNPS), which were designed by using spiking neural P systems for directly obtaining the approximate solutions of optimization problems without the aid of meta-heuristic algorithms. In what follows, we start from the first kind of membrane algorithms and then describe the second one.

A very promising direction of research, namely, applying membrane computing in devising approximate algorithms for solving hard optimization problems, was initiated by Nishida, in Nishida (2004), who proposed membrane algorithms as a new class of distributed evolutionary algorithms. These algorithms can be considered as a high-level (distributed and dynamically evolving their structure during the computation) evolutionary algorithms. In short, candidate solutions evolve in compartments of a (dynamical) membrane structure according to local algorithms, with better solutions migrating through the membrane structure; after a specified halting condition is met, the current best solution is extracted as the result of the algorithm.

Nishida has checked this strategy for the traveling salesman problem, and the results were more than encouraging for a series of benchmark problems: the convergence is very fast, the number of membranes is rather influential on the quality of the solution, the method is reliable, and both the average quality and the worst solutions were good enough and always better than the average and the worst solutions given by simulated annealing.

This combination of two nature-inspired computational approaches has led to many variants of such models and applications of various types. A survey of the results obtained is published in Zhang et al. (2014b). Real-life applications of this approach have been reported in Zhang et al. (2017). A membrane algorithm is a successful instance of a model linking membrane computing and evolutionary algorithms. In Zhang et al. (2014a), the role played by P systems in membrane algorithms was discussed. Dynamic behaviors of membrane algorithms by introducing a set of population diversity and convergence measures were analyzed. This is the first attempt to obtain deep insights into the search capabilities of membrane algorithms. The analysis is performed on the membrane algorithm, QEPS (a quantum-inspired evolutionary algorithm based on membrane computing), and its counterpart algorithm, QIEA (a quantum-inspired evolutionary algorithm), using a comparative approach in an experimental context to better understand their characteristics and performances. Experiments are performed on the knapsack problems. The comparison with respect to the diversity measure, Hamming distance between the best and worst binary individuals (D hbw ) in a population between QEPS and QIEA, is shown in Fig. 2. The best fitness convergence (C fb ) comparison is shown in Fig. 3. NoFE represents the number of function evaluations. It is shown that QEPS can achieve better balance between convergence and diversity than QIEA, which indicates QEPS has a stronger capacity of balancing exploration and exploitation than QIEA in order to prevent premature convergence that might occur.
Fig. 2

D hbw of QEPS and QIEA on the knapsack problem with 800 items (From Zhang et al. (2017))

Fig. 3

C fb of QEPS and QIEA on the knapsack problem with 800 items (From Zhang et al. (2017))

In the sequel we use these references for presenting several types of membrane algorithms and then, using the later reference, describe some applications dealing with complex industrial problems of optimization.

Now this area has reached a certain level of maturity, and the focus is on developing new variants of meta-heuristics by using different membrane structures, types of evolution rules and other computational capabilities of membrane systems, and various evolutionary computation methods. Four types of hierarchical structures and two network structures of the membrane systems are used Zhang et al. (2014b). The membrane algorithms using hierarchical membrane systems are membrane algorithms with nested membranes (NMS, for short), one-level membrane structure (OLMS), hybrid membrane structure (HMS), and dynamic membrane structure (DMS). The membrane algorithms using network membrane structures are membrane algorithms with static network structure (SNS) and dynamic network structure (DNS). In each of these cases, various meta-heuristic approaches have been considered, including tabu search, genetic algorithms, quantum-inspired evolutionary algorithms, ant colony optimization, differential evolution, particle swarm optimization, and so on.

The network structure considered for membrane systems is called tissue, and the models are called tissue P systems or neural P systems. In the sequel we refer to membrane algorithms designed with a tissue P system structure and differential evolution (DETPS) approach presented in Zhang et al. (2013).

In Zhang et al. (2017), experiments with five constrained problems having a mixture of linear or quadratic objective functions and constraints are presented. DETPS results are compared with those obtained by using hybrid immune-hill climbing algorithm (HIHC), genetic algorithm with an artificial immune system (GAIS), genetic algorithm based on immune network modeling (GAINM), teaching-learning-based optimization (TLBO), multi-membered evolutionary strategy (M-ES), particle evolutionary swarm optimization (PESO), cultural differential evolution (CDE), coevolutionary differential evolution (CoDE), and artificial bee colony (ABC).

We present from Zhang et al. (2017) the problem below with nine linear constraints and a quadratic objective function. Two types of experiments are performed with different halting criteria and using different sets of optimization algorithms. In both cases DETPS is used. In addition to this, in the first case, DETPS, HIHC, GAIS, and GAINM are used, whereas in the second one, TLBO, M-ES, PESO, VDE, CoDE, and ABC are used.

Problem:
$$ \min f(x)=5\sum_{i=1}^4{x}_i-5\sum_{i=1}^4{x}_i^2-\sum_{i=5}^{13}{x}_i $$
(1)
subject to
$$ \left\{\begin{array}{l}{g}_1(x)=2{x}_1+2{x}_2+{x}_{10}+{x}_{11}-10\le 0\hfill \\ {}{g}_2(x)=2{x}_1+2{x}_3+{x}_{10}+{x}_{12}-10\le 0\hfill \\ {}{g}_3(x)=2{x}_2+2{x}_3+{x}_{11}+{x}_{12}-10\le 0\hfill \\ {}{g}_4(x)=-8{x}_1+{x}_{10}\le 0\hfill \\ {}{g}_5(x)=-8{x}_2+{x}_{11}\le 0\hfill \\ {}{g}_6(x)=-8{x}_3+{x}_{12}\le 0\hfill \\ {}{g}_7(x)=-2{x}_4-{x}_5+{x}_{10}\le 0\hfill \\ {}{g}_8(x)=-2{x}_6-{x}_7+{x}_{11}\le 0\hfill \\ {}{g}_9(x)=-2{x}_8-{x}_9+{x}_{12}\le 0\hfill \end{array}\right. $$
where 0≤ x i ≤1, i = 1,2,3,…,9; 0≤ x i ≤100, i = 10, 11, 12; and 0≤ x 13≤ 1. The optimal solution is f(x *) = −15 at x * = (1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 1).
In Table 1, the results of using the first set of optimization algorithms are presented, and in Table 2, the results of running the second set are presented. One can observe that DETPS produces similar results to the other algorithms (Table 2) if not better (Table 1). In both sets of experiments, DETPS arrives at the solution with less function evaluations (Table 1) or significantly less (Table 2).
Table 1

Statistical results of DETPS, HIHC, GAIS, and GAINM to test Problem. Best, mean, worst, and SD represent the best solution, mean best solution, worst solution, and standard deviation over independent 30 runs, respectively

Methods

Best

Mean

Worst

SD

Function evaluations

DETPS

−15.0000

−15.0000

−15.0000

2.2362e-6

 64,156

HIHC

−15

−14.8266

−14.3417

0.145

120,000

GAIS

−14.7841

−14.5266

−13.8417

0.2335

150,000

GAINM

−5.2735

−3.7435

−2.4255

0.9696

150,000

Table 2

Statistical results of seven algorithms to test the problem. Best, mean, and worst represent the best solution, mean best solution, and worst solution over independent 30 runs, respectively

Methods

Best

Mean

Worst

Function evaluations

DETPS

−15.0

−15.0

−15.0

20,875

TLBO

−15.0

−15.0

−15.0

25,000

M-ES

−15.0

−15.0

−15.0

240,000

PESO

−15.0

−15.0

−15.0

350,000

CDE

−15.0

−15.0

−15.0

100,100

CoDE

−15.0

−15.0

−15.0

248,000

ABC

−15.0

−15.0

−15.0

240,000

Membrane algorithms are successfully applied to optimization problems in engineering in Zhang et al. (2017). An OLMS with a quantum-inspired evolutionary algorithm is applied to analyze radar signals and solve the image sparse decomposition problem. OLMS with a particle swarm optimization algorithm is used to optimize the design of a proportional integral derivative controller and mobile robot path planning.

DETPS, presented earlier, is applied for manufacturing parameter optimization problem. A DNS based on population P systems, a variant of tissue P systems with dynamic structure, with a quantum-inspired evolutionary algorithm is used to solve the distribution network reconfiguration problem in power systems. A SNS based on neural P systems algorithm is used to solve the power system fault diagnosis problem.

The synthesis of various classes of P systems solving different problems has been investigated with evolutionary methods. A survey of this work is presented in Zhang et al. (2014b).

The membrane algorithms discussed above were designed by combining P systems with meta-heuristic techniques. In what follows, an optimization algorithm, optimization spiking neural P system (OSNPS), is directly derived from membrane computing models, spiking neural P systems (SN P systems) in Zhang et al. (2014c).

Inspired by the behavior of the language generating SN P systems, OSNPS, as shown in Fig. 4, was constructed by using a family of extended SN P systems (ESNPS) and a guider to adaptively adjust rule probabilities. ESNPS, as shown in Fig. 5, is designed by introducing the probabilistic selection of evolution rules and the output collection from multiple neurons. In each compartment there are rewriting \( \left({r}_i^1\right) \) and forgetting \( \left({r}_i^2\right) \) rules, 1≤ im.
Fig. 4

OSNPS (From Zhang et al. (2017))

Fig. 5

ESNPS structure (From Zhang et al. (2017))

The viability and effectiveness of OSNPS were tested on knapsack problems by considering genetic quantum algorithm (GQA), quantum-inspired evolutionary algorithm (QEA), novel quantum evolutionary algorithm (NQEA), quantum-inspired evolutionary algorithm based on P systems (QEPS), and two membrane-inspired evolutionary algorithms with quantum-inspired subalgorithms (MAQIS1 and MAQIS2) as benchmark algorithms in the experiments. Eleven knapsack problems, labeled 1–11, with 1000, 1200, 1400, 1600, 1800, 2000, 2200, 2400, 2600, 2800, and 3000 items are used. GQA, which obtained the worst performance among the seven algorithms, is regarded as benchmarks to illustrate the percentage of the improvements of QEA, NQEA, QEPS, OSNPS, MAQIS1, and MAQIS2. The experimental results show that OSNPS is superior or competitive to the other six optimization approaches, GQA, QEA, NQEA, QEPS, MAQIS1, and MAQIS2, with respect to the best solutions over 11 problems and 30 independent runs.

Fault Diagnosis and Robot Control

Fault diagnosis problems, especially in electric power systems, can be solved by using fuzzy reasoning spiking neural P systems (short for FRSNP), a graphic modeling approach combining spiking neural P systems and fuzzy logic theory in Peng et al. (2013), Wang et al. (2015b), and Zhang et al. (2017)). FRSNP models offer an intuitive description of a system based on fuzzy logics, good fault tolerance principles, a complete set of relationships between protective devices and faults, and an understandable diagnosis model-building process. In what follows, we will refer to FRSNP models with trapezoidal fuzzy numbers.

In Wang et al. (2015b) and Zhang et al. (2017), the FRSNP model with trapezoidal fuzzy numbers is used in experiments carried out on seven cases of the local system in an electric power system. It is shown that this FRSNP model obtains better or competitive results, compared with four methods reported in the literature, fuzzy logic, fuzzy Petri nets, genetic algorithm-tabu search, and genetic algorithm.

Enzymatic numerical P systems have been considered in modeling the robot controller in Zhang et al. (2017). These classes of P systems introduce significantly new features to the standard membrane computing framework. Membrane controller P systems change the multiset rewriting mechanism, widely utilized by the transformation rules, with a computational procedure based on a distributed way of calculating different polynomials.

Membrane controllers for mobile robots use a hierarchical cognitive architecture and are designed by using the syntax (such as the membrane structure, initial multisets, and evolution rules) and semantics of numerical P systems (NPS) or enzymatic numerical P systems (ENPS). In NPS and ENPS, the values of the variables received from various sensors are real-valued numbers, and the computation is performed on real-valued variables.

Algorithm 1 shows the generic structure of membrane controllers in Buiu et al. (2012). In the first step, the robot parameters are set to initial values. In the second step, real-time data are read from the sensors. The NPS corresponding to the current membrane computing process is executed in the third step. Finally, the motors’ speeds are set. Then the execution of the controller goes back to the second step.

Algorithm 1 Generic structure of membrane controllers

Require: parameters = initialiseBehaviourParameters(robot, behaviour)
 While (True)
  sensors = readSensors(robot)
  # simulate Numerical P System on the network server
  query = constructQuery(robot, behaviour, sensors, parameters)
  response = queryWebApp(address, query)
  speed = extractContent(response)
  setSpeed(robot, speed)
 End While

Suppose that u and y are the inputs and outputs of a membrane controller and r is the predefined setpoints. A standard membrane controller (MeC), defined in Buiu et al. (2012), is used as a P system model for designing robot controllers.

In Buiu et al. (2012) and Wang et al. (2015c), several examples using robot controllers designed with NPS or ENPS models are presented. They deal with features such as obstacle avoidance, wall following, following another robot, and trajectory tracking.

Other Applications

In Ciobanu et al. (2006) applications of membrane systems in computer science are presented. Different sorting algorithms (A. Alhazov and D. Sburlan) are considered, and their solutions make use of the massive parallelism of the membrane system models; a public key protocol (O. Michel and F. Jaquemard) is described in the framework of membrane systems. Applications were also reported in computer graphics (A. Georgiou, M. Gheorghe, and F. Bernardini) – where the compartmentalization seems to add a significant efficiency to well-known techniques based on L systems, linguistics, both as a representation language for various concepts related to language evolution, dialog, and semantics (G. Bel Enguix, M. D. Jiménez-Lopez) and as a parsing tool utilizing a new concept of automata-based translation where the parallelism of the model is exploited (R. Gramatovici and G. Bel Enguix).

The additional bibliography consists of papers referring to other applications of membrane systems. Some of the most significant are in economics (where many biochemical metaphors find a natural counterpart, with the mentioning that the “reactions” which take place in economics, for instance, in market-like frameworks, are not driven only by probabilities/stoichiometric calculations but also by psychological influences, which make the modeling still more difficult than in engineering or biological applications). R. Nicolescu and his collaborators have utilized in a series of papers various extensions of the membrane systems to solve problems of synchronization, of broadcasting, or of representing complex data structures with compact and efficient membrane systems-based notations.

For most of the applications presented so far, there have been developed software tools helping analyzing the systems investigated. Simulators for the models built for different types of P systems and, in some cases, tools revealing properties of the systems are provided. Here there will be mentioned the most established software tools.

P-Lingua tool (http://www.p-lingua.org/wiki/index.php/Main_Page) provides a domain-specific language, with the same name, allowing to describe models for a large set of P systems, including those presented in chapter 4 of Frisco et al. (2014). The P-Lingua language is supported by a dashboard allowing to handle input and output data associated with the models and data visualization. This is integrated with a tool, MeCoSim (http://www.p-lingua.org/mecosim/), that provides connections to various run time platforms.

Stochastic P systems presented in chapter 1 of Frisco et al. (2014) can be described in a specific format and then simulated within the Infobiotics software platform (http://infobiotics.org). This allows to specify and verify properties of the system expressed as probabilistic temporal logic formulas.

Deterministic models written as metabolic P systems, presented in chapter 7 of Frisco et al. (2014), are simulated with MetaPlab (http://mplab.sci.univr.it/index.html). The tool provides support for data visualization but also calibrates the model based on observed time series referring to the system investigated.

SRSim simulator (http://www.biosys.uni-jena.de/members/gerd+gruenert/srsim.html) allows to analyze P systems with spatiotemporal features, as those presented in chapter 5 of Frisco et al. (2014).

Some more details about these tools, including the domain-specific languages they use, the simulators employed, and other features helping the analysis of the investigated system, are presented in the additional bibliography.

Future Directions

We present future developments of membrane computing applications, membrane algorithms, and finally FRSNP models and robot control models, as reflected in Gheorghe et al. (2013) and Zhang et al. (2017).

In Gheorghe et al. (2013) some future developments of the membrane computing pointing out to applications of P systems as well are presented. The most important developments with respect to applications are:
  1. 1.

    The analysis methods for P system models – formal verification and testing, causality, and semantics – and the efficient and robust development of tools related to numerical P system models will be considered.

     
  2. 2.

    The tool development will continue, especially with an emphasis on parallel implementations and their integration with existing tools. New parallelization algorithms should be considered, given the complexity of the models and the systems investigated.

     
  3. 3.

    More complex and diverse problems, requiring both modeling and optimization aspects, are expected to be approached with the methods and tools developed so far or with new ones.

     
Future developments regarding membrane algorithms, as listed in Gheorghe et al. (2013), are as follows:
  1. 1.

    Further combinations of a larger set of evolutionary algorithms with various classes of membrane computing models such as cell P systems with active membranes, tissue P systems, and population P systems are expected to be studied.

     
  2. 2.

    Usually, in a membrane algorithm, an evolutionary algorithm is placed inside a membrane. Given the distributed structure of a P system, it is natural to consider several different types of evolutionary operators, or several distinct kinds of evolutionary mechanisms, such as a genetic algorithm, evolutionary programming, evolution strategy, differential evolution, and particle swarm optimization acting in parallel across the model. Furthermore, the flexible communication rules can be used at the level of genes, instead of at the level of individuals.

     
  3. 3.

    The single-objective problems are usually involved in the investigations reported so far in the literature. It is worth investigating how multi-objective, dynamic, peaked optimization problems might lead to better solutions by using the P systems environment.

     
  4. 4.

    More real-world application problems, such as power system optimization, software/hardware co-design, and vehicle route plan, might benefit from a membrane algorithm-based approach.

     
  5. 5.

    A deeper and fine grain performance analysis and evaluation of membrane algorithms starting from the work in Zhang et al. (2014a) is requested in order to reveal more precisely the role played by P systems in the hybrid optimization algorithms.

     

New research developments regarding FRSNP models are identified in Zhang et al. (2017). New variants of SN P systems and their reasoning algorithms are expected to be investigated in connection with more complex fault diagnosis problems, such as online diagnosis, fast fault diagnosis, high-precision diagnosis, as well as power supply systems for urban rail transit, mechanical fault diagnosis, and power systems with new energies. Another promising research avenue is the usage of FRSNP models with learning abilities.

The future work with respect to the use of P systems in supporting robot controller design is reported in Zhang et al. (2017):
  1. 1.

    The design of membrane controllers for more complex behaviors of a larger class of wheeled robots

     
  2. 2.

    The applicability of numerical P systems to other advanced robot control strategies with applications in various engineering areas

     
  3. 3.

    The use of P systems, including numerical P systems, in constructing cognitive and executable architectures (planning, learning, execution) of autonomous robots, as stated in Buiu et al. (2012), whereby P systems-based cognitive architectures at higher levels in a control system can communicate with lower level membrane controllers

     

Notes

Acknowledgments

The work of G. Zhang was supported by the National Natural Science Foundation of China (61373047 and 61672437) and the Research Project of Key Laboratory of Fluid and Power Machinery (Xihua University), Ministry of Education, P. R. China (JYBFXYQ-1).

Bibliography

Primary Literature

  1. Bartocci E, Lió (2016) Computational modeling, formal analysis, and tools for systems biology. PLoS Comput Biol 21(1):e1004,591CrossRefGoogle Scholar
  2. Buiu C, Vasile CI, Arsene O (2012) Development of membrane controllers for mobile robots. Inf Sci 187:33–51CrossRefGoogle Scholar
  3. Ciobanu G, Păun Gh, Pérez-Jiménez MJ (eds) (2006) Applications of membrane computing. Natural computing series. Springer, BerlinGoogle Scholar
  4. Fisher J, Henzinger T (2007) Executable cell biology. Nat Biotechnol 25(11):1239–1249CrossRefGoogle Scholar
  5. Frisco P, Gheorghe M, Pérez-Jiménez MJ (eds) (2014) Applications of membrane computing in systems and synthetic biology. Emergence, complexity and computation. Springer, ChamGoogle Scholar
  6. Gheorghe M, Păun G, Pérez-Jiménez MJ, Rozenberg G (2013) Research frontiers of membrane computing: open problems and research topics. Int J Found Comput Sci 24(5):547–624MathSciNetCrossRefzbMATHGoogle Scholar
  7. Nishida TY (2004) An application of P system: a new algorithm for NP-complete optimization problems. In: Proceedings of the 8th world multi-conference on systems, cybernetics and informatics, vol 5, pp 109–112Google Scholar
  8. Păun G (2000) Computing with membranes. J Comput Syst Sci 61(1):108–143. also Turku Center for Computer Science Report TUCS 208, Nov 1998MathSciNetCrossRefzbMATHGoogle Scholar
  9. Păun GH (2012) Membrane computing. In: Rozenberg G, Bäck T, Kok JN (eds) Handbook of natural computing. Springer, Berlin, pp 1355–1377CrossRefGoogle Scholar
  10. Păun G, Rozenberg G, Salomaa A (eds) (2010a) The Oxford handbook of membrane computing. Oxford University Press, OxfordzbMATHGoogle Scholar
  11. Peng H, Wang J, Pérez-Jiménez MJ, Wang H, Shao J, Wang T (2013) Fuzzy reasoning spiking neural P system for fault diagnosis. Inf Sci 235:106–116MathSciNetCrossRefzbMATHGoogle Scholar
  12. Wang T, Zhang G, Pérez-Jiménez MJ (2015a) Fuzzy membrane computing: theory and applications. Int J Comput Commun 10:904–935Google Scholar
  13. Wang T, Zhang G, Zhao J, He Z, Zhao J, Wang J, Pérez-Jiménez MJ (2015b) Fault diagnosis of electric power systems based on fuzzy reasoning spiking neural P systems. IEEE T Power Syst 30(3):1182–1194CrossRefGoogle Scholar
  14. Wang X, Zhang G, Neri F, Jiang T, Zhao J, Gheorghe M, Ipate F, Lefticaru R (2015c) Design and implementation of membrane controllers for trajectory tracking of nonholonomic wheeled mobile robots. Integr Comput Aided Eng 23(1):15–30CrossRefGoogle Scholar
  15. Zhang G, Cheng J, Gheorghe M, Meng Q (2013) A hybrid approach based on differential evolution and tissue membrane systems for solving constrained manufacturing parameter optimization problems. Appl Soft Comput 13(3):1528–1542CrossRefGoogle Scholar
  16. Zhang G, Cheng J, Gheorghe M (2014a) Dynamic behavior analysis of membrane-inspired evolutionary algorithms. Int J Comput Commun 9(2):227–242ADSCrossRefGoogle Scholar
  17. Zhang G, Gheorghe M, Pan L, Pérez-Jiménez MJ (2014b) Evolutionary membrane computing: a comprehensive survey and new results. Inf Sci 279:528–551CrossRefGoogle Scholar
  18. Zhang G, Rong H, Neri F, Pérez-Jiménez MJ (2014c) An optimization spiking neural P system for approximately solving combinatorial optimization problems. Int J Neural Syst 24(5):1–16CrossRefGoogle Scholar
  19. Zhang G, Pérez-Jiménez MJ, Gheorghe M (2017) Real-life applications with membrane computing. Emergence, complexity and computation. Springer, ChamGoogle Scholar

Books and Reviews

  1. del Amor MAM, García-Quismondo M, Macías-Ramos LF, Valencia-Cabrera L, Nez ARN, Pérez-Jiménez MJ (2015) Simulating P systems on GPU devices: a survey. Fundam Inform 136(3):269–284MathSciNetzbMATHGoogle Scholar
  2. Dinneen MJ, Kim YB, Nicolescu R (2012) Faster synchronization in P systems. Nat Comput 11(1):107–115MathSciNetCrossRefzbMATHGoogle Scholar
  3. Freund R, Păun G, Rozenberg G, Salomaa A (eds) (2006) Membrane computing, 6th international workshop, WMC 2005, Vienna, 18–21 July 2005, Revised selected and invited papers, Lecture notes in computer science, vol 3850, SpringerGoogle Scholar
  4. Leporati A, Rozenberg G, Salomaa A, Zandron C (eds) (2017) Membrane computing – 17th international conference, CMC 2016, Milan, 25–29 July 2016, Revised selected papers, Lecture notes in computer science, vol 10105, SpringerGoogle Scholar
  5. Macías-Ramos LF, Valencia-Cabrera L, Song B, Song T, Pan L, Pérez-Jiménez MJ (2015) A P_Lingua based simulator for P systems with symport/antiport rules. Fundam Inform 139(2):211–227CrossRefzbMATHGoogle Scholar
  6. Manca V (2013) Infobiotics – information in biotic systems. Emergence, complexity and computation. Springer, HeidelbergGoogle Scholar
  7. Nicolescu R, Ipate F, Wu H (2013) Programming P systems with complex objects. In: Alhazov A, Cojocaru S, Gheorghe M, Rogohzin Y, Rozenberg G, Salomaa A (eds) Membrane computing, international conference, CMC 2013, Chişninău, 20–23 Aug 2013, Revised papers, Springer, Lecture notes in computer science, vol 8340, pp 280–300Google Scholar
  8. Păun GH, Pérez-Jiménez MJ, Riscos-Núñez A, Rozenberg G, Salomaa A (eds) (2010b) Membrane computing, 10th international workshop, WMC 2009, Curtea de Arges, 24–27 Aug 2009. Revised selected and invited papers, Lecture notes in computer science, vol 5957, SpringerGoogle Scholar

Copyright information

© Springer Science+Business Media LLC 2017

Authors and Affiliations

  • Marian Gheorghe
    • 1
    Email author
  • Andrei Păun
    • 2
  • Sergey Verlan
    • 3
  • Gexiang Zhang
    • 4
    • 5
    • 6
  1. 1.School of Electrical Engineering and Computer ScienceUniversity of BradfordBradfordUK
  2. 2.Department of Computer ScienceUniversity of BucharestBucharestRomania
  3. 3.LACLUniversité Paris Est CréteilCréteilFrance
  4. 4.Robotics Research CenterXihua UniversityChengduChina
  5. 5.China Key Laboratory of Fluid and Power MachineryXihua University, Ministry of EducationChengduChina
  6. 6.School of Electrical EngeneeringSouthwest Jiaotong UniversityChengduChina