A fast Pareto genetic algorithm approach for solving expensive multiobjective optimization problems

We present a new multiobjective evolutionary algorithm (MOEA), called fast Pareto genetic algorithm (FastPGA), for the simultaneous optimization of multiple objectives where each solution evaluation is computationally- and/or financially-expensive. This is often the case when there are time or resource constraints involved in finding a solution. FastPGA utilizes a new ranking strategy that utilizes more information about Pareto dominance among solutions and niching relations. New genetic operators are employed to enhance the proposed algorithm’s performance in terms of convergence behavior and computational effort as rapid convergence is of utmost concern and highly desired when solving expensive multiobjective optimization problems (MOPs). Computational results for a number of test problems indicate that FastPGA is a promising approach. FastPGA yields similar performance to that of the improved nondominated sorting genetic algorithm (NSGA-II), a widely-accepted benchmark in the MOEA research community. However, FastPGA outperforms NSGA-II when only a small number of solution evaluations are permitted, as would be the case when solving expensive MOPs.     

Evolutionary multiobjective optimization in noisy problem environments

This paper presents a multiobjective evolutionary algorithm (MOEA) capable of handling stochastic objective functions. We extend a previously developed approach to solve multiple objective optimization problems in deterministic environments by incorporating a stochastic nondomination-based solution ranking procedure. In this study, concepts of stochastic dominance and significant dominance are introduced in order to better discriminate among competing solutions. The MOEA is applied to a number of published test problems to assess its robustness and to evaluate its performance relative to NSGA-II. Moreover, a new stopping criterion is proposed, which is based on the convergence velocity of any MOEA to the true Pareto optimal front, even if the exact location of the true front is unknown. This stopping criterion is especially useful in real-world problems, where finding an appropriate point to terminate the search is crucial.     

Solving multiobjective,multiconstraint knapsack problems using mathematical programming and evolutionary algorithms

In this paper, we solve instances of the multiobjective multiconstraint (or multidimensional) knapsack problem (MOMCKP) from the literature, with three objective functions and three constraints. We use exact as well as approximate algorithms. The exact algorithm is a properly modified version of the multicriteria branch and bound (MCBB) algorithm, which is further customized by suitable heuristics. Three branching heuristics and a more general purpose composite branching and construction heuristic are devised. Comparison is made to the published results from another exact algorithm, the adaptive ε-constraint method [Laumanns, M., Thiele, L., Zitzler, E., 2006. An efficient, adaptive parameter variation scheme for Metaheuristics based on the epsilon-constraint method. European Journal of Operational Research 169, 932–942], using the same data sets. Furthermore, the same problems are solved using standard multiobjective evolutionary algorithms (MOEA), namely, the SPEA2 and the NSGAII. The results from the exact case show that the branching heuristics greatly improve the performance of the MCBB algorithm, which becomes faster than the adaptive ε -constraint. Regarding the performance of the MOEA algorithms in the specific problems, SPEA2 outperforms NSGAII in the degree of approximation of the Pareto front, as measured by the coverage metric (especially for the largest instance).     

A continuation approach to mode-finding of multivariate Gaussian mixtures and kernel density estimates

This paper presents a novel method of multi-objective optimization by learning automata (MOLA) to solve complex multi-objective optimization problems. MOLA consists of multiple automata which perform sequential search in the solution domain. Each automaton undertakes dimensional search in the selected dimension of the solution domain, and each dimension is divided into a certain number of cells. Each automaton performs a continuous search action, instead of discrete actions, within cells. The merits of MOLA have been demonstrated, in comparison with a multi-objective evolutionary algorithm based on decomposition (MOEA/D) and non-dominated sorting genetic algorithm II (NSGA-II), on eleven multi-objective benchmark functions and an optimal problem in the midwestern American electric power system which is integrated with wind power, respectively. The simulation results have shown that MOLA can obtain more accurate and evenly distributed Pareto fronts, in comparison with MOEA/D and NSGA-II.     

