Transcript kLimit

The AutoSimOA Project
A 3 year, EPSRC funded project in collaboration
with SIMUL8 Corporation.
Katy Hoad, Stewart Robinson, Ruth Davies
Warwick Business School
OR49 Sept 07
OUTLINE
Introduction
Methods
Algorithm
Test Methodology
Test Results
Extended Algorithm & Results
Discussion
Summary
Objective
To provide an easy to use method, that can
be incorporated into existing simulation
software, that enables practitioners to
obtain results of a specified accuracy from
their discrete event simulation model.
(Only looking at analysis of a single scenario)
• Initial Setup:
Introduction
 Any warm-up problems already dealt with.
 Run length (m) decided upon.
 Modeller decided to use multiple replications to
obtain better estimate of mean performance.
• Multiple replications performed by changing the random
number streams used by the model and re-running the
simulation.
X 21 , , X m1 
2
2
2
X 1 , X 2 , , X m 




 
X 1N , X 2N , , X mN 
X 11 ,
Output data from model
Xˆ 1 = summary statistic
N replications
Response
measure
of interest
from rep1

Xˆ N = summary statistic

from repN
1 N
X  Xj
N j 1
QUESTION IS…
How many replications
are needed?
• Limiting factors: computing time and
expense.
If performing N replications achieves a
sufficient estimate of mean performance:
> N replications: Unnecessary use of computer
time and money.
< N replications: Inaccurate results → incorrect
decisions.
4 main methods found in the
literature for choosing N:
1.
Rule of Thumb
Run at least 3 to 5 replications.
Advantage:
Very simple.
Disadvantage: Does not use characteristics of
model output.
No measured precision level.
2.
Simple Graphical Method
• Plot Cumulative mean -v- number of replications
Cumulative mean
Cumulative mean graph
55
53
51
49
47
45
1
9
17
25
33 41 49 57 65 73
Number of replications (n)
81
89
97
105
• Visually select point where cumulative mean line becomes
“flat”. Use this as N.
Advantages:
Simple
Uses output of interest in decision.
Disadvantages:
Subjective
No measured precision level.
3. Confidence Interval (with Specified
Precision) Method
• User decides size of error they can tolerate.
• Run increasing numbers of replications,
• Construct Confidence Intervals around sequential
cumulative mean of output variable until desired precision
achieved.
Advantages:
Relies upon statistical inference to determine
number of replications required.
Allows the user to tailor accuracy of
output results to their particular requirement
or purpose for that model and result.
Disadvantage: Many simulation users do not have the skills
to apply such an approach.
4. Prediction Formula Method
• User decides size of error they can tolerate.
• Run a few replications, estimate variance & mean
• Use formula to predict N.
 t , N 1 s 
2

N 





• Check desired precision achieved – if not amend N and
repeat
Advantages:
Disadvantage:
Simple.
Uses data from model.
Provides specified precision.
Can be very inaccurate especially
for small number of replications.
If variance estimate low
underestimate N
If variance estimate high
overestimate N
• Chose to automate:
Confidence Interval (with Specified
Precision) Method
The replication algorithm interacts with the simulation model
sequentially.
START:
Load
Input
Run one
more
replication
Run
Model
NO
Precision
criteria met?
YES
Recommend
replication number
Produce
Output
Results
Run
Replication
Algorithm
ALGORITHM DEFINITIONS
We define the precision, dn, as the ½ width of the Confidence Interval
expressed as a percentage of the cumulative mean:
dn
Where

100t n1,
sn
2
n
Xn
n is the current number of replications carried out,
t n1, is the student t value for n-1 df and a significance of 1-α,
2
X n is the cumulative mean,
sn is the estimate of the standard deviation,
calculated using results Xi (i = 1 to n) of the n current replications.
Stopping Criteria
•
Simplest method:
Stop when dn 1st found to be ≤ desired
precision, drequired , and recommend that
number of replications, Nsol, to the user.
•
Problem: Data series could prematurely
converge, by chance, to incorrect estimate of
the mean, with precision drequired , then diverge
again.
•
‘Look-ahead’ procedure: When dn 1st found to
be ≤ drequired, algorithm performs set number of
extra replications, to check that precision
remains ≤ drequired.
‘Look-ahead’ procedure
kLimit = ‘look ahead’ value.
Actual number of replications checked ahead is a function of this user
defined value:
kLimit ,
n  100

f (kLimit )
n  kLimit
, n  100

100


Function relates ‘look ahead’ period length with current value of n.
140
kLimit=0
kLimit=10
120
kLimit=5
kLimit=25
f(kLimit)
100
80
60
40
20
0
470
433
396
359
322
285
248
211
174
137
100
3
replication number (n )
Replication Algorithm
37
95% confidence limits
Precision ≤ 5%
Cumulative mean, X
35
33
X
31
29
27
f(kLimit)
25
Nsol
Nsol +
f(kLimit)
23
3
4
5
6
7
8 9 10 11 12 13 14 15 16 17 18 19 20
Replication number (n)
1.15
Precision
> 5%
Precision
≤ 5%
1.2
Precision ≤ 5%
1.1
1.05
1
0.95
0.9
f(kLimit)
0.85
Nsol
Nsol
Nsol +
f(kLimit)
0.8
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
Replication number (n)
TESTING METHODOLOGY
• 24 artificial data sets created:
Left skewed, symmetric, right skewed;
Varying values of relative standard deviation (stdev/mean).
• Advantage: true mean and variance known.
• Artificial data set: 100 sequences of 2000 data values.
• 8 real models selected.
• Different lengths of ‘look ahead’ period looked at:
kLimit values = 0 (i.e. no ‘look ahead’ period), 5, 10, 25.
• drequired value kept constant at 5%.
5 performance measures
1.
2.
3.
4.
5.
•
Coverage of the true mean
Bias
Absolute Bias
Average Nsol value
Comparison of 4. with Theoretical Nsol
value
For real models: ‘true’ mean and st.dev values estimated from whole sets of output data
(3000 to 11000 data points).
Results
• Nsol values for individual algorithm runs
are very variable.
• Average Nsol values for 100 runs per
model close to the theoretical values of
Nsol.
• Normality assumption appears robust.
• Using a ‘look ahead’ period improves
performance of the algorithm.
No ‘lookahead’
period
kLimit = 5
Mean bias
significantly
different to
zero
Failed in
coverage
of true
mean
Mean est. Nsol
significantly
different to
theoretical Nsol
(>3)
Proportion of
Artificial
models
4/24
2/24
9/18
Proportion of
Real models
1/8
1/8
3/5
Proportion of
Artificial
models
1/24
0
1/18
Proportion of
Real models
0
0
0
Impact of different look ahead periods on
performance of algorithm
% decrease in absolute mean bias
Artificial
Models
Real
Models
kLimit = 0 to
kLimit = 5
kLimit = 5 to
kLimit = 10
kLimit = 10 to
kLimit = 25
8.76%
0.07%
0.26%
10.45%
0.14%
0.33%
Number of times the Nsol value changes (out of 100 runs of
the algorithm per model) because of the lengthening of the
‘look ahead’ period.
Model
kLimit = 0 to
kLimit = 5 to
kLimit = 10 to
ID
kLimit = 5
kLimit = 10
kLimit = 25
R1
0
0
0
R3
2
0
0
R5
24
0
1
R8
24
4
1
A5
30
1
3
A6
26
6
3
A15
1
0
0
A17
22
0
1
A21
25
2
1
A24
37
0
0
Eg.s of changes in Nsol & improvement in estimate of true mean
Model ID kLimit
Nsol Theoretical Nsol
(approx)
Mean estimate significantly
different to the true mean?
A22
0
4
Yes
5
54
0
4
5
120
0
3
5
718
0
8
5
38
0
3
5
8
0
3
5
7
0
3
5
46
A9
A24
A21
R7
R4
R8
64
No
112
Yes
No
755
Yes
No
37
Yes
No
10
Yes
No
6
Yes
No
45
Yes
No
Examples of changes in Nsol & improvement in estimate of
true mean
Model kLimit Nsol
ID
Theoretical
Mean estimate significantly
Nsol (approx) different to the true mean?
A9
0
5
4
120
112
Yes
No
A24
0
5
3
718
755
Yes
No
R7
0
5
3
8
10
Yes
No
R4
0
5
0
3
7
3
6
Yes
No
Yes
5
46
R8
45
No
DISCUSSION
•
kLimit default value set to 5.
•
Initial number of replications set to 3.
•
Multiple response variables - Algorithm run
with each response - use maximum
estimated value for Nsol.
•
Different scenarios - advisable to repeat
algorithm every few scenarios to check that
precision has not degraded significantly.
•
Inclusion into simulation package: Full
explanations of algorithm and results.
SUMMARY
•
•
•
Selection and automation of Confidence
Interval (with Specified Precision) Method
for estimating the number of replications to
be run in a simulation.
Algorithm created with ‘look ahead’ period efficient and performs well on wide
selection of artificial and real model output.
‘Black box’ - fully automated and does not
require user intervention.
ACKNOWLEDGMENTS
This work is part of the Automating Simulation Output
Analysis (AutoSimOA) project
(http://www.wbs.ac.uk/go/autosimoa) that is funded by the
UK Engineering and Physical Sciences Research Council
(EP/D033640/1). The work is being carried out in
collaboration with SIMUL8 Corporation, who are also
providing sponsorship for the project.
Katy Hoad, Stewart Robinson, Ruth Davies
Warwick Business School
OR49 Sept 07