A multiobjective immune algorithm based on a multiple-affinity model

This paper presents a new multiobjective immune algorithm based on a multiple-affinity model inspired by immune system (MAM-MOIA). The multiple-affinity model builds the relationship model among main entities and concepts in multiobjective problems (MOPs) and multiobjective evolutionary algorithms (MOEAs), including feasible solution, variable space, objective space, Pareto-optimal set, ranking and crowding distance. In the model, immune operators including clonal proliferation, hypermutation and immune suppression are designed to proliferate superior antibodies and suppress the inferiors. MAM-MOIA is compared with NSGA-II, SPEA2 and NNIA in solving the ZDT and DTLZ standard test problems. The experimental study based on three performance metrics including coverage of two sets, convergence and spacing proves that MAM-MOIA is effective for solving MOPs.     

Design of a motorcycle frame using neuroacceleration strategies in MOEAs

Designing a low-budget lightweight motorcycle frame with superior dynamic and mechanical properties is a complex engineering problem. This complexity is due in part to the presence of multiple design objectives—mass, structural stress and rigidity—, the high computational cost of the finite element (FE) simulations used to evaluate the objectives, and the nature of the design variables in the frame’s geometry (discrete and continuous). Therefore, this paper presents a neuroacceleration strategy for multiobjective evolutionary algorithms (MOEAs) based on the combined use of real (FE simulations) and approximate fitness function evaluations. The proposed approach accelerates convergence to the Pareto optimal front (POF) comprised of nondominated frame designs. The proposed MOEA uses a mixed genotype to encode discrete and continuous design variables, and a set of genetic operators applied according to the type of variable. The results show that the proposed neuro-accelerated MOEAs, NN-NSGA II and NN-MicroGA, improve upon the performance of their original counterparts, NSGA II and MicroGA. Thus, this neuroacceleration strategy is shown to be effective and probably applicable to other FE-based engineering design problems.     

A novel evolution strategy for multiobjective optimization problem

Recent literatures have suggested that multiobjective evolutionary algorithms (MOEAs) can serve as a more exploratory and effective tool in solving multiobjective optimization problems (MOPs) than traditional optimizers. In order to contain a good approximation of Pareto optimal set with wide diversity associated with the inherent characters and variability of MOPs, this paper proposes a new evolutionary approach—(μ, λ) multiobjective evolution strategy ((μ, λ)-MOES). Following the highlight of how to balance proximity and diversity of individuals in exploration and exploitation stages respectively, some cooperative techniques are devised. Firstly, a novel combinatorial exploration operator that develops strong points from Gaussian mutation of proximity exploration and from Cauchy mutation of diversity preservation is elaborately designed. Additionally, we employ a complete nondominance selection so as to ensure maximal pressure for proximity exploitation while a fitness assignment determined by dominance and population diversity information is simultaneous used to ensure maximal diversity preservation. Moreover, a dynamic external archive is introduced to store elitist individuals as well as relatively better individuals and exchange information with the current population when performing archive increase scheme and archive decrease scheme. By graphical presentation and examination of selected performance metrics on three prominent benchmark test functions, (μ, λ)-MOES is found to outperform SPEA-II to some extent in terms of finding a near-optimal, well-extended and uniformly diversified Pareto optimal front.     

The Pareto fitness genetic algorithm: Test function study

Evolutionary algorithms have shown some success in solving multiobjective optimization problems. The methods of fitness assignment are mainly based on the information about the dominance relation between individuals. We propose a Pareto fitness genetic algorithm (PFGA) in which we introduce a modified ranking procedure and a promising way of sharing; a new fitness function based on the rank of the individual and its density value is designed. This is considered as our main contribution. The performance of our algorithm is evaluated on six multiobjective benchmarks with different Pareto front features. Computational results (quality of the approximation of the Pareto optimal set and the number of fitness function evaluations) proving its efficiency are reported.     

On the convergence of multiobjective evolutionary algorithms

We consider the usage of evolutionary algorithms for multiobjective programming (MOP), i.e. for decision problems with alternatives taken from a real-valued vector space and evaluated according to a vector-valued objective function. Selection mechanisms, possibilities of temporary fitness deterioration, and problems of unreachable alternatives for such multiobjective evolutionary algorithms (MOEAs) are studied. Theoretical properties of MOEAs such as stochastic convergence with probability 1 are analyzed.     