Evaluation of the multiobjective ant colony algorithm performances on biobjective quadratic assignment problems

The difficulty of resolving the multiobjective combinatorial optimization problems with traditional methods has directed researchers to investigate new approaches which perform better. In recent years some algorithms based on ant colony optimization (ACO) metaheuristic have been suggested to solve these multiobjective problems. In this study these algorithms have been reported and programmed both to solve the biobjective quadratic assignment problem (BiQAP) instances and to evaluate the performances of these algorithms. The robust parameter sets for each 12 multiobjective ant colony optimization (MOACO) algorithms have been calculated and BiQAP instances in the literature have been solved within these parameter sets. The performances of the algorithms have been evaluated by comparing the Pareto fronts obtained from these algorithms. In the evaluation step, a multi significance test is used in a non hierarchical structure, and a performance metric (P metric) essential for this test is introduced. Through this study, decision makers will be able to put in the biobjective algorithms in an order according to the priority values calculated from the algorithms’ Pareto fronts. Moreover, this is the first time that MOACO algorithms have been compared by solving BiQAPs.     

A Trust-Region Method for Unconstrained Multiobjective Problems with Applications in Satisficing Processes

Multiobjective optimization has a significant number of real-life applications. For this reason, in this paper we consider the problem of finding Pareto critical points for unconstrained multiobjective problems and present a trust-region method to solve it. Under certain assumptions, which are derived in a very natural way from assumptions used to establish convergence results of the scalar trust-region method, we prove that our trust-region method generates a sequence which converges in the Pareto critical way. This means that our generalized marginal function, which generalizes the norm of the gradient for the multiobjective case, converges to zero. In the last section of this paper, we give an application to satisficing processes in Behavioral Sciences. Multiobjective trust-region methods appear to be remarkable specimens of much more abstract satisficing processes, based on “variational rationality” concepts. One of their important merits is to allow for efficient computations. This is a striking result in Behavioral Sciences.     

Multiobjective evolutionary algorithms for complex portfolio optimization problems

This paper investigates the ability of Multiobjective Evolutionary Algorithms (MOEAs), namely the Non-dominated Sorting Genetic Algorithm II (NSGA-II), Pareto Envelope-based Selection Algorithm (PESA) and Strength Pareto Evolutionary Algorithm 2 (SPEA2), for solving complex portfolio optimization problems. The portfolio optimization problem is a typical bi-objective optimization problem with objectives the reward that should be maximized and the risk that should be minimized. While reward is commonly measured by the portfolio’s expected return, various risk measures have been proposed that try to better reflect a portfolio’s riskiness or to simplify the problem to be solved with exact optimization techniques efficiently. However, some risk measures generate additional complexities, since they are non-convex, non-differentiable functions. In addition, constraints imposed by the practitioners introduce further difficulties since they transform the search space into a non-convex region. The results show that MOEAs, in general, are efficient and reliable strategies for this kind of problems, and their performance is independent of the risk function used.     

Solving multi-objective parallel machine scheduling problem by a modified NSGA-II

In this paper, we modify a Multi-Objective Evolutionary Algorithm, known as Nondominated sorting Genetic Algorithm-II (NSGA-II) for a parallel machine scheduling problem with three objectives. The objectives are – (1) minimization of total cost due tardiness, (2) minimization of the deterioration cost and (3) minimization of makespan. The formulated problem has been solved by three Multi-Objective Evolutionary Algorithms which are: (1) the original NSGA-II (Non-dominated Sorting Genetic Algorithm–II), (2) SPEA2 (Strength Pareto Evolutionary Algorithm-2) and (3) a modified version of NSGA-II as proposed in this paper. A new mutation algorithm has also been proposed depending on the type of problem and embedded in the modified NSGA-II. The results of the three algorithms have been compared and conclusions have been drawn. The modified NSGA-II is observed to perform better than the original NSGA-II. Besides, the proposed mutation algorithm also works effectively, as evident from the experimental results.     

A fast steady-state <Emphasis Type="Italic">ε</Emphasis>-dominance multi-objective evolutionary algorithm

