Memetic algorithm using multi-surrogates for computationally expensive optimization problems

In this paper, we present a multi-surrogates assisted memetic algorithm for solving optimization problems with computationally expensive fitness functions. The essential backbone of our framework is an evolutionary algorithm coupled with a local search solver that employs multi-surrogate in the spirit of Lamarckian learning. Inspired by the notion of ‘blessing and curse of uncertainty’ in approximation models, we combine regression and exact interpolating surrogate models in the evolutionary search. Empirical results are presented for a series of commonly used benchmark problems to demonstrate that the proposed framework converges to good solution quality more efficiently than the standard genetic algorithm, memetic algorithm and surrogate-assisted memetic algorithms.     

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

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.     

ParEGO: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems

This paper concerns multiobjective optimization in scenarios where each solution evaluation is financially and/or temporally expensive. We make use of nine relatively low-dimensional, nonpathological, real-valued functions, such as arise in many applications, and assess the performance of two algorithms after just 100 and 250 (or 260) function evaluations. The results show that NSGA-II, a popular multiobjective evolutionary algorithm, performs well compared with random search, even within the restricted number of evaluations used. A significantly better performance (particularly, in the worst case) is, however, achieved on our test set by an algorithm proposed herein-ParEGO-which is an extension of the single-objective efficient global optimization (EGO) algorithm of Jones et al. ParEGO uses a design-of-experiments inspired initialization procedure and learns a Gaussian processes model of the search landscape, which is updated after every function evaluation. Overall, ParEGO exhibits a promising performance for multiobjective optimization problems where evaluations are expensive or otherwise restricted in number.     

A rigorous framework for optimization of expensive functions by surrogates

The goal of the research reported here is to develop rigorous optimization algorithms to apply to some engineering design problems for which direct application of traditional optimization approaches is not practical. This paper presents and analyzes a framework for generating a sequence of approximations to the objective function and managing the use of these approximations as surrogates for optimization. The result is to obtain convergence to a minimizer of an expensive objective function subject to simple constraints. The approach is widely applicable because it does not require, or even explicitly approximate, derivatives of the objective. Numerical results are presented for a 31-variable helicopter rotor blade design example and for a standard optimization test example.     

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

A tutorial on multiobjective optimization: fundamentals and evolutionary methods

In almost no other field of computer science, the idea of using bio-inspired search paradigms has been so useful as in solving multiobjective optimization problems. The idea of using a population of search agents that collectively approximate the Pareto front resonates well with processes in natural evolution, immune systems, and swarm intelligence. Methods such as NSGA-II, SPEA2, SMS-EMOA, MOPSO, and MOEA/D became standard solvers when it comes to solving multiobjective optimization problems. This tutorial will review some of the most important fundamentals in multiobjective optimization and then introduce representative algorithms, illustrate their working principles, and discuss their application scope. In addition, the tutorial will discuss statistical performance assessment. Finally, it highlights recent important trends and closely related research fields. The tutorial is intended for readers, who want to acquire basic knowledge on the mathematical foundations of multiobjective optimization and state-of-the-art methods in evolutionary multiobjective optimization. The aim is to provide a starting point for researching in this active area, and it should also help the advanced reader to identify open research topics.     

A two-stage adaptive multi-fidelity surrogate model-assisted multi-objective genetic algorithm for computationally expensive problems

Surrogate model-assisted multi-objective genetic algorithms (MOGA) show great potential in solving engineering design problems since they can save computational cost by reducing the calls of expensive simulations. In this paper, a two-stage adaptive multi-fidelity surrogate (MFS) model-assisted MOGA (AMFS-MOGA) is developed to further relieve their computational burden. In the warm-up stage, a preliminary Pareto frontier is obtained relying only on the data from the low-fidelity (LF) model. In the second stage, an initial MFS model is constructed based on the data from both LF and high-fidelity (HF) models at the samples, which are selected from the preliminary Pareto set according to the crowding distance in the objective space. Then the fitness values of individuals are evaluated using the MFS model, which is adaptively updated according to two developed strategies, an individual-based updating strategy and a generation-based updating strategy. The former considers the prediction uncertainty from the MFS model, while the latter takes the discrete degree of the population into consideration. The effectiveness and merits of the proposed AMFS-MOGA approach are illustrated using three benchmark tests and the design optimization of a stiffened cylindrical shell. The comparisons between the proposed AMFS-MOGA approach and some existing approaches considering the quality of the obtained Pareto frontiers and computational efficiency are made. The results show that the proposed AMFS-MOGA method can obtain Pareto frontiers comparable to that obtained by the MOGA with HF model, while significantly reducing the number of evaluations of the expensive HF model.

     

A computational intelligence algorithm for expensive engineering optimization problems

