Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Cellular adaptive Petri net based on learning automata and its application to the vertex coloring problem

  • Published:
Discrete Event Dynamic Systems Aims and scope Submit manuscript

Abstract

In a Petri net, a decision point is raised when two or more transitions are simultaneously enabled in a given marking. The decision to be made at such a point is the selection of an enabled transition for firing. Decision making in Petri nets is accomplished by a so called controlling mechanism. Whenever a Petri net is used to represent an algorithm, the application of a different controlling mechanism results in a different instance of that algorithm. Recently, an adaptive controlling mechanism has been introduced for Petri nets in which several learning automata are used as decision makers during the evolution of the Petri nets. A Petri net with this adaptive controlling mechanism is referred to as APN-LA. Using APN-LA, one may be able to design adaptive algorithms to solve problems. There are problems for which designing a single APN-LA is tedious and results in a large and complex model. One class of such problems is the cellular problem, in which an identical algorithm must be executed in each cell and the solution to the problem is generated from the cooperation of these identical algorithms. To avoid having large and complex APN-LAs for cellular problems, a cellular adaptive Petri net called CAPN-LA is proposed in this paper, which consists of a cellular structure and a number of identical APN-LAs. In CAPN-LA, each APN-LA represents the algorithm which must be executed in each cell, and the required cooperation between the neighboring cells is handled by means of cooperation between the APN-LAs in those cells. The notation of expediency for this model is defined, and, using the steady-state analysis of the behavior of the CAPN-LA model, conditions under which this model is expedient are stated. A measure of expediency is defined for comparing different CAPN-LAs according to their expected reward; a CAPN-LA which receives a higher expected reward is regarded as more expedient. The proposed CAPN-LA is then used to design different algorithms for the classic problem of vertex coloring. The measure of expediency is calculated for these algorithms and results of using them for coloring vertices of different graphs are also included.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Notes

  1. The notation a ≫ b means that a is much greater than b.

  2. More details on the firing rules of the APN-LA are given in (Vahidipour et al. 2015).

