A Genetic Algorithm Approach to Minimum Initial Marking Problems of Petri Nets
A Genetic Algorithm Approach to Minimum Initial Marking Problems of Petri Nets Koji Hachiman, Non-member (University of Okinawa), Morikazu Nakamura, Member, Shiro Tamaki, Non-member (University of the Ryukyus), Kenji Onaga, Non-member (Digital Society Research Centre) In this paper, we considered the minimum initial marking problems of Petri nets. Petri nets have been widely recognized as the best mathematical tool for modeling and analyzing concurrent systems. However, the performance analysis is restricted by the potential state space explosion. Many papers have proposed approximation algorithms for Petri nets analysis. However, a few paper reported application of genetic algorithm to Petri net analysis. The minimum initial marking problem is one of the important problems for Petri net analysis. We proposed a new solution based on a Genetic algorithm with heuristic rearrangement of strings to solve approximately the problem. Effectiveness of the proposed method was shown by experimental evaluation and we found that the proposed method can obtain better solution with higher probability than AMIM for many cases.