A new multiobjective simulated annealing algorithm

A new multiobjective simulated annealing algorithm for continuous optimization problems is presented. The algorithm has an adaptive cooling schedule and uses a population of fitness functions to accurately generate the Pareto front. Whenever an improvement with a fitness function is encountered, the trial point is accepted, and the temperature parameters associated with the improving fitness functions are cooled. Beside well known linear fitness functions, special elliptic and ellipsoidal fitness functions, suitable for the generation on non-convex fronts, are presented. The effectiveness of the algorithm is shown through five test problems. The parametric study presented shows that more fitness functions as well as more iteration gives more non-dominated points closer to the actual front. The study also compares the linear and elliptic fitness functions. The success of the algorithm is also demonstrated by comparing the quality metrics obtained to those obtained for a well-known evolutionary multiobjective algorithm.     

Covering Pareto Sets by Multilevel Subdivision Techniques

In this work, we present a new set-oriented numerical method for the numerical solution of multiobjective optimization problems. These methods are global in nature and allow to approximate the entire set of (global) Pareto points. After proving convergence of an associated abstract subdivision procedure, we use this result as a basis for the development of three different algorithms. We consider also appropriate combinations of them in order to improve the total performance. Finally, we illustrate the efficiency of these techniques via academic examples plus a real technical application, namely, the optimization of an active suspension system for cars.The authors thank Joachim Lückel for his suggestion to get into the interesting field of multiobjective optimization. Katrin Baptist as well as Frank Scharfeld helped the authors with fruitful discussions. This work was partly supported by the Deutsche Forschungsgemeinschaft within SFB 376 and SFB 614.     

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.     

On the structure of multiobjective combinatorial search space: MNK-landscapes with correlated objectives

The structure of the search space explains the behavior of multiobjective search algorithms, and helps to design well-performing approaches. In this work, we analyze the properties of multiobjective combinatorial search spaces, and we pay a particular attention to the correlation between the objective functions. To do so, we extend the multiobjective NK-landscapes in order to take the objective correlation into account. We study the co-influence of the problem dimension, the degree of non-linearity, the number of objectives, and the objective correlation on the structure of the Pareto optimal set, in terms of cardinality and number of supported solutions, as well as on the number of Pareto local optima. This work concludes with guidelines for the design of multiobjective local search algorithms, based on the main fitness landscape features.     

Fuzzy classifier identification using decision tree and multiobjective evolutionary algorithms

This paper presents a hybrid method for identification of Pareto-optimal fuzzy classifiers (FCs). In contrast to many existing methods, the initial population for multiobjective evolutionary algorithms (MOEAs) is neither created randomly nor a priori knowledge is required. Instead, it is created by the proposed two-step initialization method. First, a decision tree (DT) created by C4.5 algorithm is transformed into an FC. Therefore, relevant variables are selected and initial partition of input space is performed. Then, the rest of the population is created by randomly replacing some parameters of the initial FC, such that, the initial population is widely spread. That improves the convergence of MOEAs into the correct Pareto front. The initial population is optimized by NSGA-II algorithm and a set of Pareto-optimal FCs representing the trade-off between accuracy and interpretability is obtained. The method does not require any a priori knowledge of the number of fuzzy sets, distribution of fuzzy sets or the number of relevant variables. They are all determined by it. Performance of the obtained FCs is validated by six benchmark data sets from the literature. The obtained results are compared to a recently published paper [H. Ishibuchi, Y. Nojima, Analysis of interpretability-accuracy tradeoff of fuzzy systems by multiobjective fuzzy genetics-based machine learning, International Journal of Approximate Reasoning 44 (1) (2007) 4–31] and the benefits of our method are clearly shown.     

Explicit gradient information in multiobjective optimization

This work presents an algorithm that converges to points that satisfy a first-order necessary condition of weakly Pareto solutions of multiobjective optimization problems. Hints on how to include second-order information are given. Preliminary numerical results are encouraging.     

A predictive gradient strategy for multiobjective evolutionary algorithms in a fast changing environment