The modern engineering design optimization process often replaces laboratory experiments with computer simulations, which leads to expensive black-box optimization problems. Such problems often contain candidate solutions which cause the simulation to fail, and therefore they will have no objective value assigned to them, a scenario which degrades the search effectiveness. To address this, this paper proposes a new computational intelligence optimization algorithm which incorporates a classifier into the optimization search. The classifier predicts which solutions are expected to cause a simulation failure, and its prediction is used to bias the search towards solutions for which the simulation is expected to succeed. To further enhance the search effectiveness, the proposed algorithm continuously adapts during the search the type of model and classifier being used. A rigorous performance analysis using a representative application of airfoil shape optimization shows that the proposed algorithm outperformed existing approaches in terms of the final result obtained, and performed a search with a competitively low number of failed evaluations. Analysis also highlights the contribution of incorporating the classifier into the search, and of the model and classifier selection steps.     

A local multiobjective optimization algorithm using neighborhood field

A new local search algorithm for multiobjective optimization problems is proposed to find the global optima accurately and diversely. This paper models the cooperatively local search as a potential field, which is called neighborhood field model (NFM). Using NFM, a new Multiobjective Neighborhood Field Optimization (MONFO) algorithm is proposed. In MONFO, the neighborhood field can drive each individual moving towards the superior neighbor and away from the inferior neighbor. MONFO is compared with other popular multiobjective algorithms under twelve test functions. Intensive simulations show that MONFO is able to deliver promising results in the respects of accuracy and diversity, especially for multimodal problems.     

A multiobjective optimization solver using rank-niche evolution strategy

A rank-niche evolution strategy (RNES) algorithm has been developed in this paper to solve unconstrained multiobjective optimization problems. A required number of Pareto-optimal solutions can be generated by the algorithm in a single run. In addition to the operations of recombination, mutation and selection used in original evolution strategy (ES), an external elite set which contains a given number of non-dominated elites is updated and trimmed by a clustering technique to maintain a uniformly distributed Pareto front. The fitness function for each individual contains the information of rank and crowding status. The selection operation using this fitness function considers the superiority and distribution simultaneously. Eight test problems illustrated in other papers are used to test RNES. For some test problems the Pareto-optimal solutions obtained by RNES are better than those obtained by GA-based algorithms.     

Solving multiobjective optimization problems using quasi-separable MDO formulations and analytical target cascading

One approach to multiobjective optimization is to define a scalar substitute objective function that aggregates all objectives and solve the resulting aggregate optimization problem (AOP). In this paper, we discern that the objective function in quasi-separable multidisciplinary design optimization (MDO) problems can be viewed as an aggregate objective function (AOF). We consequently show that a method that can solve quasi-separable problems can also be used to obtain Pareto points of associated AOPs. This is useful when AOPs are too hard to solve or when the design engineer does not have access to the models necessary to evaluate all the terms of the AOF. In this case, decomposition-based design optimization methods can be useful to solve the AOP as a quasi-separable MDO problem. Specifically, we use the analytical target cascading methodology to formulate decomposed subproblems of quasi-separable MDO problems and coordinate their solution in order to obtain Pareto points of the associated AOPs. We first illustrate the approach using a well-known simple geometric programming example and then present a vehicle suspension design problem with three objectives related to ground vehicle ride and handling.     

Tree decomposition and discrete optimization problems: A survey

The paper considers tree decomposition methods as applied to discrete optimization and presents relevant mathematical results. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 102–118, July–August 2007.     

Solution of multiobjective optimization problems: coevolutionary algorithm based on evolutionary game theory

When attempting to solve multiobjective optimization problems (MOPs) using evolutionary algorithms, the Pareto genetic algorithm (GA) has now become a standard of sorts. After its introduction, this approach was further developed and led to many applications. All of these approaches are based on Pareto ranking and use the fitness sharing function to keep diversity. On the other hand, the scheme for solving MOPs presented by Nash introduced the notion of Nash equilibrium and aimed at solving MOPs that originated from evolutionary game theory and economics. Since the concept of Nash Equilibrium was introduced, game theorists have attempted to formalize aspects of the evolutionary equilibrium. Nash genetic algorithm (Nash GA) is the idea to bring together genetic algorithms and Nash strategy. The aim of this algorithm is to find the Nash equilibrium through the genetic process. Another central achievement of evolutionary game theory is the introduction of a method by which agents can play optimal strategies in the absence of rationality. Through the process of Darwinian selection, a population of agents can evolve to an evolutionary stable strategy (ESS). In this article, we find the ESS as a solution of MOPs using a coevolutionary algorithm based on evolutionary game theory. By applying newly designed coevolutionary algorithms to several MOPs, we can confirm that evolutionary game theory can be embodied by the coevolutionary algorithm and this coevolutionary algorithm can find optimal equilibrium points as solutions for an MOP. We also show the optimization performance of the co-evolutionary algorithm based on evolutionary game theory by applying this model to several MOPs and comparing the solutions with those of previous evolutionary optimization models. This work was presented, in part, at the 8th International Symposium on Artificial Life and Robotics, Oita, Japan, January 24#x2013;26, 2003.     

