×

Constructing Petri net models using genetic search. (English) Zbl 0995.68508

Summary: The problem considered is that of constructing a Petri net model of a particular device, process, or system described by observations of its interactions with its environment. The algorithm proposed for achieving a solution employs the principles of genetic search. Also presented is a detailed investigation of its operation, thereby affording a theoretical justification of its design.
The expressive and representational power of Petri nets renders them ideally suited to the modelling of many complex event systems. As a modelling language, they directly support the intrinsically difficult concepts of concurrent and parallel activities, synchronization of events, and the distribution of various resources. However, the development of a model of a significant system is laborious, and circumstances of limited knowledge of the system’s internal structure compound the difficulty.
By composing the perceived stimuli and responses of the system under study as a set of behavioural requirements, the Petri net construction problem can be examined. The inherently difficult nature of this problem renders most other approaches inapplicable or inadequate; the quest for a satisfactory solution leads instead to the development of an algorithm employing genetic search technology.
Built around a genetics-based machine learning architecture, the first algorithm developed shows a deficiency in its dependence on the particular order in which various options are explored. Alleviating this difficulty through a simple modification may also hold a lesson for other classifier systems.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cao, T.; Sanderson, A. C., Task sequence planning using fuzzy Petri Nets, (Proceedings of the Command and Control Research Symposium, JDL Basic Research Group, National Defence University (1991))
[2] Chiola, G., A software package for the analysis of generalized SPN models, (Proceedings of the International Workshop on Timed Petri Nets, IEECS Press. Proceedings of the International Workshop on Timed Petri Nets, IEECS Press, Torino, Italy (1985))
[3] Peterson, H. L., Petri Net Theory and the Modelling of Systems (1981), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0461.68059
[4] Chiola, G.; Franceschinis, R.; Gaeta, R.; Ribaudo, M., GreatSPN 1.7: A graphical editor and analyzer for timed and stochastic Petri Nets, Performance Evaluation, 24 (1995) · Zbl 0875.68663
[5] Genrich, H. J.; Lautendach, K., System modelling with high-level Petri Nets, Theoretical Computer Science, Volume 13 (1981) · Zbl 0454.68052
[6] Der Jeng, M.; DiCesare, F., A review of synthesis techniques for Petri Nets with applications to automated manufacturing systems, IEEE Transactions on Systems, Manm, and Cybernetics, 23, 1 (1993) · Zbl 0775.93171
[7] Jensen, K., Coloured Petri Nets: A High-Level Language for System Design and Analysis, (Lecture Notes in Computer Science (1990), Springer-Verlag: Springer-Verlag Berlin)
[8] Lindemann, C., DSPNexpress; A software package for the efficient solution of deterministic and stochastic Petri Nets, Performance Evaluation, 22 (1995)
[9] Lu, Z.; Levis, A. H., A coloured Petri Net model of distributed tactical decision making, (Proceedings of the Command and Control Research Symposium, JDL, Basic Research Group, National Defence University (1991))
[10] Peterson, H. L., Petri Net Theory and the Modelling of Systems (1981), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0461.68059
[11] Peterson, J., Petri Nets, Computing Surveys, 9, 3 (1977) · Zbl 0357.68067
[12] Reutenaur, C., The Mathematics of Petri Nets (1990), Masson and Prentice-Hall International
[13] Valavanis, K. P., On the hierarchical modelling analysis and simulation of flexible manufacturing systems with extended Petri Nets, IEEE Transactions on Systems, Man and Cybernetics, 20, 1 (1990)
[14] Arnone, S.; Dell’Orto, M., Toward a fuzzy government of genetic populations, (International Conference on Tools with Artificial Intelligence (1994))
[15] Bach, T.; Hoffmeister, F., Extended selection mechanisms in genetic algorithms, (Proceedings of the Fourth International Conference on Genetic Algorithms (1991))
[16] Deb, K.; Horn, J.; Goldberg, D., Multimodal deceptive functions, Complex Systems, 7 (1993) · Zbl 0814.90103
[17] Jensen, K., Coloured Petri Nets: A High-Level Language for System Design and Analysis, (Lecture Notes in Computer Science (1990), Springer-Verlag: Springer-Verlag Berlin)
[18] De Jong, K., Learning with genetic algorithms: An overview, Machine Learning, 3 (1988)
[19] Goldberg, D., Genetic Algorithms in Search, Optimization, and Machine Learning (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0721.68056
[20] Holland, J. H., Escaping brittleness: The possibilities of general-purpose learning algorithms applies to parallel rule-based systems, Machine Learning: An Artificial Intelligence Approach, 2 (1986)
[21] Maini, H.; Mehrotra, K.; Mohan, C.; Sanjay, R., Knowledge-based nonuniform crossover, Complex Systems, 8 (1994) · Zbl 0828.68112
[22] Potts, J. C.; Giddens, T. D.; Yadav, S. B., The development and evaluation of an improved genetic algorithm based on migration and artificial selection, IEEE Transactions on Systems, Man, and Cybernetics, 24, 1 (1994)
[23] Reid, D. J., Genetic algorithms in constrained optimization, Mathematical and Computer Modelling, 23, 5, 87-112 (1996) · Zbl 0852.90118
[24] D.J. Reid, Enhanced genetic operators for the resolution of discrete optimization problems, Computers and Operations Reserach; D.J. Reid, Enhanced genetic operators for the resolution of discrete optimization problems, Computers and Operations Reserach
[25] Shang, Y.; Li, G., New crossover operators in genetic algorithms, (Proceedings of the 1991 IEEE International Conference on Tools for Artificial Intelligence. Proceedings of the 1991 IEEE International Conference on Tools for Artificial Intelligence, San Jose, CA (1991))
[26] Siedlecki, W.; Sklanski, J., Constrained genetic optimization via dynamics reward-penalty balancing and its use in pattern recognition, (Proceedings of the Third International Conference on Genetic Algorithms (1989))
[27] Whitley, D., The genitor algorithm and selection pressure: Why rank-based allocation of reproductive trials is best, (Proceedings of the Third International Conference on Genetic Algorithms (1989))
[28] B.B. Chai, T. Huang, X. Zhuang, Y. Zhao and J. Sklansky, Piecewise linear classifiers using binary tree structure and genetic algorithm, Pattern Recognition29; B.B. Chai, T. Huang, X. Zhuang, Y. Zhao and J. Sklansky, Piecewise linear classifiers using binary tree structure and genetic algorithm, Pattern Recognition29
[29] Dorigo, M.; Schnepf, U., Genetics-based machine learning and behaviour-based robotics: A new synthesis, IEEE Transactions on Systems, Man, and Cybernetics, 23, 1 (1993)
[30] Ho, T. K.; Hull, J. J.; Srihari, S. N., Decision combination in multiple classifier systems, IEEE Transactions on Pattern Analysis and Machine Intelligence, 16, 1 (1994)
[31] Nakaoka, K.; Furuhashi, T.; Uchikawa, Y., A study on apportionment of credits of fuzzy classifier system for knowledge acquisition of large scale systems, (Proceedings of the Third IEEE International Conference on Fuzzy Systems (1994))
[32] Oliver, J., Finding decision rules with genetic algorithms, (AI Expert (March 1994))
[33] Terano, T.; Muro, Z., On-the-fly knowledge base refinement by a classifier system, AI Communications, 7, 2 (1994)
[34] Wah, B. W., Population-based learning: A method for learning from examples under resource constraints, IEEE Transactions on Knowledge and Data Engineering, 4, 5 (1992)
[35] Yuang, Y.; Huang, H. A., A genetic algorithm for generating fuzzy classification rules, Fuzzy Sets and Systems, 84 (1996 Sets and Systems)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.