Multi-objective evolutionary algorithms (MOEAs) have become an increasingly popular tool for design and optimization tasks in real-world applications. Most of the popular baseline algorithms are pivoted on the use of Pareto-ranking (that is empirically inefficient) to improve the convergence to the Pareto front of a multi-objective optimization problem. This paper proposes a new ε-dominance MOEA (EDMOEA) which adopts pair-comparison selection and steady-state replacement instead of the Pareto-ranking. The proposed algorithm is an elitist algorithm with a new preservation technique of population diversity based on the ε-dominance relation. It is demonstrated that superior results could be obtained by the EDMOEA compared with other algorithms: NSGA-II, SPEA2, IBEA, ε-MOEA, PESA and PESA-II on test problems. The EDMOEA is able to converge to the Pareto optimal set much faster especially on the ZDT test functions with a large number of decision variables.     

Multiobjective scatter search for a commercial territory design problem

In this paper, a multiobjective scatter search procedure for a bi-objective territory design problem is proposed. A?territory design problem consists of partitioning a set of basic units into larger groups that are suitable with respect to some specific planning criteria. These groups must be compact, connected, and balanced with respect to the number of customers and sales volume. The bi-objective commercial territory design problem belongs to the class of NP-hard problems. Previous work showed that large instances of the problem addressed in this work are practically intractable even for the single-objective version. Therefore, the use of heuristic methods is the best alternative for obtaining approximate efficient solutions for relatively large instances. The proposed scatter search-based framework contains a diversification generation module based on a greedy randomized adaptive search procedure, an improvement module based on a relinked local search strategy, and a combination module based on a solution to an assignment problem. The proposed metaheuristic is evaluated over a variety of instances taken from literature. This includes a comparison with two of the most successful multiobjective heuristics from literature such as the Scatter Tabu Search Procedure for Multiobjective Optimization (SSPMO) by Molina et al. (INFORMS J. Comput. 19(1):91?C100, 2007), and the Non-dominated Sorting Genetic Algorithm (NSGA-II) by Deb et?al. (Parallel problem solving from nature ?C PPSN VI, Lecture notes in computer science, vol. 1917, Springer, Berlin, pp.?849?C858, 2000). Experimental work reveals that the proposed procedure consistently outperforms both heuristics, SSPMO and NSGA-II, on all instances tested.     

Multiobjective optimization using differential evolution for real-world portfolio optimization

Portfolio optimization is an important aspect of decision-support in investment management. Realistic portfolio optimization, in contrast to simplistic mean-variance optimization, is a challenging problem, because it requires to determine a set of optimal solutions with respect to multiple objectives, where the objective functions are often multimodal and non-smooth. Moreover, the objectives are subject to various constraints of which many are typically non-linear and discontinuous. Conventional optimization methods, such as quadratic programming, cannot cope with these realistic problem properties. A valuable alternative are stochastic search heuristics, such as simulated annealing or evolutionary algorithms. We propose a new multiobjective evolutionary algorithm for portfolio optimization, which we call DEMPO??Differential Evolution for Multiobjective Portfolio Optimization. In our experimentation, we compare DEMPO with quadratic programming and another well-known evolutionary algorithm for multiobjective optimization called NSGA-II. The main advantage of DEMPO is its ability to tackle a portfolio optimization task without simplifications, while obtaining very satisfying results in reasonable runtime.     

Multiobjective shortest path problems with lexicographic goal-based preferences

Multiobjective shortest path problems are computationally harder than single objective ones. In particular, execution time is an important limiting factor in exact multiobjective search algorithms. This paper explores the possibility of improving search performance in those cases where the interesting portion of the Pareto front can be initially bounded. We introduce a new exact label-setting algorithm that returns the subset of Pareto optimal paths that satisfy a set of lexicographic goals, or the subset that minimizes deviation from goals if these cannot be fully satisfied. Formal proofs on the correctness of the algorithm are provided. We also show that the algorithm always explores a subset of the labels explored by a full Pareto search. The algorithm is evaluated over a set of problems with three objectives, showing a performance improvement of up to several orders of magnitude as goals become more restrictive.     

