Simulation Budget Allocation for Further Enhancing the Efficiency of Ordinal Optimization

Ordinal Optimization has emerged as an efficient technique for simulation and optimization. Exponential convergence rates can be achieved in many cases. In this paper, we present a new approach that can further enhance the efficiency of ordinal optimization. Our approach determines a highly efficient number of simulation replications or samples and significantly reduces the total simulation cost. We also compare several different allocation procedures, including a popular two-stage procedure in simulation literature. Numerical testing shows that our approach is much more efficient than all compared methods. The results further indicate that our approach can obtain a speedup factor of higher than 20 above and beyond the speedup achieved by the use of ordinal optimization for a 210-design example.     

Optimal computing budget allocation for Monte Carlo simulation with application to product design

Ordinal optimization has emerged as an efficient technique for simulation and optimization, converging exponentially in many cases. In this paper, we present a new computing budget allocation approach that further enhances the efficiency of ordinal optimization. Our approach intelligently determines the best allocation of simulation trials or samples necessary to maximize the probability of identifying the optimal ordinal solution. We illustrate the approach’s benefits and ease of use by applying it to two electronic circuit design problems. Numerical results indicate the approach yields significant savings in computation time above and beyond the use of ordinal optimization.     

序的分类预测在进化算法中的应用

昂贵优化问题的求解往往伴随着计算成本灾难, 为了减少目标函数的真实评估次数, 将序预测方法用于进化算法中候选解的选取. 通过分类预测直接得到候选解的相对优劣关系, 避免了对目标函数建立精确代理模型的需求, 并且设计了序样本集约简方法, 以降低序样本集的冗余性, 提高序预测模型的训练效率. 接下来, 将序预测与遗传算法相结合. 序预测辅助遗传算法在昂贵优化测试函数上的仿真实验表明, 序预测方法可有效降低求解昂贵优化问题时的计算成本.     

Ordinal Comparison via the Nested Partitions Method

We analyze a new approach for simulation-based optimization of discrete event systems that draws on two recent stochastic optimization methods: an adaptive sampling approach called the nested partitions method and ordinal optimization. The ordinal optimization perspectives provides new insights into the convergence of the nested partitions method and guidelines for its implementation. We also use this approach to show that global convergence requires relatively simulation runs and propose new effective variants of the algorithm. Simulation results are presented to demonstrate the key results.     

Ordinal Hill Climbing Algorithms for Discrete Manufacturing Process Design Optimization Problems

Thispaper introduces ordinal hill climbing algorithms for addressingdiscrete manufacturing process design optimization problems usingcomputer simulation models. Ordinal hill climbing algorithmscombine the search space reduction feature of ordinal optimizationwith the global search feature of generalized hill climbing algorithms.By iteratively applying the ordinal optimization strategy withinthe generalized hill climbing algorithm framework, the resultinghybrid algorithm can be applied to intractable discrete optimizationproblems. Computational results on an integrated blade rotormanufacturing process design problem are presented to illustratethe application of the ordinal hill climbing algorithm. The relationshipbetween ordinal hill climbing algorithms and genetic algorithmsis also discussed. This discussion provides a framework for howthe ordinal hill climbing algorithm fits into currently appliedalgorithms, as well as to introduce a bridge between the twoalgorithms.     

Ordinal optimization approach to rare event probability problems

In this paper we introduce a new approach to rare event simulation. Because of the extensive simulation required for precise estimation of performance criterion dependent on rare event occurrences, obstacles such as computing budget/time constraints and pseudo-random number generator limitations can become prohibitive, particularly if comparative study of different system designs is involved. Existing methods for rare events simulation have focused on simulation budget reduction while attempting to generate accurate performance estimates. In this paper we propose a new approach for rare events system analysis in which we relax the simulation goal to the isolation of a set of good enough designs with high probability. Given this relaxation, referred to as ordinal optimization and advanced by Ho et al. (1992), this paper's approach calls instead for the consideration of an appropriate surrogate design problem This surrogate problem is characterized by its approximate ordinal equivalence to the original problem and its performance criterion's dependence not on rare event occurrences, but on more frequent events. Evaluation of such a surrogate problem under the relaxed goals of ordinal optimization has experimentally resulted in orders of magnitude reduction in simulation burden.     

