Parallel radial basis function methods for the global optimization of expensive functions

We introduce a master–worker framework for parallel global optimization of computationally expensive functions using response surface models. In particular, we parallelize two radial basis function (RBF) methods for global optimization, namely, the RBF method by Gutmann [Gutmann, H.M., 2001a. A radial basis function method for global optimization. Journal of Global Optimization 19(3), 201–227] (Gutmann-RBF) and the RBF method by Regis and Shoemaker [Regis, R.G., Shoemaker, C.A., 2005. Constrained global optimization of expensive black box functions using radial basis functions, Journal of Global Optimization 31, 153–171] (CORS-RBF). We modify these algorithms so that they can generate multiple points for simultaneous evaluation in parallel. We compare the performance of the two parallel RBF methods with a parallel multistart derivative-based algorithm, a parallel multistart derivative-free trust-region algorithm, and a parallel evolutionary algorithm on eleven test problems and on a 6-dimensional groundwater bioremediation application. The results indicate that the two parallel RBF algorithms are generally better than the other three alternatives on most of the test problems. Moreover, the two parallel RBF algorithms have comparable performances on the test problems considered. Finally, we report good speedups for both parallel RBF algorithms when using a small number of processors.     

An adaptive radial basis algorithm (ARBF) for expensive black-box global optimization

