Petri Nets are graph based tools to model and study concurrent systems and their properties; one of them is liveness, which is related to the possibility of every part of the system to be activated eventually. Siphons are sets of places that have been related to liveness properties. When we need to deal with realistic problems its computation is hard or even impossible and this is why in this paper we are approaching it using evolutionary computation, a meta-heuristic that has proved it can successfully find solutions when the search space is big. In this work a formulation of the siphon property using linear constraints is presented for general Petri Nets. We will also present an evaluation for a family of resource allocation systems (RAS). The proposed solution is based on a genetic algorithm (GA); we will show how siphons can be computed using it, with experiments showing that in some cases they are able to find a few solutions in less time than previous deterministic algorithms.
A Resource Allocation System (RAS) is a discrete event system in which a finite
set of concurrent processes shares in a competitive way a finite set of resources.
RAS are usually complex enough to take advantage of the use of formal methods,
which can help to improve its understanding, providing tools for the analysis and
implementation steps. They also help in the dialog between people involved in
the design, construction and system management. Our proposal is to use Petri
(or Place/Transition) Nets as a tool for this purpose. They are used to visualize
and, through formal analysis, describe structural properties of the system they
represent[
Software systems are also complex systems that can be seen as a set of
processes sharing (and competing for) resources. There is some recent work in this
area, such as [
In [
In this work we are going to propose a genetic algorithm (GA). that uses a formulation of the siphon property by means on linear constraints. This implementation has been tested in a well-known family of RAS. We will show how we can compute siphons using a genetic algorithm with an existing generic package. This approach opens the door to adapt another siphon-based techniques for deadlock prevention.
The contents of this paper are organized as follows. Section 2 provides an introduction to Petri Nets and the main concepts related to the problem, Section 3 presents the standard Genetic Algorithm. There is also some information about methods existing in the literature for solving the same problem, Section 4 presents the adapted method, Section 5 shows our experimental setup and the experimental results, together with some discussion about them. Finally, some conclusions are presented. 2
A Petri net (or Place/Transition net) is a 3-tuple N = hP, T, W i where P and T are two non-empty disjoint sets whose elements are called places and transitions, respectively. In a generic way, elements belonging to P [ T are called nodes. W : (P ⇥ T ) [ (T ⇥ P ) ! IN defines the weighted flow relation: if W (x, y) > 0, then we say that there is an arc from x to y, with weight or multiplicity W (x, y). Ordinary nets are those where W : (P ⇥ T ) [ (T ⇥ P ) ! { 0, 1}.
Given a net N = hP, T, W i and a node x 2 P [ T , •x = {y 2 P [ T | W (y, x) > 0} is the pre-set of x, while x• = {y 2 P [ T | W (x, y) > 0} is the post-set of x. This notation is extended to a set of nodes as follows: given X ✓ P [ T, •X = Sx2 X •x, X• = Sx2 X x•.
A Petri net is self–loop free when W (x, y) 6= 0 implies that W (y, x) = 0. The Pre–incidence matrix Pre : P ⇥ T ! IN of N is Pre[p, t] = W (p, t). The Post–incidence matrix Post : P ⇥ T ! IN of N is Post[p, t] = W (t, p). A self–loop free Petri net N = hP, T, W i can be alternatively represented as N = hP, T, Ci where C is the incidence matrix: a P ⇥ T indexed matrix such that C[p, t] = W (t, p) W (p, t) = Post[p, t] Pre[p, t]. A marking is a mapping m : P ! IN; in general, markings are represented in vector form. A transition t 2 T is enabled for a marking m if and only if 8 p 2 •t . m[p] W (p, t); this fact will be denoted as m! t (or m[t>). If t is enabled at m, it can occur; when it occurs, this gives a new marking m0 = m + C[P, t]; this will be denoted as m t m0 (or m[t>m0), and we say that m’ is reached from m by the occurrence ! of t. The state equation of a marked net is an algebraic equation that gives a necessary condition for the reachability of a marking from the initial marking: a markings m 2 IN|P | such that 9 2 IN|T | . m = m0 +C· is said to be potentially reachable. The potentially reachability set of a net is the set of solutions for the state equation. Flows (Semiflows) are integer (natural) annullers of matrix C (That is, a vector, y 6= 0 such that y · C = 0). Right and left annullers are called T–(Semi)flows and P–(Semi)flows, respectively. The support of P– (Semi)flows is given by: kyk = {p 2 P | y[p] > 0}. Let PS be the set of minimal P–Semiflows of N . A (Semi)flow is called minimal when its support is not a strict super-set of the support of any other, and the greatest common divisor of its elements is one. A P–Semiflow y defines the following invariant property: 8 m0 . 8 m 2 PRS(N , m0) . y · m = y · m0 (cyclic behavior law).
Given N an ordinary Petri net, a subset of places D ✓ P is a siphon (E ✓ P
is a trap) of the net N if, and only if, •D ✓ D• (E• ✓ •E). A siphon (trap)
is minimal if, and only if, it does not properly contain another siphon (trap).
Siphons have the important property that, if at a given marking the siphon is
unmarked, it will never be marked. Researchers have considered and studied
different methods for finding siphons and traps. Among them let us present the
main types, that we will classify based on the underlying techniques used for their
computation: Algebraic methods compute families of siphons by means of the
solution of a set of linear equations or inequalities. They use the net incidence–
matrix or a transformation of it. Methods using this approach can be found
in [
Genetic algorithms [
(d) (Accepting) Place new offspring in a new population
in current population
The main task of a genetic algorithms designer is to find good parameter
settings (population size, encoding, selection criteria, genetic operator
probabilities, fitness evaluation, ...). We have used the Algorithm::Evolutionary [
As far as we know, there are no approaches using genetic algorithms to compute
structural properties of Petri Net models. Some work has been done on process
mining and scheduling [
It is straightforward to try to use the standard GA without much difficulty: each place p of the Petri net will be represented by means of a binary variable vp. The siphon property can be represented as follows: 8 p 2 P, 8 t 2 •p, vp
X vq, with vq, vp 2 { 0, 1} q2 •t (1)
The siphon would be composed of the set of places whose corresponding variable equals to one, vp = 1. The meaning of each equation is that if place p is in the set (it belongs to the siphon) it must contain, at least, one of the
That is, we are not interested in the whole set of places since it is a siphon but it is an uninteresting one. Finally,
X vp < |P \ P0| p2 P \P0 8 Y 2 PS , X vp < kYk
p2 Y places that are in the pre–set of each of its entry transitions. This needs to be completed with some restrictions that avoid undesired situations:
In this case, the selected set of places cannot be a P-Semiflow, since they are uninteresting siphons. P-Semiflows cannot be emptied because of the cyclic behavior law described above. Moreover, they are much less expensive from a computational point of view. For the Figure 1 and the set of equations shown there the assignment vp_0_1 = vp_1_0 = vr_0_0 = vr_0_1 = 1 is a solution and the set of places defined by them is a minimal siphon ({p_0_1, p_1_0, r_0_0, r_0_1}). It is easy to see that if we add vp_0_0 = 1 to the previous solution the equations remain true. This is one of the problems of this method: these equations can describe siphons, but they do not need to be minimal. (2) (3)
With this formulation we can construct a fitness function for the genetic algorithm that can guide the system towards a solution. As each variable can have a value of 0 or 1, this approach is well-suited to be formulated as a genetic algorithm. A final remark is that the genetic algorithm is an optimization algorithm so some objective function is needed. We have decided to minimize the number of active variables. Since we cannot state by means of a simple logical formula the minimality property, we have chosen to compute the smaller siphons. We can imagine alternative objective functions that would take into account just the number of resource places, the number of process places, or some more complex measurements. The complete system would be: (4) min Pp2 P vp 8 p 2 P, 8 t 2 •p, vp Pq2 •t vq, vp 2 { 0, 1} Pp2 P \P0 vp < |P \ P0| 8 Y 2 PS , Pp2 Y vp < kYk
Since we want to obtain a result that minimizes the function and that satisfies the restrictions we need to combine this information. When we have an individual which represents an empty siphon or a siphon composed by all the places of the net, we can return a negative number, equivalent to twice the number of restrictions (the idea is to help de GA to avoid these solutions). For the other restrictions, we can just count the number of places in the siphon when they are met. When there are unmet restrictions, we just return the difference between the number of such restrictions and the total number of restrictions (this is a negative number, that grows when more restrictions are met). We have tried several configurations giving more weight to the number of places in the siphon or to the number of satisfied restrictions but not significant differences appear. 5
We have compared the nets used in [
There is a more detailed presentation of some of these models in [
process; the resource used at the second step of the first process is used by the one that is previous to the last step in the second process, and so on. The second process is composed with the third one in a similar way and so on, until we reach the total number of composed processes. The last process is composed with the first one, in a similar way. Using the previous ideas two different families of S4P R nets have been generated, labeled as FMSAD and FMSLD in the tables.
FMSAD nets are obtained by means of the composition of a variable number of sequential processes as the ones depicted in Figure 1, with a fixed length of 3. The number of processes to be composed in parallel is the parameter. In the experiments, the number of composed processes is varying from 3 to 8. FMSLD nets are obtained by means of the composition of a fixed number of two sequential processes as the ones depicted in Figure 1, with a variable length which is the parameter. In the experiments, this length is varying from 3 to 8.
The last one corresponds to an implementation of the well known dining philosophers problem. The parameter corresponds to the number of philosophers. initial population and the number of evaluations. We start the experiment for each example with an initial population of size 8 and we run the program thirty times; if it fails (does not compute a siphon) more than once, we double the size of the initial population and repeat until we can reach thirty iterations with at most one failed result. We also established a maximum number of evaluations: if no solution is found after this number of evaluations the algorithm stops (and we consider this run a failure).
We have tested two approaches for the initial population: First, introducing
the P–Semiflows (when there are less P–Semiflows than the size of the initial
population we add the needed individuals at random; when there are more,
we add all of them and we complete the population until we reach a multiple of
eight individuals). Second, using a fully random initial population. The reason for
trying the first approach is that P–Semiflows could guide the algorithm toward
interesting places in the net (in some classes of nets it is possible to construct
them as a seed [
When the algorithm stops, we can check whether the solution with best fitness is a siphon or not: if it has not positive fitness it won’t be a siphon.
The results obtained can be seen in Table 2. They also can be seen in a graphical way in the second column of Figure 3 and in Figure 4. In the Figure 4 we have also included the standard deviation of the thirty runs of the program. We have included in the Figure 3 the graphics for the algebraic methods as a baseline. The times provided in the table and in the figures for the genetic algorithms are the average of the thirty runs of each experiment with the smaller acceptable initial population for each size of each problem.
We can see that the genetic algorithm is slower, in general, than the algebraic methods except for the case of FMSAD example, where the genetic algorithm seems to obtain its solution in less time (and it grows slowly if we compare with the algebraic method, which seems to grow exponentially).
There are two things to remark here: the results should not be compared directly, since the algebraic implementations where done in C, and the genetic algorithm has been programmed using Perl (an interpreted language). Nevertheless, putting the results together helps us to see that they are not so far away and that the approach can be adequate for some types of problems or when the size grows in such a way that it cannot be managed with deterministic methods. The second thing to note is that the genetic algorithm does not obtain all the siphons but a number of them (as the best fitted members of the final population).
In Table 2 we can see that there are no relevant differences in time when using the P–Semiflows as the initial population and when we use a random initial population. In the FMSAD example there is a small difference in the number of evaluations, which tend to be bigger (but the differences are small and there are cases when there are less evaluations with the random population -sizes 4, 5-). In the FMSLD example the number of evaluations tends to be lower for the initial random population (except for sizes 5,7). Finally, in the Phil example, the cases where the number of evaluations is better is the same for both initial types of initial population.
The results obtained show that the approach is suitable: we can compute (minimal) siphons with the proposed method. Comparing with traditional methods the genetic approach does not provide better time computation except for one example (but they are implementations in different languages) and the behavior is better with more complex problems (as one would expect). If we were interested in computing all the siphons, we could add the computed ones as negative restrictions (this set of places cannot be a solution, as we have done with P–Semiflows) and apply again the GA.
As another way to evaluate the approach we computed Table 3 where we can see the total number of different siphons obtained with the proposed method compared to the total number of siphons for each system. For this we have used
the same experiments as in the previous table: we can count the number of different siphons for each size of each problem in the 30 runs of the experiment. With this we can show that the genetic algorithm has a good behavior (different runs examine different parts of the solutions space) but we are not measuring what would happen with the addition of new restrictions to forbid siphons that have been computed previously. Moreover, when the size of the problem increases the method computes less siphons. Our feeling is that this is due to the size of the population (the size is small compared to the number of total siphons when
the size of the problem grows). For this reason we have added columns 6 and 7. There we can see that the number of different siphons computed increases with a bigger initial population. We can also see in that Table that the random initial population tends to produce more different siphons across different experiments.
6
Some deadlock prevention control policies need the set of minimal siphons to be computed. It is well known that this is a very hard task because the number of such components can be very high. This paper has concentrated on the study of such question.
An adaptation of a set of logical formulas has been provided in order to try the genetic algorithm to search for a structural component of the net (siphons).
Even when it is not clear if the method has a good enough performance, it opens the door to further work. It is our intention to try to apply it to some deadlock prevention methods proposed in the past, where some special siphons need to be computed at each step.
Moreover, when the computation of all the siphons becomes prohibitively expensive, the genetic algorithm can still deal with bigger problems if it is acceptable for us to have a partial set of the siphons instead of the whole set provided by algebraic approaches.
In this sense, our proposal for further work will follow several ideas: First
of all, the genetic algorithm is well suited for parallelization as in [
The authors are indebted to the anonymous referees and the PC who have helped us to improve the quality and presentation of this paper. This work is supported in part by project ANYSELF (TIN2011-28627-C04-02) by the Spanish Mineco and TIN2011-27479-C04-01 by the Spanish Ministry of Science and Innovation; P08-TIC-03903 awarded by the Andalusian Regional Government, project 83, Campus CEI BioTIC, and by Group of Discrete Event Systems Engineering (GISED) awarded by Aragonese Government.