结合特征扰动与分配策略的集成辅助多目标优化算法

代理模型利用近似预测代替算法对多目标优化问题的真实评价,大幅减少了算法寻优所需的真实适应度评估次数。为提高代理模型在求解高维问题时的准确性并降低计算开销,提出一种基于特征扰动与分配策略的集成辅助多目标优化算法。将径向基函数网络代理模型与支持向量机回归代理模型作为集成过程中的基模型,降低算法在高维问题上的计算开销。结合特征扰动与基于记忆的影响因子分配策略构建集成代理模型,提高集成准确性。使用集成预测值与不确定信息加权辅助管理集成代理模型,平衡全局搜索与局部探索,增强算法在目标空间中的寻优能力。实验结果表明,该算法在ZDT1~ZDT3和ZDT6测试问题上所得解集的分布性与收敛性相比经典算法更好,并且当决策变量维数增加时,使用集成代理模型相比于Kriging代理模型约减少了90%的适应度评估次数,同时可获得更准确的预测结果。     

SO-MI: A surrogate model algorithm for computationally expensive nonlinear mixed-integer black-box global optimization problems

This paper introduces a surrogate model based algorithm for computationally expensive mixed-integer black-box global optimization problems with both binary and non-binary integer variables that may have computationally expensive constraints. The goal is to find accurate solutions with relatively few function evaluations. A radial basis function surrogate model (response surface) is used to select candidates for integer and continuous decision variable points at which the computationally expensive objective and constraint functions are to be evaluated. In every iteration multiple new points are selected based on different methods, and the function evaluations are done in parallel. The algorithm converges to the global optimum almost surely. The performance of this new algorithm, SO-MI, is compared to a branch and bound algorithm for nonlinear problems, a genetic algorithm, and the NOMAD (Nonsmooth Optimization by Mesh Adaptive Direct Search) algorithm for mixed-integer problems on 16 test problems from the literature (constrained, unconstrained, unimodal and multimodal problems), as well as on two application problems arising from structural optimization, and three application problems from optimal reliability design. The numerical experiments show that SO-MI reaches significantly better results than the other algorithms when the number of function evaluations is very restricted (200–300 evaluations).     

Adaptive partitioned random search to global optimization

This paper considers global optimization (maximization) problems. For a generic function, it is inherently difficult to find the global optimum within a finite number of function evaluations; it is more realistic to talk about maximizing the expectation of the largest function value that can be obtained for a given number of function evaluations. Based on decision theoretic argument, we propose that the search region of the objective function be partitioned into certain number of subregions. Using the sampled function values from each subregion, estimators are derived to determine how “promising” each subregion is. The most promising subregion is further partitioned. The proposed adaptive partitioned random search (APRS) is a tree search type of algorithms like branch-and-bound algorithms. The APRS, however, abandons the idea of finding the subregion where the global maximum is likely located in the first place. Instead it seeks the subregion where the largest improvement of the performance is most likely to be obtained if more function evaluations are taken. The APRS in general can provide a much better-than-average solution within a modest number of function evaluations. In fact, our various numerical experiments have shown that in comparison with the crude random search (CRS) in terms of number of function evaluations, the APRS can be at least hundreds of times more efficient. The simplicity and robustness of the APRS in terms of easy implementation and minimum assumptions are also demonstrated     

Handling expensive multi-objective optimization problems with a cluster-based neighborhood regression model

This paper gives attention to multi-objective optimization in scenarios where objective function evaluation is expensive, that is, expensive multi-objective optimization. We firstly propose a cluster-based neighborhood regression model, which incorporates the linear regression technique to predict the descent direction and generate new potential offspring. Combining this model with the classical decomposition-based multi-objective optimization framework, we propose an efficient and effective algorithm for tackling computationally expensive multi-objective optimization problems. As opposed to the conventional approach of replacing the original time-consuming objective functions with the approximated ones obtained by surrogate model, the proposed algorithm incorporates the proposed regression model to serve as an operator producing higher-quality offspring so that the algorithm requires fewer iterations to reach a given solution quality. The proposed algorithm is compared with several state-of-the-art surrogate-assisted algorithms on a variety of well-known benchmark problems. Empirical results demonstrate that the proposed algorithm outperforms or is competitive with other peer algorithms, and has the ability to keep a good trade-off between solution quality and running time within a fairly small number of function evaluations. In particular, our proposed algorithm shows obvious superiority in terms of the computational time used for the algorithm components, and can obtain acceptable solutions for expensive problems with high efficiency.     

