Publication: IIE Transactions
Publication Date: 01-JUL-07
Delivery: Immediate Online Access
Author: Hong, L. Jeff ; Nelson, Barry L.
Article Excerpt
1. Introduction
Ranking-and-Selection (R & S) procedures have been proposed to select the simulated system with the largest or smallest mean performance from among a finite number of alternative systems (see Bechhofer et al. (1995) for a summary). These procedures require that all alternative systems are known at the beginning of the experiment. In many cases, however, some alternative systems may not be known at the beginning and they may be revealed during the process of the experiment.
One instance of this situation is iterative system design. System design is naturally a sequential process. New designs are created based on the evaluation of the current designs. The design process typically lasts several rounds and the design selected in the end should at least be the best design among all alternatives that have been evaluated. Another instance is optimization via simulation (see Fu (2002) for a thorough review). The optimization-via-simulation process can be thought of as a system-design process with no human interaction. Optimization algorithms, e.g., the simulated annealing algorithm of Alrefaei and Andradottir (1999), the nest partitions algorithm of Shi and Olafsson (2000), and the COMPASS algorithm of Hong and Nelson (2006) decide what new solutions to visit on each iteration based on information on the current best solution. For example, in the COMPASS algorithm new candidate solutions are generated on each iteration based on the location of the selected best solution among all solutions visited through the previous iteration. In iterative system design and optimization via simulation the experiment may terminate when some stopping rule is satisfied, and then the selected system on that iteration is treated as the best system among all alternative systems generated. Therefore, it is important to find the best system (design or solution) on each iteration to help generate better systems on the next iteration, and also to provide a certain (statistical) guarantee that the selected system is the true best whenever the experiment terminates.
This problem is different from the typical R & S problem since the number of alternative systems is not known at the beginning of the experiment, and a selection decision has to be made each time new alternative systems are revealed. The existing selection procedures cannot be applied directly to solve this problem. In this paper, we propose two general approaches to solve the problem, the single-elimination approach and the stop-and-go approach, and design several procedures accordingly.
There are two types of R & S procedures: frequentist procedures and Bayesian procedures. Frequentist procedures such as Rinott (1978) and Kim and Nelson (2001) allocate simulation effort to different systems to ensure a probability of correct selection even for the least favorable configuration. They are typically conservative for an average case. Bayesian procedures such as Chen et al. (2000) and Chick and Inoue (2001a, 2001b) maximize the posterior probability of correct selection or minimize an opportunity cost given a simulation budget. However, they do not provide a guaranteed probability of correct selection. In this paper we take the frequentist viewpoint and the procedures proposed in this paper all guarantee a prespecified probability of correct selection.
The procedures provided in this paper are also sequential procedures. Among the frequentist procedures, Kim and Nelson (2001) first introduce a fully sequential procedure to solve simulation selection problems. They approximate the sum of differences between two systems as a Brownian motion process and use a triangular continuation region to determine the stopping time of the selection process. Like other frequentist procedures, sequential selection procedures are designed for the least favorable configuration where the differences between the true mean of the best system and the true means of all other systems are exactly the Indifference-Zone (IZ) parameter, [delta]. However, unlike the popular two-stage procedures such as Rinott (1978), sequential selection procedures terminate faster if the systems are not in this unfavorable configuration.
Boesel et al. (2003) and Pichitlamken et al. (2006) have applied R & S in the optimization-via-simulation context. Boesel et al. (2003) propose efficient R & S procedures that can be used at the end of the optimization process to guarantee that the chosen solution is the true best among all solutions visited by the optimization process with a certain confidence. However, their procedures do not help make correct selection decisions on each iteration of the optimization process. Pichitlamken et al. (2006) propose a selection procedure that can be applied on each iteration of the optimization process to provide a statistical guarantee on that iteration. However, their procedure does not provide an overall statistical guarantee on all visited solutions.
The procedures proposed in this paper combine aspects of Boesel et al. (2003) and Pichitlamken et al. (2006) to help make selection decisions on each iteration and provide an overall statistical guarantee at the end of the design or optimization process. However, there is a price to pay for this very strong inference. Providing a statistical guarantee of correct selection on each iteration, especially when the number of candidate solutions that the optimization process visits is large, is very demanding. Therefore, our proposed procedures are only applicable to iterative system-design problems and small-scale optimization problems. Extensions of these procedures to optimization problems with a very large number of alternatives is a subject of ongoing research.
The paper is organized as follows. The mathematical formulation of the problem is provided in Section 2. We discuss the single-elimination approach and the stop-and-go approach in Sections 3 and 4, respectively. Numerical examples are presented in Section 5, followed by the conclusions and possible future research directions in Section 6.
2. The mathematical formulation
Consider the following generic algorithm for generating new alternative systems.
System Generating Algorithm (SGA)
Step 0. We start with [k.sub.0] simulated systems, [[pi].sub.1], [[pi].sub.2],..., [[pi].sub.k.sub.0], and [k.sub.0] [greater than or equal to] 2. Let i and [K.sub.i] denote the iteration count and the total number of alternative systems generated through iteration i, respectively. Set i = and [K.sub.0] = [k.sub.0]. Go to Step 2.
Step 1. Let i = i + 1. Generate [k.sub.i] [greater than or equal to] 1 alternatives, [[pi].sub.[K.sub.i-1]+1], [[pi].sub.[K.sub.i-1]+2],..., [[pi].sub.[K.sub.i-1]+[k.sub.i]]. Let [K.sub.i] = [K.sub.i-1] + [k.sub.i].
Step 2. Select the best system in all [K.sub.i] alternatives [[pi].sub.1], [[pi].sub.2],..., [[pi].sub.K.sub.i].
Step 3. If the stopping rule is satisfied, stop; otherwise, go to Step 1.
Remark 1. In Step 1 of SGA [k.sub.i] is determined by the designer or the optimization algorithm, and it may depend on the simulation budget (i.e., available time to solve the problem). However, the selection procedures provided in this paper work for any deterministic [k.sub.i] [greater than or equal to] 1.
Clearly, Step 2 of SGA is where R & S should be applied. IZ selection procedures select the best system with a Probability of Correct Selection (PCS) greater than or equal to 1 - [alpha] from a given set of alternative systems whenever the true mean performance of the best system in the set is at least [delta] greater than the true mean of the second-best system. The IZ parameter [delta] > is set by the experimenter to the minimum difference in expected performance that it is important to detect. Differences of less than [delta] are considered practically insignificant. In this paper, we assume that the best system is the system with the largest mean performance.
IZ selection procedures for SGA are different from typical IZ selection procedures, since the total number of systems for comparison is not fixed. Since SGA generates new alternative systems iteration by iteration, it is natural to design IZ selection procedures that compare the new alternative systems to only the previous best system, and systems determined not to be the best are eliminated and never considered again. For this type of procedure, allocating the Probability of Incorrect Selection (PICS) among the different comparisons can solve the problem of changing the total number of alternatives. When the total number of alternatives that SGA will generate can be bounded, one can allocate the PICS uniformly. When the total number cannot be bounded, one can design an infinite sequence, whose sum converges to PICS, to allocate the PICS. As we show in Section 3, both approaches guarantee the overall PCS whenever SGA terminates.
Another approach is to solve a R & S problem with [K.sub.i] alternatives on the ith iteration. We can apply an IZ selection procedure to all alternatives, whether or not they have been eliminated during previous iterations. In Section 4, we show that this approach can be efficient in terms of sampling; however, it does require more switches among the simulated alternative systems, which can be costly...
NOTE: All illustrations and photos have been removed from this article.
More articles from
IIE Transactions
Locating capacitated facilities to maximize captured demand, 01-NOV-07
Erratum, 01-NOV-07
Sequencing with limited flexibility, 01-OCT-07
Looking for additional articles?
Click here to search our database of over 3 million articles.
Looking for more in-depth information on this industry?
Click here to search our complete database of Industry & Market reports by text, subject, publication name or publication date.
About Goliath
Whether you're looking for sales prospects, competitive information, company analysis or best practices in managing your organization, Goliath can help you meet your business needs.
Our extensive business information databases empower business professionals with both the breadth and depth of credible, authoritative information they need to support their business goals. Whether it be strategic planning, sales prospecting, company research or defining management best practices - Goliath is your leading source for accurate information. |
