A GA Approach to Solving Reachability Problems for Petri Nets (Special Section on Description Models for Concurrent Systems and Their Applications)

スポンサーリンク

概要

• 論文の詳細を見る

• 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 GAs is more useful method than postpone search for solving more harder reachabi1ity problems from the both points of view; "reliability " and "efficiency."

• 社団法人電子情報通信学会の論文
• 1996-11-25

著者

• Yamamura Masayuki

  The Department Of Computational Intelligence And Systems Science

• KOBAYASHI Shigenobu

  National Institute of Industrial Safety, Independent Administrative Institution

• TAKAHASHI Keiko

  the Department of Computational Intelligence and Systems Science

• KOBAYASHI Shigenobu

  the Department of Computational Intelligence and Systems Science

• Kobayashi S

  National Institute Of Industrial Safety Independent Administrative Institution

関連論文

• Study on the Safety Evaluation Method of the Power Reed Switch--Estimation on the Occurrence Probability of Failure to Danger based on Field Data (国際セッションIS--EMD 2003) -- (Session 5 Switching devices)
• Study on the Safety Evaluation Method of the power Reed Switch : Estimation on the Occurrence Probability of Failure to Danger based on Field Data
• A GA Approach to Solving Reachability Problems for Petri Nets (Special Section on Description Models for Concurrent Systems and Their Applications)

スポンサーリンク