基于不确定度采样准则的费时问题优化算法

在实际工程和控制领域中,许多优化问题的性能评价是费时的,由于进化算法在获得最优解之前需要大量的目标函数评价,无法直接应用其求解这类费时问题.引入代理模型以辅助进化算法是求解计算费时优化问题的有效方法,如何采样新个体对其进行真实的目标函数评价是影响代理模型辅助的进化算法寻优性能的重要因素.鉴于此,利用径向基函数神经网络作...     

Sampling-based RBDO using the stochastic sensitivity analysis and Dynamic Kriging method

This paper presents a sampling-based RBDO method using surrogate models. The Dynamic Kriging (D-Kriging) method is used for surrogate models, and a stochastic sensitivity analysis is introduced to compute the sensitivities of probabilistic constraints with respect to independent or correlated random variables. For the sampling-based RBDO, which requires Monte Carlo simulation (MCS) to evaluate the probabilistic constraints and stochastic sensitivities, this paper proposes new efficiency and accuracy strategies such as a hyper-spherical local window for surrogate model generation, sample reuse, local window enlargement, filtering of constraints, and an adaptive initial point for the pattern search. To further improve computational efficiency of the sampling-based RBDO method for large-scale engineering problems, parallel computing is proposed as well. Once the D-Kriging accurately approximates the responses, there is no further approximation in the estimation of the probabilistic constraints and stochastic sensitivities, and thus the sampling-based RBDO can yield very accurate optimum design. In addition, newly proposed efficiency strategies as well as parallel computing help find the optimum design very efficiently. Numerical examples verify that the proposed sampling-based RBDO can find the optimum design more accurately than some existing methods. Also, the proposed method can find the optimum design more efficiently than some existing methods for low dimensional problems, and as efficient as some existing methods for high dimensional problems when the parallel computing is utilized.     

A new surrogate placement algorithm for cloud-based content delivery networks

Cloud-based content delivery networks (CCDNs) have been developed as the next generation of content delivery networks (CDNs). In CCDNs, the cloud contributes to the cost-effective, pay-as-you-go model, and virtualization and the traditional CDNs contribute to content replications. Delivering infrastructure as a service in a networked cloud computing environment requires mapping virtual resources to physical resources, as well as traditional surrogate placement. In this paper, we develop a novel algorithm for virtual surrogate placement that combines multiple knapsack and competitive facility location problems. Moreover, we provide new formulations and theories for this problem. Finally, we compare our algorithm with the previous heuristics. Simulation results show that the proposed algorithm achieves significantly better results in terms of a decreased number of surrogate servers, decreased total path length between end users and surrogate servers, decreased average workload variance and CCDN deployment cost.     

异构集成代理辅助多目标粒子群优化算法

针对代理辅助进化算法在减少昂贵适应度评估时难以通过少量样本点构造高质量代理模型的问题,提出异构集成代理辅助多目标粒子群优化算法。该方法通过使用加权平均法将Kriging模型和径向基函数网络模型组合成高精度的异构集成模型,达到增强算法处理不确定性信息能力的目的。基于集成学习的两种代理模型分别应用于全局搜索和局部搜索,在多目标粒子群优化算法框架基础上,新提出的方法为每个目标函数自适应地构造了异构集成模型,利用其模型的非支配解来指导粒子群的更新,得出目标函数的最优解集。实验结果表明,所提方法提高了代理模型的搜索能力,减少了评估次数,并且随着搜索维度的增加,其计算复杂性也具有更好的可扩展性。     

An adaptive hybrid surrogate model

