In: Proc. 30th Annual Hawaii Int. Conf. on System Sciences; Vol. 5: System Sciences, 7-10 January 1997, Wailea, HI, pages 89-98. 1997.
Abstract: This paper applied genetic algorithms (GAs), simulated annealing (SA) and postpone search to approximately solve reachability problems in Petri nets and to compare the performance of these methods. The discussed approaches do not determine the exact solutions, but they are not affected by the state explosion. First, it is assumed that there exists a nonnegative Parikh vector which satisfies the necessary reachability conditions. It is shown how to present GAs and SA as optimization problems. Next, random reachability problems are presented which are capable of handling the state space and the number of firing sequences which affect the hardness of problems. By using those random reachability problems, GAs performance is compared with the performance of SA or postpone search.
Keywords: Petri nets, genetic algorithms, reachability problem, simulated annealing.