Диссертация (1137084), страница 20
Текст из файла (страница 20)
Thus, in the worst case, a while loopmakes approximately . ⋅ ⋃︀ ⋃︀ operations. The third for_all loop removesremaining tokens from all places. Thus, all number of steps in the worst case may be estimatedas (. ⋅ (⋃︀ ⋃︀ + . ⋅ ⋃︀ ⋃︀ + ⋃︀ ⋃︀)) = (⋃︀ ⋃︀), where ⋃︀ ⋃︀is a number of places in the simulated Petri net.83Algorithm 3 Algorithm to generate an event logInput:– is an initial marking,– is a final marking,– are the settings.Output: is an event log.1: ← ∅2: ← ()3: ← 14: While ≤ . do5: ← ∐︀̃︀6: ← .
()7: ← . ()8:For all ∈ do9:. ()10:EndFor11: ℎ ← ∅12: ℎ .( )13: ← 014:ℎ ℎ ← 15:While < . ℎ ℎ do16: ← ℎ ( ℎ ) // Chooses place using random number17:// Tries to move from this place, if it is possible,18:// then moves and records corresponding event in the trace,19:// and returns the set of places which got tokens.20: ℎ ← .(, )21: ℎ ( ℎ )22:For all ∈ do23:If . () > 0 then24:ℎ ℎ ← 25:Break26:EndIf27:EndFor28: ℎ .( ℎ )29: ← + 130:EndWhile31:For all ∈ ℎ do32:.
()33:EndFor34:.()35: ← + 136: EndWhile37: return Generation of a Set of Event LogsMultiple log generation is a very simple but convenient feature of the tool presented. Togenerate a set of event logs the tool uses a loop which calls generateLog algorithm. Every timewe loop, we generate a single log.
Thus, the loop is repeated until we get a desired number ofevent logs. If the initial marking contains several places, and a set of places-to-fire to be randomlyselected, each execution of log generation method works with it’s own beginning.A set of event logs is stored in an object of EventLogArray class. This is the specialclass from ProM 6 “Divide and Conquer” package [129] intended to store arrays of event logs.84ProM Framework has a modular structure and contains lots of plug-ins for different operations [26].Several plug-ins contain classes and methods which support the work with particular modellingformalisms and approaches.
In this tool we use one of these common classes to work with sets ofevent logs. Thus, one can process the generated sets directly in other plug-ins which are based on“Divide and Conquer” package. Algorithm 4 is intended to generate a set of event logs.Algorithm 4 Algorithm to generate a set of event logsInput:– is an initial marking,– is a final marking,– are the settings.Output: is an array of event logs.1:2:3:4:5:6:7:8:←0 ← ∅While < .
do ← ( , , ) // the call of Algorithm 3.()←+1EndWhilereturn PreferencesWhen a place has multiple output arcs the plug-in allows a user to decide which output ismore likely to be fired. Every output has a so-called preference 6 which resembles the probabilityof this output to be selected.t1p1t2t3Figure 3.3: PreferencesConsider an example shown in Figure 3.3.
The outputs (from 1 to 1 ), (from 1 to 2 ), (from1 to 3 ) have preferences , , respectively. An array with size of 3 elements is created. The firstelement is equal to , the second is equal to + , the third is equal to + + . Then plug-in getsa random number within a range from 0 to + + (excluding 0 and including + + ). If thisrandom number is less or equal to then the output (from 1 to 1 ) is selected and transition 16Note that in the current implementation they called priorities.85is fired. If the number is bigger than , but less or equal to + then the output (from 1 to 2 )is selected and 2 is fired, otherwise the selected output is (from 1 to 3 ) and 3 is fired.Each output can have the preference between 0 and 100 (including 0 and 100).
Zero preferencemeans that this output arc will be completely ignored. However, maximum preference does notmean that this output will be always fired. For every two outputs 1 and 2 it is true thatrelationship of the 1 probability to be fired to the 2 probability is equal to the relationship of 1preference to 2 preference. Hence the higher preference is, the higher chance for this output tobe fired. Outputs with the same preference have equal chances to be fired. The approach selectsan output transition to fire according to the Algorithm 5.Algorithm 5 Selecting the preferable outputInput: is the list of available outputs (outgoing arcs).Output: (︀⌋︀ is the selected output.1:2:3:4:5:6:7:8:9:10:11:12:13:14:15:16:17:18:19:20:// Creation of array whose length is equal to the length of preferencesIf ⋃︀ ⋃︀ > 0 then (︀0⌋︀ ← (︀0⌋︀.
←1While < ⋃︀ ⋃︀ do (︀⌋︀ ← (︀ − 1⌋︀ + (︀⌋︀. ←+1EndWhileIf (︀⋃︀ ⋃︀ − 1⌋︀ = 0 thenreturn NULLEndIf ← (0, (︀⋃︀ ⋃︀ − 1⌋︀) + 1←0While < ⋃︀ ⋃︀ doIf ≤ (︀⌋︀ thenreturn (︀⌋︀EndIf←+1EndWhileEndIfEvent Log Generation with NoiseOur approach allows to add randomized noise when generates an event log.
Here, noiseis defined as deliberate deviations from the model’s real behaviour which are generated whensimulating the model, and recorded in an event log.We assume two kinds noise. First component is a totally random noise that represents outerinterferences in the process or system crashes. Second component has more or less strict order.
Itrepresents breakages, incorrect or unfair activities performed in the process. Both components aretaken into account by the presented approach.It is possible to add noise in a totally correct event log that has already been generated bysome tool or obtained from any software system. Another way is to change the original modeland to generate correct event logs from this changed model. Our approach adds noise during the86model simulation. This scheme is more similar to real-life process execution. The tool generates anevent log with drawbacks and deviations during process functioning, which is usual for a numberof processes.When working in a noise addition mode, the tool additionally process every transition firingusing special function.
If the setting is applied, a user is asked to select the so-called noise level. Itshows the probability of noise events to appear during simulation process. For example, if a userset the noise level to be 0.5, then with probability12each process event (when some transitionfires) will be considered as noise event.
In particular, a noise event at each step of the simulationmay be represented in several following ways:(1) adding to the log an artificial event with name from the set of names specified by user,whereas there are no transitions with such label in the model;(2) adding to the log an event with the name that matches with the label of some transitionfrom a model, but this transition is not enabled in that step;(3) skipping an event; i.e.
a transition fires, but the corresponding event is not added to theevent log; in this case artificial events and existing transitions may be added to the log.Thus, depending on a choice made, either noise event will be recorded to the event log insteadcorrect event (or with it), or a correct event will be skipped.Table 3.2 shows a fragment of possible event log with noise that can be generated using amodel from Figure 3.2.Table 3.2: Fragment of an event log with noiseTrace012...Events∐︀, , , , ̃︀∐︀, , , , ̃︀∐︀, , , , ̃︀...In this example, is the name of an additional noise event added to the log.3.2.2Tool DescriptionPresented approach has been implemented as a software. This section presents an overview ofthis tool.
It has been implemented on the base of ProM 6 Framework 7 [26]. A short description ofthis framework and its architecture can be found in Section 4.1 of this thesis. Selection of ProMas a platform for the tool strongly influences on its design.Our tool consists of six main following classes:– LogGenerator class is responsible for interaction with framework and GUI.7ProM official page: http://promtools.org87– AbstractPetriNode represents an element of Petri net (place or transition). It wraps anobject of PetriNode class from PetriNets package providing convenient access to inputs andoutputs of a node.– Place extends AbstractPetriNode getting specific features of a place.
An object of thisclass holds a number of tokens and allows us to choose between the outputs.– Transition class also extends AbstractPetriNode getting specific features of a transition.Actions of transition firing and writing to an event log are described in this class.– Generator class encapsulates creation of a net acceptable for the log generation based on agiven Petri net and performs generation.– An object of GenerationDescription class holds information about settings specified by auser about the set of event logs to be generated (number of event logs, number of traces perlog, preferences and others).Figure 3.4: Main settings of the event log generator GenaThe tool has several graphical user interface (GUI) screens to interact with user. In this section,a number of screen-shots provided in order to illustrate the tool. The main screen asks a user aboutgeneral settings of event log generation (see Figure 3.4).
A user may set the following parameters:– a desired number of logs to be created,– a number of traces per each log,88– the maximum number of simulation steps for one trace.The last setting is needed to avoid infinite behaviours, which are theoretically possible in someprocess models.Note that in a case when user uses noise generation, the specified maximum number ofsimulation steps may differ from the actual number of events per trace: some activities maybe skipped, others may be added. However, it can be guaranteed, that the number of events willbe at most doubled.
This is the case when at each step an additional noise event has been added.A user may ask the tool to use (or not) preferences and/or noise. The screens specifying noisegeneration options are shown to the user, only if he (or she) selects to use generation with noise.A user may specify if an execution of an activity is represented in a log with one or two events.The first event indicates when the execution of the activity begins (START event). The second oneindicates when the tool ends recording activity with information about time according to specifiedtime of execution (COMPLETE event). When a user chooses to separate the start and completeevents for each activity, it is possible to set the time of execution of every activity manually oruse default values.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
