Minimum Initial Marking Estimation in Labeled Petri Nets through Genetic Algorithm and Tabu Search

This paper develops estimation algorithms to compute minimal initial markings, following the observation of sequences of labels produced by a labeled Petri net. We focus on the running time. For that purpose, we investigate meta-heuristic based method and demonstrate that such methods have the potential to solve efficiently the problem. Genetic algorithm is suitable to compute a large number of random sequences. Then, the Tabu search algorithm is used to find the minimum initial marking of the different random sequences in a labeled Petri net (LPN).