Fast calculation of multiobjective probability of improvement and expected improvement criteria for Pareto optimization

The use of surrogate based optimization (SBO) is widely spread in engineering design to reduce the number of computational expensive simulations. However, “real-world” problems often consist of multiple, conflicting objectives leading to a set of competitive solutions (the Pareto front). The objectives are often aggregated into a single cost function to reduce the computational cost, though a better approach is to use multiobjective optimization methods to directly identify a set of Pareto-optimal solutions, which can be used by the designer to make more efficient design decisions (instead of weighting and aggregating the costs upfront). Most of the work in multiobjective optimization is focused on multiobjective evolutionary algorithms (MOEAs). While MOEAs are well-suited to handle large, intractable design spaces, they typically require thousands of expensive simulations, which is prohibitively expensive for the problems under study. Therefore, the use of surrogate models in multiobjective optimization, denoted as multiobjective surrogate-based optimization, may prove to be even more worthwhile than SBO methods to expedite the optimization of computational expensive systems. In this paper, the authors propose the efficient multiobjective optimization (EMO) algorithm which uses Kriging models and multiobjective versions of the probability of improvement and expected improvement criteria to identify the Pareto front with a minimal number of expensive simulations. The EMO algorithm is applied on multiple standard benchmark problems and compared against the well-known NSGA-II, SPEA2 and SMS-EMOA multiobjective optimization methods.     

Approximating the irregularly shaped Pareto front of multi-objective reservoir flood control operation problem

Decomposition based multi-objective evolutionary algorithm (MOEA/D) has been proved to be effective on multi-objective optimization problems. However, it fails to achieve satisfactory coverage and uniformity on problems with irregularly shaped Pareto fronts, like the reservoir flood control operation (RFCO) problem. To enhance the performance of MOEA/D on the real-world RFCO problem, a Pareto front relevant (PFR) decomposition method is developed in this paper. Different front the decomposition method in the original MOEA/D which is based on a unique reference point (i.e. the estimated ideal point), the PFR decomposition method uses a set of reference points which are uniformly sampled from the fitting model of the obtained Pareto front. As a result, the PFR decomposition method can provide more flexible adaptation to the Pareto front shapes of the target problems. Experimental studies on benchmark problems and typical RFCO problems at Ankang reservoir have illustrated that the proposed PFR decomposition method significantly improves the adaptivity of MOEA/D to the complex Pareto front shape of the RFCO problem and performs better both in terms of coverage and uniformity.     

TRANSFORM-ANN for online optimization of complex industrial processes: Casting process as case study

Artificial Neural Networks (ANNs) are well known for their credible ability to capture non-linear trends in scientific data. However, the heuristic nature of estimation of parameters associated with ANNs has prevented their evolution into efficient surrogate models. Further, the dearth of optimal training size estimation algorithms for the data greedy ANNs resulted in their overfitting. Therefore, through this work, we aim to contribute a novel ANN building algorithm called TRANSFORM aimed at simultaneous and optimal estimation of ANN architecture, training size and transfer function. TRANSFORM is integrated with three standalone Sobol sampling based training size determination algorithms which incorporate the concepts of hypercube sampling and optimal space filling. TRANSFORM was used to construct ANN surrogates for a highly non-linear industrially validated continuous casting model from steel plant. Multiobjective optimization of casting model to ensure maximum productivity, maximum energy saving and minimum operational cost was performed by ANN assisted Non-dominated Sorting Genetic Algorithms (NSGA-II). The surrogate assisted optimization was found to be 13 times faster than conventional optimization, leading to its online implementation. Simple operator's rules were deciphered from the optimal solutions using Pareto front characterization and K-means clustering for optimal functioning of casting plant. Comprehensive studies on (a) computational time comparisons between proposed training size estimation algorithms and (b) predictability comparisons between constructed ANNs and state of art statistical models, Kriging Interpolators adds to the other highlights of this work. TRANSFORM takes physics based model as the only input and provides parsimonious ANNs as outputs, making it generic across all scientific domains.     

