A genetic algorithm for decision problems stated on discrete event systems
-
1
Universidad Pública de Navarra
info
-
2
Universidad de La Rioja
info
ISBN: 978-076954016-0
Any de publicació: 2010
Volum: 5481000
Pàgines: 86-91
Tipus: Capítol de llibre
Resum
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.