Efficient Dynamic Simulation Allocation in Ordinal Optimization

Ordinal optimization has emerged as an efficient technique for simulation optimization. A good allocation of simulation samples across designs can further dramatically improve the efficiency of ordinal optimization. We investigate the efficiency gains of using dynamic simulation allocation for ordinal optimization by comparing the sequential version of the optimal computing budget allocation (OCBA) method with optimal static and one-step look-ahead dynamic allocation schemes with "perfect information" on the sampling distribution. Computational results indicate that this sequential version of OCBA, which is based on estimated performance, can easily outperform the optimal static allocation derived using the true sampling distribution. These results imply that the advantage of sequential allocation often outweighs having accurate estimates of the means and variances in determining a good simulation budget allocation. Furthermore, the performance of the perfect information dynamic scheme can be viewed as an approximate upper bound on the performance of different sequential schemes, thus providing a target for further achievable efficiency improvements using dynamic allocations     

Standard clock simulation and ordinal optimization applied to admission control in integrated communication networks

In this paper we apply the ideas of ordinal optimization and the technique of Standard Clock (SC) simulation to the voice-call admission-control problem in integrated voice/data multihop radio networks. This is an important problem in networking that is not amenable to exact analysis by means of the usual network modeling techniques. We first describe the use of the SC approach on sequential machines, and quantify the speedup in simulation time that is achieved by its use in a number of queueing examples. We then develop an efficient simulation model for wireless integrated networks based on the use of the SC approach, which permits the parallel simulation of a large number of admission-control policies, thereby reducing computation time significantly. This model is an extension of the basic SC approach in that it incorporates fixed-length data packets, whereas SC simulation is normally limited to systems with exponentially distributed interevent times. Using this model, we demonstrate the effectiveness of ordinal-optimization techniques, which provide a remarkably good ranking of admission-control policies after relatively short simulation runs, thereby facilitating the rapid determination of good policies. Moreover, we demonstrate that the use of crude, inaccurate analytical and simulation models can provide highly accurate policy rankings that can be used in conjunction with ordinal-optimization methods, provided that they incorporate the key aspects of system operation.     

A simulation-based two-stage scheduling methodology for controlling semiconductor wafer fabs

In this paper, we propose an efficient simulation-based two-stage scheduling methodology by integrating vector ordinal optimization (VOO) and response surface methodology (RSM) to make a good scheduling policy for fab operation. The suggested method combines local and global rules into a single rule, with the objective of simultaneously optimizing multiple performance indices. Our approach consists of 2 stages: rule combination selection, and parameter optimization. In the first stage, we apply the VOO techniques to effectively selecting good rule combination. Results show that 1 orders of computation time reduction over traditional simulations can be achieved. In the second stage, we adopt RSM and desirability function to tune the parameters associated to scheduling algorithm. The proposed approach is validated by means of a comparison with other scheduling policies. The results show that the proposed scheduling method is effective.     

Using Ordinal Optimization Approach to Improve Efficiency of Selection Procedures

Indifference-zone selection procedures have been widely studied and applied to determine the sample sizes for selecting a good design among k alternative designs. However, efficiency is still a key concern for using simulation to solve ranking and selection problems. Ordinal optimization has emerged as an effective technique to improve efficiency of simulation and optimization. In this paper, we incorporate the concept of ordinal optimization with ranking-and-selection methodology and propose using a normal approximation to estimate the probability of correct selection. The proposed procedure takes into account not only the sample variances but also the difference of sample means when determining the sample sizes. Furthermore, the procedure is valid with the variance reduction technique of common random numbers. An experimental performance evaluation demonstrates the efficiency of the new procedure.     

Motion planning of walking robots using ordinal optimization

