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).     

Stochastic radial basis function algorithms for large-scale optimization involving expensive black-box objective and constraint functions

This paper presents a new algorithm for derivative-free optimization of expensive black-box objective functions subject to expensive black-box inequality constraints. The proposed algorithm, called ConstrLMSRBF, uses radial basis function (RBF) surrogate models and is an extension of the Local Metric Stochastic RBF (LMSRBF) algorithm by Regis and Shoemaker (2007a) [1] that can handle black-box inequality constraints. Previous algorithms for the optimization of expensive functions using surrogate models have mostly dealt with bound constrained problems where only the objective function is expensive, and so, the surrogate models are used to approximate the objective function only. In contrast, ConstrLMSRBF builds RBF surrogate models for the objective function and also for all the constraint functions in each iteration, and uses these RBF models to guide the selection of the next point where the objective and constraint functions will be evaluated. Computational results indicate that ConstrLMSRBF is better than alternative methods on 9 out of 14 test problems and on the MOPTA08 problem from the automotive industry (Jones, 2008 [2]). The MOPTA08 problem has 124 decision variables and 68 inequality constraints and is considered a large-scale problem in the area of expensive black-box optimization. The alternative methods include a Mesh Adaptive Direct Search (MADS) algorithm (Abramson and Audet, 2006 [3]; Audet and Dennis, 2006 [4]) that uses a kriging-based surrogate model, the Multistart LMSRBF algorithm by Regis and Shoemaker (2007a) [1] modified to handle black-box constraints via a penalty approach, a genetic algorithm, a pattern search algorithm, a sequential quadratic programming algorithm, and COBYLA (Powell, 1994 [5]), which is a derivative-free trust-region algorithm. Based on the results of this study, the results in Jones (2008) [2] and other approaches presented at the ISMP 2009 conference, ConstrLMSRBF appears to be among the best, if not the best, known algorithm for the MOPTA08 problem in the sense of providing the most improvement from an initial feasible solution within a very limited number of objective and constraint function evaluations.     

粒子群Memetic算法求解多峰函数优化

针对目前多峰函数优化问题较难找到全部局部最优解的情况,提出了一种粒子群Memetic算法。算法结合了粒子群优化的全局搜索能力和爬山法的局部搜索能力,增强了算法搜索最优解的能力。实验结果表明,该算法求解精度较高,且收敛速度较快。     

An algorithm for computationally expensive engineering optimization problems

Abstract

Modern engineering design often relies on computer simulations to evaluate candidate designs, a scenario which results in an optimization of a computationally expensive black-box function. In these settings, there will often exist candidate designs which cause the simulation to fail, and can therefore degrade the search effectiveness. To address this issue, this paper proposes a new metamodel-assisted computational intelligence optimization algorithm which incorporates classifiers into the optimization search. The classifiers predict which candidate designs are expected to cause the simulation to fail, and this prediction is used to bias the search towards designs predicted to be valid. To enhance the search effectiveness, the proposed algorithm uses an ensemble approach which concurrently employs several metamodels and classifiers. A rigorous performance analysis based on a set of simulation-driven design optimization problems shows the effectiveness of the proposed algorithm.     

基于新模型的多目标Memetic算法及收敛分析

将多目标函数优化问题转化成单目标约束优化问题.对转化后的问题提出了基于约束主导原理的选择方法,克服了多数方法只使用Pareto优胜关系作为选择策略而没有采用偏好信息这一缺陷;Memetic算法是求解多目标优化问题最有效的方法之一,它融合了局部搜索和进化计算.新的多目标Memetic算法引进C-metric,将模拟退火算法与遗传算法结合起米,改善了全局搜索能力.用概率论的有关知识证明了算法的收敛性.仿真结果表明该方法对不同的试验函数均可求出一组沿着Pareto前沿分布均匀且散布广泛的非劣解.     

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.     

A Memetic Chaotic Gravitational Search Algorithm for unconstrained global optimization problems

Metaheuristic optimization algorithms address two main tasks in the process of problem solving: i) exploration (also called diversification) and ii) exploitation (also called intensification). Guaranteeing a trade-off between these operations is critical to good performance. However, although many methods have been proposed by which metaheuristics can achieve a balance between the exploration and exploitation stages, they are still worse than exact algorithms at exploitation tasks, where gradient-based mechanisms outperform metaheuristics when a local minimum is approximated. In this paper, a quasi-Newton method is introduced into a Chaotic Gravitational Search Algorithm as an exploitation method, with the purpose of improving the exploitation capabilities of this recent and promising population-based metaheuristic. The proposed approach, referred to as a Memetic Chaotic Gravitational Search Algorithm, is used to solve forty-five benchmark problems, both synthetic and real-world, to validate the method. The numerical results show that the adding of quasi-Newton search directions to the original (Chaotic) Gravitational Search Algorithm substantially improves its performance. Also, a comparison with the state-of-the-art algorithms: Particle Swarm Optimization, Genetic Algorithm, Rcr-JADE, COBIDE and RLMPSO, shows that the proposed approach is promising for certain real-world problems.     