The determination of complex underlying relationships between system parameters from simulated and/or recorded data requires advanced interpolating functions, also known as surrogates. The development of surrogates for such complex relationships often requires the modeling of high dimensional and non-smooth functions using limited information. To this end, the hybrid surrogate modeling paradigm, where different surrogate models are combined, offers an effective solution. In this paper, we develop a new high fidelity surrogate modeling technique that we call the Adaptive Hybrid Functions (AHF). The AHF formulates a reliable Crowding Distance-Based Trust Region (CD-TR), and adaptively combines the favorable characteristics of different surrogate models. The weight of each contributing surrogate model is determined based on the local measure of accuracy for that surrogate model in the pertinent trust region. Such an approach is intended to exploit the advantages of each component surrogate. This approach seeks to simultaneously capture the global trend of the function as well as the local deviations. In this paper, the AHF combines four component surrogate models: (i) the Quadratic Response Surface Model (QRSM), (ii) the Radial Basis Functions (RBF), (iii) the Extended Radial Basis Functions (E-RBF), and (iv) the Kriging model. The AHF is applied to standard test problems and to a complex engineering design problem. Subsequent evaluations of the Root Mean Squared Error (RMSE) and the Maximum Absolute Error (MAE) illustrate the promising potential of this hybrid surrogate modeling approach.     

Efficiency improvement of simulated annealing in optimal structural designs

Although simulated annealing (SA) is one of the easiest optimization algorithms available, the huge number of function evaluations deters its use in structural optimizations. In order to apply SA in structural optimization efficiently the number of finite element analyses (function evaluations) has to be reduced as much as possible. Two methods are proposed in this paper. One is to estimate the feasible region using linearized constraints and the SA searches proceed in the estimated feasible region. The other one makes SA search start with an area containing higher design variable values. The search area is then gradually moved toward the optimum point in the following temperatures. Using these approaches, it is hopeful that the number of finite element analyses in the infeasible region can be greatly reduced. The efficiency of SA is thus increased. Three examples show positive results by these methods.     

A study into the potential of GPUs for the efficient construction and evaluation of Kriging models

The surrogate modelling technique known as Kriging, and its various derivatives, requires an optimization process to effectively determine the model’s defining parameters. This optimization typically involves the maximisation of a likelihood function which requires the construction and inversion of a correlation matrix dependent on the selected modelling parameters. The construction of such models in high dimensions and with a large numbers of sample points can, therefore, be considerably expensive. Similarly, once such a model has been constructed the evaluation of the predictor, error and other related design and model improvement criteria can also be costly. The following paper investigates the potential for graphical processing units to be used to accelerate the evaluation of the Kriging likelihood, predictor and error functions. Five different Kriging formulations are considered including, ordinary, universal, non-stationary, gradient-enhanced and multi-fidelity Kriging. Other key contributions include the derivation of the adjoint of the likelihood function for a fully and partially gradient-enhanced Kriging model as well as the presentation of novel schemes to accelerate the likelihood optimization via a mixture of single and double precision calculations and by automatically selecting the best hardware to perform the evaluations on.     

Ensemble of surrogate based global optimization methods using hierarchical design space reduction

For computationally expensive black-box problems, surrogate models are widely employed to reduce the needed computation time and efforts during the search of the global optimum. However, the construction of an effective surrogate model over a large design space remains a challenge in many cases. In this work, a new global optimization method using an ensemble of surrogates and hierarchical design space reduction is proposed to deal with the optimization problems with computation-intensive, black-box objective functions. During the search, an ensemble of three representative surrogate techniques with optimized weight factors is used for selecting promising sample points, narrowing down space exploration and identifying the global optimum. The design space is classified into: Original Global Space (OGS), Promising Joint Space (PJS), Important Local Space (ILS), using the newly proposed hierarchical design space reduction (HSR). Tested using eighteen representative benchmark and two engineering design optimization problems, the newly proposed global optimization method shows improved capability in identifying promising search area and reducing design space, and superior search efficiency and robustness in identifying the global optimum.     

Robust aerodynamic shape design based on an adaptive stochastic optimization framework

