For the most recent entries see the Petri Nets Newsletter.

A GA approach to solving reachability problems for Petri nets.

Takahashi, K.; Yamamura, M.; Kobayashi, S.

In: IEICE Trans. on Fundamentals in Electronics, Communications and Computer Science, Vol. E79-A, No. 11, pages 1774-1780. 1996.

Abstract: The paper presents an efficient method to solve reachability problems for Petri nets, based on genetic algorithms and a kind of random search which is called postpone search. Genetic algorithm (GA) is one of algorithms developed for solving several problems of optimization. The proposed approach applies GA and postpones to approximately solving reachability problems. This approach cannot determine exact solution, however, from applicability point of view, does not directly face the state space explosion problems and can extend the class of Petri nets to deal with very large state spaces in reasonable time. The paper first describes how to represent reachability problems of each of GAs and postpone the search. The existence of a non-negative Parikh vector which satisfies the necessary reachability condition is assumed. Possible firing sequences of transitions induced by the Parikh vector are encoded in GAs. Reachability problems are be interpreted as optimization problems on GAs. Fitness function to solve reachability problems is defined. Then, random reachability problems are introduced which are capable of handling the state space and a number of firing sequences which can reach the target marking from an initial marking. State space and the number of firing sequences are considered as factors which effect the hardness of reachability problems to be solves by stochastic methods. Furthermore, by using those random reachability problems and the well known dining philosophers problem as benchmarks, GAs' performance is compared with the performance of the postponed search. Empirical results are presented whichs how that GAs are more useful than the postponed search method for solving harder reachability problems from both reliability and efficiency points of view.

Keywords: Petri nets, genetic algorithms, reachability problem, state space explosion.


Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography