On a Paired-t Confidence Interval Based Ranking and Selection Method
On a Paired-t Confidence Interval Based Ranking and Selection Method
Yifan Wu*, Liping Liu, and Shuxia Li
Department of Management Science and Engineering
Institute of Operations and Supply Chain Management
East China University of Science and Technology
Shanghai 200237, P.R. China
ABSTRACT
Simulation optimization is a widely used methodology for complex stochastic system design. Though the
simulation provides a flexible tool for model building, the optimization process could be very challenging due to
the cumbersome computing times. A paired-t confidence interval based ranking and selection method is
developed to tackle such a problem. The survive probability of each candidate system is calculated with the
lower and upper bounds of the confidence interval obtained using paired-t comparison method. The proposed
method is tested with several numerical examples. The experimental results suggest that the proposed method
outperforms the other classical Ranking and Selection procedures.
1. INTRODUCTION
The ultimate task for analyzing a simulation model is, perhaps to find a combination of the input factors that
optimizes a specific output performance measure. When the number of combination is limited, say k, the goal is to
select one of the k systems as being the best one. However, the selection is not guaranteed to be correct and most
methods in this field are designed to enhance the probability of selecting the real best system or selecting a subset
of m out of the k systems so that this selected subset contains the best system. The study in this paper hires the first
strategy. Ranking and selection (R&S) methods are classical statistical method specifically designed for such
problem [1]. Since the simulation computation can be very time consuming it is essential to allocate appropriate
replications for all the candidate systems. A paired-t confidence interval is constructed for comparisons between
any two systems in order to effectively allocate the computation resources.
The rest of the paper is organized as follows. Section 2 presents a brief literature review on related methods. A
detailed problem description is presented in Section 3. Section 4 illustrates the replication allocation rule. Section 5
presents the numerical results to demonstrate the efficiency of the proposed approach. Section 6 gives the
conclusions.
2. LITERATURE REVIEW
Studies on selecting the best of k systems has been developed for decades. Dudewicz and Dalal [2] develop a
classical statistical procedure for solving such a problem. The sampling from each of the k systems is divided into
two stages. A fixed number of replications are allocated to each system and the resulting variance estimates are
used to determine the replication numbers in the second stage for each system. Rinott [3] develops another popular
procedure for tackling the same problem.
In recent years, several more efficient approaches are proposed. The optimal computing budget allocation
(OCBA) proposed by Chen et al. [4-6] reduces the total simulation cost by determining an efficient number of
simulation replications or samples for each candidate system to ensure a high probability of correct selection (PCS).
Chick and Inoue [7, 8] hire Bayesian posterior distributions to estimate the PCS and allocate more replications
using decision theory. Excellent surveys on R&S can be found in Swisher et al. [9].
* Corresponding author: Tel.: +86-21-64250973; E-mail: yifanwu@ecust.edu.cn
Flexible Automation and Intelligent Manufacturing, FAIM2014
3. THE PROBLEM
This paper studies the basic version of the system selecting problem in which the design candidates are in a
one-dimensional space. The principal goal is to select the best of k candidates. Without loss of generality, the
minimization problem shown in Equation (1) is considered. The best candidate is the one with the smallest
expected objective value. We aim to select the candidate associated with the smallest mean performance measure
from among the k systems within the constraint of a total computing budget with only T simulation replications.
min
(
)
(
)
,
∈
1
,
2
,
…
(1)
We designate the design system with the smallest estimated mean performance measure as xb so that
min
Since it’s hard to exactly estimate the underlying function values, xb is a random variable that is dependent upon the
size of the computing budget and the allocations to each system. The correct selection is defined as the event where xb is
indeed the best system and Ni is the number of simulation replications allocated to system xi. Since the simulation is time
consuming and the total computing budget is restricted, we seek to develop an effective allocation rule for each Ni in
order to identify the best system with the highest probability. This problem is summarized in Equation (2):
max
(
)
∀
s.t. N1 + N2 + … + Nk = T (2)
The nature of this problem makes it extremely difficult to solve. Multiple simulation runs has to be conducted
to estimate f(xi) in order to understand the underlying function y(xi). Furthermore, since f(xi) is a function of the
random variable ε. To even estimate the performance at single point on the domain, the uncertainty in the system
requires multiple runs to obtain good approximations of the performance measure. Since y(xb) is dependent upon
the uncertainty of the system parameters and the random variable xb, we can only estimate the PCS after
exhausting the total simulation budget T.
4. THE ALLOCATION RULE
This section develops a paired-t confidence interval based allocation rule to eliminate dominated systems and
allocate more replications to the survived systems in the next loop. The whole process is summarized as follows.
Let yi1, yi2, …, yin be a sample of n IID observations from system i, i = 1, 2, …,k. Choose the system with the
lowest mean value at this loop as the current “best” system.
argmin
̅
1
Σ
=
1
(3)
Choose any system xi other than the current “best” system
, let Zj = xij - xbj, j = 1, 2, …, n. Zj’s are IID
random variables and E(Zj) =.
Let
Z
n
Σ
=
1
(4)
And
V
𝑎
[
̅(
)]
Σ
−
(
)
2
=
1
−
1
(5)
Then we can form the
100
1
α
percent confidence interval as below
Z
n
−
1
,
1
−
2
V
𝑎
[
̅(
)] (6)
On a Paired-t Confidence Interval Based Ranking and Selection Method
If
Z
(
n)
−
1
,
1
−
2
V
𝑎
[
̅(
)]
0, then eliminate xi from the candidate system set. Next, allocate some
more replications to each survived candidate system. Continue this process until the total replications run out or
there is only single system left.
5. NUMERICAL TEST
In order to compare the results obtained using the proposed method against other two methods. The first one
is a simple method of equally allocating (EA) the replications to each candidate. The second one is the optimal
computing budget allocation (OCBA) method introduced forehead. The results of three different methods are
compared in two experiments. The first experiment utilizes an underlying quadratic function with 11 candidates
while the second experiment utilizes a quadratic function with 101 candidates.
We conducted the first experiment using a total computing budget of 1000 runs, the second experiment with
45 000 runs. To mitigate the fact that the methods have varying fixed costs associated with them and in order to
compare the performance of the methods using various simulation budgets, we calculated the PCS for each method
during each iteration until the total simulation budget was exhausted. We repeated this whole procedure 10 000
times and then calculated the PCS obtained for each method after these 10 000 independent applications.
In experiment 1, the following function is used to present the simulation output:
f(xi) = (xi - a)2+N(0,1)
We used a domain consisting of 11 evenly spaced candidates where x [
−1, −0.8,... 1]. The parameter a is
randomly selected for each of the 10 000 independent applications, where a ~ Uniform(-1, 1). The results are
shown in Figure 1.
Figure 1. PCS results of experiment 1.
In experiment 2, we used the same quadratic underlying equation used for Experiment 1 and all the other
parameters are kept the same except that we used a domain of 101 candidates where x [
−1, −0.98,..., 1] and the
total number of simulation replications is 40000. The results are shown in Figure 2.
According to the results of the two experiments, the proposed approach outperforms the other two methods.
Note that in Experiment 2, the performance of the other two methods drops dramatically, which shows these
methods are not proper for large number candidate selection.
0
0.1
0.2
0.3
0.4
0.5
0.6
0 500 1000 1500
Probability of Correct Selection, PCS
Total number of simulation replications
EA
OCBA
The proposed
approach
Flexible Automation and Intelligent Manufacturing, FAIM2014
Figure 2. PCS results of experiment 2.
6. CONCLUSIONS
This paper proposes a paired-t confidence interval based ranking and selection method to tackle the system
selection problem when the evaluation of each system has to be done by simulation. All the candidate systems are
allocated with a number of replications in the first loop. Then the survive probability of each candidate system is
calculated with the lower and upper bounds of the confidence interval obtained using paired-t comparison method.
The replication allocation is adjusted using the confidence interval in the coming loops. The final results are
obtained until the total number of replications runs out or the number of survived candidate equals to one. The
proposed method is tested against other two existing methods in two numerical experiments. The results suggest
that the proposed method is effective and efficient.
ACKNOWLEDGEMENT
This work was supported by National Natural Science Foundation of China (71101051), the Shanghai
Educational Development Foundation (11CG33), the Fundamental Research Funds for the Central Universities
(WN1123001) and the National Key Technology R&D Program (2013BAH11F00).
REFERENCES
[1] D. Goldsman and B.L. Nelson, “Ranking, selection, and multiple comparison in computer simulation”, in Proceedings of
the 1994 Winter Simulation Conference, Tew, J., Manivannan, M.S.,Sadowski, D.A. and Seila, A.F. (eds), IEEE Press,
Piscataway, NJ, pp. 192–199, 1994
[2] E. J. Dudewicz and S. R. Dalal: “Allocation of observations in ranking and selection with unequal variances”, Sankhya,
B37, pp.28–78, 1975.
[3] Y. Rinott: “On two-stage selection procedures and related probability-inequalities”, Communications in Statistics, Vol.7,
No. 8, pp.799–811, 1978.
[4] C.H.Chen, J. Lin, E. Yucesan and S.E. Chick, “Simulation budget allocation for further enhancing the efficiency of
ordinal optimization”, Journal of Discrete Event Dynamic Systems: Theory and Applications, Vol.10, pp.251–270, 2000.
[5] C.H. Chen, D. He and M. Fu, “Efficient dynamic simulation allocation in ordinal optimization”. IEEE Transactions on
Automatic Control, Vol.51, No.12, pp.2005–2009, 2006.
[6] C.H. Chen, D. He, M. Fu and L.H. Lee, “Efficient simulation budget allocation for selecting an optimal subset”, Informs
Journal on Computing, Vol.20, No.4, pp.579–595, 2008.
[7] S. Chick and K. Inoue, "New procedures to select the best simulated system using common random numbers",
Management Science,Vol.47, No.8, pp.1133–1149, 2001.
[8] S. Chick and K. Inoue, "New two-stage and sequential procedures for selecting the best simulated system", Operations
Research, Vol.49, pp.1609–1624, 2001.
[9] J.R. Swisher, S.H. Jacobson and E. Yucesan, "Discrete-event simulation optimization using ranking, selection, and
multiple comparison procedures: a survey", ACM Transactions on Modeling and Computer Simulation, Vol.13, pp.134–
154, 2003.
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
0.45
0.5
0 10000 20000 30000 40000 50000
Probability of Correct Selection, PCS
Total number of simulation replications
EA
OCBA
The proposed
approach