An essential feature of a dynamic multiobjective evolutionary algorithm (MOEA) is to converge quickly to the Pareto-optimal Set before it changes. In cases where the behavior of the dynamic problem follows a certain trend, convergence can be accelerated by anticipating the characteristics of future changes in the problem. A prediction model is usually used to exploit past information and estimate the location of the new Pareto-optimal Set. In this work, we propose the novel approach of tracking and predicting the changes in the location of the Pareto Set in order to minimize the effects of a landscape change. The predicted direction and magnitude of the next change, known as the predictive gradient, is estimated based on the history of previously discovered solutions using a weighted average approach. Solutions updated with the predictive gradient will remain in the vicinity of the new Pareto-optimal Set and help the rest of the population to converge. The prediction strategy is simple to implement, making it suitable for fast-changing problems. In addition, a new memory technique is introduced to exploit any periodicity in the dynamic problem. The memory technique selects only the more promising stored solutions for retrieval in order to reduce the number of evaluations used. Both techniques are incorporated into a variant of the multi-objective evolutionary gradient search (MO-EGS) and two other MOEAs for dynamic optimization and results indicate that they are effective at improving performance on several dynamic multiobjective test problems.     

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.     

Solving a multiobjective location routing problem with a metaheuristic based on tabu search. Application to a real case in Andalusia

In this work we present a multiobjective location routing problem and solve it with a multiobjective metaheuristic procedure. In this type of problem, we have to locate some plants within a set of possible locations to meet the demands of a number of clients with multiple objectives. This type of model is used to solve a problem with real data in the region of Andalusia (Spain). Thus, we study the location of two incineration plants for the disposal of solid animal waste from some preestablished locations in Andalusia, and design the routes to serve the different slaughterhouses in this region. This must be done while taking into account certain economic objectives (start-up, maintenance, and transport costs) and social objectives (social rejection by towns on the truck routes, maximum risk as an equity criterion, and the negative implications for towns close to the plant).     

Multiobjective duality for convex ratios

In this paper we present a duality approach for a multiobjective fractional programming problem. The components of the vector objective function are particular ratios involving the square of a convex function and a positive concave function. Applying the Fenchel-Rockafellar duality theory for a scalar optimization problem associated to the multiobjective primal, a dual problem is derived. This scalar dual problem is formulated in terms of conjugate functions and its structure gives an idea about how to construct a multiobjective dual problem in a natural way. Weak and strong duality assertions are presented.     

Local dominance and local recombination in MOEAs on 0/1 multiobjective knapsack problems

This work studies and compares the effects on performance of local dominance and local recombination applied with different locality in multiobjective evolutionary algorithms on combinatorial 0/1 multiobjective knapsack problems. For this purpose, we introduce a method that creates a neighborhood around each individual and assigns a local dominance rank after alignment of the principle search direction of the neighborhood by using polar coordinates in objective space. For recombination a different neighborhood determined around a random principle search direction is created. The neighborhood sizes for dominance and recombination are separately controlled by two different parameters. Experimental results show that the optimum locality of dominance is different from the optimum locality of recombination. Additionally, it is shown that the performance of the algorithm that applies local dominance and local recombination with different locality is significantly better than the performance of algorithms applying local dominance alone, local recombination alone, or dominance and recombination globally as conventional approaches do.     

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.     

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

Hard uncertainties in multiobjective layout optimization of photovoltaic power plants

This paper describes how to treat hard uncertainties defined by so-called uncertainty maps in multiobjective optimization problems. For the uncertainty map being set-valued, a Taylor formula is shown under appropriate assumptions. The hard uncertainties are modeled using parametric set optimization problems for which a scalarization result is given. The presented new approach for the solution of multiobjective optimization problems with hard uncertainties is then applied to the layout optimization of photovoltaic power plants. Since good weather forecasts are difficult to obtain for future years, weather data are really hard uncertainties arising in the planning process. Numerical results are presented for a real-world problem on the Galapagos island Isabela.     

Multi-start and path relinking methods to deal with multiobjective knapsack problems

This paper deals with a multiobjective combinatorial optimization problem called Extended Knapsack Problem. By applying multi-start search and path relinking we rapidly guide the search toward the most balanced zone of the Pareto-optimal front. The Pareto relation is applied in order to designate a subset of the best generated solutions to be the current efficient set of solutions. The max-min criterion with the Hamming distance is used as a measure of dissimilarity in order to find diverse solutions to be combined. The performance of our approach is compared with several state-of-the-art MOEAs for a suite test problems taken from the literature.