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.     

On the optimal computing budget allocation problem for large scale simulation optimization

Selecting a set that contains the best simulated systems is an important area of research. When the number of alternative systems is large, then it becomes impossible to simulate all alternatives, so one needs to relax the problem in order to find a good enough simulated system rather than simulating each alternative. One way for solving this problem is to use two-stage sequential procedure. In the first stage the ordinal optimization is used to select a subset that overlaps with the actual best systems with high probability. Then in the second stage an optimization procedure can be applied on the smaller set to select the best alternatives in it. In this paper, we consider the optimal computing budget allocation (OCBA) in the second stage that distribute available computational budget on the alternative systems in order to get a correct selection with high probability. We also discuss the effect of the simulation parameters on the performance of the procedure by implementing the procedure on three different examples. The numerical results indeed indicate that the choice of these parameters affect its performance.     

一种求解随机有限缓冲区流水线调度的混合差分进化算法

针对随机有限缓冲区流水线调度问题(Flow shop scheduling problem, FSSP), 提出混合差分进化(Differential evolution, DE)算法OHTDE, 用来最小化提前/拖后指标和最小化总体完成时间指标. OHTDE将DE和最优计算量分配(Optimal computing budget allocation, OCBA)技术以及假设检验(Hypothesis test, HT)有效结合. DE用于执行全局搜索和局部搜索; OCBA用于对有限计算量进行合理分配, 从而保证优质解得到较多仿真计算量, 提高了在噪声环境下获得优质解的置信度; HT用于在统计意义上比较解的性能, 从而一定程度上避免在解空间相近区域进行重复搜索. 进而, 对由OCBA和HT确定的优质解执行一种特殊的交叉操作, 加强DE的局部开发能力. 同时也采用有限马氏链理论对OHTDE的随机收敛性进行了分析. 仿真实验和算法比较验证了算法的有效性和鲁棒性.     

一种新的混合优化算法及其在车间调度中的应用

提出了一种解决车间调度问题的新方法, 该方法将序优化思想融入巢分区算法框架, 采用"序比较"的方法进行算法的局部寻优. "序"的指数收敛性加快了巢分区算法的局部收敛速度, 从而提高了算法整体的优化效率. 最优计算量分配技术则依据在线数据对计算量进行合理的分配, 进一步提高算法的收敛速度和结果的可靠性. 混合算法继承了巢分区算法的全局搜索特性以及序优化的快速收敛性. 用该算法解决标准 Jobshop 调度问题, 并与序优化方法和模拟退火算法进行比较, 发现本文算法在收敛速度与优化质量方面均优于这些算法.     

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

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

Adaptive hash routing for a cluster of client-side web proxies

Hash routing reduces cache misses for a cluster of web proxies by eliminating the duplication of cache contents. In this paper, we investigate the optimization of hash routing performance by dynamically adapting object and DNS allocations to the traffic pattern. An analytical model is developed for hash routing that takes into consideration the original request distribution, the object allocation strategy, the speeds of the proxies and the cache hit ratios. Based on this model, the optimal hash routing problem is studied. The analytical results are applied to the design of two adaptive hash routing schemes: ADA-OBJ optimizes object allocation under static client configuration, and ADA-OBJ/DNS optimizes both object and DNS allocations under dynamic client configuration. Trace-driven simulation experiments have been conducted to evaluate the performance of the proposed schemes. The results show that they significantly outperform the intuitive static hash routing scheme based only on the speeds of the proxies.     

Computing budget allocation for efficient ranking and selection of variances with application to target tracking algorithms

This paper addresses the problem of ranking and selection for stochastic processes, such as target tracking algorithms, where variance is the performance metric. Comparison of different tracking algorithms or parameter sets within one algorithm relies on time-consuming and computationally demanding simulations. We present a method to minimize simulation time, yet to achieve a desirable confidence of the obtained results by applying ordinal optimization and computing budget allocation ideas and techniques, while taking into account statistical properties of the variance. The developed method is applied to a general tracking problem of N/sub s/ sensors tracking T targets using a sequential multi-sensor data fusion tracking algorithm. The optimization consists of finding the order of processing sensor information that results in the smallest variance of the position error. Results that we obtained with high confidence levels and in reduced simulation times confirm the findings from our previous research (where we considered only two sensors) that processing the best available sensor the last performs the best, on average. The presented method can be applied to any ranking and selection problem where variance is the performance metric.     

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     

