A genetic algorithm for decision problems stated on discrete event systems

Resumen

Petri nets (PN) paradigm is broadly used to model discrete event systems (DES). Thanks to both, its graphical and algebraic representations, PN provide a powerful and uniform tool, with an important theoretical support for modelling and formal analysis. On the other hand, genetic algorithms constitute a metaheuristics able to cope with complex problems of combinatorial optimisation. The use of genetic algorithms to solve optimisation problems based on PN models is a classical research line; nevertheless, it has been applied mainly to decision support systems related only to the operation of DES. In this paper a general statement of decision problems is proposed, including not only the operation but also the design process of the DES. This leads to a set of undefined parameters, classified according to their role in the PN model. Moreover, under certain circumstances, the PN model can appear as a disjunctive constraint. Alternatives aggregation PN are presented as a natural formalism to afford the transformation of the disjunctive constraint and to define a single solution space that allows genetic algorithms to perform a very efficient search of the best solution in a single process. A case-study is presented exhaustively, where the proposed methodology outperforms more classical approaches. © 2010 IEEE.