'''Обобщени мрежи, ОМ (Generalized nets, GNs''') са средство за конструиране на адаптивни, гъвкави и структурирани модели на комплексни системи, в които протичат паралелни във времето процеси и са изградени от множество взаимодействащи си компоненти. Обобщените мрежи представляват значително разширение и обобщение на понятието [[мрежи на Петри]], както и на други [[разширения и модификации на мрежи на Петри]].
[[Generalized nets|'''Обобщените мрежи, ОМ (Generalized nets, GNs)''']] са средство за конструиране на адаптивни, гъвкави и структурирани модели на комплексни системи, в които протичат паралелни във времето процеси и са изградени от множество взаимодействащи си компоненти. Обобщените мрежи представляват значително разширение и обобщение на понятието [[мрежи на Петри]], както и на други [[разширения и модификации на мрежи на Петри]].
[[Image:GN-transition-mxn.png|right|thumb|25oxp|Преход от ОМ с ''m'' входни позиции и ''n'' изходни позиции]]
[[Image:GN-transition-mxn.png|right|thumb|25oxp|Преход от ОМ с ''m'' входни позиции и ''n'' изходни позиции]]
Обобщената мрежа е изградена от '''преходи (Transitions)'''. Преходът в контекста на обобщените мрежи е обект от статичната структура на мрежата, който съдържа условията за преминаването на '''ядра (Token)''' от входните в изходните му '''позиции (Places)''', след като преходът се е активирал.
Обобщената мрежа е изградена от '''преходи (transitions)'''. Преходът в контекста на обобщените мрежи е обект от статичната структура на мрежата, който съдържа условията за преминаването на '''ядра (token)''' от входните в изходните му '''позиции (places)''', след като преходът се е активирал.
От позиция или в позиция на прехода може да излиза или съответно да влиза не повече от една дъга. Позиция, от която излиза дъга се нарича входна за прехода, а позиция, в която влиза дъга се нарича изходна за прехода. Всеки преход в ОМ има поне една входна и поне една изходна позиция.
От позиция или в позиция на прехода може да излиза или съответно да влиза не повече от една дъга. Позиция, от която излиза дъга се нарича входна за прехода, а позиция, в която влиза дъга се нарича изходна за прехода. Всеки преход в ОМ има поне една входна и поне една изходна позиция.
Line 31:
Line 31:
\end{array}
\end{array}
</math>
</math>
*: where <math>r_{i,j}</math> са предикати, <math>1 \le i \le m, 1 \le j \le n</math>
*: където <math>r_{i,j}</math> са предикати, <math>1 \le i \le m, 1 \le j \le n</math>
* <math>M</math> is the index matrix of the capacities of the transition's arcs:
* <math>M</math> задава капацитетите на дъгите. Представлява индексирана матрица от вида:
*: <math> M =
*: <math> M =
\begin{array}{c|c c c c c} & l''_1 & ... & l''_j & ... & l''_n \\
\begin{array}{c|c c c c c} & l''_1 & ... & l''_j & ... & l''_n \\
Line 43:
Line 43:
\end{array}
\end{array}
</math>
</math>
*: where <math>M_{i,j} \ge 0</math> are natural numbers or <math>\infty</math>, <math>1 \le i \le m, 1 \le j \le n</math>
*: където <math>M_{i,j} \ge 0</math> са естествени числа и <math>\infty</math>, <math>1 \le i \le m, 1 \le j \le n</math>
* <math>\Box</math> is called transition's type, an object having a form similar to a Boolean expression. It may contain as variables the symbols that serve as labels for transition's input places, and it is an expression constructed of variables and the Boolean connectives <math>\land</math> and <math>\lor</math> determining the following conditions:
* <math>\Box</math> се нарича тип на прехода и представлява булев израз. Ако стойността му е “true” съответният преход може да се активира, а ако е “false” - не. В него участват идентификаторите на всички входни позиции на прехода, свързани с логическите операции "и" <math>\land</math> и "или" <math>\lor</math>:
*: <math>\land(l_{i_1}, l_{i_2},...,l_{i_u})</math> - each of the places <math>l_{i_1}, l_{i_2},...,l_{i_u}</math> must contain at least one token,
*: <math>\land(l_{i_1}, l_{i_2},...,l_{i_u})</math> - във всяка входна позиция <math>l_{i_1}, l_{i_2},...,l_{i_u}</math> трябва да има най-малко по едно ядро,
*: <math>\lor(l_{i_1}, l_{i_2},...,l_{i_u})</math> - there must be at least one token in the set of places <math>l_{i_1}, l_{i_2},...,l_{i_u}</math> where <math>\lbrace l_{i_1}, l_{i_2},...,l_{i_u} \rbrace \subset L'</math>
*: <math>\lor(l_{i_1}, l_{i_2},...,l_{i_u})</math> - най-малко в една от входните позиции <math>l_{i_1}, l_{i_2},...,l_{i_u}</math> трябва да има най-малко едно ядро.
*: When the value of a type (calculated as a Boolean expression) is ''"true"'', the transition can become active, otherwise it cannot.
== Формално описание на обобщена мрежа ==
Formally described, the generalized net is represented by the following four-tuple:
* <math>A</math> is a ''set of transitions'' (see the [[Transition#Formal description|formal definition of a transition]])
; ''1. Статична структура (Static structure)''
* <math>\pi_{A}</math> is a function giving the ''priorities of the transitions'', i.e. <math>\pi_{A} : A \rightarrow N</math> where N = {0, 1, 2, ...} ∪ {∞}
* <math>A</math> е множеството от всички преходи в мрежата''.
* <math>\pi_{L}</math> is a function giving the ''priorities of the places'', i.e. <math>\pi_{L} : L \rightarrow N</math>
* <math>\pi_{A}</math> е функция, задаваща ''приоритетите на преходите'', т.е. <math>\pi_{A} : A \rightarrow N</math> където N = {0, 1, 2, ...} ∪ {∞}.
* <math>c</math> is a function giving the ''place capacities'', i.e. <math>c : L \rightarrow N</math>
* <math>\pi_{L}</math> е функция, задаваща ''приоритетите на позициите'', т.е. <math>\pi_{L} : L \rightarrow N</math>.
* <math>f</math> is a function giving the ''truth value of the predicates''. In the basic case, it may obtain values "true" (1) and "false" (0). In [[fuzzy generalized net]]s its domain is the [0;1] interval (see [[fuzzy set]]) and in the [[intuitionistic fuzzy generalized net]]s its domain is the set [0;1]×[0;1] (see [[intuitionistic fuzzy set]]).
* <math>c</math> е функция, задаваща ''капацитетите на позициите'', т.е. <math>c : L \rightarrow N</math>.
* <math>\theta_{1}</math> is a function giving the ''next time moment'' when a given transition will be fired (will become active). Hence, <math>\theta_{1}(t) = t'</math> where <math>t, t' \in [T, T+t^*]; t \le t'</math>. The value of this function is being recalculated in the moment when the transition's active state ceases.
* <math>f</math> е функция, определяща ''вярностната стойност на предикатите''.
* <math>\theta_{2}</math> is a function giving the ''duration of the transition's active state''. Hence, <math>\theta_{2}(t) = t'</math> where <math>t, t' \in [T, T+t^*]; t' \ge 0</math>. The value of this function is calculated in the moment when the transition's active state begins.
* <math>\theta_{1}</math> задава ''следващия момент'', в който може да се активира прехода. Стойността на тази функция се преизчислява в момента, в който завършва активното състояние на прехода. Оттук <math>\theta_{1}(t) = t'</math> където <math>t, t' \in [T, T+t^*]; t \le t'</math>
* <math>\theta_{2}</math> е функция, която задава ''продължителността на активното състояние на даден преход''. Стойността й се изчислява в момента, в който се активира прехода. Оттук <math>\theta_{2}(t) = t'</math> където <math>t, t' \in [T, T+t^*]; t' \ge 0</math>.
; ''2. Динамична структура (Dynamic structure)''
* <math>K</math> е ''множество от ядрата'' в обобщената мрежа.
* <math>\pi_K</math> е функция, която задава ''приоритетите на ядрата'', т.е. <math>\pi_{K} : K \rightarrow N</math>
* <math>\theta_K</math> е функция, която задава ''момента от време, в който определено ядро може да влезе'' в ОМ, т.е. <math>\theta_K (\alpha)=t</math> където <math>\alpha \in K, t \in [T; T+t^*]</math>
; ''2. Dynamic structure''
* <math>K</math> is the ''set of tokens'' of the generalized net. In certain cases it is more convenient to denote this set as <math>K = \bigcup_{l \in Q^I} K_{l} </math> where <math>K_{l}</math> is the set of all GN tokens which are waiting to enter place <math>l</math> and <math>Q^I</math> is the set of all input places in the net.
* <math>\pi_K</math> is a function giving the ''priorities of the tokens'', i.e. <math>\pi_{K} : K \rightarrow N</math>
* <math>\theta_K</math> is a function giving the ''moment of time when a given token may enter'' the GN, i.e. <math>\theta_K (\alpha)=t</math> where <math>\alpha \in K, t \in [T; T+t^*]</math>
; ''3. Времева компонента (Time)''
* <math>T</math> е начален момент от време, в който ОМ започва функционирането си. Моментът Т се определя по фиксирана времева скала.
* <math>t^0</math> е времева стъпка на фиксирана времева скала.
* <math>t^*</math> продължителност на функционирането на ОМ.
; ''3. Time''
* <math>T</math> is the moment of time when the generalized net starts functioning. This moment is determined according to a fixed global timescale.
* <math>t^0</math> is the elementary time step of the fixed global timescale (the interval with which time increments in the timescale).
* <math>t^*</math> is the total duration of functioning of the net.
; ''4. Компонента памет (Memory)''
* <math>X</math> е ''множество на началните характеристики'', с които ядрата влизат в мрежата.
* <math>\Phi</math> е ''характеристична функция''. Тя определя новата характеристика на ядрото при преместването му от входната позиция на даден преход в изходната.
* <math>b</math> е функция, задаваща ''максималния брой характеристики'', които едно ядро може да получи по време на движението си в ОМ, т.e. <math>b : K \rightarrow N</math>.
; ''4. Memory''
== Литература ==
* <math>X</math> is the ''set of initial characteristics'', which tokens may exhibit when they enter the net for first.
* <math>\Phi</math> is a ''characteristic function'', which assigns a new characteristic to each token when it makes the transfer from an input to an output place of a given transition.
* <math>b</math> is a function giving the ''maximal number of characteristics'', which a given token may obtain during its movement throughout the net, i.e. <math>b : K \rightarrow N</math>. In general, <math>b</math> may possess four different values: 0, 1, <math>s</math> or <math>\infty</math> meaning that the token keeps, respectively: none of its characteristics, its last characteristic, its last <math>s</math> characteristics, or all of its characteristics obtained during its movement in the net.
Latest revision as of 15:03, 21 August 2011
Изследване на възможностите за използване на Data Mining за управление на процеси в електронен университет
Обобщените мрежи, ОМ (Generalized nets, GNs) са средство за конструиране на адаптивни, гъвкави и структурирани модели на комплексни системи, в които протичат паралелни във времето процеси и са изградени от множество взаимодействащи си компоненти. Обобщените мрежи представляват значително разширение и обобщение на понятието мрежи на Петри, както и на други разширения и модификации на мрежи на Петри.
Преход от ОМ с m входни позиции и n изходни позиции
Обобщената мрежа е изградена от преходи (transitions). Преходът в контекста на обобщените мрежи е обект от статичната структура на мрежата, който съдържа условията за преминаването на ядра (token) от входните в изходните му позиции (places), след като преходът се е активирал.
От позиция или в позиция на прехода може да излиза или съответно да влиза не повече от една дъга. Позиция, от която излиза дъга се нарича входна за прехода, а позиция, в която влиза дъга се нарича изходна за прехода. Всеки преход в ОМ има поне една входна и поне една изходна позиция.
Входна позиция, в която не влиза дъга се нарича вход на мрежата, а изходна позиция, от която не излиза дъга – изход на мрежата. В позициите може да има ядра. Те се преместват от входните към съответните изходни позиции на преходите. Когато настъпи определения за прехода момент от време, и във входните позиции има достатъчен брой ядра, то ядрата от входните позиции придобиват възможност да се придвижат до изходните позиции. Този процес се нарича активиране на прехода. В началото ядрата, които постъпват в мрежата през входните й позиции имат т.нар. начални характеристики. При всяко преминаване през преход в мрежата те получават нови характеристики и така всяко ядро в мрежата е уникално и има своя история. Всяка позиция има свой капацитет.
Формално описание на преход
Преходът Z в ОМ се представя като наредена последователност от седем компоненти:
[math]\displaystyle{ Z = \langle L', L'', t_1, t_2, r, M, \Box \rangle }[/math]
където:
[math]\displaystyle{ L' }[/math] са крайно непразно множество от входните позиции на прехода.
[math]\displaystyle{ L'' }[/math] са крайно непразно множество от изходните позиции на прехода.
[math]\displaystyle{ t_1 }[/math] е момент време на активиране на прехода.
[math]\displaystyle{ t_2 }[/math] задава продължителността на активното състояние на прехода.
[math]\displaystyle{ r }[/math] е условие на прехода. Представлява индексирана матрица от вида:
където [math]\displaystyle{ M_{i,j} \ge 0 }[/math] са естествени числа и [math]\displaystyle{ \infty }[/math], [math]\displaystyle{ 1 \le i \le m, 1 \le j \le n }[/math]
[math]\displaystyle{ \Box }[/math] се нарича тип на прехода и представлява булев израз. Ако стойността му е “true” съответният преход може да се активира, а ако е “false” - не. В него участват идентификаторите на всички входни позиции на прехода, свързани с логическите операции "и" [math]\displaystyle{ \land }[/math] и "или" [math]\displaystyle{ \lor }[/math]:
[math]\displaystyle{ \land(l_{i_1}, l_{i_2},...,l_{i_u}) }[/math] - във всяка входна позиция [math]\displaystyle{ l_{i_1}, l_{i_2},...,l_{i_u} }[/math] трябва да има най-малко по едно ядро,
[math]\displaystyle{ \lor(l_{i_1}, l_{i_2},...,l_{i_u}) }[/math] - най-малко в една от входните позиции [math]\displaystyle{ l_{i_1}, l_{i_2},...,l_{i_u} }[/math] трябва да има най-малко едно ядро.
[math]\displaystyle{ A }[/math] е множеството от всички преходи в мрежата.
[math]\displaystyle{ \pi_{A} }[/math] е функция, задаваща приоритетите на преходите, т.е. [math]\displaystyle{ \pi_{A} : A \rightarrow N }[/math] където N = {0, 1, 2, ...} ∪ {∞}.
[math]\displaystyle{ \pi_{L} }[/math] е функция, задаваща приоритетите на позициите, т.е. [math]\displaystyle{ \pi_{L} : L \rightarrow N }[/math].
[math]\displaystyle{ c }[/math] е функция, задаваща капацитетите на позициите, т.е. [math]\displaystyle{ c : L \rightarrow N }[/math].
[math]\displaystyle{ f }[/math] е функция, определяща вярностната стойност на предикатите.
[math]\displaystyle{ \theta_{1} }[/math] задава следващия момент, в който може да се активира прехода. Стойността на тази функция се преизчислява в момента, в който завършва активното състояние на прехода. Оттук [math]\displaystyle{ \theta_{1}(t) = t' }[/math] където [math]\displaystyle{ t, t' \in [T, T+t^*]; t \le t' }[/math]
[math]\displaystyle{ \theta_{2} }[/math] е функция, която задава продължителността на активното състояние на даден преход. Стойността й се изчислява в момента, в който се активира прехода. Оттук [math]\displaystyle{ \theta_{2}(t) = t' }[/math] където [math]\displaystyle{ t, t' \in [T, T+t^*]; t' \ge 0 }[/math].
2. Динамична структура (Dynamic structure)
[math]\displaystyle{ K }[/math] е множество от ядрата в обобщената мрежа.
[math]\displaystyle{ \pi_K }[/math] е функция, която задава приоритетите на ядрата, т.е. [math]\displaystyle{ \pi_{K} : K \rightarrow N }[/math]
[math]\displaystyle{ \theta_K }[/math] е функция, която задава момента от време, в който определено ядро може да влезе в ОМ, т.е. [math]\displaystyle{ \theta_K (\alpha)=t }[/math] където [math]\displaystyle{ \alpha \in K, t \in [T; T+t^*] }[/math]
3. Времева компонента (Time)
[math]\displaystyle{ T }[/math] е начален момент от време, в който ОМ започва функционирането си. Моментът Т се определя по фиксирана времева скала.
[math]\displaystyle{ t^0 }[/math] е времева стъпка на фиксирана времева скала.
[math]\displaystyle{ t^* }[/math] продължителност на функционирането на ОМ.
4. Компонента памет (Memory)
[math]\displaystyle{ X }[/math] е множество на началните характеристики, с които ядрата влизат в мрежата.
[math]\displaystyle{ \Phi }[/math] е характеристична функция. Тя определя новата характеристика на ядрото при преместването му от входната позиция на даден преход в изходната.
[math]\displaystyle{ b }[/math] е функция, задаваща максималния брой характеристики, които едно ядро може да получи по време на движението си в ОМ, т.e. [math]\displaystyle{ b : K \rightarrow N }[/math].
