Rescom TP instructions : Différence entre versions
De MARMOTE
(→Instructions for building Markov Chains) |
(→Developing a new model) |
||
(Une révision intermédiaire par le même utilisateur non affichée) | |||
Ligne 73 : | Ligne 73 : | ||
* a main() function. | * a main() function. | ||
</blockquote> | </blockquote> | ||
− | * modify the code of MakeGenerator( batchDistrib, batchSize, bufferSize ) to have it create the transition matrix of the queue with | + | * modify the code of MakeGenerator( batchDistrib, batchSize, bufferSize ) to have it create the transition matrix of the Markov chain of the queue with |
** arrivals in batches distributed according to batchDistrib | ** arrivals in batches distributed according to batchDistrib | ||
** one server serving batches of size batchSize | ** one server serving batches of size batchSize | ||
Ligne 91 : | Ligne 91 : | ||
** batchDistrib->probas() for getting the array of probabilities | ** batchDistrib->probas() for getting the array of probabilities | ||
** Mean() for computing its average | ** Mean() for computing its average | ||
− | ** Write( stdout, | + | ** Write( stdout, DEFAULT_PRINT_MODE ) for displaying it on the terminal. |
</blockquote> | </blockquote> | ||
* in the main(), create a DiscreteDistribution object for the distribution: | * in the main(), create a DiscreteDistribution object for the distribution: |
Version actuelle datée du 28 juin 2019 à 10:28
Instuctions for the Lab on Markov chain modeling and MDP analysis, at the RESCOM2019 summer school
Sommaire
Objective
The goals of the Lab session is
- program the model of a discrete-time queue with impatience, batch size and finite capacity, using the marmoteCore library;
- program the same model with a control of admission in service, with the marmoteMDP library;
- compute the optimal service policy in this queue.
Steps
Preparation
The first step is to have the library installed on your computer. Two possibilities:
- using a virtual machine with virtualbox
- download VM + instructions from this page
- copy it from USB drive, available at the conference.
- using the compiled library (linux only)
- tarball + instructions from marmoteCore's site
The instructions with virtualbox are then:
- install the virtualbox software from its web site
- launch virtualbox
- click on "Machine > Add"
- enter the location of the virtual machine that has been downloaded
- select the VM (Rescom2019_TP) in the right-hand pane and click on "Start"
- log in with username/password pierre/Rescom2019*
- you should see a desktop with two folders: TP_Marmote and TP_MDP
Instructions for building Markov Chains
Testing the example provided
- Click on the TP_MarkovChain folder
- click on the file "example1.cpp" (or right-click then select "geany")
- a command-line terminal should appear at the bottom. Type
./example1
Example 1: construction of a discrete-time Markov chain on a 3-state space.
- the program takes as arguments:
- n, a number of steps
- p1 p2 p3, three probabilities summing up to 1, representing the initial distribution
- it outputs
- the probability transition matrix
- a trajectory x[0], x[1], ... x[n]
- run the example with values, e.g.
./example1 4 0.2 0.3 0.5
- use the editor to modify the code example1.cpp, in order to make state 2 absorbing
- compile by clicking "Construire > Make"
- execute again
- modify further the code to make it compute the value of the distribution after n steps:
Distribution* trDis = c1->TransientDistributionDT( 0, n );
trDis->Write( stdout, DEFAULT_PRINT_MODE );
- compile and execute
Developing a new model
- download/copy the skeleton of the program from here.
- copy/rename it as main.cpp (overwite the present one)
The file contains:
- the "include" instructions necessary
- a "combinations" and "binomial" useful for computing some probabilities
- the template of a "MakeGenerator" function returning a matrix (type SparseMatrix)
- a main() function.
- modify the code of MakeGenerator( batchDistrib, batchSize, bufferSize ) to have it create the transition matrix of the Markov chain of the queue with
- arrivals in batches distributed according to batchDistrib
- one server serving batches of size batchSize
- buffer + server capacity = bufferSize
- the formulas useful for this are available below
The object DiscreteDistribution:
- represents a discrete distribution on some finite set of values
- is created as
new DiscreteDistribution( n, values, probas );
- where n is the number of values, and the two other parameters are arrays of double.
- has member functions
- nb_vals() for getting the number of values
- batchDistrib->values() for getting the array of values
- batchDistrib->probas() for getting the array of probabilities
- Mean() for computing its average
- Write( stdout, DEFAULT_PRINT_MODE ) for displaying it on the terminal.
- in the main(), create a DiscreteDistribution object for the distribution:
- with values 0, 1, 2, 3, 4,
- with probabilities 1/2, 1/4, 1/8, 1/16, 1/16
- adapt the code from example1.cpp to create a SparseMatrix object with MakeGenerator, then a Markov chain
- simulate the chain for some time
- compute its stationary distribution with the MarkovChain method:
Distribution* StationaryDistributionDT();
- then write it to the terminal.
Instructions for building a MDP model
- move to the TP_MDP directory
- download/copy the skeleton of the program "main.cpp" from here.
- adapt the code of the file MDP_jouet.cpp in order to:
- create in the object P1 the transition matrix of a queue with batch service (reuse the code of the previous exercise)
- create in the object P2 the transition matrix of the same queue, but without any service
- create in the object R1 the matrix of rewards/costs for each pair (state,action)
- create the discountedMDP object from these elements
- solve the MDP problem with the discountedMDP method
solutionMDP* valueIteration( epsilon, maxIter )
- where epsilon is some precision parameter and maxIter the maximum number of iterations
- write the result to the terminal with the writeSolution() method
- do the same with the discountedMDP method policyIterationModified( epsilon, maxIter, value, period )
where value = 0.01 and period = 100 - compile
- execute with
./main
Formulas
Documentation:
- site of marmoteCore with examples and documentation
- the formulas for building transition probabilities Fichier:Formulas.pdf