Token-baserad repris

Tokenbaserad replay- teknik är en algoritm för överensstämmelsekontroll som kontrollerar hur väl en process överensstämmer med sin modell genom att spela upp varje spår på modellen (i Petrinet-notation) . Med hjälp av de fyra räknarna producerade tokens, förbrukade tokens, saknade tokens och återstående tokens, registrerar den situationer där en övergång tvingas avfyras och de återstående polletterna efter att omspelningen är slut. Baserat på räkningen vid varje räknare kan vi beräkna fitnessvärdet mellan spåret och modellen.

Algoritmen

Token-replay-tekniken använder fyra räknare för att hålla reda på ett spår under omspelningen:

$p$ : Producerade tokens
$c$ : Förbrukade tokens
$m$ : Saknade tokens (konsumeras när de inte är där)
$r$ : Återstående tokens (producerade men inte konsumerade)

Invarianter:

När som helst: $p+m\geq c\geq m$
I slutet: $r=p+mc$

I början produceras en token för källplatsen (p = 1) och i slutet konsumeras en token från sinkplatsen (c' = c + 1). När reprisen slutar kan fitnessvärdet beräknas enligt följande:

{\frac {1}{2}}(1-{\frac {m}{c}})+{\frac {1 }{2}}(1-{\frac {r}{p}})

Exempel

Anta att det finns en processmodell i Petri net -notation enligt följande:

En processmodell M med aktiviteterna a, b, c, d

Exempel 1: Spela om spåret ( $a, b, c, d$ ) på modellen M

Steg 1: En token initieras. Det finns en producerad token ( $p=1$ ).

Steg 2: Aktiviteten $\mathbf {a}$ förbrukar 1 token som ska avfyras och producerar 2 tokens ( $p=1+2=3$ och ${\ displaystil c=1}$ ).

Steg 3: Aktiviteten $\mathbf {b}$ förbrukar 1 token och producerar 1 token ( $p=3+1=4$ och $c=1+1=2$ ).

Steg 4: Aktiviteten $\mathbf {c}$ förbrukar 1 token och producerar 1 token ( $p=4+1=5$ och $c=2+1=3$ ).
Steg 5: Aktiviteten $\mathbf {d}$ förbrukar 2 tokens och producerar 1 token ( $p=5+1=6$ , $c=3+2=5$ ).

Steg 6: Token vid slutplatsen förbrukas ( ${\displaystyle c=5+1=6})$ . Spåret är komplett.

Lämpligheten för spåret ( $\mathbf {a,b,c,d}$ ) på modellen $\mathbf {M}$ är:

{\frac {1}{2}}(1 -{\frac {m}{c}})+{\frac {1}{2}}(1-{\frac {r}{p}})={\frac {1}{2}}(1 -{\frac {0}{6}})+{\frac {1}{2}}(1-{\frac {0}{6}})=1

Exempel 2: Spela om spåret (a, b, d) på modellen M

Steg 1: En token initieras. Det finns en producerad token ( $p=1$ ).

Steg 2: Aktiviteten $\mathbf {a}$ förbrukar 1 token som ska avfyras och producerar 2 tokens ( $p=1+2=3$ och ${\ displaystil c=1}$ ).

Steg 3: Aktiviteten $\mathbf {b}$ förbrukar 1 token och producerar 1 token ( $p=3+1=4$ och $c=1+1=2$ ).

Steg 4: Aktiviteten $\mathbf {d}$ måste aktiveras men det finns inte tillräckligt med tokens. En artificiell token producerades och den saknade token-räknaren ökas med en ( ${\displaystyle m=1})$ . Den konstgjorda token och token på plats $[\mathbf {b,d} ]$ förbrukas ( ${\displaystyle c=2+2=4} )$ och en token produceras vid platsslutet ( ${\displaystyle p=4+1=5})$ .
Steg 5: Token på slutplatsen förbrukas ( ${\displaystyle c=4+1=5})$ . Spåret är komplett. Det finns en token kvar på plats $[\mathbf {a,c} ]$ ( $r=1$ ).