'''Обобщени мрежи, ОМ (Generalized nets, GNs''' са средство за конструиране на адаптивни, гъвкави и структурирани модели на комплексни системи, в които протичат паралелни във времето процеси и са изградени от множество взаимодействащи си компоненти. Обобщените мрежи представляват значително разширение и обобщение на понятието [[мрежи на Петри]], както и на други [[разширения и модификации на мрежи на Петри]].
[[Generalized nets|'''Обобщените мрежи, ОМ (Generalized nets, GNs)''']] са средство за конструиране на адаптивни, гъвкави и структурирани модели на комплексни системи, в които протичат паралелни във времето процеси и са изградени от множество взаимодействащи си компоненти. Обобщените мрежи представляват значително разширение и обобщение на понятието [[мрежи на Петри]], както и на други [[разширения и модификации на мрежи на Петри]].
== Components of a generalized net ==
[[Image:GN-transition-mxn.png|right|thumb|25oxp|Преход от ОМ с ''m'' входни позиции и ''n'' изходни позиции]]
[[Image:GN-transition-mxn.png|right|thumb|25oxp|A GN transition with ''m'' inputs and ''n'' outputs]]
A generalized net consists of:
Обобщената мрежа е изградена от '''преходи (transitions)'''. Преходът в контекста на обобщените мрежи е обект от статичната структура на мрежата, който съдържа условията за преминаването на '''ядра (token)''' от входните в изходните му '''позиции (places)''', след като преходът се е активирал.
* a static structure,
* a dynamic structure,
От позиция или в позиция на прехода може да излиза или съответно да влиза не повече от една дъга. Позиция, от която излиза дъга се нарича входна за прехода, а позиция, в която влиза дъга се нарича изходна за прехода. Всеки преход в ОМ има поне една входна и поне една изходна позиция.
* temporal components.
Входна позиция, в която не влиза дъга се нарича вход на мрежата, а изходна позиция, от която не излиза дъга – изход на мрежата. В позициите може да има ядра. Те се преместват от входните към съответните изходни позиции на преходите. Когато настъпи определения за прехода момент от време, и във входните позиции има достатъчен брой ядра, то ядрата от входните позиции придобиват възможност да се придвижат до изходните позиции. Този процес се нарича активиране на прехода. В началото ядрата, които постъпват в мрежата през входните й позиции имат т.нар. начални характеристики. При всяко преминаване през преход в мрежата те получават нови характеристики и така всяко ядро в мрежата е уникално и има своя история. Всяка позиция има свой капацитет.
The '''''static structure''''' consists of objects called ''[[transition]]s'', which have input and output ''[[place]]s''. Two transitions can share a place, but every place can be an input of at most one transition and can be an output of at most one transition.
== Формално описание на преход ==
The '''''dynamic structure''''' consists of ''[[token]]s'', which act as information carriers and can occupy a single place at every moment of the GN execution. The tokens pass through the transition from one input to another output place; such an ordered pair of places is called ''[[transition arc]]''. The tokens' movement is governed by conditions (''predicates''), contained in the [[predicate matrix]] of the transition.
Преходът Z в ОМ се представя като наредена последователност от седем компоненти:
The information carried by a token is contained in its [[token characteristics|characteristics]], which can be viewed as an associative array of characteristic names and values. The values of the token characteristics change in time according to specific rules, called ''[[characteristic function]]s''. Every place possesses at most one characteristic function, which assigns new characteristics to the incoming tokens. Apart from movement in the net and change of the characteristics, tokens can also split and merge in the places.
The '''''temporal components''''' describe the time scale of GN execution. ''Temporal conditions'' control the transitions' moments of activation and duration of active state. Various other tools for fine tuning of the GN functioning are provided in the form of ''priorities'' of separate transitions, places and tokens, as well as ''capacities'' of places and transitions arcs.
където:
* <math>L'</math> са крайно непразно множество от входните позиции на прехода.
* <math>L''</math> са крайно непразно множество от изходните позиции на прехода.
* <math>t_1</math> е момент време на активиране на прехода.
* <math>t_2</math> задава продължителността на активното състояние на прехода.
* <math>r</math> е условие на прехода. Представлява индексирана матрица от вида:
*: <math> r =
\begin{array}{c|c c c c c} & l''_1 & ... & l''_j & ... & l''_n \\
\hline
l'_1 & & & & & \\
... & & & & & \\
l'_i & & & r_{i,j} & & \\
... & & & & & \\
l'_m & & & & & \\
\end{array}
</math>
*: където <math>r_{i,j}</math> са предикати, <math>1 \le i \le m, 1 \le j \le n</math>
* <math>M</math> задава капацитетите на дъгите. Представлява индексирана матрица от вида:
*: <math> M =
\begin{array}{c|c c c c c} & l''_1 & ... & l''_j & ... & l''_n \\
\hline
l'_1 & & & & & \\
... & & & & & \\
l'_i & & & M_{i,j} & & \\
... & & & & & \\
l'_m & & & & & \\
\end{array}
</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> се нарича тип на прехода и представлява булев израз. Ако стойността му е “true” съответният преход може да се активира, а ако е “false” - не. В него участват идентификаторите на всички входни позиции на прехода, свързани с логическите операции "и" <math>\land</math> и "или" <math>\lor</math>:
*: <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> - най-малко в една от входните позиции <math>l_{i_1}, l_{i_2},...,l_{i_u}</math> трябва да има най-малко едно ядро.
=== Graphic representation ===
== Формално описание на обобщена мрежа ==
== Formal description ==
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 14: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].