References

  • Akbari Torkestani J (2009) Channel assignment and multicast routing in mobile ad hoc networks based on learning automata, PhD dissertation, Dep. of Eng., Univ. Islamic Azad, Iran

  • Akbari Torkestani J (2013) A new approach to the vertex coloring problem. Cybern Syst 44(5):444–466

    Article  MATH  Google Scholar 

  • Akbari Torkestani J, Meybodi MR (2009) "Graph coloring problem based on learning automata", Proceedings of International Conference on Information Management and Engineering, Kuala-Lumpur, Malaysia, pp. 718–722

  • Akbari Torkestani J, Meybodi MR (2010) A new vertex coloring algorithm based on variable action-set learning automata. Journal of Computing and Informatics 29(3):1001–1020

    MathSciNet  MATH  Google Scholar 

  • Akbari Torkestani J, Meybodi MR (2011) A cellular learning automata based algorithm for solving the vertex coloring problem. Expert Syst Appl 38(8):9237–9247

    Article  Google Scholar 

  • Asmuni H, Burke EK, Garibaldi JM, McCollum B, Parkes AJ (2009) An investigation of fuzzy multiple heuristic orderings in the construction of University examination timetables. Comput Oper Res 36:981–1001

    Article  MATH  Google Scholar 

  • Barnier N, Brisset P (2002) Graph coloring for air traffic flow management. Proceedings of the Fourth International Workshop on Integration of AI and OR Techniques, Le Croisic, France:133–147

  • Bause F (1996) On the analysis of Petri net with static priorities. Acta Informatica 33:669–685

    Article  MathSciNet  MATH  Google Scholar 

  • Bause F (1997) Analysis of Petri nets with a dynamic priority method. Application and Theory of Petri Nets 1248:215–234

  • Beigy H, Meybodi MR (2006) Utilizing distributed learning automata to solve stochastic shortest path problem. International Journal of Uncertainty, Fuzziness and Knowledge- based Systems 14(5):591–617

    Article  MathSciNet  MATH  Google Scholar 

  • Billard EA (1996) Stability of adaptive search in multi-level games under delayed information. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans 26:231–240

    Article  Google Scholar 

  • Billard EA (1997) "Chaotic behavior of learning automata in multi-level games under DelayedInformation", Proc. of IEEE Intl. Conf. on Systems, Man, and Cybernetics, pp. 1412–1417

  • Burkhard HD (1981) Ordered firing in Petri nets. EIK (Journal of information processing and cybernetics) 17(2/3):71–86

    MathSciNet  MATH  Google Scholar 

  • Carter M, Laporte G, Lee S (1996) Examination timetabling: algorithmic strategies and applications. J Oper Res Soc 47:373–383

    Article  Google Scholar 

  • Chiola G, Ferscha A (1993) Distributed simulation of Petri nets. IEEE Concurr 3:33–50

    Google Scholar 

  • Ding Z, Zhou Y, Zhou M (2016) Modeling self-adaptive software systems with learning Petri nets. IEEE Transactions on Systems, Man, and Cybernetics: Systems 46(4):483–498

    Article  Google Scholar 

  • Enami Eraghi A, Akbari Torkestani J, Meybodi MR (2009) "Cellular learning automata-based graph coloring problem", Proceedings of 2009 International Conference on Machine Learning and Computing. Perth, Australia, pp 163–167

    Google Scholar 

  • Enayatzare M, Meybodi MR (March, 2009) "Solving graph coloring problem using cellular learning automata", Proceedings of 14th Annual CSI Computer Conference of Iran. Amirkabir University of Technology, Tehran, Iran

    Google Scholar 

  • Esnaashari M, Meybodi MR (2015) Irregular cellular learning automata. IEEE Transactions on Cybernetics 45(8):1622–1632

    Article  Google Scholar 

  • Fujimoto RM (2001) Parallel simulation: parallel and distributed simulation systems. In: Proceedings of the 33nd conference on winter simulation, IEEE Computer Society, pp. 147–157

  • Gao M, Zhou M, Huang X, Wu Z (2003) Fuzzy reasoning Petri nets. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans 33(3):314–324 May 2003

    Article  Google Scholar 

  • Ghavipour M, Meybodi MR (2016) An adaptive fuzzy recommender system based on learning automata. Electron Commer Res Appl 20:105–115

    Article  Google Scholar 

  • Golzari Sh, Meybodi MR (2002) "A parallel graph coloring algorithm for two dimensional cellular automata", Proceedings of Tenth Conference on Electrical Engineering, University of Tabriz, vol. 1, pp. 288–299, May 2002

  • Hashemi B, Meybodi MR (2009) Cellular Pso: a Pso for dynamic environments In: Advances in Computation and Intelligence, Lecture Notes in Computer Science, vol. 5821/2009, pp. 422–433

  • Holloway LE, Krogh BH (1994) Controlled Petri nets: a tutorial survey. In: The 11th international conference on analysis and optimization of systems discrete event systems. Springer, Berlin Heidelberg, pp 158–168

    Chapter  Google Scholar 

  • Jensen TR, Toft B (1994) Graph coloring problems. Wiley, USA

    Book  MATH  Google Scholar 

  • Karp RM (1972) Reducibility among combinatorial problems. Complexity of Computer Computations, Plenum Press, USA:85–103

  • Lewis R, Paechter B (2007) Finding feasible timetables using group based operators. IEEE Trans Evol Comput 11(3):397–413

    Article  Google Scholar 

  • Linial N (1992) Locality in distributed graph algorithms. SIAM J Comput 21(1):193–201

    Article  MathSciNet  MATH  Google Scholar 

  • Mabrouk BB, Hasni H, Mahjoub Z (2009) On a parallel genetic-tabu search based algorithm for solving the graph coloring problem. Eur J Oper Res 197:1192–1201

    Article  MATH  Google Scholar 

  • Malaguti E, Toth P (2008) An evolutionary approach for bandwidth multi-coloring problems. Eur J Oper Res 189:638–651

    Article  MATH  Google Scholar 

  • Meybodi MR, Beigy H, Taherkhani M (2003) Cellular learning automata and its applications. Sharif Journal of Science and Technology 19(25):54–77

    Google Scholar 

  • Mollakhalili Meybodi MR, Meybodi MR (2014) "Extended distributed learning automata: an automata-based framework for solving stochastic graph optimization problems", Appl Intell, vol. 41, vo. 3, pp. 923–940

  • Murata T (1989) "Petri nets: properties, analysis and applications", Proc IEEE, vo1.77, pp. 541–580

  • Narendra KS, Thathachar MAL (1989) Learning automata: an introduction. Prentice-Hall, Inc., Englewood cliffs, New Jersey, USA

  • Peterson JL (1981) Petri net theory and the modeling of systems. Prentice-Hall, Inc., Upper Saddle River, New Jersey, USA

  • Rastegar R, Arasteh AR, Harriri A, and Meybodi MR (2004) A fuzzy clustering algorithm using cellular learning automata based evolutionary algorithm. In: Proc. of the Fourth Intl. Conf. on Hybrid Intelligent Systems (HIS04), Japan, Kitakyushu, pp. 310–314

  • Reisig W (2013a) Understanding Petri Nets: modeling techniques, Analysis methods, case studies, Springer Science & Business. Springer Publishing Company, Springer-Verlag Berlin Heidelberg

  • Reisig W (2013b) The synthesis problem. In: Jensen K, van der Aalst WMP, Balbo G, Koutny M, Wolf K (eds) Transactions on Petri nets and other models of concurrency VII. Springer, Berlin Heidelberg, pp 300–313

    Chapter  Google Scholar 

  • Rezvanian A, Meybodi MR (2016) Stochastic graph as a model for social networks. Comput Hum Behav 64:621–640

    Article  Google Scholar 

  • Talavan PM, Yanez J (2008) The graph coloring problem: a neuronal network approach. Eur J Oper Res 191:100–111

    Article  MathSciNet  MATH  Google Scholar 

  • Terán-Villanueva JD et al (2013) Cellular processing algorithms. In: Soft computing applications in optimization, control, and recognition. Springer, Berlin Heidelberg, pp 53–74

    Chapter  Google Scholar 

  • Thathachar MAL, Satstry PS (1997) A hierarchical system of learning automata that can learn the globally optimal path. Inf Sci 42(2):743–166

    MathSciNet  Google Scholar 

  • Thathacher MA, Harita BR (1987) Learning automata with changing number of actions. IEEE Transactions on Systems, Man and Cybernetics 17(6):1095–1100

    Article  Google Scholar 

  • Vafashoar R, Meybodi MR, and Momeni AH (2012) "CLA-DE: a hybrid model based on cellular learning automata for numerical optimization", Journal of Applied Intelligence, Springer Verlag, vol. 36, no. 3, pp. 735–748

  • Vahidipour SM, Meybodi MR (2013) "Adaptation in priority Petri net using learning automata".In: Proceedings of 11th Iranian Conference on Intelligent Systems, Kharazmi University, Tehran, Iran, February 27–28

  • Vahidipour SM, Meybodi MR, Esnaashari M (2015) Learning automata based adaptive Petri net and its application to priority assignment in queuing systems with unknown parameters. IEEE Transactions on Systems, Man, and Cybernetics 45(10):1373–1384

    Article  Google Scholar 

  • Williams RJ (1988) Toward a theory of reinforcement learning connectionist systems, Technical Report, Nu-ccs-88-3. Northeastern University, Boston

    Google Scholar 

  • Zhang J, Wang C, Zhou MC (2014) Last-position elimination-based learning automata. Cybernetics, IEEE Transactions 44(12):2484–2492 Dec. 2014

    Article  Google Scholar 

  • Zhang J, Wang C, Zhou M (2015) Fast and epsilon-optimal discretized pursuit learning automata. IEEE transactions on cybernetics 45(10):2089–2099

    Article  Google Scholar 

  • Zhang J, Wang C, Zang D, Zhou M (2016) Incorporation of optimal computing budget allocation for ordinal optimization into learning automata. IEEE Trans Autom Sci Eng 13(2):1008–1017

    Article  Google Scholar 

  • Zhou MC, Venkatesh K (1998) Modeling, simulation and control of flexible manufacturing systems: a Petri net approach. World Scientific, Singapore

  • Zymolka AM, Koster CA, Wessaly R (2003) “Transparent optical network design with sparse wavelength conversion”, Proceedings of the 7th IFIP Working Conference on Optical Network Design a nd Modelling. Budapest, Hungary, pp 61–80

    Google Scholar 

Download references

Acknowledgment

This research was in part supported by a grant from IPM. (No. CS1396-4-21).

Author information

Authors and Affiliations

  1. Faculty of Electrical and Computer Engineering, Department of Computer, University of Kashan, Kashan, Iran

    S. Mehdi Vahidipour

  2. School of Computer Science, Institute for Research in Fundamental Sciences (IPM), P.o.Box 19395-5746, Tehran, Iran

    S. Mehdi Vahidipour

  3. Computer Engineering and Information Technology Department, Amirkabir University of Technology, Tehran, Iran

    Mohammad Reza Meybodi

  4. Computer Engineering Department, K. N. Toosi University of Technology, Tehran, Iran

    Mehdi Esnaashari

Authors
  1. S. Mehdi Vahidipour
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mohammad Reza Meybodi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mehdi Esnaashari
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to S. Mehdi Vahidipour.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Vahidipour, S.M., Meybodi, M.R. & Esnaashari, M. Cellular adaptive Petri net based on learning automata and its application to the vertex coloring problem. Discrete Event Dyn Syst 27, 609–640 (2017). https://doi.org/10.1007/s10626-017-0251-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10626-017-0251-z

Keywords

Search

Navigation