=Paper=
{{Paper
|id=None
|storemode=property
|title=The foundation of Evolutionary Petri Nets
|pdfUrl=https://ceur-ws.org/Vol-988/paper6.pdf
|volume=Vol-988
|dblpUrl=https://dblp.org/rec/conf/apn/NobileBCM13
}}
==The foundation of Evolutionary Petri Nets==
https://ceur-ws.org/Vol-988/paper6.pdf
The Foundation of Evolutionary Petri Nets?
Marco S. Nobile1 , Daniela Besozzi2 , Paolo Cazzaniga3 , Giancarlo Mauri1
1
Università degli Studi di Milano-Bicocca, Dipartimento di Informatica,
Sistemistica e Comunicazione
Viale Sarca 336, 20126 Milano (Italy)
E-mail: {nobile,mauri}@disco.unimib.it
2
Università degli Studi di Milano, Dipartimento di Informatica
Via Comelico 39, 20135 Milano (Italy)
E-mail: besozzi@di.unimi.it
3
Università degli Studi di Bergamo, Dipartimento di Scienze Umane e Sociali
Piazzale S. Agostino 2, 24129 Bergamo (Italy)
E-mail: paolo.cazzaniga@unibg.it
Abstract. Evolutionary Computation (EC) mimics evolution processes
to solve burdensome computational problems, like the design, optimiza-
tion 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 anal-
ysis of the structural and behavioral properties of complex systems. Here
we introduce a novel evolutionary algorithm inspired by EC, the Evolu-
tionary 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 optimiza-
tion 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.
1 Introduction
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 [1], when classic deterministic approaches may
results unfeasible due to a prohibitive computational effort, for instance in the
case of high-dimensional combinatorial problems. In the EC field, the individuals
forming a population correspond to a set of candidate solutions (smaller than
the whole set of possible solutions) which are iteratively improved by means of
an evolutive pressure, driven by a fitness function that quantifies the quality of
?
Partially supported by Research Infrastructure SYSBIO Centre of Systems Biology
G. Balbo and M. Heiner (Eds.): BioPPN 2013, a satellite event of PETRI NETS 2013,
CEUR Workshop Proceedings Vol. 988, 2013.
The Foundation of Evolutionary Petri Nets 61
each individual. The improvement is determined by the application of genetic
operators (e.g., mutation, crossover), which modify the structure of each indi-
vidual, allowing the exploration of the search space and the convergence toward
an optimal solution.
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 [2]. PNs have been coupled to EC to solve problems in
a plethora of different fields, e.g., job scheduling optimization [3], development
of robust and flexible manufacturing systems [4], learning and classification [5].
PNs have also been exploited to solve complex biological problems, such as the
discovery of PN models of biochemical systems consistent with population level
genetic models [6] or the automatic reverse engineering of kinetic metabolic path-
ways [7], that is, the automatic creation of a model of a biological system able to
explain some experimentally observed phenomena. EC have been widely applied
to the latter problem [8–11]. Nevertheless, only a few works have exploited a
PN representation of individuals in EC methods [12], probably because of the
difficulty in defining proper genetic operators and the intrinsic limitations of
standard PNs.
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 oper-
ators, crossover and mutation, that altogether give a foundation for the devel-
opment 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
Evolutionary Computation (EC) exploits the Darwinian evolution theory to
solve complex problems [1]. Many bio-inspired EC methods have been proposed
(e.g., Genetic Algorithms (GA) [13], Particle Swarm Optimization [14]), all shar-
ing the following common traits: (i) they exploit a population P of randomly
generated individuals, i.e., the candidate solutions; (ii) P evolves, generation af-
ter generation, thanks to an iterative process that employs random modifications
of the individuals; (iii) the individuals able to solve the problem better than the
other candidate solutions are conserved and promoted during the evolutive pro-
cess; (iv) to the aim of discriminating the best solutions in P, a fitness function
quantifies the quality of each individual; (v) the process is executed iteratively
until a termination criterion is met.
In the particular case of GAs, the individuals are encoded as fixed-length
strings (the genome), composed by concatenating symbols from a finite alpha-
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
62 Nobile, Besozzi, Cazzaniga, Mauri
bet, 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 [15]. The crossover operator simulates the exchange of genetic material occur-
ring during biological reproduction, by creating two offspring from the union of
substructures belonging to two selected parents, aiming at the recombination of
two promising parents, in order to improve the average quality of the population.
The individuals undergo the crossover mechanism with a certain probability; al-
ternatively, individuals are identically copied into P. In both cases, the mutation
operator can randomly modify these individuals – with a low probability – by
changing, for instance, symbols in its genome. The mutation mechanism is used
for the exploration of the search space, being the only operator able to introduce
new genetic material in the population.
GAs have shown the ability of efficiently solving a plethora of complex prob-
lems, but all these results represent specific solutions to particular instances of a
generic problem. In contrast, Genetic Programming (GP) [16] is an extension of
GA in which the individuals are computer programs, generally encoded as tree
data structures where the inner nodes are functions, and the leaves (or terminal
nodes) are constant values or variables. Because of this peculiar representation,
GP can identify the optimal solution for whole classes of problems, instead of
specific instances. The functioning of GP is conceptually identical to GA and
shares all the common traits of evolutionary algorithms, but it presents some
slight difference with respect to GAs. Since the individuals are represented as
trees, they are not fixed in height and they are exposed to bloating, that is,
the uncontrolled growth of individuals, generation after generation. A maximum
height D for the individuals can be defined, but this might negatively affect the
evolution of the population. Moreover, the (unknown) actual height of the tree
corresponding to the optimum might be greater than D.
GP has been extended to support individuals encoded as graphs [17], lead-
ing to the definition of many crossover operators, which are supposed to work
with individuals whose number of nodes is different. For some applications, the
individuals of GP may be represented by even more complex data structures like
bipartite graphs, which describe in a more natural way the elements of a com-
plex system and their mutual interactions. Anyway, the development of robust
genetic operators, able to perform the evolution of such graphs, is challenging.
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 evo-
lutionary process, represent putative bipartite graphs, namely Petri Nets. Our
methodology is able to automatically determine the best fitting size for the in-
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
The Foundation of Evolutionary Petri Nets 63
ferred network, by modifying the number of nodes of the candidate solutions
during the evolutionary process by means of a special mutation operator.
3 Evolutionary Petri Nets
Petri Net (PN) is a modeling formalism for distributed, asynchronous and con-
current systems [2], which is defined as a weighted, directed, bipartite graph
consisting of two kinds of nodes: the nodes representing the state (or conditions)
of the system, called places and denoted by circles, and the nodes representing
transitions (or events) between places, denoted by bars. PNs are extensively
exploited for the simulation and analysis of the structural and behavioral prop-
erties of complex systems. Basic notions and notations of PNs can be found in
[18]. To the aim of developing an evolutionary methodology whose candidate
solutions are based on PNs, we hereby propose an extension of the conventional
PN formalism, called Evolutionary Petri Net (EPN). EPNs provide a conceptual
framework for the representation of candidate solutions, and embed robust and
consistent genetic operators.
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 = {p1 , . . . , pm } is a finite set of places;
– P h is the set of hidden places, such that P ∩ P h = ∅;
– T = {t1 , . . . , tn } 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 ) = ∅; S
– F ⊆ (P ∪ P h ) × (T ∪ T h ) (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 ∈ N is the maximum pre-order allowed in the RPN, that is, for each
t ∈ (T ∪ T h ) X
W (p, t) ≤ Opre ; (1)
p∈• t
p∈(P ∪P h )
– Opost ∈ N is the maximum post-order allowed in the RPN, that is, for each
t ∈ (T ∪ T h ) X
W (t, p) ≤ Opost . (2)
p∈t•
p∈(P ∪P h )
Differently from a traditional PN, a RPN is composed of a fixed number of
places (|P | = m) and transitions (|T | = n), together with a variable number of
hidden places and transitions in the sets P h and T h , respectively, whose cardi-
nalities can change during the evolutionary process because of the application of
the genetic operators. Two examples of RPN are depicted in Figure 1a; unlike
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
64 Nobile, Besozzi, Cazzaniga, Mauri
other similar works on dynamically reconfigurable PNs [18], or on virtual PNs
[19], RPNs are modified by “exogenous” mutations that can arbitrarily intro-
duce new hidden places and new hidden transitions, where hidden transitions
can represent events involving both elements from P and P h . In RPNs we ex-
plicitly separate the sets P and T from the hidden (modifiable) sets P h and
T h in order to make use of the available, consolidated domain knowledge of the
system under investigation as static (i.e., non modifiable) places and transitions.
In the case of zero-knowledge on the interaction of the elements of the net, the
set P is populated with those elements that are known to be part of the system
and whose data can be exploited by the fitness function, while T = ∅.
Conversely, hidden places and transitions are exploited by the genetic oper-
ators 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 sim-
plified 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 = ∞.
The modifiers of RPNs, exploited by the evolutionary algorithm, are two
classic genetic operators: crossover and mutation. Given the space Ξ of all pos-
sible RPN topologies, we can define an Evolutionary Petri Net (EPN) as a triple
E = (ξ, χ, µ) where:
– ξ ∈ Ξ;
– χ : (Ξ × Ξ) → (Ξ × Ξ) is the crossover operator which modifies two RPNs
ξ and ξ,¯ where ξ and ξ¯ are such that Pξ = P ;
ξ̄
– µ : Ξ ∪ {pin , t, pout } → Ξ is the mutation operator, where {pin , t, pout } is
a triple consisting of two places pin and pout and a transition t, namely
pin , pout ∈ (P ∪ P h ) ∪ P ∞ and t ∈ (T ∪ T h ) ∪ T ∞ , where P ∞ and T ∞ are
infinite sets of places and transitions, such that P ∞ ∩ (P ∪ P h ) = ∅ and
T ∞ ∩ (T ∪ T h ) = ∅.
The functioning of χ and µ is described in the next sections, where we denote
by ξ(τ ), τ ∈ N, the RPN at the τ -th generation of the evolutionary process.
3.1 The Crossover Operator
The crossover mechanism implements the exchange of genetic material between
two RPNs, in order to generate new offspring which inherit the best substructures
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
The Foundation of Evolutionary Petri Nets 65
of the parents. Various crossover mechanisms specifically designed for graphs
have been proposed in literature [20, 21], in particular to tackle the complex
case of two networks with a different number of nodes [17] but, to the best of
our knowledge, no specific work exists about the crossover between bipartite
graphs or, more specifically, PNs. Indeed, the crossover between two PNs is
supposed to identify some substructures in each graph, “detach” them from one
parent graph and “attach” them into the other, and viceversa, while keeping the
consistency of both graphs. The difficulties arise in: (i) how to characterize a
substructure; (ii) how to “detach” it from a graph; (iii) how to “attach” it to a
new graph, considering that there is not a direct correspondence between the
elements belonging to different sets of hidden places. The last issue is extremely
relevant, because it determines the ability of EPNs to transferring a precise
functionality from a RPN to its offspring.
Our proposal for a crossover mechanism of two RPNs ξ(τ ), ξ(τ ¯ ) ∈ Ξ, is named
sticky crossover (SC). SC works on hidden transitions as follows: a transition
tχ ∈ T h (t̄χ ∈ 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
+ • • h +
P = ( tχ ∪ tχ ) ∩ P (P̄ , respectively) the set of hidden places contained in the
substructure connected to tχ (t̄χ ), that is added to ξ¯ (ξ); F + = {(tχ , p), (p, tχ ) ∈
F | p ∈ P + } (F̄ + ) denotes the set of arcs belonging to this substructure.
To the aim of determining the attachment points for the moving substruc-
tures, we randomly select two input places pb ∈ • tχ and p̄b ∈ • t̄χ , and two
output places pe ∈ tχ • and p̄e ∈ t̄χ• (Figure 1c); pb , pe , p̄b , and p̄e 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 p̄b is replaced by
pb , p̄e 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 + \ {p̄b , p̄e }; P h = P h ∪ P̄ + \ {pb , pe };
T̄ h =T̄ h ∪ {tχ } \ {t̄χ }; T h = T h ∪ {t̄χ } \ {tχ };
F̄ =F̄ ∪ F + \ F̄ + ∪ {(t̄, pb )|t̄ ∈ • p̄b } ∪ {(pe , t̄)|t̄ ∈ p̄e• } ∪
∪ {(pb , t̄)|t̄ ∈ p̄b• } ∪ {(t̄, pe )|t̄ ∈ • p̄e } \ {(t̄, p̄b )|t̄ ∈ • p̄b } \
\ {(p̄e , t̄)|t̄ ∈ p̄e• } \ {(p̄b , t̄)|t̄ ∈ p̄b• } \ {(t̄, p̄e )|t̄ ∈ • p̄e };
F =F ∪ F̄ + \ F + ∪ {(t, p̄b )|t ∈ • pb } ∪ {(p̄e , t)|t ∈ pe • } ∪
∪ {(p̄b , t)|t ∈ pb• } ∪ {(t, p̄e )|t ∈ • pe } \ {(t, pb )|t ∈ • pb } \
\ {(pe , t)|t ∈ pe • } \ {(pb , t)|t ∈ pb• } \ {(t, pe )|t ∈ • pe }.
The weights of the arcs exchanged during the crossover process are not modi-
fied. 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 ∈ (• tχ ∪ tχ• ) ∩ P , where tχ is the transition selected for crossover,
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
66 Nobile, Besozzi, Cazzaniga, Mauri
p1 p1 p1 p1
ht1 ht5 ht1 ht5
hp1 hp4 hp1 hp4
ht2 ht3 ht6 ht2 ht3 ht6
hp2 hp3 hp5 hp6 hp2 hp3 hp5 hp6
ht4 ht7 ht4 ht7
p2 p2 p2 p2
(a) Parents RPNs (b) Step #1: selection of the
transitions tχ and t̄χ
p1 p1 p1
p1
ht1 ht5 ht1 ht5
hp1 hp4 hp4 hp1
ht2 ht3 ht6 ht6 ht3 ht2
hp2 hp3 hp5 hp6 hp5 hp6 hp3 hp2
ht4 ht7 ht4 ht7
p2 p2 p2 p2
(c) Step #2: random selection (d) Step #3: exchange of
of pb , pe , p̄b and p̄e nodes substructures
Fig. 1. Example of sticky crossover between two RPNs. (a) From each parent RPN
(b) a hidden transition is randomly selected (red nodes ht2 and ht6 ), identifying the
substructures that will be exchanged between the RPNs (dotted gray line). (c) One
random place from the preset and one from the postset of ht2 and ht6 are selected (the
blue nodes hp1 , hp2 , hp4 and hp5 that correspond to pb , pe , p̄b and p̄e , respectively).
(d) The substructures are exchanged between the RPNs and attached by replacing the
respective blue nodes, thus yielding the two offspring. For the sake of compactness we
do not report the weights of arcs when they are equal to 1.
we let F̄ = F̄ ∪ {(p̄, tχ )} ∪ {(tχ , p̄)} 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.
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
The Foundation of Evolutionary Petri Nets 67
p1 p1 p1 p1
ht1 ht5 ht1 ht5
hp1 hp4 hp1
hp4
ht2 ht3 ht6 ht6 ht3 ht2
hp2 hp3 hp5 hp6 hp5 hp6 hp3 hp6 hp2
ht4 ht7 ht8 ht4 ht8 ht7
p2 p2 hp7 hp7 p2
p2
(a) Parents RPNs (b) RPNs after crossover
Fig. 2. Example of sticky crossover breaking up one RPN, thus creating a separate
component (the hidden transition ht8 in Subfigure (b), and its pre- and postsets).
If the SC involves p ∈ P h and p̄ ∈ P̄ as the selected “attachment” places of
the crossover then, in the exchange of the substructure from ξ to ξ, ¯ place p̄ ∈ P̄
¯ ¯
in ξ remains unchanged, while in the exchange from ξ to ξ, place p ∈ 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 auto-
matically conserved; (iii) the “directionality” of transitions is preserved, since
SC swaps substructures whose presets are still presets, and elements of post-
sets 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 ∈ (• tχ ∪ tχ• ), p 6∈ {pe , pb }, 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 sub-
structure accordingly; the second strategy is to determine a value ρ ∈ N such
that 1 ≤ ρ ≤ min{|T h |, |T̄ h |}, and to repeat the crossover on ρ different transi-
tions, that is, to randomly create two vectors of indexes i1 , . . . , iρ and j1 , . . . , jρ
(with ik , jk ∈ N, k = 1, . . . , ρ), and then apply the crossover operator on each
couple (tik , t̄jk ). 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(|F |2 · |P |).
However, the use of a hash function might yield a reduction of the computational
cost, in the average case, to O(|P |).
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
68 Nobile, Besozzi, Cazzaniga, Mauri
3.2 The Mutation Operator
The mutation operator modifies the structure of a RPN ξ(τ ) in Ξ, or the prop-
erties of its places and arcs (i.e., capacity and weight), by acting on a single,
randomly chosen hidden transition t ∈ T h . In particular, the mutation operator
associates ξ(τ ) to a new consistent RPN ξ(τ + 1), according to a specified triple
{pin , t, pout }. 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 oper-
ator for all the possible cases of {pin , t, pout } 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 ∈ 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 ∈ P h and @ {(p, t), (t, p)} ∀t ∈ T ∪ T h , then P h = P h \ {p}; (ii) if t ∈ T h
and @ {(t, p), (p, t)} ∀p ∈ P ∪ P h , then T h = T h \ {t}.
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, re-
spectively) 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̃ ∈ • t (p̃ ∈ 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.
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
The Foundation of Evolutionary Petri Nets 69
Table 1. Effect of the mutation operator on a Resizable Petri Net ξ(τ ).
No. Condition ξ(τ + 1) Semantics of the mutation
1. pin 6∈ P ∪ P h P h = P h ∪ {pin } A new hidden place pin is created and added to
h ∞ ∞ P h ; transition t is extended to have a new input
t∈T ∪T P =P \ {pin } place pin
h
pout ∈ P ∪ P
2. pin ∈ P ∪ P h P h = P h ∪ {pout } A new hidden place pout is created and added to
P h ; transition t is extended to have a new output
t∈T ∪T h
P ∞ = P ∞ \ {pout } place pout
pout 6∈ P ∪ P h
3. pin ∈ P ∪ P h T h = T h ∪ {t} A new hidden transition t is created and added to
h ∞ ∞ T h ; transition t is connected to the existing input
t 6∈ T ∪ T T =T \ {t} and output places pin and pout , respectively
pout ∈ P ∪ P h
4. pin 6∈ P ∪ P h P h = P h ∪ {pin } A new hidden transition t is created and added
h h h
to T h ; a new hidden place pin is created and
t 6∈ T ∪ T T = T ∪ {t} added to P h ; transition t is connected to new in-
put place pin and to an existing output place pout
P ∞ = P ∞ \ {pin }
h
pout ∈ P ∪ P
T ∞ = T ∞ \ {t}
h
5. pin ∈ P ∪ P T h = T h ∪ {t} A new hidden transition t is created and added to
h h h
T h ; a new hidden place pout is created and added
t 6∈ T ∪ T P = P ∪ {pout } to P h ; transition t is connected to an existing
input place pin and to the new output place pout
P ∞ = P ∞ \ {pout }
h
pout 6∈ P ∪ P
T ∞ = T ∞ \ {t}
h
6. pin 6∈ P ∪ P P h = P h ∪ {pin , pout } Two new hidden places pin and pout are created
h ∞ ∞ and added to P h ; transition t is connected to pin
t∈T ∪T P =P \ {pin , pout } as input place and to pout as output place
h
pout 6∈ P ∪ P
7. pin 6∈ P ∪ P h P h = P h ∪ {pin , pout } A new hidden transition t is created and added
h h h
to T h ; two new hidden places pin and pout are
t 6∈ T ∪ T T = T ∪ {t} created and added to P h ; transition t is connected
to the new input place pin and to the new output
pout 6∈ P ∪ P h P ∞ = P ∞ \ {pin , pout } place pout
T ∞ = T ∞ \ {t}
h
8. pin ∈ P ∪ P Ph = Ph No new genetic material is introduced. Either pin
or pout is randomly chosen; then, its capacity or
t ∈ T ∪ Th h
T =T h
the weight of the arc connecting it to t is modified
pout ∈ P ∪ P h P ∞ = P ∞ , T ∞ = T ∞
The computational complexity of the mutation operator is, for the worst case,
O(|P |). 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 < |P |.
4 Toward the Application of EPNs for the Reverse
Engineering of Biochemical Reaction Networks
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
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
70 Nobile, Besozzi, Cazzaniga, Mauri
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 knowl-
edge, although most of the times the exact molecular mechanisms occurring in
living cells are not known and cannot be fully understood by means of labo-
ratory 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 param-
eterized, 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ζ ∈
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 ∈ N are the stoichiometric coefficients of Rζ , and kζ ∈ R+ is the
kinetic constant associated to Rζ . The species occurring on the left-hand (right-
hand) 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 [22] defined as a set of re-
actions in the form of Rζ . To this aim, a transformation of a network η into
a corresponding PN (and viceversa) needs to be defined. Briefly, a mapping
f : S → P can be used to associate the species to the places of a PN, where
the transitions represent the chemical reactions (i.e., g : R → T ) and where the
weights correspond to the stoichiometry of the reagents and products of each
reaction (i.e., vr : aζi → W (pi , tζ ), vp : bζi → W (tζ , pi )). According to these
mappings, it is straightforward to show that the PN on the left in Figure 1a
represents the following set of reactions: {R1h : S1 → S1h , R2h : S1h → S2h , R3h :
S1h → S3h , R4h : S2h → S2 }. The number of tokens (given as discrete or continu-
ous value) in each place represents the molecular amount (given as number of
molecules or concentration, respectively) of the corresponding chemical species,
so that M0 represents the initial state of the biochemical system.
The PN representation of a biochemical reaction network allows the investi-
gation of its structural features by means of theoretical approaches [22, 23]; in
addition, PNs can be easily extended with timed delays [24], or to incorporate
quantitative information (e.g., reaction rates, concentration levels) to the aim of
investigating the dynamic evolution of biochemical systems [25]. Kinetic param-
eters can also be associated to the reactions, in order to derive the probability
of each reaction to occur [26], or to convert the system into a set of coupled
ordinary differential equations; in the latter case, places contain continuous val-
ues corresponding to the concentration of the chemical species associated to each
place. Once that a model η of a biochemical network is defined in terms of a fully
parameterized extended PN, according to the available domain knowledge, its
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
The Foundation of Evolutionary Petri Nets 71
dynamic behavior can be investigated. Anyway, when the domain knowledge is
incomplete, uncertain or completely missing, a (fully parameterized) PN model
of a biochemical system cannot be constructed. In such a case, it is necessary to
perform the RE of the biochemical reaction network, investigating the unknown
reactions and chemical species that are responsible for the observed phenomena.
Many works perform the RE by means of evolutionary techniques [12, 27, 28].
One limitation of many of these techniques is that the individuals are modeled
by means of data structures that are not ideal to describe reaction networks;
in addition, many constraints and consistency controls must be introduced to
control the quality and validity of the inferred network. The strongest limitation
of all these methods is that the cardinality of S, that is, the number of chemical
species that are present in the system, is assumed to be known and kept fixed
during the optimization. This is generally a strong assumption, that may be jus-
tified only if the biochemical system is very well known (but, in such a case, the
network should be known as well) or when laboratory experiments can yield this
information with a certain precision. As a matter of fact, in most cases the exact
number and nature of the chemical species involved in the system – including the
intermediate complexes formed by the chemical bonds among various molecules
– is unknown; anyway, this is a fundamental information to properly carry out
the RE of the system. Thanks to the flexibility of hidden places and transitions,
the use of RPNs to represent the candidate solutions gives to EPN the possibil-
ity to explore much more possibilities than the traditional RE approaches that
exploit a fixed number of chemical species, thus leading to the formulation of
new hypotheses for the structure of the biochemical network that should then
be validated with ad hoc laboratory experiments. In this context, hidden places
in the RPN can be exploited to represent some molecular species or complexes
which are necessary to reproduce the expected behavior of the biochemical sys-
tem, but that have not been yet identified with experimental techniques; similar
considerations hold for hidden transitions, which can represent molecular inter-
actions that are not known from a biochemical point of view, but that might
yield a better system functioning (in terms of the specified fitness function, and
according to the available experimental data).
The application of an EPN-based methodology for the RE of biochemical sys-
tems 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 ∆ ∈ N experimental samples
of the |P | = m non-hidden chemical species (places in P ) against the dynam-
ics generated through simulations [29], exploiting the set of reactions that the
P∆ Pm
RPN represents: f itness(η) = δ=1 i=1 |Qpi (tδ )−Lpηi (tδ )|, where Qpi (tδ ) and
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
72 Nobile, Besozzi, Cazzaniga, Mauri
Lpηi (tδ ) denote, respectively, the experimental and simulated quantity (concen-
tration or molecular amount) of the pi -th chemical species at time tδ .
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 higher-
order 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 ∈ 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 Rh , renamed Rh
2 6
after the crossover, has an additional product (i.e., S6h , left side of Figure 1d).
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.
5 Conclusion and Future Work
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 pro-
vided an example of a potential application of EPNs – the RE of biochemical
reaction networks – which might represent a killer-application for our evolution-
ary 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
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
The Foundation of Evolutionary Petri Nets 73
is further complicated by the need of a parameter estimation (PE) methodol-
ogy for the inference of the missing kinetic parameters [30, 31]: to this aim, we
are developing an integrated methodology that embeds the PE process in each
generation of the RE. A further difficulty of the RE process is due to the fact
that different networks can lead to the same dynamic behavior; this problem,
known as undistinguishability [32], cannot be solved, in general, without addi-
tional knowledge. EPNs do not directly mitigate this drawback, even though
pre- and post-order conditions allow the reduction of the possible topologies,
thus permitting the derivation of meaningful networks that can be then discrim-
inated by domain expertise. Finally, the initial marking of the hidden places was
set to zero: a further extension of EPN, in which the initial marking co-evolves
with the topology, is under investigation.
References
1. DeJong, K.: Evolutionary computation: a unified approach. The MIT Press (2006)
2. Murata, T.: Petri nets: Properties, analysis and applications. In: Proc. IEEE.
Volume 77. (1989) 541–580
3. Thome, H., Nakamura, M., Hachiman, K.: Evolutionary Petri net approach to
periodic job-shop scheduling. In: Proc. IEEE Int. Conf. on Systems, Man, and
Cybernetics (SMC’99). Volume 4., IEEE Computer Society Press (1999) 441–446
4. Saitou, K., Malpathak, S., Qvam, H.: Robust design of flexible manufacturing
systems using colored Petri net and genetic algorithm. Journal of Intelligent Man-
ufacturing 13(5) (2002) 339–351
5. Mauch, H.: Evolving Petri nets with a genetic algorithm. In: Proc. of the 2003
conference on genetic and evolutionary computation (GECCO ’03). Volume 2724
of LNCS., Springer (2003) 1810–1811
6. Moore, J., L.W.Hahn: Grammatical evolution for the discovery of Petri net mod-
els of complex genetic systems. In: Proc. of the 2003 conference on genetic and
evolutionary computation (GECCO ’03). Volume 2724 of LNCS., Springer (2003)
2412–2413
7. Kitagawa, J., Iba, H.: Identifying metabolic pathways and gene regulation networks
with evolutionary algorithms. In: Evolutionary Computation in Bioinformatics.
Morgan Kaufmann (2003) 255–278
8. Koza, J.R., Mydlowec, W., Lanza, G., Yu, J., Keane, M.A.: Reverse engineering
of metabolic pathways from observed data using genetic programming. In: Pacific
Symposium on Biocomputing. Volume 6. (2001) 434–445
9. Sugimoto, M., Kikuchi, S., Tomita, M.: Reverse engineering of biochemical equa-
tions from time-course data by means of genetic programming. BioSystems 80(2)
(2005) 155–164
10. Ando, S., Sakamoto, E., Iba, H.: Evolutionary modeling and inference of gene
network. Information Sciences 145(3) (2002) 237–259
11. Iba, H.: Inference of differential equation models by genetic programming. Infor-
mation Sciences 178(23) (2008) 4453–4468
12. Nummela, J., Julstrom, B.A.: Evolving petri nets to represent metabolic pathways.
In: Proc. of the 2005 conference on genetic and evolutionary computation (GECCO
’05), ACM (2005) 2133–2139
13. Holland, J.: Adaptation in Natural and Artificial Systems. The University of
Michigan Press (1975)
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013
74 Nobile, Besozzi, Cazzaniga, Mauri
14. Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proc. IEEE Interna-
tional Conference on Neural Networks. Volume 4., IEEE (1995) 1942–1948
15. Bäck, T.: Selective pressure in evolutionary algorithms: A characterization of se-
lection mechanisms. In: Proc. of the First IEEE Conference on Evolutionary Com-
putation. Volume 1., IEEE (1994) 57–62
16. Koza, J.: Genetic Programming: On the Programming of Computers by Means of
Natural Selection. The MIT Press (1992)
17. Katagiri, H., Hirasawa, K., Hu, J., Murata, J.: Comparing some graph crossover
in genetic network programming. In: Proc. of the 41st SICE Annual Conference.
Volume 2., IEEE (2002) 1263–1268
18. Llorens, M., Oliver, J.: Structural and dynamic changes in concurrent systems:
Reconfigurable Petri nets. IEEE Trans. on Computers 53(9) (2004) 1147–1158
19. Morandin Jr, O., Kato, E.: Virtual Petri nets as a modular modeling method for
planning and control tasks of FMS. International Journal of Computer Integrated
Manufacturing 18(2-3) (2005) 100–106
20. Larrañaga, P., Kujipers, C., Murga, R., Inza, I., Dizdarevic, S.: Genetic algorithms
for the travelling salesman problem: A review of representations and operators.
Artificial Intelligence Review 13(2) (1999) 129–170
21. Pereira, F., Machado, P., Costa, E., Cardoso, A.: Graph based crossover – a case
study with the busy beaver problem. In: Proc. of the Genetic and Evolutionary
Computation Conference (GECCO ’99). Volume 2. (1999) 1149–1155
22. Chaouiya, C.: Petri net modelling of biological networks. Briefings in Bioinformat-
ics 8(4) (2007) 210–219
23. Voss, K., Heiner, M., Koch, I.: Steady state analysis of metabolic pathways using
Petri nets. In Silico Biology 3(3) (2003) 367–387
24. Li, C., Ge, Q., Nakata, M., Matsuno, H., Miyano, S.: Modelling and simulation of
signal transduction in an apoptosis pathway by using timed Petri nets. Journal of
Biosciences 32(1) (2006) 113–127
25. Goss, P., Peccoud, J.: Quantitative modeling of stochastic systems in molecular
biology by using stochastic Petri nets. PNAS 95(12) (1998) 6750–6755
26. Gillespie, D.T.: Stochastic simulation of chemical kinetics. Annual Review of
Physical Chemistry 58 (2007) 35–55
27. Cho, D., Cho, K., Zhang, B.: Identification of biochemical networks by S-tree based
genetic programming. Bioinformatics 22(13) (2006) 1631–1640
28. Nobile, M.S., Besozzi, D., Cazzaniga, P., Pescini, D., Mauri, G.: Reverse engineer-
ing of kinetic reaction networks by means of cartesian genetic programming and
particle swarm optimization. In: Proc. IEEE Congress on Evolutionary Computa-
tion (CEC2013). (2013, in press)
29. Ghosh, S., Matsuoka, Y., Asai, Y., Hsin, K.Y., Kitano, H.: Software for systems
biology: from tools to integrated platforms. Nature Reviews Genetics 12(12) (2011)
821–832
30. Nobile, M.S., Besozzi, D., Cazzaniga, P., Mauri, G., Pescini, D.: A GPU-based
multi-swarm PSO method for parameter estimation in stochastic biological systems
exploiting discrete-time target series. In: Proc. EvoBIO 2012. Volume 7246 of
LNCS. Springer (2012) 74–85
31. Moles, C.G., Mendes, P., Banga, J.R.: Parameter estimation in biochemical path-
ways: a comparison of global optimization methods. Genome Research 13(11)
(2003) 2467–2474
32. Szederkenyi, G., Banga, J.R., Alonso, A.A.: Inference of complex biological net-
works: distinguishability issues and optimization-based solutions. BMC Systems
Biology 5(1) (2011) 177
Proc. BioPPN 2013, a satellite event of PETRI NETS 2013