A general approach for coordinating the legs of a multi-legged statically stable walking machine on an uneven terrain. The method of ordinal optimization is used to find a good motion plan for low travel time that specifies the footholds and the gait of the walking machine. Numerical simulations illustrate the approach and demonstrate that we can find a good motion plan for uneven terrain with high complexity in a reasonably short time     

Ordinal optimization for a class of deterministic and stochasticdiscrete resource allocation problems

The authors consider a class of discrete resource allocation problems which are hard due to the combinatorial explosion of the feasible allocation search space. In addition, if no closed-form expressions are available for the cost function of interest, one needs to evaluate or (for stochastic environments) estimate the cost function through direct online observation or through simulation. For the deterministic version of this class of problems, the authors derive necessary and sufficient conditions for a globally optimal solution and present an online algorithm which they show to yield a global optimum. For the stochastic version, they show that an appropriately modified algorithm, analyzed as a Markov process, converges in probability to the global optimum, An important feature of this algorithm is that it is driven by ordinal estimates of a cost function, i.e., simple comparisons of estimates, rather than their cardinal values. They can therefore exploit the fast convergence properties of ordinal comparisons, as well as eliminate the need for “step size” parameters whose selection is always difficult in optimization schemes. An application to a stochastic discrete resource allocation problem is included, illustrating the main features of their approach     

A Hybrid approach for integer programming combining genetic algorithms, linear programming and ordinal optimization

Hybrid methods are promising tools in integer programming, as they combine the best features of different methods in a complementary fashion. This paper presents such a framework, integrating the notions of genetic algorithm, linear programming, and ordinal optimization in an effort to shorten computation times for large and/or difficult integer programming problems. Capitalizing on the central idea of ordinal optimization and on the learning capability of genetic algorithms to quickly generate good feasible solutions, and then using linear programming to solve the problem that results from fixing the integer part of the solution, one may be able to obtain solutions that are close to optimal. Indeed ordinal optimization guarantees the quality of the solutions found. Numerical testing on a real-life complex scheduling problem demonstrates the effectiveness and efficiency of this approach.     

Real-time spacecraft actuator fault diagnosis with state-segmented particle filtering

Fault diagnosis permits computational redundancy, which renders a system sustainable and eventually leads to hardware cost reduction. To achieve the posterior distribution computation needed for fault diagnosis along with motion estimation, we suggest a particle filtering (PF)-based state-segmentation approach. Here, both a continuous state vector and fault states are segmented accordingly to allow flexible reasoning for fault diagnosis and motion estimation. For each segmented space, an attempt is made to construct a corresponding posterior distribution independently, resulting in a reduction of the number of particles. Our experimental simulation demonstrates fault diagnosis among billions of fault states. Our state-segmentation approach reduced 98% of particles compared with the ordinal PF approach.     

Managing transitivity and consistency of preferences in AHP group decision making based on minimum modifications

Preference transitivity characterized by ordinal consistency is a fundamental principle for decision making models based on pairwise comparison matrices (PCMs). However, little previous research has addressed ordinal consistency in an optimal way. Further, because ordinal consistency is not considered in the consensus reaching process, non-transitive preferences may still exist in the revised PCMs. In this paper, optimization models are proposed to obtain transitive preferences for solving individual consistency and group consensus problems. First, the conditions satisfying the ordinal consistency of PCMs are analysed and a system of constraints is derived to allow for the ordinal consistency to be explicitly controlled in the optimization model. A mixed integer linear optimization model is then proposed to assist decision makers satisfy both the ordinal and cardinal consistencies. A second mixed integer linear optimization model is then designed to ensure that the consensus level in group decision making problems can be achieved when both the group as a whole and all individuals have acceptably cardinal and ordinal consistencies. Optimization models considering ordinal consistency and classical cardinal consistency indices are open problems needing to be managed in future. Compared with existing methods, the proposed models provide an optimal way to minimize modifications in deriving transitive preferences. Finally, the feasibility and validity of the models are verified through comparisons with classic models.     