求解多目标问题的Memetic免疫优化算法

将基于Pareto支配关系的局部下山算子和差分算子引入免疫多目标优化算法之中,提出了一种求解多目标问题的Memetic免疫优化算法(Memetic immune algorithm for multiobjective optimization,简称MIAMO).该算法利用种群中抗体在决策空间上的位置关系设计了两种有效的启发式局部搜索策略,提高了免疫多目标优化算法的求解效率.仿真实验结果表明,MIAMO与其他4种有效的多目标优化算法相比,不仅在求得Pareto最优解集的逼近性、均匀性和宽广性上有明显优势,而且算法的收敛速度与免疫多目标优化算法相比明显加快.     

Improving surrogate-assisted variable fidelity multi-objective optimization using a clustering algorithm

Surrogate-assisted evolutionary optimization has proved to be effective in reducing optimization time, as surrogates, or meta-models can approximate expensive fitness functions in the optimization run. While this is a successful strategy to improve optimization efficiency, challenges arise when constructing surrogate models in higher dimensional function space, where the trade space between multiple conflicting objectives is increasingly complex. This complexity makes it difficult to ensure the accuracy of the surrogates. In this article, a new surrogate management strategy is presented to address this problem. A k-means clustering algorithm is employed to partition model data into local surrogate models. The variable fidelity optimization scheme proposed in the author's previous work is revised to incorporate this clustering algorithm for surrogate model construction. The applicability of the proposed algorithm is illustrated on six standard test problems. The presented algorithm is also examined in a three-objective stiffened panel optimization design problem to show its superiority in surrogate-assisted multi-objective optimization in higher dimensional objective function space. Performance metrics show that the proposed surrogate handling strategy clearly outperforms the single surrogate strategy as the surrogate size increases.     

Rosenbrock artificial bee colony algorithm for accurate global optimization of numerical functions

A Rosenbrock artificial bee colony algorithm (RABC) that combines Rosenbrock’s rotational direction method with an artificial bee colony algorithm (ABC) is proposed for accurate numerical optimization. There are two alternative phases of RABC: the exploration phase realized by ABC and the exploitation phase completed by the rotational direction method. The proposed algorithm was tested on a comprehensive set of complex benchmark problems, encompassing a wide range of dimensionality, and it was also compared with several algorithms. Numerical results show that the new algorithm is promising in terms of convergence speed, success rate, and accuracy. The proposed RABC is also capable of keeping up with the direction changes in the problems.     

基于免疫Memetic算法的网络组播路由优化

为了求得代价最小的网络组播路径,提出了一种基于免疫Memetic算法的优化求解方法。算法充分结合免疫全局搜索和局部搜索机制,设计了适合组播路由问题的各种免疫算子,加快了算法的收敛速度。实验结果表明,该算法在无需备选路径集的情况下,可以较快地找到最优路径,并且算法更加简单。     

An improved evolutionary algorithm for handling many-objective optimization problems

It has been shown that the multi-objective evolutionary algorithms (MOEAs) act poorly in solving many-objective optimization problems which include more than three objectives. The research emphasis, in recent years, has been put into improving the MOEAs to enable them to solve many-objective optimization problems efficiently. In this paper, we propose a new composite fitness evaluation function, in a novel way, to select quality solutions from the objective space of a many-objective optimization problem. Using this composite function, we develop a new algorithm on a well-known NSGA-II and call it FR-NSGA-II, a fast reference point based NSGA-II. The algorithm is evaluated for producing quality solutions measured in terms of proximity, diversity and computational time. The working logic of the algorithm is explained using a bi-objective linear programming problem. Then we test the algorithm using experiments with benchmark problems from DTLZ family. We also compare FR-NSGA-II with four competitive algorithms from the extant literature to show that FR-NSGA-II will produce quality solutions even if the number of objectives is as high as 20.     

一种求解函数优化问题的改进鲸鱼优化算法

为提高鲸鱼优化算法求解复杂函数优化问题的性能,提出一种基于自适应参数及小生境技术的改进鲸鱼优化算法。首先,引入自适应概率阈值协调算法的全局探索及局部开发能力;其次,利用自适应位置权重对鲸鱼位置更新公式进行调整,提高算法的收敛速度及寻优精度;最后,采用预选择小生境技术,避免算法出现早熟收敛的现象。通过对12个典型基准测试函数的仿真表明,改进算法的寻优精度和收敛速度较对比算法均有明显提升,证明了提出的改进策略能有效提高鲸鱼优化算法求解复杂函数优化问题的性能。     

基于Memetic算法的带时间窗车辆路径问题研究*

提出一种模拟文化进化的Memetic算法求解带时间窗的车辆路径问题。设计了一种实数编码方案,将离散的问题转为连续优化问题。采用邻域搜索帮助具备一定学习能力的个体提高寻优速度;采用禁忌搜索帮助部分个体跳出局部最优点,增强全局寻优性能。实验结果表明,该算法可以更有效地求出优化解,是带时间窗车辆路径问题的一种有效求解算法。     