Powerful response surface methods based on kriging and radial basis function (RBF) interpolation have been developed for expensive, i.e. computationally costly, global nonconvex optimization. We have implemented some of these methods in the solvers rbfSolve and EGO in the TOMLAB Optimization Environment (http://www.tomopt.com/tomlab/). In this paper we study algorithms based on RBF interpolation. The practical performance of the RBF algorithm is sensitive to the initial experimental design, and to the static choice of target values. A new adaptive radial basis interpolation (ARBF) algorithm, suitable for parallel implementation, is presented. The algorithm is described in detail and its efficiency is analyzed on the standard test problem set of Dixon–Szegö. Results show that it outperforms the published results of rbfSolve and several other solvers.     

A metamodel-assisted evolutionary algorithm for expensive optimization

Expensive optimization aims to find the global minimum of a given function within a very limited number of function evaluations. It has drawn much attention in recent years. The present expensive optimization algorithms focus their attention on metamodeling techniques, and call existing global optimization algorithms as subroutines. So it is difficult for them to keep a good balance between model approximation and global search due to their two-part property. To overcome this difficulty, we try to embed a metamodel mechanism into an efficient evolutionary algorithm, low dimensional simplex evolution (LDSE), in this paper. The proposed algorithm is referred to as the low dimensional simplex evolution extension (LDSEE). It is inherently parallel and self-contained. This renders it very easy to use. Numerical results show that our proposed algorithm is a competitive alternative for expensive optimization problems.     

Improved Strategies for Radial basis Function Methods for Global Optimization

We propose some strategies that can be shown to improve the performance of the radial basis function (RBF) method by Gutmann [J. Global optim. 19(3), 201–227 (2001a)] (Gutmann-RBF) and the RBF method by Regis and Shoemaker [J. Global optim. 31, 153–171 (2005)] (CORS–RBF) on some test problems when they are initialized by symmetric Latin hypercube designs (SLHDs). Both methods are designed for the global optimization of computationally expensive functions with multiple local optima. We demonstrate how the original implementation of Gutmann-RBF can sometimes converge slowly to the global minimum on some test problems because of its failure to do local search. We then propose Controlled Gutmann-RBF (CG-RBF), which is a modification of Gutmann-RBF where the function evaluation point in each iteration is restricted to a subregion of the domain centered around a global minimizer of the current RBF model. By varying the size of this subregion in different iterations, we ensure a better balance between local and global search. Moreover, we propose a complete restart strategy for CG-RBF and CORS-RBF whenever the algorithm fails to make any substantial progress after some threshold number of consecutive iterations. Computational experiments on the seven Dixon and Szegö [Towards Global optimization, pp. 1–13. North-Holland, Amsterdam (1978)] test problems and on nine Schoen [J. Global optim. 3, 133–137 (1993)] test problems indicate that the proposed strategies yield significantly better performance on some problems. The results also indicate that, for some fixed setting of the restart parameters, the two modified RBF algorithms, namely CG-RBF-Restart and CORS-RBF-Restart, are comparable on the test problems considered. Finally, we examine the sensitivity of CG-RBF-Restart and CORS-RBF-Restart to the restart parameters.     

服务台不可靠的重试排队系统均衡分析

本文研究服务台不可靠的M/M/1常数率重试排队系统中顾客的均衡进队策略, 其中服务台在正常工作和空闲状态下以不同的速率发生故障。在该系统中, 服务台前没有等待空间, 如果到达的顾客发现服务台处于空闲状态, 该顾客可占用服务台开始服务。否则, 如果服务台处于忙碌状态, 顾客可以选择留下信息, 使得服务台在空闲时可以按顺序在重试空间中寻找之前留下信息的顾客进行服务。当服务台发生故障时, 正在被服务的顾客会发生丢失, 且系统拒绝新的顾客进入系统。根据系统提供给顾客的不同程度的信息, 研究队长可见和不可见两种信息情形下系统的稳态指标, 以及顾客基于收入-支出函数的均衡进队策略, 并建立单位时间内服务商的收益和社会福利函数。比较发现, 披露队长信息不一定能提高服务商收益和社会福利。     

Particle swarm optimization with age-group topology for multimodal functions and data clustering

This paper proposes particle swarm optimization with age-group topology (PSOAG), a novel age-based particle swarm optimization (PSO). In this work, we present a new concept of age to measure the search ability of each particle in local area. To keep population diversity during searching, we separate particles to different age-groups by their age and particles in each age-group can only select the ones in younger groups or their own groups as their neighbourhoods. To allow search escape from local optima, the aging particles are regularly replaced by new and randomly generated ones. In addition, we design an age-group based parameter setting method, where particles in different age-groups have different parameters, to accelerate convergence. This algorithm is applied to nonlinear function optimization and data clustering problems for performance evaluation. In comparison against several PSO variants and other EAs, we find that the proposed algorithm provides significantly better performances on both the function optimization problems and the data clustering tasks.     

Particle swarm with equilibrium strategy of selection for multi-objective optimization

A new ranking scheme based on equilibrium strategy of selection is proposed for multi-objective particle swarm optimization (MOPSO), and the preference ordering is used to identify the “best compromise” in the ranking stage. This scheme increases the selective pressure, especially when the number of objectives is very large. The proposed algorithm has been compared with other multi-objective evolutionary algorithms (MOEAs). The experimental results indicate that our algorithm produces better convergence performance.     

Balanced fuzzy particle swarm optimization

In the present study an extension of particle swarm optimization (PSO) algorithm which is in conformity with actual nature is introduced for solving combinatorial optimization problems. Development of this algorithm is essentially based on balanced fuzzy sets theory. The classical fuzzy sets theory cannot distinguish differences between positive and negative information of membership functions, while in the new method both kinds of information “positive and negative” about membership function are equally important. The balanced fuzzy particle swarm optimization algorithm is used for fundamental optimization problem entitled traveling salesman problem (TSP). For convergence inspecting of new algorithm, method was used for TSP problems. Convergence curves were represented fast convergence in restricted and low iterations for balanced fuzzy particle swarm optimization algorithm (BF-PSO) comparison with fuzzy particle swarm optimization algorithm (F-PSO).     

Particle swarm optimization: Hybridization perspectives and experimental illustrations

Metaheuristic optimization algorithms have become popular choice for solving complex and intricate problems which are otherwise difficult to solve by traditional methods. In the present study an attempt is made to review the hybrid optimization techniques in which one main algorithm is a well known metaheuristic; particle swarm optimization or PSO. Hybridization is a method of combining two (or more) techniques in a judicious manner such that the resulting algorithm contains the positive features of both (or all) the algorithms. Depending on the algorithm/s used we made three classifications as (i) Hybridization of PSO and genetic algorithms (ii) Hybridization of PSO with differential evolution and (iii) Hybridization of PSO with other techniques. Where, other techniques include various local and global search methods. Besides giving the review we also show a comparison of three hybrid PSO algorithms; hybrid differential evolution particle swarm optimization (DE-PSO), adaptive mutation particle swarm optimization (AMPSO) and hybrid genetic algorithm particle swarm optimization (GA-PSO) on a test suite of nine conventional benchmark problems.     

Hybrid evolutionary algorithm with Hermite radial basis function interpolants for computationally expensive adjoint solvers

In this paper, we present an evolutionary algorithm hybridized with a gradient-based optimization technique in the spirit of Lamarckian learning for efficient design optimization. In order to expedite gradient search, we employ local surrogate models that approximate the outputs of a computationally expensive Euler solver. Our focus is on the case when an adjoint Euler solver is available for efficiently computing the sensitivities of the outputs with respect to the design variables. We propose the idea of using Hermite interpolation to construct gradient-enhanced radial basis function networks that incorporate sensitivity data provided by the adjoint Euler solver. Further, we conduct local search using a trust-region framework that interleaves gradient-enhanced surrogate models with the computationally expensive adjoint Euler solver. This ensures that the present hybrid evolutionary algorithm inherits the convergence properties of the classical trust-region approach. We present numerical results for airfoil aerodynamic design optimization problems to show that the proposed algorithm converges to good designs on a limited computational budget.     

Preconditioning for radial basis functions with domain decomposition methods

In our previous work, an effective preconditioning scheme that is based upon constructing least-squares approximation cardinal basis functions (ACBFs) from linear combinations of the RBF-PDE matrix elements has shown very attractive numerical results. The preconditioner costs O(N²) flops to set up and O(N) storage. The preconditioning technique is sufficiently general that it can be applied to different types of different operators. This was applied to the 2D multiquadric method, with c~1/√N on the Poisson test problem, the preconditioned GMRES converges in tens of iterations. In this paper, we combine the RBF methods and the ACBF preconditioning technique with the domain decomposition method (DDM). We studied different implementations of the ACBF-DDM scheme and provide numerical results for N > 10,000 nodes. We shall demonstrate that the efficiency of the ACBF-DDM scheme improves dramatically as successively finer partitions of the domain are considered.     

Asymptotic coefficients for Gaussian radial basis function interpolants

Gaussian radial basis functions (RBFs) on an infinite interval with uniform grid pacing h are defined by ?(x;α,h)≡exp(-[α²/h²]x²). The only significant numerical parameter is α, the inverse width of the RBF functions relative to h. In the limit α→0, we demonstrate that the coefficients of the interpolant of a typical function f(x) grow proportionally to exp(π²/[4α²]). However, we also show that the approximation to the constant f(x)≡1 is a Jacobian theta function whose coefficients do not blow up as α→0. The subtle interplay between the complex-plane singularities of f(x) (the function being approximated) and the RBF inverse width parameter α are analyzed. For α≈1/2, the size of the RBF coefficients and the condition number of the interpolation matrix are both no larger than O(10⁴) and the error saturation is smaller than machine epsilon, so this α is the center of a “safe operating range” for Gaussian RBFs.     

Improved particle swarm algorithm for hydrological parameter optimization

In this paper, a new method named MSSE-PSO (master-slave swarms shuffling evolution algorithm based on particle swarm optimization) is proposed. Firstly, a population of points is sampled randomly from the feasible space, and then partitioned into several sub-swarms (one master swarm and other slave swarms). Each slave swarm independently executes PSO or its variants, including the update of particles’ position and velocity. For the master swarm, the particles enhance themselves based on the social knowledge of master swarm and that of slave swarms. At periodic stage in the evolution, the master swarm and the whole slave swarms are forced to mix, and points are then reassigned to several sub-swarms to ensure the share of information. The process is repeated until a user-defined stopping criterion is reached. The tests of numerical simulation and the case study on hydrological model show that MSSE-PSO remarkably improves the accuracy of calibration, reduces the time of computation and enhances the performance of stability. Therefore, it is an effective and efficient global optimization method.     

A rank based particle swarm optimization algorithm with dynamic adaptation

The particle swarm optimization (PSO) technique is a powerful stochastic evolutionary algorithm that can be used to find the global optimum solution in a complex search space. This paper presents a variation on the standard PSO algorithm called the rank based particle swarm optimizer, or PSO_rank, employing cooperative behavior of the particles to significantly improve the performance of the original algorithm. In this method, in order to efficiently control the local search and convergence to global optimum solution, the γ best particles are taken to contribute to the updating of the position of a candidate particle. The contribution of each particle is proportional to its strength. The strength is a function of three parameters: strivness, immediacy and number of contributed particles. All particles are sorted according to their fitness values, and only the γ best particles will be selected. The value of γ decreases linearly as the iteration increases. A time-varying inertia weight decreasing non-linearly is introduced to improve the performance. PSO_rank is tested on a commonly used set of optimization problems and is compared to other variants of the PSO algorithm presented in the literature. As a real application, PSO_rank is used for neural network training. The PSO_rank strategy outperformed all the methods considered in this investigation for most of the functions. Experimental results show the suitability of the proposed algorithm in terms of effectiveness and robustness.     

Integrating particle swarm optimization with genetic algorithms for solving nonlinear optimization problems

Heuristic optimization provides a robust and efficient approach for solving complex real-world problems. The aim of this paper is to introduce a hybrid approach combining two heuristic optimization techniques, particle swarm optimization (PSO) and genetic algorithms (GA). Our approach integrates the merits of both GA and PSO and it has two characteristic features. Firstly, the algorithm is initialized by a set of random particles which travel through the search space. During this travel an evolution of these particles is performed by integrating PSO and GA. Secondly, to restrict velocity of the particles and control it, we introduce a modified constriction factor. Finally, the results of various experimental studies using a suite of multimodal test functions taken from the literature have demonstrated the superiority of the proposed approach to finding the global optimal solution.     

On the selection of the most adequate radial basis function

Radial basis function (RBF) methods can provide excellent interpolants for a large number of poorly distributed data points. For any finite data set in any Euclidean space, one can construct an interpolation of the data by using RBFs. However, RBF interpolant trends between and beyond the data points depend on the RBF used and may exhibit undesirable trends using some RBFs while the trends may be desirable using other RBFs. The fact that a certain RBF is commonly used for the class of problems at hand, previous good behavior in that (or other) class of problems, and bibliography, are just some of the many valid reasons given to justify a priori selection of RBF. Even assuming that the justified choice of the RBF is most likely the correct choice, one should nonetheless confirm numerically that, in fact, the most adequate RBF for the problem at hand is the RBF chosen a priori. The main goal of this paper is to alert the analyst as to the danger of a priori selection of RBF and to present a strategy to numerically choose the most adequate RBF that better captures the trends of the given data set. The wing weight data fitting problem is used to illustrate the benefits of an adequate choice of RBF for each given data set.     

A novel hybrid differential evolution and particle swarm optimization algorithm for unconstrained optimization

An algorithm called DE-PSO is proposed which incorporates concepts from DE and PSO, updating particles not only by DE operators but also by mechanisms of PSO. The proposed algorithm is tested on several benchmark functions. Numerical comparisons with different hybrid meta-heuristics demonstrate its effectiveness and efficiency.     

Rational radial basis function interpolation with applications to antenna design

Functions with poles occur in many branches of applied mathematics which involve resonance phenomena. Such functions are challenging to interpolate, in particular in higher dimensions. In this paper we develop a technique for interpolation with quotients of two radial basis function (RBF) expansions to approximate such functions as an alternative to rational approximation. Since the quotient is not uniquely determined we introduce an additional constraint, the sum of the RBF-norms of the numerator and denominator squared should be minimal subjected to a norm condition on the function values. The method was designed for antenna design applications and we show by examples that the scattering matrix for a patch antenna as a function of some design parameters can be approximated accurately with the new method. In many cases, e.g. in antenna optimization, the function evaluations are time consuming, and therefore it is important to reduce the number of evaluations but still obtain a good approximation. A sensitivity analysis of the new interpolation technique is carried out and it gives indications how efficient adaptation methods could be devised. A family of such methods are evaluated on antenna data and the results show that much performance can be gained by choosing the right method.     

Enhanced speciation in particle swarm optimization for multi-modal problems

In this paper, we present a novel multi-modal optimization algorithm for finding multiple local optima in objective function surfaces. We build from Species-based particle swarm optimization (SPSO) by using deterministic sampling to generate new particles during the optimization process, by implementing proximity-based speciation coupled with speciation of isolated particles, and by including “turbulence regions” around already found solutions to prevent unnecessary function evaluations. Instead of using error threshold values, the new algorithm uses the particle’s experience, geometric mean, and “exclusion factor” to detect local optima and stop the algorithm. The performance of each extension is assessed with leave-it-out tests, and the results are discussed. We use the new algorithm called Isolated-Speciation-based particle swarm optimization (ISPSO) and a benchmark algorithm called Niche particle swarm optimization (NichePSO) to solve a six-dimensional rainfall characterization problem for 192 rain gages across the United States. We show why it is important to find multiple local optima for solving this real-world complex problem by discussing its high multi-modality. Solutions found by both algorithms are compared, and we conclude that ISPSO is more reliable than NichePSO at finding optima with a significantly lower objective function value.     

A cooperative swarm intelligence algorithm for multi-objective discrete optimization with application to the knapsack problem

We propose a novel cooperative swarm intelligence algorithm to solve multi-objective discrete optimization problems (MODP). Our algorithm combines a firefly algorithm (FA) and a particle swarm optimization (PSO). Basically, we address three main points: the effect of FA and PSO cooperation on the exploration of the search space, the discretization of the two algorithms using a transfer function, and finally, the use of the epsilon dominance relation to manage the size of the external archive and to guarantee the convergence and the diversity of Pareto optimal solutions.We compared the results of our algorithm with the results of five well-known meta-heuristics on nine multi-objective knapsack problem benchmarks. The experiments show clearly the ability of our algorithm to provide a better spread of solutions with a better convergence behavior.