Optimization techniques combined with uncertainty quantification are computationally expensive for robust aerodynamic optimization due to expensive CFD costs. Surrogate model technology can be used to improve the efficiency of robust optimization. In this paper, non-intrusive polynomial chaos method and Kriging model are used to construct a surrogate model that associate stochastic aerodynamic statistics with airfoil shapes. Then, global search algorithm is used to optimize the model to obtain optimal airfoil fast. However, optimization results always depend on the approximation accuracy of the surrogate model. Actually, it is difficult to achieve a high accuracy of the model in the whole design space. Therefore, we introduce the idea of adaptive strategy to robust aerodynamic optimization and propose an adaptive stochastic optimization framework. The surrogate model is updated adaptively by increasing training airfoils according to historical optimization results to guarantee the accuracy near the optimal design point, which can greatly reduce the number of training airfoils. The proposed method is applied to a robust aerodynamic shape optimization for drag minimization considering uncertainty of Mach number in transonic region. It can be concluded that the proposed method can obtain better optimal results more efficiently than the traditional robust optimization method and global surrogate model method.     

An application of a GA with Markov network surrogate to feature selection

Surrogate models of fitness have been presented as a way of reducing the number of fitness evaluations required by evolutionary algorithms. This is of particular interest with expensive fitness functions where the time taken for building the model is outweighed by the savings of using fewer function evaluations. In this article, we show how a Markov network model can be used as a surrogate fitness function for a genetic algorithm in a new algorithm called Markov Fitness Model Genetic Algorithm (MFM-GA). We thoroughly investigate its application to a fitness function for feature selection in Case-Based Reasoning (CBR), using a range of standard benchmarks from the CBR community. This fitness function requires considerable computation time to evaluate and we show that using the surrogate offers a significant decrease in total run-time compared to a GA using the true fitness function. This comes at the cost of a reduction in the global best fitness found. We demonstrate that the quality of the solutions obtained by MFM-GA improves significantly with model rebuilding. Comparisons with a classic GA, a GA using fitness inheritance and a selection of filter selection methods for CBR shows that MFM-GA provides a good trade-off between fitness quality and run-time.     

INDUCTIVE LEARNING FOR PARAMETER OPTIMIZATION

Optimization of simulation model output is one of the most important tasks in a simulation study of a complex system. Efficacy of an optimization approach is expressed in the accuracy of locating a global extremum, as well as in the number of investigated search points. The approach Machine Learning Optimization (ML-Opt), presented in this article, explores functional dependencies between search points in order to reduce the number of evaluations. Functional relations between search points are determined by an inductive learning algorithm, which generates a classifier used as a control structure in the optimization process. The classifier approximates the structure of the unknown goal function given by a simulation model and affects the generation of new search points. A discussion of a numerical example concludes the paper.     

Manifold mapping optimization with or without true gradients

This paper deals with the space mapping optimization algorithms in general and with the manifold mapping technique in particular. The idea of such algorithms is to optimize a model with a minimum number of each objective function evaluations using a less accurate but faster model. In this optimization procedure, fine and coarse models interact at each iteration in order to adjust themselves in order to converge to the real optimum. The manifold mapping technique guarantees mathematically this convergence but requires gradients of both fine and coarse model. Approximated gradients can be used for some cases but are subject to divergence. True gradients can be obtained for many numerical model using adjoint techniques, symbolic or automatic differentiation. In this context, we have tested several manifold mapping variants and compared their convergence in the case of real magnetic device optimization.     

Classification- and Regression-Assisted Differential Evolution for Computationally Expensive Problems