An efficient class of direct search surrogate methods for solving expensive optimization problems with CPU-time-related functions

In this paper, we characterize a new class of computationally expensive optimization problems and introduce an approach for solving them. In this class of problems, objective function values may be directly related to the computational time required to obtain them, so that, as the optimal solution is approached, the computational time required to evaluate the objective is significantly less than at points farther away from the solution. This is motivated by an application in which each objective function evaluation requires both a numerical fluid dynamics simulation and an image registration process, and the goal is to find the parameter values of a predetermined reference image by comparing the flow dynamics from the numerical simulation and the reference image through the image comparison process. In designing an approach to numerically solve the more general class of problems in an efficient way, we make use of surrogates based on CPU times of previously evaluated points, rather than their function values, all within the search step framework of mesh adaptive direct search algorithms. Because of the expected positive correlation between function values and their CPU times, a time cutoff parameter is added to the objective function evaluation to allow its termination during the comparison process if the computational time exceeds a specified threshold. The approach was tested using the NOMADm and DACE MATLAB? software packages, and results are presented.     

Dynamic multiobjective optimization problems: test cases, approximations, and applications

After demonstrating adequately the usefulness of evolutionary multiobjective optimization (EMO) algorithms in finding multiple Pareto-optimal solutions for static multiobjective optimization problems, there is now a growing need for solving dynamic multiobjective optimization problems in a similar manner. In this paper, we focus on addressing this issue by developing a number of test problems and by suggesting a baseline algorithm. Since in a dynamic multiobjective optimization problem, the resulting Pareto-optimal set is expected to change with time (or, iteration of the optimization process), a suite of five test problems offering different patterns of such changes and different difficulties in tracking the dynamic Pareto-optimal front by a multiobjective optimization algorithm is presented. Moreover, a simple example of a dynamic multiobjective optimization problem arising from a dynamic control loop is presented. An extension to a previously proposed direction-based search method is proposed for solving such problems and tested on the proposed test problems. The test problems introduced in this paper should encourage researchers interested in multiobjective optimization and dynamic optimization problems to develop more efficient algorithms in the near future.     

Multi-criteria human resource allocation for solving multistage combinatorial optimization problems using multiobjective hybrid genetic algorithm

Multi-criteria human resource allocation involves deciding how to divide human resource of limited availability among multiple demands in a way that optimizes current objectives. In this paper, we focus on multi-criteria human resource allocation for solving multistage combinatorial optimization problem. Hence we tackle this problem via a multistage decision-making model. A multistage decision-making model is similar to a complex problem solving, in which a suitable sequence of decisions is to be found. The task can be interpreted as a series of interactions between a decision maker and an outside world, at each stage of which some decisions are available and their immediate effect can be easily computed. Eventually, goals would be reached due to the found of optimized variables. In order to obtain a set of Pareto solutions efficiently, we propose a multiobjective hybrid genetic algorithm (mohGA) approach based on the multistage decision-making model for solving combinatorial optimization problems. According to the proposed method, we apply the mohGA to seek feasible solutions for all stages. The effectiveness of the proposed algorithm was validated by its application to an illustrative example dealing with multiobjective resource allocation problem.     

The application of gradient-only optimization methods for problems discretized using non-constant methods

We study the minimization of objective functions containing non-physical jump discontinuities. These discontinuities arise when (partial) differential equations are discretized using non-constant methods and the resulting numerical solutions are used in computing the objective function. Although the functions may become discontinuous, gradient information may be computed at every point. Gradient information is computable everywhere since every point has an associated discretization for which (semi) analytical sensitivities can be calculated. Rather than the construction of global approximations using only function value information to overcome the discontinuities, we propose to use only the gradient information. We elaborate on the modifications of classical gradient based optimization algorithms for use in gradient-only approaches, and we then present gradient-only optimization strategies using both BFGS and a new spherical quadratic approximation for sequential approximate optimization (SAO). We then use the BFGS and SAO algorithms to solve three problems of practical interest, both unconstrained and constrained.     

A jumping genes inspired multi-objective differential evolution algorithm for microwave components optimization problems

Exploitation and exploration are equally important for multi-objective evolutionary algorithms (MOEAs) to approximate the optimal Pareto Front (PF). However, most existing multi-objective differential evolution algorithms (MODEs) focus on exploitation with proposals of elitism methods that may result in poor diversity or sticking into local optimal front. Inspired by a biological discovery, this study proposes a jumping genes based MODE algorithm, termed as JGDE with two components. The first component is the application of jumping genes operator to MODE to promote population diversity while in the second component, an elitism leading mechanism is designed to accelerate the convergence. Experimental studies show the superiority of JGDE over other competitive algorithms in both convergence and diversity. More importantly, JGDE can deal with local optimal fronts that are difficult to handle by the existing MODEs. The studies are also further verified by the solvement of a practical microwave components optimization problem and the comparison between different optimization algorithms.