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算法。算法结合了粒子群优化的全局搜索能力和爬山法的局部搜索能力,增强了算法搜索最优解的能力。实验结果表明,该算法求解精度较高,且收敛速度较快。     

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.     

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.     

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.     

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.     

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.     

Learning experiments with genetic optimization of a generalized regression neural network

This paper reports a study unifying optimization by genetic algorithm with a generalized regression neural network. Experiments compare hill-climbing optimization with that of a genetic algorithm, both in conjunction with a generalized regression neural network. Controlled data with nine independent variables are used in combination with conjunctive and compensatory decision forms, having zero percent and 10 percent noise levels. Results consistently favor the GRNN unified with the genetic algorithm.     

A hybrid particle swarm optimization algorithm for high-dimensional problems

In recent years, particle swarm optimization (PSO) emerges as a new optimization scheme that has attracted substantial research interest due to its simplicity and efficiency. However, when applied to high-dimensional problems, PSO suffers from premature convergence problem which results in a low optimization precision or even failure. To remedy this fault, this paper proposes a novel memetic PSO (CGPSO) algorithm which combines the canonical PSO with a Chaotic and Gaussian local search procedure. In the initial evolution phase, CGPSO explores a wide search space that helps avoid premature convergence through Chaotic local search. Then in the following run phase, CGPSO refines the solutions through Gaussian optimization. To evaluate the effectiveness and efficiency of the CGPSO algorithm, thirteen high dimensional non-linear scalable benchmark functions were examined. Results show that, compared to the standard PSO, CGPSO is more effective, faster to converge, and less sensitive to the function dimensions. The CGPSO was also compared with two PSO variants, CPSO-H, DMS-L-PSO, and two memetic optimizers, DEachSPX and MA-S2. CGPSO is able to generate a better, or at least comparable, performance in terms of optimization accuracy. So it can be safely concluded that the proposed CGPSO is an efficient optimization scheme for solving high-dimensional problems.     

Solving multiobjective problems using cat swarm optimization

This paper proposes a new multiobjective evolutionary algorithm (MOEA) by extending the existing cat swarm optimization (CSO). It finds the nondominated solutions along the search process using the concept of Pareto dominance and uses an external archive for storing them. The performance of our proposed approach is demonstrated using standard test functions. A quantitative assessment of the proposed approach and the sensitivity test of different parameters is carried out using several performance metrics. The simulation results reveal that the proposed approach can be a better candidate for solving multiobjective problems (MOPs).     

Disturbed Exploitation compact Differential Evolution for limited memory optimization problems

This paper proposes a novel and unconventional Memetic Computing approach for solving continuous optimization problems characterized by memory limitations. The proposed algorithm, unlike employing an explorative evolutionary framework and a set of local search algorithms, employs multiple exploitative search within the main framework and performs a multiple step global search by means of a randomized perturbation of the virtual population corresponding to a periodical randomization of the search for the exploitative operators. The proposed Memetic Computing approach is based on a populationless (compact) evolutionary framework which, instead of processing a population of solutions, handles its statistical model. This evolutionary framework is based on a Differential Evolution which cooperatively employs two exploitative search operators: the first is based on a standard Differential Evolution mutation and exponential crossover, and the second is the trigonometric mutation. These two search operators have an exploitative action on the algorithmic framework and thus contribute to the rapid convergence of the virtual population towards promising candidate solutions. The action of these search operators is counterbalanced by a periodical stochastic perturbation of the virtual population, which has the role of “disturbing” the excessively exploitative action of the framework and thus inhibits its premature convergence. The proposed algorithm, namely Disturbed Exploitation compact Differential Evolution, is a simple and memory-wise cheap structure that makes use of the Memetic Computing paradigm in order to solve complex optimization problems. The proposed approach has been tested on a set of various test problems and compared with state-of-the-art compact algorithms and with some modern population based meta-heuristics. Numerical results show that Disturbed Exploitation compact Differential Evolution significantly outperforms all the other compact algorithms present in literature and reaches a competitive performance with respect to modern population algorithms, including some memetic approaches and complex modern Differential Evolution based algorithms. In order to show the potential of the proposed approach in real-world applications, Disturbed Exploitation compact Differential Evolution has been implemented for performing the control of a space robot by simulating the implementation within the robot micro-controller. Numerical results show the superiority of the proposed algorithm with respect to other modern compact algorithms present in literature.     

Memetic algorithm with route decomposing for periodic capacitated arc routing problem

In this paper, the Periodic Capacitated Arc Routing Problem (PCARP) is investigated. PCARP is an extension of the well-known CARP from a single period to a multi-period horizon. In PCARP, two objectives are to be minimized. One is the number of required vehicles (nv), and the other is the total cost (tc). Due to the multi-period nature, given the same graph or road network, PCARP can have a much larger solution space than the single-period CARP counterpart. Furthermore, PCARP consists of an additional allocation sub-problem (of the days to serve the arcs), which is interdependent with the routing sub-problem. Although some attempts have been made for solving PCARP, more investigations are yet to be done to further improve their performance especially on large-scale problem instances. It has been shown that optimizing nv and tc separately (hierarchically) is a good way of dealing with the two objectives. In this paper, we further improve this strategy and propose a new Route Decomposition (RD) operator thereby. Then, the RD operator is integrated into a Memetic Algorithm (MA) framework for PCARP, in which novel crossover and local search operators are designed accordingly. In addition, to improve the search efficiency, a hybridized initialization is employed to generate an initial population consisting of both heuristic and random individuals. The MA with RD (MARD) was evaluated and compared with the state-of-the-art approaches on two benchmark sets of PCARP instances and a large data set which is based on a real-world road network. The experimental results suggest that MARD outperforms the compared state-of-the-art algorithms, and improves most of the best-known solutions. The advantage of MARD becomes more obvious when the problem size increases. Thus, MARD is particularly effective in solving large-scale PCARP instances. Moreover, the efficacy of the proposed RD operator in MARD has been empirically verified.     