基于混合概率解发掘算法的第四方物流弹复性网络设计

为了使第四方物流系统能够安全、有效地运作,研究基于弹复性的第四方物流网络设计问题。建立以网络构建成本为约束、弹复性为目标的优化模型,针对问题模型设计基于最优计算预算分配的混合概率解发掘算法。通过随机产生的不同规模问题,对混合概率解发掘算法进行性能评估,并将实验结果与传统的概率解发掘算法进行比较。实验结果表明了模型与算法的有效性。     

基于分布估计算法的弹性飞翼飞行器多操纵面控制分配

针对弹性飞翼飞行器多操纵面控制分配问题,提出了衡量弹性震动的机振力指标,建立了完整的控制分配模型,提出了采用分布估计算法（EDA）对模型进行求解。首先进行舵面结构设计,分析各气动舵面的工作方式及控制能力,并依据气动数据中升降副翼、余度舵、副翼的舵面控制效率,进行舵面功能配置。在进行控制分配时,分析控制分配的主要性能指标,确立总体多目标优化评价函数,并结合等式和不等式约束条件。采用性能优越的EDA进行求解。通过建立概率模型来估计真实分布,在EDA的进化过程中,各个舵面会根据偏转效率进行分配,结合优化函数最终收敛到最优解。最后分析机翼气动弹性对系统静态操纵效能的影响。从不考虑气动弹性系统响应曲线和考虑气动弹性之后的系统响应曲线比较结果可以看出,有弹性情况下系统响应曲线超调量和过渡时间都减小,飞翼式飞行器飞行品质得到显著提高,优化之后系统效能提高了10%。仿真结果表明,EDA能够较好地解决控制分配问题,并能提高系统动态品质,验证了多操纵面控制分配模型和算法的有效性。     

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.     

Computing efforts allocation for ordinal optimization and discreteevent simulation

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 intelligently determines the optimal number of simulation replications (or samples) and significantly reduces the total simulation cost. Numerical illustrations are included. The results indicate that our approach can obtain an additional 74% computation time reduction above and beyond the reduction obtained through the use of ordinal optimization for a 10-design example     

有限计算量下模拟退火算法的参数序优化

针对模拟退火算法作为一类全局随机搜索算法，其理论收敛条件难以严格实现，有限计算量下的算法性能在实际应用时对参数有严重的依赖性，并且确定合适参数的经验或试验方法缺少系统性等问题，提出将有限计算量下模拟退火的最优参数确定问题视为随机优化问题，并基于序优化和最优计算量分配技术研究出一种确定最优参数组合的系统性方法．典型调度问题的仿真结果验证了该方法的可行性和有效性．     

Performance evaluation of unified memory and dynamic parallelism for selected parallel CUDA applications

The aim of this paper is to evaluate performance of new CUDA mechanisms—unified memory and dynamic parallelism for real parallel applications compared to standard CUDA API versions. In order to gain insight into performance of these mechanisms, we decided to implement three applications with control and data flow typical of SPMD, geometric SPMD and divide-and-conquer schemes, which were then used for tests and experiments. Specifically, tested applications include verification of Goldbach’s conjecture, 2D heat transfer simulation and adaptive numerical integration. We experimented with various ways of how dynamic parallelism can be deployed into an existing implementation and be optimized further. Subsequently, we compared the best dynamic parallelism and unified memory versions to respective standard API counterparts. It was shown that usage of dynamic parallelism resulted in improvement in performance for heat simulation, better than static but worse than an iterative version for numerical integration and finally worse results for Golbach’s conjecture verification. In most cases, unified memory results in decrease in performance. On the other hand, both mechanisms can contribute to simpler and more readable codes. For dynamic parallelism, it applies to algorithms in which it can be naturally applied. Unified memory generally makes it easier for a programmer to enter the CUDA programming paradigm as it resembles the traditional memory allocation/usage pattern.     

舰载机多雷达传感器任务分配与采样间隔融合优化算法

针对舰载机协同探测中多雷达传感器资源配置问题,提出一种多目标跟踪场景下的多传感器数据率管理与任务分配融合优化算法.在基于协方差控制的多传感器分配模型基础上,加以目标优先级和传感器效能条件约束,建立一种多传感器数据率管理与任务分配融合优化模型.将驻留时间改进因子引入序贯卡尔曼滤波算法,计算不同采样间隔下传感器组合状态估计...     

Efficient resource allocation for genetic algorithm based multi-objective optimization with 1,000 simulations

