Cellular Adaptive Petri Net Based on Learning Automata and Its Application to Vertex Coloring Problem

چکیده مقاله

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.