基于Memetic算法的要地防空优化部署方法

火力单元优化部署问题是网络化防空火控系统的一个重要研究内容. 本文将要地防空优化部署作为组合优化问题, 优化目标为最大化部署方案对保护要地的防御贡献程度, 约束主要考虑了地理条件和火力资源. 利用网格离散化思想对防区进行划分, 对部署方案、火力覆盖能力、约束条件以及火力覆盖要求等条件进行了表征, 建立了问题的数学模型. 构造了一种基于Memetic算法的优化求解方法, 运用遗传算法和邻域搜索作为全局和局部搜索方法, 用解的构造方式和选择策略处理了约束条件,比较了局部搜索使用不同邻域时算法的运行效率. 最后通过实验验证了本方法的合理性和有效性.     

A surrogate-assisted evolutionary algorithm based on the genetic diversity objective

In this work, a novel surrogate-assisted memetic algorithm is proposed which is based on the preservation of genetic diversity within the population. The aim of the algorithm is to solve multi-objective optimization problems featuring computationally expensive fitness functions in an efficient manner. The main novelty is the use of an evolutionary algorithm as global searcher that treats the genetic diversity as an objective during the evolution and uses it, together with a non-dominated sorting approach, to assign the ranks. This algorithm, coupled with a gradient-based algorithm as local searcher and a back-propagation neural network as global surrogate model, demonstrates to provide a reliable and effective balance between exploration and exploitation. A detailed performance analysis has been conducted on five commonly used multi-objective problems, each one involving distinct features that can make the convergence difficult toward the Pareto-optimal front. In most cases, the proposed algorithm outperformed the other state-of-the-art evolutionary algorithms considered in the comparison, assuring higher repeatability on the final non-dominated set, deeper convergence level and higher convergence rate. It also demonstrates a clear ability to widely cover the Pareto-optimal front with larger percentage of non-dominated solutions if compared to the total number of function evaluations.     

A RBF-based constrained global optimization algorithm for problems with computationally expensive objective and constraints

This paper presents a metamodel-based constrained optimization method, called Radial basis function-based Constrained Global Optimization (RCGO), to solve optimization problems involving computationally expensive objective function and inequality constraints. RCGO is an extension of the adaptive metamodel-based global optimization (AMGO) algorithm which can handle unconstrained black-box optimization problems. Firstly, a sequential sampling method is implemented to obtain the initial points for building the radial basis function (RBF) approximations to all computational expensive functions while enforcing a feasible solution. Then, an auxiliary objective function subject to the approximate constraints is constructed to determine the next iterative point and further improve the solution. During the process, a distance function with a group of exponents is introduced in the auxiliary function to balance the local exploitation and the global exploration. The RCGO method is tested on a series of benchmark problems, and the results demonstrate that RCGO needs fewer costly evaluations and can be applied for costly constrained problems with all infeasible start points. And the test results on the 30D problems demonstrate that RCGO has advantages in solving the problems. The proposed method is then applied to the design of a cycloid gear pump and desirable results are obtained.     

混沌时间序列的混合粒子群优化预测

提出一种混合粒子群优化算法,即在改进粒子群优化算法全局搜索模型参数的基础上,利用梯度下降法进一步确定径向基神经网络模型参数,以提高网络的收敛精度和网络性能.采用基于RBFNN的混合粒子群优化算法进行离散Henon和连续Mackey-Glass混沌时间序列预测仿真,结果表明该算法能快速精确地预测混沌时间序列,是研究复杂非线性动力系统辨识和控制的一种有效方法.     

Learning algorithm for multimodal optimization

We present a new evolutionary algorithm—“learning algorithm” for multimodal optimization. The scheme for reproducing a new generation is very simple. Control parameters, of the length of the list of historical best solutions and the “learning probability” of the current solutions being moved towards the current best solutions and towards the historical ones, are used to assign different search intensities to different parts of the feasible area and to direct the updating of the current solutions. Results of numerical tests on minimization of the 2D Schaffer function, the 2D Shubert function and the 10D Ackley function show that this algorithm is effective and efficient in finding multiple global solutions of multimodal optimization problems.     

A self-adaptive linear evolutionary algorithm for solving constrained optimization problems

In many real-world applications of evolutionary algorithms, the fitness of an individual requires a quantitative measure. This paper proposes a self-adaptive linear evolutionary algorithm (ALEA) in which we introduce a novel strategy for evaluating individual’s relative strengths and weaknesses. Based on this strategy, searching space of constrained optimization problems with high dimensions for design variables is compressed into two-dimensional performance space in which it is possible to quickly identify ‘good’ individuals of the performance for a multiobjective optimization application, regardless of original space complexity. This is considered as our main contribution. In addition, the proposed new evolutionary algorithm combines two basic operators with modification in reproduction phase, namely, crossover and mutation. Simulation results over a comprehensive set of benchmark functions show that the proposed strategy is feasible and effective, and provides good performance in terms of uniformity and diversity of solutions.