A lower bound for the correct subset-selection probability and itsapplication to discrete-event system simulations

Ordinal optimization concentrates on finding a subset of good designs, by approximately evaluating a parallel set of designs, and reduces the required simulation time dramatically for discrete-event simulation and optimization. The estimation of the confidence probability (CP) that the selected designs contain at least one good design is crucial to ordinal optimization. However, it is very difficult to estimate this probability in DES simulation, especially for complicated DES with large number of designs. This paper proposes two simple lower bounds for quantifying the confidence probability. Numerical testing is presented     

Data augmentation and parameter expansion for independent or spatially correlated ordinal data

Data augmentation and parameter expansion can lead to improved iterative sampling algorithms for Markov chain Monte Carlo (MCMC). Data augmentation allows for simpler and more feasible simulation from a posterior distribution. Parameter expansion accelerates convergence of iterative sampling algorithms by increasing the parameter space. Data augmentation and parameter-expanded data augmentation MCMC algorithms are proposed for fitting probit models for independent ordinal response data. The algorithms are extended for fitting probit linear mixed models for spatially correlated ordinal data. The effectiveness of data augmentation and parameter-expanded data augmentation is illustrated using the probit model and ordinal response data, however, the approach can be used broadly across model and data types.     

Dynamical optimization using reduced order models: A method to guarantee performance

Many methods employed for the modeling, analysis, and control of dynamical systems are based on underlying optimization schemes, e.g., parameter estimation and model predictive control. For the popular single and multiple shooting optimization approaches, in each optimization step one or more simulations of the commonly high-dimensional dynamical systems are required. This numerical simulation is frequently the biggest bottleneck concerning the computational effort.In this work, systems described by parameter dependent linear ordinary differential equations (ODEs) are considered. We propose a novel approach employing model order reduction, improved a posteriori bounds for the reduction error, and nonlinear optimization via vertex enumeration. By combining these methods an upper bound for the objective function value of the full order model can be computed efficiently by simulating only the reduced order model. Therefore, the reduced order model can be utilized to minimize an upper bound of the true objective function, ensuring a guaranteed objective function value while reducing the computational effort.The approach is illustrated by studying the parameter estimation problem for a model of an isothermal continuous tube reactor. For this system we derive an asymptotically stable reduction error estimator and analyze the speed-up of the optimization.     

基于两阶段随机仿真优化算法的体检顾客预约调度

针对体检机构顾客排队等待时间长的问题，研究随机服务时间下的体检顾客调度，采用多人时间槽预约策略，并在预约调度策略的基础上优化每位顾客的体检项目顺序，提出一种包含粗糙仿真评估和精确仿真评估两阶段随机仿真优化算法。运用序优化思想将基于亲和度评估的多种群遗传算法作为迭代优化策略，并利用改进的最优计算量分配方法排除超级个体的影响，形成仿真资源的全局和自适应优化分配机制。实验结果表明，与不进行任何调度及使用体检顺序启发式调度规则的离散事件结果相比，该算法获得了更好的调度解。     

优势-等价关系下序贯三支决策的属性约简

序贯三支决策方法是一种能够表示问题中的多重层次粒度,并将多粒度结合起来解决不确定决策问题的有效途径。优势-等价关系粗糙集则是针对条件属性具有偏好关系的分类问题,提取有序信息,对目标概念进行近似,从而形成决策知识。利用传统的优势关系粗糙集方法进行知识约简和提取的效率低下,而目前大部分序贯三支决策方法则局限在符号值属性的信息系统中,对连续值和有序值不能进行有效处理,造成一定程度的信息丢失。因此,将序贯三支决策的思想应用于优势关系粗糙集模型中,定义了一种新的基于序贯三支决策的属性约简及相应的属性重要度,对具有偏好值属性的信息系统进行更加高效的处理,通过多粒度的表示和关系的研究,加速了知识约简过程。选取了多组UCI数据进行实验,结果表明所提出的基于优势关系的序贯三支决策方法能够在保证约简质量的基础上明显降低时间耗费。