بهینه سازی چند هدفه ترتیبی برای مسایل بهینه سازی شبیه سازی

Ordinal optimization (OO) has been successfully applied to accelerate the simulation optimization process with single objective by quickly narrowing down the search space. In this paper, we extend the OO techniques to address multi-objective simulation optimization problems by using the concept of Pareto optimality. We call this technique the multi-objective OO (MOO). To define the good enough set and the selected set, we introduce two performance indices based on the non-dominance relationship among the designs. Then we derive several lower bounds for the alignment probability under various scenarios by using a Bayesian approach. Numerical experiments show that the lower bounds of the alignment probability are valid when they are used to estimate the size of the selected set as well as the expected alignment level. Though the lower bounds are conservative, they have great practical value in terms of narrowing down the search space.

For many large-scale discrete-event dynamic systems (DEDS), such as traffic systems, supply chain systems, and communication systems, it is often difficult to obtain nice form analytical models which can be used to accurately capture the behavior of the system. For these systems, simulation techniques are commonly used to evaluate and compare the design alternatives to identify the best design among them. However, when the systems are complex and the number of design alternatives is very large or infinite, simulation can be both expensive and time consuming. Therefore, it is important to improve the simulation efficiency through optimization techniques that can maximize the use of simulation output to evaluate and compare the systems while the resources used are minimal. This area of research, known as simulation optimization, has recently become an important topic in evaluating DEDS. Without loss of generality, the simulation optimization problem which minimizes the expected value of the objective function with respect to its constraint set can be expressed as follows where J(θ)=E[L(θ,ɛ)] is the performance measure of the problem, L(θ,ɛ) is the sample performance, ɛ represents the stochastic effects in the system, θ is a vector of discrete controllable factors and Θ is the discrete set containing all the feasible θ. If J(θ) is a scalar function, the problem is a single objective optimization problem; whereas if it is a vector valued function, the problem becomes a multi-objective optimization problem. Note that, in this formulation, constraints on states and outputs are not explicitly expressed because we consider simulation as a black box which takes in certain inputs and provides desirable outputs, and therefore possible constraints on states and outputs can be taken into account by properly defining the feasible design space Θ and by properly building the simulation model. Moreover, we focus on systems with discrete control parameters because they often pose more difficulty due to lack of structure and huge search space. For systems with continuous control parameters, they can be addressed by stochastic approximation, response surface methodology, and gradient-based search methods. The above problem can be very challenging, both analytically and computationally, due to three kinds of difficulties summarized in Lau and Ho (1997): lack of structure, huge search space and large uncertainties. To such problems, finding an optimal or near optimal solution can become an insurmountable task in terms of computational burden. In light of these issues, Ho, Sreenivas, and Vakili (1992) proposed the concept of ordinal optimization (OO). The idea of this approach is to find a subset of good enough solutions with high confidence by ordinal comparison. The successful application of OO in solving simulation optimization problem is due to the following two tenets (Ho, 1999): (1) Ordinal comparison—Order converges exponentially fast (Dai, 1997) while value converges at a rate of View the MathML source, where n is the size of samples used to estimate value. (2) Goal softening—Eases the computational burden of finding the optimum: relax the optimization goal from finding the optimal solution for sure to satisfying with the good enough solution with high probability. The overall objective of OO is to effectively enhance the power of (discrete-event) simulations (Lee, Lau, & Ho, 1999). This is achieved by its capability of quick narrowing down of potential solutions with high confidence during the initial phase of a design process. The resources can then be more efficiently allocated for detailed analysis and improvements of these potential solutions. Successful applications of OO techniques have been found in studies of single objective DEDS (Cassandras et al., 1998, Deng and Ho, 1999, Gong et al., 1999, Ho and Larson, 1995 and Lee et al., 2000). However, for many real life DEDS, the designs are often evaluated in terms of more than one performance measure. In this case, the objective of formulation (1) becomes a vector, and we are dealing with a multi-objective simulation optimization problem. We refer to the application of OO techniques in solving such a problem as the multi-objective OO (MOO). The research in the area of MOO is now summarized as below. Li, Lee, and Ho (1999) proposed the vector OO (VOO) approach for a multi-objective computer network routing design problem. They used the order-based weighting and order-based constraint approach to generate the non-inferior solutions and define the good enough and selected sets. Li, Lee, and Ho (2002) addressed the multi-objective problem by optimizing one performance measure and treating the rest of the performance measures as order constraints. In both papers, they transform the multi-objective problem into a single objective problem. Zhao, Ho, and Jia (2005) proposed to integrate the concept of Pareto optimality with the OO techniques to address the problem. Their solution framework is based on the concept of layer, where the selected set and good enough set are defined in terms of observed and true layers. One limitation of the above framework is that, for a certain good enough set defined by more than one layer, it is not intuitive enough to know how good a design from this set is. Moreover, designs from different layers may be equally good as they may be dominated by the same number of designs. In this paper, we also employ the concept of Pareto optimality, but we present a different solution framework. We define the good enough set as a set with designs being dominated by at most a certain number of designs. In addition, rather than using regression and the concept of OPC to determine the size of the selected set, we employ a Bayesian framework to develop lower bounds of the alignment probability for this purpose. In this paper, we consider a simulation optimization problem formulated as in (1), where the objective View the MathML source to be minimized is a vector consisting of H independent performance measures following continuous distributions, and the design space Θ is a discrete and finite set with a very large number of alternatives. The problem is to consider, under the simulation output with very high noise, how to find a subset of good enough non-dominated solutions with high confidence for the multi-objective simulation optimization problem. The paper is organized as follows: in Section 2, we first introduce the Bayesian framework applied in this study, and then provide definitions for some basic concepts in MOO. Lower bounds of the alignment probability in different scenarios are derived in Section 3. Section 4 presents some results for testing the validity of the lower bounds. Lastly, we give the conclusions and future directions in Section 5

In this paper, we present a multi-objective OO (MOO) framework to improve the search efficiency for multi-objective simulation optimization problems. Based on new definition of the good enough set and the selected set in MOO, several lower bounds are derived for calculating the alignment probability in different scenarios. Results show that, the lower bounds of the alignment probability are valid when they are used to estimate the size of the selected set with various alignment levels or to estimate the expected alignment level with given selected and good enough sets. Though the lower bounds are conservative in nature, they can reduce the search space significantly which is highly desirable in practice. Moreover, the lower bounds of the alignment probability serving the above purposes are effective when the performance measures are independent as well as when they are correlated. For future directions, we may consider how to find tighter lower bounds for the alignment probability, how to handle the correlated performance measures by directly incorporating the correlations into the computation. We may also consider, in very high noise scenarios, when lower bound of alignment probability tends to be more conservative, how to balance the techniques of goal softening (by changing the size of the selected set and the good enough set) and lowering down the noise (by running more simulation replications)—a problem similar to the multi-objective optimal computing budget allocation (MOCBA) problem in OO (Lee et al., 2005).