An efficient evolutionary multi-objective framework for MEMS design optimisation: validation, comparison and analysis

The application of multi objective evolutionary algorithms (MOEA) in the design optimisation of microelectromechanical systems (MEMS) is of particular interest in this research. MOEA is a class of soft computing techniques of biologically inspired stochastic algorithms, which have proved to outperform their conventional counterparts in many design optimisation tasks. MEMS designers can utilise a variety of multi-disciplinary design tools that explore a complex design search space, however, still follow the traditional trial and error approaches. The paper proposes a novel framework, which couples both modelling and analysis tools to the most referenced MOEAs (NSGA-II and MOGA-II). The framework is validated and evaluated through a number of case studies of increasing complexity. The research presented in this paper unprecedentedly attempts to compare the performances of the mentioned algorithms in the application domain. The comparative study shows significant insights into the behaviour of both of the algorithms in the design optimisation of MEMS. The paper provides extended discussions and analysis of the results showing, overall, that MOGA-II outperforms NSGA-II, for the selected case studies.     

A novel elitist multiobjective optimization algorithm: Multiobjective extremal optimization

Recently, a general-purpose local-search heuristic method called extremal optimization (EO) has been successfully applied to some NP-hard combinatorial optimization problems. This paper presents an investigation on EO with its application in numerical multiobjective optimization and proposes a new novel elitist (1 + λ) multiobjective algorithm, called multiobjective extremal optimization (MOEO). In order to extend EO to solve the multiobjective optimization problems, the Pareto dominance strategy is introduced to the fitness assignment of the proposed approach. We also present a new hybrid mutation operator that enhances the exploratory capabilities of our algorithm. The proposed approach is validated using five popular benchmark functions. The simulation results indicate that the proposed approach is highly competitive with the state-of-the-art multiobjective evolutionary algorithms. Thus MOEO can be considered a good alternative to solve numerical multiobjective optimization problems.     

Comparative analysis of multiobjective evolutionary algorithms for random and correlated instances of multiobjective d-dimensional knapsack problems

This study analyzes multiobjective d-dimensional knapsack problems (MOd-KP) within a comparative analysis of three multiobjective evolutionary algorithms (MOEAs): the ε-nondominated sorted genetic algorithm II (ε-NSGAII), the strength Pareto evolutionary algorithm 2 (SPEA2) and the ε-nondominated hierarchical Bayesian optimization algorithm (ε-hBOA). This study contributes new insights into the challenges posed by correlated instances of the MOd-KP that better capture the decision interdependencies often present in real world applications. A statistical performance analysis of the algorithms uses the unary ε-indicator, the hypervolume indicator and success rate plots to demonstrate their relative effectiveness, efficiency, and reliability for the MOd-KP instances analyzed. Our results indicate that the ε-hBOA achieves superior performance relative to ε-NSGAII and SPEA2 with increasing number of objectives, number of decisions, and correlative linkages between the two. Performance of the ε-hBOA suggests that probabilistic model building evolutionary algorithms have significant promise for expanding the size and scope of challenging multiobjective problems that can be explored.     

Parallel multiobjective evolutionary algorithms for batch scheduling in heterogeneous computing and grid systems

This article presents six parallel multiobjective evolutionary algorithms applied to solve the scheduling problem in distributed heterogeneous computing and grid systems. The studied evolutionary algorithms follow an explicit multiobjective approach to tackle the simultaneous optimization of a system-related (i.e. makespan) and a user-related (i.e. flowtime) objectives. Parallel models of the proposed methods are developed in order to efficiently solve the problem. The experimental analysis demonstrates that the proposed evolutionary algorithms are able to efficiently compute accurate results when solving standard and new large problem instances. The best of the proposed methods outperforms both deterministic scheduling heuristics and single-objective evolutionary methods previously applied to the problem.