This study pertains to practical use of the GA for industrial applications where only a limited number of simulations can be afforded. Specifically, an attempt is made to find an efficient allocation of the total simulation budget (population size and number of generations) for constrained multi-objective optimization. A study is conducted to seek improvements while restricting the number of simulations to 1,000. Parallelization is exploited using concurrent simulations for each GA generation on a HP quad-core cluster, and resulted in a significant time savings. Furthermore, the efficient distribution of computational effort to achieve the greatest improvement in performance was explored. Two analytical examples as well as an automotive crashworthiness simulation of a finite element model with 58,000 elements were used as test examples. Various population sizes and numbers of generations were tried while limiting the total number of simulations to 1,000. The optimization performance was compared with Monte-Carlo and space filling sampling methods. It was observed that using the GA, many feasible and trade-off solutions could be found. It is shown that allowing a large number of generations is beneficial to get good trade-off solutions. For the vehicle design, significant improvements in the performance were observed. This example also suggests that, for problems with a small feasible region, the number of feasible solutions can be significantly increased in the first few generations involving about 200 simulations.     

随机资源约束项目调度问题基于序的果蝇算法

针对项目活动工期为随机变量的资源约束项目调度问题,提出一种基于序的果蝇算法.为了实现随机环境下解的有效评价,提出一种预选机制,并采用基于序的最优计算量分配技术.为了使果蝇算法能够求解资源约束项目调度问题,采用交换操作执行果蝇算法的嗅觉搜索,并采用保优更新操作执行视觉搜索.为了均衡算法的局部搜索和全局搜索能力,在标准果蝇算法中引入了协作进化环节并采用两点交叉操作加以实现.在不同随机分布的情况下,采用标准测试集进行仿真测试.与现有算法的比较结果验证了所提预选机制和基于序的果蝇算法的有效性.     

Agent scheduling model for adaptive dynamic load balancing in agent-based distributed simulations

Agent-based distributed simulations are confronted with load imbalance problem, which significantly affects simulation performance. Dynamic load balancing can be effective in decreasing simulation execution time and improving simulation performance. The characteristics of multi-agent systems and time synchronization mechanisms make the traditional dynamic load balancing approaches not suitable for dynamic load balancing in agent-based distributed simulations. In this paper, an adaptive dynamic load balancing model in agent-based distributed simulations is proposed. Due to the complexity and huge time consuming for solving the model, a distributed approximate optimized scheduling algorithm with partial information (DAOSAPI) is proposed. It integrates the distributed mode, approximate optimization and agent set scheduling approach. Finally, experiments are conducted to verify the efficiency of the proposed algorithm and the simulation performance under dynamic agent scheduling. The experiments indicate that DAOSPI has the advantage of short execution time in large-scale agent scheduling, and the distributed simulation performance under this dynamic agent scheduling outperforms that under static random agent distribution.     

Optimal base-stock policy of the assemble-to-order systems

In this work, an ordinal optimization-based evolution algorithm (OOEA) is proposed to solve a problem for a good enough target inventory level of the assemble-to-order (ATO) system. First, the ATO system is formulated as a combinatorial optimization problem with integer variables that possesses a huge solution space. Next, the genetic algorithm is used to select N excellent solutions from the solution space, where the fitness is evaluated with the radial basis function network. Finally, we proceed with the optimal computing budget allocation technique to search for a good enough solution. The proposed OOEA is applied to an ATO system comprising 10 items on 6 products. The solution quality is demonstrated by comparing with those obtained by two competing methods. The good enough target inventory level obtained by the OOEA is promising in the aspects of solution quality and computational efficiency.     

Framework for computationally efficient optimal crop and water allocation using ant colony optimization

A general optimization framework is introduced with the overall goal of reducing search space size and increasing the computational efficiency of evolutionary algorithm application to optimal crop and water allocation. The framework achieves this goal by representing the problem in the form of a decision tree, including dynamic decision variable option (DDVO) adjustment during the optimization process and using ant colony optimization (ACO) as the optimization engine. A case study from literature is considered to evaluate the utility of the framework. The results indicate that the proposed ACO-DDVO approach is able to find better solutions than those previously identified using linear programming. Furthermore, ACO-DDVO consistently outperforms an ACO algorithm using static decision variable options and penalty functions in terms of solution quality and computational efficiency. The considerable reduction in computational effort achieved by ACO-DDVO should be a major advantage in the optimization of real-world problems using complex crop simulation models.