A GA Approach to Solving Reachability Problems for Petri Nets

Keiko TAKAHASHI; Masayuki YAMAMURA; Shigenobu KOBAYASHI

A GA Approach to Solving Reachability Problems for Petri Nets

Keiko TAKAHASHI, Masayuki YAMAMURA, Shigenobu KOBAYASHI

Full Text Views

0

Share
Cite this

Summary :

In this paper we present 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 is one of algorithms developed for solving several problems of optimization. We apply GAs and postpone search to approximately solving reachability problems. This approach can not determine exact solutions, however, from applicability points of view, does not directly face state space explosion problems and can extend class of Petri nets to deal with very large state space in reasonable time. First we describe how to represent reachability problems on each of GAs and postpone search. We suppose the existence of a nonnegative parickh vector which satisfies the necessary reachability condition. Possible firing sequences of transitions induced by the parickh vector is encoded on GAs. We also define fitness function to solve reachability problems. Reachability problems can be interpreted as an optimization ones on GAs. Next we introduce random reachability problems which are capable of handling state space and the number of firing sequences which enable to reach a target marking from an initial marking. State space and the number of firing sequences are considered as factors which effect on the hardness of reachability problems to solve with stochastic methods. Furthermore, by using those random reachability problems and well known dining philosophers problems as benchmark problems, we compare GAs' performance with the performance of postpone search. Finally we present empirical results that GAa is more useful method than postpone search for solving more harder reachability problems from the both points of view; reliability and efficiency.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E79-A No.11 pp.1774-1780

Publication Date: 1996/11/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Description Models for Concurrent Systems and Their Applications)

Category

Cite this

Copy

Keiko TAKAHASHI, Masayuki YAMAMURA, Shigenobu KOBAYASHI, "A GA Approach to Solving Reachability Problems for Petri Nets" in IEICE TRANSACTIONS on Fundamentals, vol. E79-A, no. 11, pp. 1774-1780, November 1996, doi: .
Abstract: In this paper we present 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 is one of algorithms developed for solving several problems of optimization. We apply GAs and postpone search to approximately solving reachability problems. This approach can not determine exact solutions, however, from applicability points of view, does not directly face state space explosion problems and can extend class of Petri nets to deal with very large state space in reasonable time. First we describe how to represent reachability problems on each of GAs and postpone search. We suppose the existence of a nonnegative parickh vector which satisfies the necessary reachability condition. Possible firing sequences of transitions induced by the parickh vector is encoded on GAs. We also define fitness function to solve reachability problems. Reachability problems can be interpreted as an optimization ones on GAs. Next we introduce random reachability problems which are capable of handling state space and the number of firing sequences which enable to reach a target marking from an initial marking. State space and the number of firing sequences are considered as factors which effect on the hardness of reachability problems to solve with stochastic methods. Furthermore, by using those random reachability problems and well known dining philosophers problems as benchmark problems, we compare GAs' performance with the performance of postpone search. Finally we present empirical results that GAa is more useful method than postpone search for solving more harder reachability problems from the both points of view; reliability and efficiency.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e79-a_11_1774/_p

Copy

@ARTICLE{e79-a_11_1774,
author={Keiko TAKAHASHI, Masayuki YAMAMURA, Shigenobu KOBAYASHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A GA Approach to Solving Reachability Problems for Petri Nets},
year={1996},
volume={E79-A},
number={11},
pages={1774-1780},
abstract={In this paper we present 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 is one of algorithms developed for solving several problems of optimization. We apply GAs and postpone search to approximately solving reachability problems. This approach can not determine exact solutions, however, from applicability points of view, does not directly face state space explosion problems and can extend class of Petri nets to deal with very large state space in reasonable time. First we describe how to represent reachability problems on each of GAs and postpone search. We suppose the existence of a nonnegative parickh vector which satisfies the necessary reachability condition. Possible firing sequences of transitions induced by the parickh vector is encoded on GAs. We also define fitness function to solve reachability problems. Reachability problems can be interpreted as an optimization ones on GAs. Next we introduce random reachability problems which are capable of handling state space and the number of firing sequences which enable to reach a target marking from an initial marking. State space and the number of firing sequences are considered as factors which effect on the hardness of reachability problems to solve with stochastic methods. Furthermore, by using those random reachability problems and well known dining philosophers problems as benchmark problems, we compare GAs' performance with the performance of postpone search. Finally we present empirical results that GAa is more useful method than postpone search for solving more harder reachability problems from the both points of view; reliability and efficiency.},
keywords={},
doi={},
ISSN={},
month={November},}

Copy

TY - JOUR
TI - A GA Approach to Solving Reachability Problems for Petri Nets
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1774
EP - 1780
AU - Keiko TAKAHASHI
AU - Masayuki YAMAMURA
AU - Shigenobu KOBAYASHI
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E79-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 1996
AB - In this paper we present 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 is one of algorithms developed for solving several problems of optimization. We apply GAs and postpone search to approximately solving reachability problems. This approach can not determine exact solutions, however, from applicability points of view, does not directly face state space explosion problems and can extend class of Petri nets to deal with very large state space in reasonable time. First we describe how to represent reachability problems on each of GAs and postpone search. We suppose the existence of a nonnegative parickh vector which satisfies the necessary reachability condition. Possible firing sequences of transitions induced by the parickh vector is encoded on GAs. We also define fitness function to solve reachability problems. Reachability problems can be interpreted as an optimization ones on GAs. Next we introduce random reachability problems which are capable of handling state space and the number of firing sequences which enable to reach a target marking from an initial marking. State space and the number of firing sequences are considered as factors which effect on the hardness of reachability problems to solve with stochastic methods. Furthermore, by using those random reachability problems and well known dining philosophers problems as benchmark problems, we compare GAs' performance with the performance of postpone search. Finally we present empirical results that GAa is more useful method than postpone search for solving more harder reachability problems from the both points of view; reliability and efficiency.
ER -