A memetic algorithm for extending wireless sensor network lifetime

Extending the lifetime during which a wireless sensor network (WSN) can cover all targets is a key issue in WSN applications such as surveillance. One effective method is to partition the collection of sensors into several covers, each of which must include all targets, and then to activate these covers one by one. Therefore, more covers enable longer lifetime. The problem of finding the maximum number of covers has been modeled as the SET K-COVER problem, which has been proven to be NP-complete. This study proposes a memetic algorithm to solve this problem. The memetic algorithm utilizes the Darwinian evolutionary scheme and Lamarckian local enhancement to search for optima given the considerations of global exploration and local exploitation. Additionally, the proposed algorithm does not require an upper bound or any assumption about the maximum number of covers. The simulation results on numerous problem instances confirm that the algorithm significantly outperforms several heuristic and evolutionary algorithms in terms of solution quality, which demonstrate the effectiveness of the proposed algorithm in extending WSN lifetime.     

Multiobjective structural optimization using a microgenetic algorithm

In this paper, we present a genetic algorithm with a very small population and a reinitialization process (a microgenetic algorithm) for solving multiobjective optimization problems. Our approach uses three forms of elitism, including an external memory (or secondary population) to keep the nondominated solutions found along the evolutionary process. We validate our proposal using several engineering optimization problems taken from the specialized literature and compare our results with respect to two other algorithms (NSGA-II and PAES) using three different metrics. Our results indicate that our approach is very efficient (computationally speaking) and performs very well in problems with different degrees of complexity.     

Hybrid evolutionary algorithm and application to structural optimization

This paper introduces a new evolutionary algorithm with a globally stochastic but locally heuristic search strategy. It is implemented by incorporating a modified micro-genetic algorithm with two local optimization operators. Performance tests using two benchmarking functions demonstrate that the new algorithm has excellent convergence performance when applied to multimodal optimization problems. The number of objective function evaluations required to obtain global optima is only 3.5–3.7% of that of using the conventional micro-genetic algorithm. The new algorithm is used to optimize the design of an 18-bar truss, with the aim of minimizing its weight while meeting the stress, section area, and geometry constraints. The corresponding optimal design is obtained with considerably fewer computational operations than required for the existing algorithms.     

Structure optimization based on memetic algorithm for adjusting epidemic threshold on complex networks

Many social spreading phenomena can be modeled as epidemic spreading models over networks, and the studies of these phenomena are important to avoid epidemic outbreaks. Epidemic threshold of the network, which fundamentally depends on the network structure itself, is a critical measure to judge whether the epidemic dies out or results in an epidemic breakout. In this study, epidemic threshold is regarded as the objective function to control the spreading process. In addition, an efficient structure optimization strategy based on memetic algorithm is proposed to adjust the spreading threshold without changing the degree of each node. Lowering the threshold can promote the spreading process whereas heightening the threshold can prevent the spreading process. In the proposed algorithm, genetic algorithm is adopted as the global search strategy and a modified simulated annealing algorithm combined with the properties of networks is proposed as the local search strategy. Experiments on computer-generated and real-world networks demonstrate that the proposed algorithm has superior performances for both the threshold minimization and maximization problems.     

求解函数优化问题的改进布谷鸟搜索算法

为了提高布谷鸟搜索算法求解函数优化问题的求精能力和收敛速度,提出了一种基于自适应机制的改进算法.自适应机制用于控制缩放因子和发现概率,以提高种群的多样性,避免早熟,从而使更多的个体参与演化,达到提高求精能力和收敛速度的效果.仿真实验结果表明,与标准的布谷鸟搜索算法相比,基于自适应机制缩放因子的改进算法(rCS)和基于自适应机制发现概率的改进算法(paCS)在求精能力和收敛速度上都有明显的提高;同时具有自适应缩放因子和自适应发现概率的改进算法(iCS)比rCS和paCS具有更优的求精能力和收敛速度.     

Blended biogeography-based optimization for constrained optimization

Biogeography-based optimization (BBO) is a new evolutionary optimization method that is based on the science of biogeography. We propose two extensions to BBO. First, we propose a blended migration operator. Benchmark results show that blended BBO outperforms standard BBO. Second, we employ blended BBO to solve constrained optimization problems. Constraints are handled by modifying the BBO immigration and emigration procedures. The approach that we use does not require any additional tuning parameters beyond those that are required for unconstrained problems. The constrained blended BBO algorithm is compared with solutions based on a stud genetic algorithm (SGA) and standard particle swarm optimization 2007 (SPSO 07). The numerical results demonstrate that constrained blended BBO outperforms SGA and performs similarly to SPSO 07 for constrained single-objective optimization problems.     

An efficient multi-objective optimization method for black-box functions using sequential approximate technique

Multi-objective optimization problems in practical engineering usually involve expensive black-box functions. How to reduce the number of function evaluations at a good approximation of Pareto frontier has been a crucial issue. To this aim, an efficient multi-objective optimization method based on a sequential approximate technique is suggested in this paper. In each iteration, according to the prediction of radial basis function with a micro multi-objective genetic algorithm, an extended trust region updating strategy is adopted to adjust the design region, a sample inheriting strategy is presented to reduce the number of new function evaluations, and then a local-densifying strategy is proposed to improve the accuracy of approximations in concerned regions. At the end of each iteration, the obtained actual Pareto optimal points are stored in an external archive and are updated as the iteration process. The effect of the present method is demonstrated by eight test functions. Finally, it is employed to perform the structure optimization of a vehicle door.