Differential Evolution (DE) has been well accepted as an effective evolutionary optimization technique. However, it usually involves a large number of fitness evaluations to obtain a satisfactory solution. This disadvantage severely restricts its application to computationally expensive problems, for which a single fitness evaluation can be highly timeconsuming. In the past decade, a lot of investigations have been conducted to incorporate a surrogate model into an evolutionary algorithm (EA) to alleviate its computational burden in this scenario. However, only limited work was devoted to DE. More importantly, although various types of surrogate models, such as regression, ranking, and classification models, have been investigated separately, none of them consistently outperforms others. In this paper, we propose to construct a surrogate model by combining both regression and classification techniques. It is shown that due to the specific selection strategy of DE, a synergy can be established between these two types of models, and leads to a surrogate model that is more appropriate for DE. A novel surrogate model-assisted DE, named Classification-and Regression-Assisted DE (CRADE) is proposed on this basis. Experimental studies are carried out on a set of 16 benchmark functions, and CRADE has shown significant superiority over DE-assisted with only regression or classification models. Further comparison to three state-of-the-art DE variants, i.e., DE with global and local neighborhoods (DEGL), JADE, and composite DE (CoDE), also demonstrates the superiority of CRADE.     

Surrogate-enhanced evolutionary annealing simplex algorithm for effective and efficient optimization of water resources problems on a budget

In water resources optimization problems, the objective function usually presumes to first run a simulation model and then evaluate its outputs. However, long simulation times may pose significant barriers to the procedure. Often, to obtain a solution within a reasonable time, the user has to substantially restrict the allowable number of function evaluations, thus terminating the search much earlier than required. A promising strategy to address these shortcomings is the use of surrogate modeling techniques. Here we introduce the Surrogate-Enhanced Evolutionary Annealing-Simplex (SEEAS) algorithm that couples the strengths of surrogate modeling with the effectiveness and efficiency of the evolutionary annealing-simplex method. SEEAS combines three different optimization approaches (evolutionary search, simulated annealing, downhill simplex). Its performance is benchmarked against other surrogate-assisted algorithms in several test functions and two water resources applications (model calibration, reservoir management). Results reveal the significant potential of using SEEAS in challenging optimization problems on a budget.     

SOMS: SurrOgate MultiStart algorithm for use with nonlinear programming for global optimization

SOMS is a general surrogate‐based multistart algorithm, which is used in combination with any local optimizer to find global optima for computationally expensive functions with multiple local minima. SOMS differs from previous multistart methods in that a surrogate approximation is used by the multistart algorithm to help reduce the number of function evaluations necessary to identify the most promising points from which to start each nonlinear programming local search. SOMS's numerical results are compared with four well‐known methods, namely, Multi‐Level Single Linkage (MLSL), MATLAB's MultiStart, MATLAB's GlobalSearch, and GLOBAL. In addition, we propose a class of wavy test functions that mimic the wavy nature of objective functions arising in many black‐box simulations. Extensive comparisons of algorithms on the wavy test functions and on earlier standard global‐optimization test functions are done for a total of 19 different test problems. The numerical results indicate that SOMS performs favorably in comparison to alternative methods and does especially well on wavy functions when the number of function evaluations allowed is limited.     

Efficient optimum seismic design of reinforced concrete frames with nonlinear structural analysis procedures

Performance-based seismic design offers enhanced control of structural damage for different levels of earthquake hazard. Nevertheless, the number of studies dealing with the optimum performance-based seismic design of reinforced concrete frames is rather limited. This observation can be attributed to the need for nonlinear structural analysis procedures to calculate seismic demands. Nonlinear analysis of reinforced concrete frames is accompanied by high computational costs and requires a priori knowledge of steel reinforcement. To address this issue, previous studies on optimum performance-based seismic design of reinforced concrete frames use independent design variables to represent steel reinforcement in the optimization problem. This approach drives to a great number of design variables, which magnifies exponentially the search space undermining the ability of the optimization algorithms to reach the optimum solutions. This study presents a computationally efficient procedure tailored to the optimum performance-based seismic design of reinforced concrete frames. The novel feature of the proposed approach is that it employs a deformation-based, iterative procedure for the design of steel reinforcement of reinforced concrete frames to meet their performance objectives given the cross-sectional dimensions of the structural members. In this manner, only the cross-sectional dimensions of structural members need to be addressed by the optimization algorithms as independent design variables. The developed solution strategy is applied to the optimum seismic design of reinforced concrete frames using pushover and nonlinear response-history analysis and it is found that it outperforms previous solution approaches.