Evolutionary Computation (EC) mimics evolution processes to solve burdensome computational problems, like the design, optimization and reverse engineering of complex systems, and its effectiveness is tied to a proper formalization of the candidate solutions. Petri Net (PN) formalism is extensively exploited for the modeling, simulation and analysis of the structural and behavioral properties of complex systems. Here we introduce a novel evolutionary algorithm inspired by EC, the Evolutionary Petri Net (EPN), which is based on an extended class of PNs, called Resizable Petri Net (RPN), provided with two genetic operators: mutation and crossover. RPN includes the new concept of hidden places and transitions, that are used by the genetic operators for the optimization of PN-based models. We present a potential application of EPNs to face one of the most challenging problems in Systems Biology, the reverse engineering of biochemical reaction networks.
Evolution is the process whereby the inherited characteristics of a population are modified over successive generations; these modifications help the offspring of the best fitting individuals in their competition for sustenance resources and survival. In other words, the evolution process is the way a population adapts itself in order to better survive in a complex and ever changing environment.
Evolutionary Computation (EC) is the application of these principles to solve
complex computational problems [
Intuitively, the structure of the individuals, and the way genetic operators
are implemented, have a deep impact on the evolutionary process. In the case
of distributed, asynchronous and concurrent systems, one of the most common
modeling approach consists in the use of Petri Nets (PNs), that is, bipartite
graphs that allow the analysis of the structural properties of the system and of
its dynamic behavior [
In this work we introduce the Evolutionary Petri Net (EPN), which is based on an extended class of PNs, called Resizable Petri Net, and two genetic operators, crossover and mutation, that altogether give a foundation for the development of a robust evolutionary algorithm for the optimization, the automatic simplification and the reverse engineering of PNs. Due to space limits, we briefly introduce a potential application of EPNs to face one of the most challenging problems in Systems Biology, i.e., the reverse engineering of biochemical reaction networks. 2
Evolutionary Computation (EC) exploits the Darwinian evolution theory to
solve complex problems [
In the particular case of GAs, the individuals are encoded as fixed-length
strings (the genome), composed by concatenating symbols from a finite
alphabet, and the evolutionary process is driven by three operators: selection, crossover
and mutation. The selection mechanism introduces an evolutionary pressure on
the population, in order to make the individuals compete and adapt according
to the fitness function that characterizes the problem in hand; selection methods
are beyond the scope of the present paper, a comprehensive review is available
in [
GAs have shown the ability of efficiently solving a plethora of complex
problems, but all these results represent specific solutions to particular instances of a
generic problem. In contrast, Genetic Programming (GP) [
GP has been extended to support individuals encoded as graphs [
The set of terminal nodes of GP is generally defined at the beginning of the evolutionary process, meaning that the interacting elements of the complex system under investigation are well known: a condition that, sometimes, is not realistic. In this work we propose a novel methodology, inspired by GP, in which individuals are encoded as multi-partite graphs which, at the end of the evolutionary process, represent putative bipartite graphs, namely Petri Nets. Our methodology is able to automatically determine the best fitting size for the inferred network, by modifying the number of nodes of the candidate solutions during the evolutionary process by means of a special mutation operator. 3
Petri Net (PN) is a modeling formalism for distributed, asynchronous and
concurrent systems [
Before introducing the EPN formalism, we define a Resizable Petri Net (RPN) as a 9-tuple = (P; P h; T; T h; F; W; M0; Opre; Opost) where: – P = fp1; : : : ; pmg is a finite set of places; – P h is the set of hidden places, such that P \ P h = ;; – T = ft1; : : : ; tng is a finite set of transitions; – T h is the set of hidden transitions, such that T \ T h = ; and (P [ P h) \ (T [ T h) = ;; – F (P [ P h) (T [ T h) S (T [ T h) (P [ P h) is the set of arcs; – W : F ! N is a weight function, which associates a non-negative integer value to each arc; – M0 : P ! N is the initial marking of non-hidden places of the net (all hidden places have zero tokens, initially); – Opre 2 N is the maximum pre-order allowed in the RPN, that is, for each t 2 (T [ T h)
W (p; t)
(1) X p2 t p2(P [P h)
X p2t p2(P [P h) – Opost 2 N is the maximum post-order allowed in the RPN, that is, for each t 2 (T [ T h)
W (t; p)
(2)
Differently from a traditional PN, a RPN is composed of a fixed number of
places (jP j = m) and transitions (jT j = n), together with a variable number of
hidden places and transitions in the sets P h and T h, respectively, whose
cardinalities can change during the evolutionary process because of the application of
the genetic operators. Two examples of RPN are depicted in Figure 1a; unlike
other similar works on dynamically reconfigurable PNs [
Conversely, hidden places and transitions are exploited by the genetic operators of EPN in order to explore alternative and more complex topologies of the net. Since hidden (i.e., modifiable) sets are dynamically modified and evaluated by the EC algorithm, EPNs allow the optimization of an existent PN according to some given constraints; moreover, they allow the automatic discovery of simplified or more efficient alternative models. These tasks can be accomplished by initializing the system of interest as a “fully-hidden” RPN (that is, P = T = ;), and letting the evolutionary algorithm explore the space of alternative models.
The RPN formalism includes the pre- and post-order conditions (Equations 1 and 2) for multiple reasons. First, they help to reduce the bloating phenomenon of GP by limiting the number of arcs. Secondly, they avoid the possibility of a convergence to degenerate or overfitting solutions, represented by completely connected PNs, by limiting the weights of in- and out-going arcs of transitions. This can also be used to limit the search space, by excluding a priori unfeasible topologies. However, both pre- and post-order conditions are optional and can be excluded from the RPN by setting Opre = Opost = 1.
The modifiers of RPNs, exploited by the evolutionary algorithm, are two classic genetic operators: crossover and mutation. Given the space of all possible RPN topologies, we can define an Evolutionary Petri Net (EPN) as a triple E = ( ; ; ) where: – – – 2 ; : ( ) ! ( ) is the crossover operator which modifies two RPNs and , where and are such that P = P ; : [ fpin; t; poutg ! is the mutation operator, where fpin; t; poutg is a triple consisting of two places pin and pout and a transition t, namely pin; pout 2 (P [ P h) [ P 1 and t 2 (T [ T h) [ T 1, where P 1 and T 1 are infinite sets of places and transitions, such that P 1 \ (P [ P h) = ; and T 1 \ (T [ T h) = ;.
The functioning of and is described in the next sections, where we denote by ( ), 2 N, the RPN at the -th generation of the evolutionary process. 3.1
The crossover mechanism implements the exchange of genetic material between
two RPNs, in order to generate new offspring which inherit the best substructures
of the parents. Various crossover mechanisms specifically designed for graphs
have been proposed in literature [
Our proposal for a crossover mechanism of two RPNs ( ); ( ) 2 , is named sticky crossover (SC). SC works on hidden transitions as follows: a transition t 2 T h (t 2 T h, respectively) is randomly selected in the RPN ( ) (the red nodes in Figure 1b), and the substructures consisting of the preset and postset of t (t ) (dotted lines) are exchanged between and . We denote by P + = ( t [ t ) \ P h (P +, respectively) the set of hidden places contained in the substructure connected to t (t ), that is added to ( ); F + = f(t ; p); (p; t ) 2 F j p 2 P +g (F +) denotes the set of arcs belonging to this substructure.
To the aim of determining the attachment points for the moving substructures, we randomly select two input places pb 2 t and pb 2 t , and two output places pe 2 t and pe 2 t (Figure 1c); pb, pe, pb, and pe will be used as “attachment” points for the incoming substructure, that is, the substructure identified by transition t is attached to , in such a way that pb is replaced by pb, pe is replaced by pe, and viceversa (see Figure 1d).
Formally, the crossover mechanism acts on the sets of places, transitions and arcs of the RPN as follows:
P h =P h [ P + n fpb; peg; P h = P h [ P + n fpb; peg; T h =T h [ ft g n ft g; T h = T h [ ft g n ft g; F =F [ F + n F + [ f(t; pb)jt 2 pbg [ f(pe; t)jt 2 pe g [ [ f(pb; t)jt 2 pb g [ f(t; pe)jt 2 peg n f(t; pb)jt 2 pbg n n f(pe; t)jt 2 pe g n f(pb; t)jt 2 pb g n f(t; pe)jt 2 peg; F =F [ F + n F + [ f(t; pb)jt 2 pbg [ f(pe; t)jt 2 pe g [ [ f(pb; t)jt 2 pb g [ f(t; pe)jt 2 peg n f(t; pb)jt 2 pbg n n f(pe; t)jt 2 pe g n f(pb; t)jt 2 pb g n f(t; pe)jt 2 peg: The weights of the arcs exchanged during the crossover process are not modified. Only hidden places are moved between RPNs during the crossover process, because each RPN contains an identical set of fixed places, so that there is a biunivocal correspondence between the elements in P and P h. For this reason, for each place p 2 ( t [ t ) \ P , where t is the transition selected for crossover, (a) Parents RPNs (b) Step #1: selection of the transitions t and t p1 ht1 hp1 ht2 hp2 ht4 p2 p1 ht1 hp1 ht2 hp2 ht4 p2 ht3 hp3 ht3 hp3 hp5 ht7 p2 p1 ht5 hp4 ht6
hp6 hp5 ht7 p2 p1 ht5 hp4 ht6 p1 ht1 hp1 ht2 hp2 ht4 p2 ht4 p2 ht3 hp3 p1 ht1 hp4 ht6 ht3 hp5 ht7 p2 p1 ht5 hp4 ht6
hp6 p1 ht5 hp1 ht2 hp2 ht7 p2 hp6 hp5 hp6 hp3 (c) Step #2: random selection of pb, pe, pb and pe nodes (d) Step #3: exchange of substructures we let F = F [ f(p; t )g [ f(t ; p)g and viceversa. It is important to clarify that the elements in P h and T h are “anonymous”, that is, they do not share any semantics between different RPNs: if a hidden element is transferred from a RPN to another during a crossover, it is considered a new unknown element with respect to the already existing elements. p1 ht1 hp1 ht2 hp2 ht4 p2 ht3 hp3 p1 ht5 hp4 ht6 hp5
hp6 ht7 p2 ht8 hp7 p1 ht1 hp4 ht6
ht3 hp5 hp6
hp3 ht4 p2 hp6 ht8 hp7 p1 ht5 hp1 ht2 hp2 ht7 p2
If the SC involves p 2 P h and p 2 P as the selected “attachment” places of the crossover then, in the exchange of the substructure from to , place p 2 P in remains unchanged, while in the exchange from to , place p 2 P h in is replaced by p. So doing, will result in a consistent RPN, since P = P .
SC is a convenient crossover operator for many reasons: (i) it allows the crossover between two arbitrary RPNs, regardless the cardinality of the sets P h; P h, which can vary during the genetic evolution; (ii) the pre- and post-order of the transitions of the offspring (as defined in Equations 1 and 2) are automatically conserved; (iii) the “directionality” of transitions is preserved, since SC swaps substructures whose presets are still presets, and elements of postsets are still postsets. Nevertheless, the SC has two drawbacks: (i) considering a substructure identified by a transition t , if t~ 6= t is connected to a place p 2 ( t [ t ); p 62 fpe; pbg, then the SC breaks the RPN leaving a separate component (see Figure 2); (ii) the SC allows the exchange of a single transition between two RPNs, which could have a little impact on large networks.
The second issue can be solved with two strategies: the first is to exploit some graph visiting algorithm (i.e., breadth- or depth-first) and extend the substructure accordingly; the second strategy is to determine a value 2 N such that 1 minfjT hj; jT hjg, and to repeat the crossover on different transitions, that is, to randomly create two vectors of indexes i1; : : : ; i and j1; : : : ; j (with ik; jk 2 N, k = 1; : : : ; ), and then apply the crossover operator on each couple (tik ; tjk ). The first strategy allows to exchange multiple transitions that have been causally connected according to the chosen graph visiting algorithm, whilst the second one allows to exchange multiple independent transitions.
In the implementation of EPNs for real case applications, the computational complexity of applying the crossover operator is, in the worst case, O(jF j2 jP j). However, the use of a hash function might yield a reduction of the computational cost, in the average case, to O(jP j).
The mutation operator modifies the structure of a RPN ( ) in , or the properties of its places and arcs (i.e., capacity and weight), by acting on a single, randomly chosen hidden transition t 2 T h. In particular, the mutation operator associates ( ) to a new consistent RPN ( + 1), according to a specified triple fpin; t; poutg. The rationale behind this triple is to provide new genetic material, that is, to modify the topology of the RPN; the functioning of the mutation operator for all the possible cases of fpin; t; poutg is summarized in Table 1. After the application of any mutation case (except #8), we set F = F [ (pin; t) [ (t; pout) and W (pin; t) = W (t; pout) = 1. Cases #7 and #8 are particular and deserve a detailed explanation.
Case #7 introduces a brand new transition which is “disconnected” from the rest of the network, since it exploits new places that are not used by any other transition. So doing, the dynamics of these places, that is, the succession of their markings as a consequence of the firings, is independent from the rest of the RPN. In other words, Case #7 is a “silent” modification of the topology of the RPN, that will not have a direct impact on its behavior. Nevertheless, a further application of a genetic operator to the mutated RPN may connect this latent transition to the main net component, thus conditioning the behavior of the whole RPN.
Case #8 does not introduce any new genetic material. This operator is used to change the capacities K(p) of randomly selected places p 2 P , i.e. K(p) = rnd, where rnd is a random number sampled from the uniform distribution (0; Kmax] (where Kmax is the maximum capacity for the places in the RPN). Alternatively, the mutation can modify the weight of an arc; for instance, given the arc weight W (p; t), its value can be updated as W (p; t) = W (p; t) 1. It is worth noting that also Case #8 can even lead to a modification in the structure of the RPN, whenever an arc weight is set to zero (i.e., the arc is removed). As a consequence, isolated hidden places or hidden transitions, which represent sources or sinks, can be introduced in the RPN after Case #8 is applied and must be removed. Therefore, after the application of this operator, the consistency of the RPN must be verified, regarding each place p and transition t involved in the mutation: (i) if p 2 P h and @ f(p; t); (t; p)g 8t 2 T [ T h, then P h = P h n fpg; (ii) if t 2 T h and @ f(t; p); (p; t)g 8p 2 P [ P h, then T h = T h n ftg.
As a final step of the evolution process, pre- and post-order conditions of the offspring need to be verified, since the described mutations might produce a putative RPN whose topology does not satisfy Equations 1 and 2. In such a case, a further modification of the weights of the ingoing and/or outgoing arcs of a transition t is required. In particular, a randomly selected input (output, respectively) place of transition t is modified so that W (p~; t) = W (p~; t) 1 (and/or W (t; p~) = W (t; p~) 1), where p~ 2 t (p~ 2 t , respectively). It is clear that if W (x; y) = 0, then the corresponding arc (x; y) is removed from F . This operation is repeated until the RPN respects all the pre- and post-order conditions.
It is worth noting that these two mechanisms implicitly allow mutation to delete places, thus reducing the size of the RPN. No. Condition
( + 1)
pout 2 P [ P h pin 2 P [ P h pout 62 P [ P h pin 2 P [ P h pout 2 P [ P h pin 62 P [ P h
t 62 T [ T pout 2 P [ P h pin 2 P [ P h
t 62 T [ T pout 62 P [ P h pin 62 P [ P h pout 62 P [ P h pin 62 P [ P h
t 62 T [ T pout 62 P [ P h pin 2 P [ P h
t 2 T [ T pout 2 P [ P h h h h h P h = P h [ fpin; poutg A new hidden transition t is created and added T h = T h [ ftg tcoreaTthed; tawnod andedwedhitdodPenh;ptlraacnessitpioinn tainsdcopnonuetctaerde P 1 = P 1 n fpin; poutg tpolatcheepnoeuwt input place pin and to the new output T 1 = T 1 n ftg P h = P h T h = T h P 1 = P 1; T 1 = T 1
No new genetic material is introduced. Either pin or pout is randomly chosen; then, its capacity or the weight of the arc connecting it to t is modified
The computational complexity of the mutation operator is, for the worst case, O(jP j). However, as in the case of crossover, the use of a hash function allows a reduction of the computational cost of this operator, in the average case, to O(C) where, in general, C < jP j. 4
In this section we sketch the theoretical basis of a potential application of EPNs in the context of Systems Biology, for the reverse engineering (RE) of biochemical interaction networks. This problem consists in the identification of the network of reactions that describe the physical interactions among the chemical species occurring in the system (genes, proteins, metabolites, etc.). These networks can be defined thanks to human expertise, by relying on some pre-existing knowledge, although most of the times the exact molecular mechanisms occurring in living cells are not known and cannot be fully understood by means of laboratory experiments only. This problem therefore demands the development of automatic RE methods, so that a plausible network of biochemical reactions – able to reproduce some given experimental observations – can be determined in faster and inexpensive ways. Since these networks are usually kinetically parameterized, they can also be exploited to analyze the dynamics of the system under different conditions.
Here, we briefly describe the modeling of biochemical systems by means of PNs and then present a possible strategy based on EPNs for solving the RE problem, which shows the feasibility of our novel methodology. A biochemical network can be modeled by means of a set of chemical species S = (S1; : : : ; SU ), involved in a set of chemical reactions R = (R1; : : : ; RZ ). Each reaction R 2 k R; = 1; : : : ; Z, is defined as R : a 1 S1 +: : :+a U SU ! b 1 S1 +: : :+b U SU , where a i; b i 2 N are the stoichiometric coefficients of R , and k 2 R+ is the kinetic constant associated to R . The species occurring on the left-hand (righthand) side of R are called reagents (products, respectively).
Because of their bipartite graph structure, PNs offer an ideal conceptual
framework for the modeling of biochemical networks [
The PN representation of a biochemical reaction network allows the
investigation of its structural features by means of theoretical approaches [
Many works perform the RE by means of evolutionary techniques [
The application of an EPN-based methodology for the RE of biochemical
systems is similar to GP. At first, a population P of RPNs is generated according to
the available domain knowledge: when the information comes from established
biological knowledge, the reactions are modeled using the sets P and T ; on the
contrary, when the information is uncertain, the network is modeled by means
of hidden places and transitions. At generation = 0, since the individuals are
all identical, they undergo a preliminary mutation. During each generation, the
best individuals are selected according to a specified fitness function, and the
EPN genetic operators are applied to yield new offspring. The fitness function
can be defined, for instance, by comparing a set of 2 N experimental samples
of the jP j = m non-hidden chemical species (places in P ) against the
dynamics generated through simulations [
To the aim of facilitating the evolutionary process and helping the generation of biologically meaningful candidate solutions, in RE we can set Opre = 2 to force the evolution of at most second-order reactions, since higher-order reactions have a probability to occur almost equal to zero, requiring the simultaneous collision of three or more reactant molecules. This choice helps the EPN functioning, since it strongly reduces the search space , but at the same time it does not pose any limitation to the practical applicability of the RE methodology, as higherorder reactions can be mimicked through a cascade of consecutive reactions of lower order. During the evolutionary process, the EPN explores this search space, and eventually a best individual I 2 P emerges, representing a consistent RPN that fits with all the observed phenomena: I is finally returned as the result of the RE. Due to space limits, we can only sketch how the crossover operator acts in determining a biochemical reaction network. Consider, for instance, the individuals (left) and (right) shown in Figure 1a: the crossover swaps the reactions R2h in and R6h in , so that the chemical reaction R2h, renamed R6h after the crossover, has an additional product (i.e., Sh, left side of Figure 1d). 6 On the contrary, the reaction R6h (renamed R2h after the crossover) in loses a product and becomes a simple transformation from one species to another. The consequence of these modifications is that the new reaction network might have a completely different dynamic behavior, and hence a different (hopefully, better) fitness value.
In this work we presented an extension of the PN formalism, the Resizable Petri Net, which introduces the notion of hidden places and transitions. The RPN represents the basis for the development of an evolutionary algorithm, the Evolutionary Petri Net, whose crossover and mutation operators allow the exploration of the space of all possible RPN topologies, in order to provide a powerful tool for solving complex problems whose solutions can be encoded as PNs; in particular, EPNs has the capability to evolve consistent and meaningful solutions. We described here the theoretical foundations of EPNs; a thorough analysis of this novel evolutive framework will be presented in a future work, in order to introduce and discuss different strategies for the construction of the RPN individuals (according to various real case applications), as well as specific selection mechanisms. The probability distributions that need to be associated to the mutation and crossover operators, and which have a relevant impact on the convergence of the evolutive process of RPNs, will also be discussed in a forthcoming extension of this work.
To the purpose of grounding this framework to practical problems, we
provided an example of a potential application of EPNs – the RE of biochemical
reaction networks – which might represent a killer-application for our
evolutionary methodology. In this context, the fitness evaluation that we proposed relies
on the simulation of the candidate solutions, which is possible only if a proper
parameterization of the candidate network in available. Hence, the RE problem
is further complicated by the need of a parameter estimation (PE)
methodology for the inference of the missing kinetic parameters [