بهینه سازی شبیه سازی بر اساس کریگینگ تیلور و الگوریتم تکاملی

This paper develops a simulation optimization algorithm based on Taylor Kriging and evolutionary algorithm (SOAKEA) for simulation models with high computational expenses. In SOAKEA, an evolutionary algorithm is used to search for optimal solutions of a simulation model, and Taylor Kriging temporarily serves as a surrogate fitness function of this evolutionary algorithm to evaluate solutions. Taylor Kriging is an enhanced version of Kriging where Taylor expansion is used to approximate the drift function of Kriging, and it improves the interpolation accuracy of Kriging. The structures and properties of SOAKEA are analyzed. A combination correction strategy is created, and it effectively reduces the computational expense of SOAKEA. The empirical comparison of SOAKEA with some other well-known metaheuristics is conducted, and the proposed SOAKEA uses particle swam optimization, a population-based evolutionary algorithm, to solve four simulation problems based on multimodal benchmark functions. The results indicate that SOAKEA has significant advantages in optimizing simulation models with high computational expenses.

Evolutionary algorithms (EAs) are effective simulation optimization tools due to their features of stochastic optimization and independence of the properties of optimized models. The typical evolutionary algorithms include Evolutionary Programming [1], Evolution Strategy (ES) [2], Genetic Algorithm (GA) [3], Particle Swarm Optimization (PSO) [4], Ant Colony Optimization [5], Differential Evolution [6], and Estimation of Distribution Algorithm [7]. To obtain a comprehensive introduction to these algorithms, readers can refer to the related references [1], [2], [3], [4], [5], [6], [7] and [8]. Fig. 1 gives the basic process of optimization operations of these algorithms. An EA uses a fitness function to calculate fitness values of candidate solutions, and use these values as a standard to evaluate the quality of solutions. According to fitness values, an EA performs evolutionary operations to generate new evolved solutions. Part of the evolved solutions and current solutions are chosen to construct next generation solutions. The algorithm continues this loop until a stopping criterion is satisfied. In EAs, fitness functions need to be frequently evaluated. For simulation optimization, an evaluation implies to run a simulation model once and is called a simulation evaluation in this paper. Due to the complexity of real-world systems, the simulation models of systems are often computer expensive based on the time of Central Processing Unit (CPU). When a simulation model is computationally too costly, EAs will encounter essential difficulties because of computer limitations such as memory capacity and processor speed. For example, when running a simulation model for one time needs 30 min and the number of simulation evaluations needed in an EA are 1000, the EA will spend about 21 days to find optimal solutions (30/(60 × 24) × 1000 ≈ 24). Influenced by costly computational expenses, evolutionary operations will be stopped due to insufficient fitness values, as indicated by the dash lines in Fig. 1. This paper explores how to introduce a metamodel to assist in evolutionary optimization while an EA is used to optimize a simulation model with high computational expenses. A Simulation Optimization Algorithm based on Taylor Kriging and Evolutionary Algorithm (SOAKEA) is thus developed. The advantages of metamodels are that they are computational inexpensive, and searching for their optimal solutions is easy. Simulation models consider more details and constraints of systems and thus need higher computational expenses. The fundamental idea of SOAKEA is that in evolutionary optimization, a metamodel fitted by known observations temporarily replaces a simulation model to evaluate simulation inputs such that simulation evaluations can be reduced, and the computational expense caused by simulation evaluations can be limited. Taylor Kriging (TK) is the chosen metamodel due to its accurate interpolation feature, and is used to assist in evolutionary optimization. TK is an enhanced version of Kriging by introducing Taylor expansion to serve as a drift function. Kriging is an accurate nonlinear interpolation tool and named after Daniel G. Krige, a mining engineer in South Africa [9]. The rest of paper is organized as follows. In Section 2, the literature review of Kriging applications in simulation and optimization is presented. In Section 3, the Taylor Kriging methodology is introduced. In Section 4, SOAKEA is developed, and its structures and properties are analyzed. In Section 5, the computational experience is provided, and a combination correction strategy is created. Finally, summary and conclusion are given.

This paper establishes an optimization algorithm named SOAKEA for simulation models with costly computational expenses. In SOAKEA, an EA is used to search optimal solutions, and TK temporarily serves as a surrogate fitness function to assist in evolutionary optimization. The idea behind SOAKEA is to integrate the robust optimization capability of EA with the precise interpolation feature of TK to search for optimal solutions of a simulation model with limited simulation observations. The accurate nonlinear interpolation capability of TK is the key factor in the use of SOAKEA. The structures and properties of SOAKEA are analyzed in detail. A combination correction strategy is introduced in SOAKEA, and it can significantly reduce computational expenses of SOAKEA. The empirical investigation on the settings of parameters in SOAKEA provides some critical insights. The empirical comparison of SOAKEA with SA, ES and PSO without Kriging indicates that SOAKEA has apparent advantages in optimizing simulation models with high computational cost. Although SOAKEA shows that it is a promising algorithm for simulation with costly computational expenses, more investigation and analysis need be conducted in order to fully understand its capabilities such that the features of SOAKEA can be better disclosed. For example, the tolerance and sensitivity of EAs for the errors from Kriging evaluation in optimization process need be analyzed in the future; the current SOAKEA only optimizes the problems with multiple inputs and one output, and the future research should explore the optimization of simulation models with multiple outputs, namely multi-objective simulation optimization. In addition, applying SOAKEA to optimizing practical simulation problems with high computational expenses is critical, which will be an important part of our future work.