Evolutionary Multi-Criterion Optimization

Evolutionary algorithms have been quite effective in dealing with single-objective “optimization” while the area of Evolutionary Multiobjective Optimization (EMOO) has extended its efficiency to Multiple Criteria Decision Making (MCDM) as well. The number of technical publications in EMOO is impressive and indicative of a rather explosive growth in recent years. It is fair to say however that most of the progress has been in applying and evolving algorithms and their convergence properties, not in evolving the optimality concept itself, nor in expanding the notions of true optimization. Yet, the conceptual constructs based on evolution and Darwinian selection have probably most to contribute – at least in theory – to the evolution of optimality. They should be least dependent on a priori fixation of anything in problem formulation: constraints, objectives or alternatives. Modern systems and problems are typical for their

flexibility

, not for their fixation. In this paper we draw attention to the impossibility of optimization when crucial variables are given and present

Eight basic concepts of optimality

. In the second part of this contribution we choose a more realistic problem of linear programming where constraints are not “given” but flexible and to be optimized and objective functions are multiple:

De novo programming

.

Evolutionary multicriteria optimization has traditionally concentrated on problems comprising 2 or 3 objectives. While engineering design problems can often be conveniently formulated as multiobjective optimization problems, these often comprise a relatively large number of objectives. Such problems pose new challenges for algorithm design, visualisation and implementation. Each of these three topics is addressed. Progressive articulation of design preferences is demonstrated to assist in reducing the region of interest for the search and, thereby, simplified the problem. Parallel coordinates have proved a useful tool for visualising many objectives in a two-dimensional graph and the computational grid and wireless Personal Digital Assistants offer technological solutions to implementation difficulties arising in complex system design.

After 20 years of development of multiobjective metaheuristics the procedures for solving multiple objective combinatorial optimization problems are generally the result of a blend of evolutionary, neighborhood search, and problem dependent components. Indeed, even though the first procedures were direct adaptations of single objective metaheuristics inspired by evolutionary algorithms or neighborhood search algorithms, hybrid procedures have been introduced very quickly. This paper discusses hybridations found in the literature and mentions recently introduced metaheuristic principles.

Due to the vagaries of optimization problems encountered in practice, users resort to different algorithms for solving different optimization problems. In this paper, we suggest an optimization procedure which specializes in solving multi-objective, multi-global problems. The algorithm is carefully designed so as to degenerate to efficient algorithms for solving other simpler optimization problems, such as single-objective uni-global problems, single-objective multi-global problems and multi-objective uni-global problems. The efficacy of the proposed algorithm in solving various problems is demonstrated on a number of test problems. Because of it’s efficiency in handling different types of problems with equal ease, this algorithm should find increasing use in real-world optimization problems.

The hypervolume measure is one of the most frequently applied measures for comparing the results of evolutionary multiobjective optimization algorithms (EMOA). The idea to use this measure for selection is self-evident. A steady-state EMOA will be devised, that combines concepts of non-dominated sorting with a selection operator based on the hypervolume measure. The algorithm computes a well distributed set of solutions with bounded size thereby focussing on interesting regions of the Pareto front(s). By means of standard benchmark problems the algorithm will be compared to other well established EMOA. The results show that our new algorithm achieves good convergence to the Pareto front and outperforms standard methods in the hypervolume covered. We also studied the applicability of the new approach in the important field of design optimization. In order to reduce the number of time consuming precise function evaluations, the algorithm will be supported by approximate function evaluations based on Kriging metamodels. First results on an airfoil redesign problem indicate a good performance of this approach, especially if the computation of a small, bounded number of well-distributed solutions is desired.

Contemporary evolutionary multiobjective optimisation techniques are becoming increasingly focussed on the notions of archiving, explicit diversity maintenance and population-based Pareto ranking to achieve good approximations of the Pareto front. While it is certainly true that these techniques have been effective, they come at a significant complexity cost that ultimately limits their application to complex problems. This paper proposes a new model that moves away from explicit population-wide Pareto ranking, abandons both complex archiving and diversity measures and incorporates a continuous accretion-based approach that is divergent from the discretely generational nature of traditional evolutionary algorithms. Results indicate that the new approach, the Combative Accretion Model (CAM), achieves markedly better approximations than NSGA across a range of well-recognised test functions. Moreover, CAM is more efficient than NSGAII with respect to the number of comparisons (by an order of magnitude), while achieving comparable, and generally preferable, fronts.

While single-objective Evolutionary Algorithms (EAs) parallelization schemes are both well established and easy to implement, this is not the case for Multi-Objective Evolutionary Algorithms (MOEAs). Nevertheless, the need for parallelizing MOEAs arises in many real-world applications, where fitness evaluations and the optimization process can be very time consuming. In this paper, we test the ‘divide and conquer’ approach to parallelize MOEAs, aimed at improving the speed of convergence beyond a parallel island MOEA with migration. We also suggest a clustering based parallelization scheme for MOEAs and compare it to several alternative MOEA parallelization schemes on multiple standard multi-objective test functions.

An improved orthogonal multi-objective evolutionary algorithm (OMOEA), called OMOEA-II, is proposed in this paper. Two new crossovers used in OMOEA-II are orthogonal crossover and linear crossover. By using these two crossover operators, only small orthogonal array rather than large orthogonal array is needed for exploiting optimal in the global space. Such reduction in orthogonal array can avoid exponential creation of solutions of OMOEA and improve the performance in robusticity without degrading precision and distribution of solutions. Experimental results show that OMOEA-II can solve problems with high dimensions and large number of local Pareto-optimal fronts better than some existing algorithms recently reported in the literatures.

Path relinking algorithms have proved their efficiency in single objective optimization. Here we propose to adapt this concept to Pareto optimization. We combine this original approach to a genetic algorithm. By applying this hybrid approach to a bi-objective permutation flow-shop problem, we show the interest of this approach.

In this paper, we present first an Adaptive Genetic Algorithm dedicated to obtain a first well diversified approximation of the Pareto set. Then, we present an original hybridization with Path Relinking algorithm, in order to intensify the search between solutions obtained by the first approach. Results obtained are promising and show that cooperation between these optimization methods could be efficient for Pareto optimization.

This paper proposes a new multiobjective evolutionary approach—the dynamic archive evolution strategy (DAES) to investigate the adaptive balance between proximity and diversity. In DAES, a novel dynamic external archive is proposed to store elitist individuals as well as relatively better individuals through archive increase scheme and archive decrease scheme. Additionally, a combinatorial operator that inherits merits from Gaussian mutation of proximity exploration and Cauchy mutation of diversity preservation is elaborately devised. Meanwhile, a complete nondominance selection ensures maximal pressure of proximity exploitation while a corresponding fitness assignment ensures the similar pressure of diversity preservation. By graphical presentation and performance metrics on three prominent benchmark functions, DAES is found to outperform three state-of-the-art multiobjective evolutionary algorithms to some extent in terms of finding a near-optimal, well-extended and uniformly diversified Pareto optimal front.

In optimization studies including multi-objective optimization, the main focus is usually placed in finding the global optimum or global Pareto-optimal frontier, representing the best possible objective values. However, in practice, users may not always be interested in finding the global best solutions, particularly if these solutions are quite sensitive to the variable perturbations which cannot be avoided in practice. In such cases, practitioners are interested in finding the so-called

robust

solutions which are less sensitive to small changes in variables. Although robust optimization has been dealt in detail in single-objective optimization studies, in this paper, we present two different robust multi-objective optimization procedures, where the emphasis is to find the robust optimal frontier, instead of the global Pareto-optimal front. The first procedure is a straightforward extension of a technique used for single-objective robust optimization and the second procedure is a more practical approach enabling a user to control the extent of robustness desired in a problem. To demonstrate the subtle differences between global and robust multi-objective optimization and the differences between the two robust optimization procedures, we define four test problems and show simulation results using NSGA-II. The results are useful and should encourage further studies considering robustness in multi-objective optimization.

Obtaining a well distributed non-dominated Pareto front is one of the key issues in multi-objective optimization algorithms. This paper proposes a new variant for the elitist selection operator to the NSGA-II algorithm, which promotes well distributed non-dominated fronts. The basic idea is to replace the crowding distance method by a maximin technique. The proposed technique is deployed in well known test functions and compared with the crowding distance method used in the NSGA-II algorithm. This comparison is performed in terms of achieved front solutions distribution by using distance performance indices.

In engineering and other ‘real-world’ applications, multiobjective optimization problems must frequently be tackled on a tight evaluation budget — tens or hundreds of function evaluations, rather than thousands. In this paper, we investigate two algorithms that use advanced initialization and search strategies to operate better under these conditions. The first algorithm, Bin_MSOPS, uses a binary search tree to divide up the decision space, and tries to sample from the largest empty regions near ‘fit’ solutions. The second algorithm, ParEGO, begins with solutions in a latin hypercube and updates a

Gaussian processes

surrogate model of the search landscape after every function evaluation, which it uses to estimate the solution of largest expected improvement. The two algorithms are tested using a benchmark suite of nine functions of two and three objectives — on a budget of only 250 function evaluations each, in total. Results indicate that the two algorithms search the space in very different ways and this can be used to understand performance differences. Both algorithms perform well but ParEGO comes out on top in seven of the nine test cases after 100 function evaluations, and on six after the first 250 evaluations.

Nearly all Multi-Objective Evolutionary Algorithms (MOEA) rely on random generation of initial population. In large and complex search spaces, this random method often leads to an initial population composed of infeasible solutions only. Hence, the task of a MOEA is not only to converge towards the Pareto-optimal front but also to guide the search towards the feasible region. This paper proposes the incorporation of a novel method for constructing initial populations into existing MOEAs based on so-called Pareto-Front-Arithmetics (PFA). We will provide experimental results from the field of embedded system synthesis that show the effectiveness of our proposed methodology.

This paper introduces a new algorithm to deal with multi-objective combinatorial and continuous problems. The algorithm is an extension of a previous one designed to deal with single objective combinatorial problems. The original purpose of the single objective version was to study in a rigorous way the properties the search graph of a particular problem needs to hold so that a randomized local search heuristic can find the optimum with high probability. The extension of these results to better understand multi-objective combinatorial problems seems to be a promising line of research. The work presented here is a first small step in this direction. A detailed description of the multi-objective version is presented along with preliminary experimental results on a well known combinatorial problem. The results show that the algorithm has the desired characteristics.

In this work the use of qualitative preferences for classifying and selecting MOEAs is introduced. The classical notions of the Analyst and the so called Prescriptive Analysis are introduced explicitly in EMO, identifying some difficulties in exploiting the results of the comparative studies performed by the current fashion. A methodology is developed that allows the analyst to translate DM’s general preferences as well as quantitative benchmarking results into a practical tool for the comparison of MOEAs, facilitating the selection of the proper method and/or parameters for the MCDM problem at hand. A comparative experimentation is performed using well known state of the art functions, allowing drawing clear conclusions about the utility of the proposed methodology. The results are useful for research, practitioners and analysts involved in benchmarking, comparative studies and prescriptive analysis for EMO.

The multiple criteria aggregation methods allow us to construct a recommendation from a set of alternatives based on the preferences of a decision maker. In some approaches, the recommendation is immediately deduced from the preferences aggregation process. When the aggregation model of preferences is based on the outranking approach, a special treatment is required, but some non-rational violations of the explicit global model of preferences could happen. In this case, the exploitation phase could then be treated as a multiobjective optimization problem. In this paper a new multiobjective evolutionary algorithm, which allows exploiting a known fuzzy outranking relation, is introduced with the purpose of constructing a recommendation for ranking problems. The performance of our algorithm is evaluated on a set of test problems. Computational results show that the multiobjective genetic algorithm-based heuristic is capable of producing high-quality recommendations.

The attainment function has been proposed as a measure of the statistical performance of stochastic multiobjective optimisers which encompasses both the quality of individual non-dominated solutions in objective space and their spread along the trade-off surface. It has also been related to results from random closed-set theory, and cast as a mean-like, first-order moment measure of the outcomes of multiobjective optimisers. In this work, the use of more informative, second-order moment measures for the evaluation and comparison of multiobjective optimiser performance is explored experimentally, with emphasis on the interpretability of the results.

This paper examines the effect of crossover operations on the performance of EMO algorithms through computational experiments on knapsack problems and flowshop scheduling problems using the NSGA-II algorithm. We focus on the relation between the performance of the NSGA-II algorithm and the similarity of recombined parent solutions. First we show the necessity of crossover operations through computational experiments with various specifications of crossover and mutation probabilities. Next we examine the relation between the performance of the NSGA-II algorithm and the similarity of recombined parent solutions. It is shown that the quality of obtained solution sets is improved by recombining similar parents. Then we examine the effect of increasing the selection pressure (i.e., increasing the tournament size) on the similarity of recombined parent solutions. An interesting observation is that the increase in the tournament size leads to the recombination of dissimilar parents, improves the diversity of solutions, and degrades the convergence performance of the NSGA-II algorithm.

This paper presents a new toolkit for creating scalable multi-objective test problems. The WFG Toolkit is flexible, allowing characteristics such as bias, multi-modality, and non-separability to be incorporated and combined as desired. A wide variety of Pareto optimal geometries are also supported, including convex, concave, mixed convex/concave, linear, degenerate, and disconnected geometries.

All problems created by the WFG Toolkit are well defined, are scalable with respect to both the number of objectives and the number of parameters, and have known Pareto optimal sets. Nine benchmark multi-objective problems are suggested, including one that is both multi-modal and non-separable, an important combination of characteristics that is lacking among existing (scalable) multi-objective problems.

Deception problems are among the hardest problems to solve using ordinary genetic algorithms. Designed to simulate a high degree of epistasis, these deception problems imitate extremely difficult real world problems. [1]. Studies show that Bayesian optimization and explicit building block manipulation algorithms, like the fast messy genetic algorithm (fmGA), can help in solving these problems. This paper compares the results acquired from an

extended

multiobjective fast messy genetic algorithm (MOMGA-IIa), ordinary multiobjective fast messy genetic algorithm (MOMGA-II), multiobjective Bayesian optimization algorithm (mBOA), and the non-dominated sorting genetic algorithm-II (NSGA-II) when applied to three different deception problems. The

extended

MOMGA-II is enhanced with a new technique exploiting the fmGA’s basis function to improve partitioned searching in both the genotype and phenotype domain. The three deceptive problems studied are: interleaved minimal deceptive problem, interleaved 5-bit trap function, and interleaved 6-bit bipolar function. The

unmodified

MOMGA-II, by design, explicitly learns building block linkages, a requirement if an algorithm is to solve these hard deception problems. Results using the MOMGA-IIa are excellent when compared to the non-explicit building block algorithm results of both the mBOA and NSGA-II.

For the past decade, many evolutionary multi-objective optimization (EMO) methodologies have been developed and applied to find multiple Pareto-optimal solutions in a single simulation run. In this paper, we discuss three different classical generating methods, some of which were suggested even before the inception of EMO methodologies. These methods specialize in finding multiple Pareto-optimal solutions in a single simulation run. On visual comparisons of the efficient frontiers obtained for a number of two and three-objective test problems, these algorithms are evaluated with an EMO methodology. The results bring out interesting insights about the strengths and weaknesses of these approaches. Further investigations of such classical generating methodologies and their evaluation should enable researchers to design a hybrid multi-objective optimization algorithm which may be better than each individual method.

We present a new analysis of the LebMeasure algorithm for calculating hypervolume. We prove that although it is polynomial in the number of points, LebMeasure is exponential in the number of objectives in the worst case, not polynomial as has been claimed previously. This result has important implications for anyone planning to use hypervolume, either as a metric to compare optimisation algorithms, or as part of a diversity mechanism in an evolutionary algorithm.

The focus of this paper is the handling of overlapping solutions in evolutionary multiobjective optimization (EMO) algorithms. In the application of EMO algorithms to some multiobjective combinatorial optimization problems, there exit a large number of overlapping solutions in each generation. We examine the effect of removing overlapping solutions on the performance of EMO algorithms. In this paper, overlapping solutions are removed from the current population except for a single solution. We implement two removal strategies of overlapping solutions. One is the removal of overlapping solutions in the objective space. In this strategy, one solution is randomly chosen among the overlapping solutions with the same objective vector and left in the current population. The other overlapping solutions with the same objective vector are removed from the current population. As a result, each solution in the current population has a different location in the objective space. It should be noted that the overlapping solutions in the objective space are not necessary the same solution in the decision space. Thus we also examine the other strategy where the overlapping solutions in the decision space are removed from the current population except for a single solution. As a result, each solution in the current population has a different location in the decision space. The effect of removing overlapping solutions is examined through computational experiments where each removal strategy is combined into the NSGA-II algorithm.

This work focuses on the working principles, behavior, and performance of state of the art multiobjective evolutionary algorithms (MOEAs) on discrete search spaces by using MNK-Landscapes. Its motivation comes from the performance shown by NSGA-II and SPEA2 on epistatic problems, which suggest that simpler population-based multiobjective random one-bit climbers are by far superior. Adaptive evolution is a search process driven by selection, drift, mutation, and recombination over fitness landscapes. We group MOEAs features and organize our study around these four important and intertwined processes in order to understand better their effects and clarify the reasons to the poor performance shown by NSGA-II and SPEA2. This work also constitutes a valuable guide for the practitioner on how to set up its algorithm and gives useful insights on how to design more robust and efficient MOEAs.

This paper examines two repair schemes (i.e., Lamarckian and Baldwinian) through computational experiments on multiobjective 0/1 knapsack problems. First we compare Lamarckian and Baldwinian with each other. Experimental results show that the Baldwinian repair outperforms the Lamarckian repair. It is also shown that these repair schemes outperform a penalty function approach. Then we examine partial Lamarckianism where the Lamarckian repair is applied to each individual with a prespecified probability. Experimental results show that a so-called 5% rule works well. Finally partial Lamarckianism is compared with an island model with two subpopulations where each island has a different repair scheme. Experimental results show that the island model slightly outperforms the standard single-population model with the 50% partial Lamarckian repair in terms of the diversity of solutions.

This paper demonstrates how adaptive population-sizing and epsilon-dominance archiving can be combined with the Nondominated Sorted Genetic Algorithm-II (NSGAII) to enhance the algorithm’s efficiency, reliability, and ease-of-use. Four versions of the enhanced Epsilon Dominance NSGA-II (ε-NSGAII) are tested on a standard suite of evolutionary multiobjective optimization test problems. Comparative results for the four variants of the (ε-NSGAII demonstrate that adapting population size based on online changes in the epsilon dominance archive size can enhance performance. The best performing version of the (ε-NSGAII is also compared to the original NSGAII and the (εMOEA on the same suite of test problems. The performance of each algorithm is measured using three running performance metrics, two of which have been previously published, and one new metric proposed by the authors. Results of the study indicate that the new version of the NSGAII proposed in this paper demonstrates improved performance on the majority of two-objective test problems studied.

This paper studies the fuzzification of the Pareto dominance relation and its application to the design of Evolutionary Multi-Objective Optimization algorithms. A generic ranking scheme is presented that assigns dominance degrees to any set of vectors in a scale-independent, non-symmetric and set-dependent manner. Based on such a ranking scheme, the vector fitness values of a population can be replaced by the computed ranking values (representing the ”dominating strength” of an individual against all other individuals in the population) and used to perform standard single-objective genetic operators. The corresponding extension of the Standard Genetic Algorithm, so-called Fuzzy-Dominance-Driven GA (FDD-GA), will be presented as well. To verify the usefulness of such an approach, an analytic study of the Pareto-Box problem is provided, showing the characteristical parameters of a random search for the Pareto front in a unit hypercube in arbitrary dimension. The basic problem here is the loss of dominated points with increasing problem dimension, which can be successfully resolved by basing the search procedure on the fuzzy dominance degrees.

Multi-objective evolutionary algorithms (MOEAs) have proven to be a powerful tool for global optimization purposes of deterministic problem functions. Yet, in many real-world problems, uncertainty about the correctness of the system model and environmental factors does not allow to determine clear objective values. Stochastic sampling as applied in noisy EAs neglects that this so-called epistemic uncertainty is not an inherent property of the system and cannot be reduced by sampling methods. Therefore, some extensions for MOEAs to handle epistemic uncertainty in objective functions are proposed. The extensions are generic and applicable to most common MOEAs. A density measure for uncertain objectives is proposed to maintain diversity in the nondominated set. The approach is demonstrated to the reliability optimization problem, where uncertain component failure rates are usual and exhaustive tests are often not possible due to time and budget reasons.

Estimation of distribution algorithms have been shown to perform well on a wide variety of single–objective optimization problems. Here, we look at a simple – yet effective – extension of this paradigm for multi–objective optimization, called the naive

${\mathbb M}$

ID

${\mathbb E}$

A. The probabilistic model in this specific algorithm is a mixture distribution, and each component in the mixture is a univariate factorization. Mixture distributions allow for wide–spread exploration of the Pareto front thus aiding the important preservation of diversity in multi–objective optimization. Due to its simplicity, speed, and effectiveness the naive

${\mathbb M}$

ID

${\mathbb E}$

A can well serve as a baseline algorithm for multi–objective evolutionary algorithms.

This paper elaborates on new ideas of a scatter search algorithm for solving multiobjective problems. Our approach adapts the well-known scatter search template for single objective optimization to the multiobjective field. The result is a simple and new metaheuristic called SSMO, which incorporates typical concepts from the multiobjective optimization domain such as Pareto dominance, crowding, and Pareto ranking. We evaluate SSMO with both constrained and unconstrained problems and compare it against NSGA-II. Preliminary results indicate that scatter search is a promising approach for multiobjective optimization.

In extending the Particle Swarm Optimisation methodology to multi-objective problems it is unclear how global guides for particles should be selected. Previous work has relied on metric information in objective space, although this is at variance with the notion of dominance which is used to assess the quality of solutions. Here we propose methods based exclusively on dominance for selecting guides from a non-dominated archive. The methods are evaluated on standard test problems and we find that probabilistic selection favouring archival particles that dominate few particles provides good convergence towards and coverage of the Pareto front. We demonstrate that the scheme is robust to changes in objective scaling. We propose and evaluate methods for confining particles to the feasible region, and find that allowing particles to explore regions close to the constraint boundaries is important to ensure convergence to the Pareto front.

Based on the concept of Immunodominance and Antibody Clonal Selection Theory, we propose a new artificial immune system algorithm, Immune Dominance Clonal Multiobjective Algorithm (IDCMA). The influences of main parameters are analyzed empirically. The simulation comparisons among IDCMA, the Random-Weight Genetic Algorithm and the Strength Pareto Evolutionary Algorithm show that when low-dimensional multiobjective problems are concerned, IDCMA has the best performance in metrics such as Spacing and Coverage of Two Sets.

Real-world engineering optimisation problems are typically multi-objective and highly constrained, and constraints may be both costly to evaluate and binary in nature. In addition, objective functions may be computationally expensive and, in the commercial design cycle, there is a premium placed on rapid initial progress in the optimisation run. In these circumstances, evolutionary algorithms may not be the best choice; we have developed a multi-objective Tabu Search algorithm, designed to perform well under these conditions. Here we present the algorithm along with the constraint handling approach, and test it on a number of benchmark constrained test problems. In addition, we perform a parametric study on a variety of unconstrained test problems in order to determine the optimal parameter settings. Our algorithm performs well compared to a leading multi-objective Genetic Algorithm, and we find that its performance is robust to parameter settings.

In this paper, we propose a new Multi-Objective Particle Swarm Optimizer, which is based on Pareto dominance and the use of a crowding factor to filter out the list of available leaders. We also propose the use of different mutation (or

turbulence

) operators which act on different subdivisions of the swarm. Finally, the proposed approach also incorporates the ∈-dominance concept to fix the size of the set of final solutions produced by the algorithm. Our approach is compared against five state-of-the-art algorithms, including three PSO-based approaches recently proposed. The results indicate that the proposed approach is highly competitive, being able to approximate the front even in cases where all the other PSO-based approaches fail.

Differential Evolution (DE) is a simple but powerful evolutionary optimization algorithm with many successful applications. In this paper we propose Differential Evolution for Multiobjective Optimization (DEMO) – a new approach to multiobjective optimization based on DE. DEMO combines the advantages of DE with the mechanisms of Pareto-based ranking and crowding distance sorting, used by state-of-the-art evolutionary algorithms for multiobjective optimization. DEMO is implemented in three variants that achieve competitive results on five ZDT test problems.

In this article, model selection for support vector machines is viewed as a multi-objective optimization problem, where model complexity and training accuracy define two conflicting objectives. Different optimization criteria are evaluated: Split modified radius margin bounds, which allow for comparing existing model selection criteria, and the training error in conjunction with the number of support vectors for designing sparse solutions.

In previous work, we have proposed a novel approach to data clustering based on the explicit optimization of a partitioning with respect to two complementary clustering objectives [6]. Here, we extend this idea by describing an advanced multiobjective clustering algorithm, MOCK, with the capacity to identify good solutions from the Pareto front, and to automatically determine the number of clusters in a data set. The algorithm has been subject to a thorough comparison with alternative clustering techniques and we briefly summarize these results. We then present investigations into the mechanisms at the heart of MOCK: we discuss a simple example demonstrating the synergistic effects at work in multiobjective clustering, which explain its superiority to single-objective clustering techniques, and we analyse how MOCK’s Pareto fronts compare to the performance curves obtained by single-objective algorithms run with a range of different numbers of clusters specified.

An artificial satellite design requires severe design objectives such as performance, reliability, weight, robustness, cost, and so on. To solve the conflicted requirements at the same time, multiobjective optimization is getting more popular in the design. Using the optimization, it becomes ordinary to get many solutions, such as Pareto solutions, quasi-Pareto solutions, and feasible solutions. The alternative solutions, however, are very difficult to be adopted to practical engineering decision directly. Therefore, to make the decision, proper information about the solutions in a function, parameter and real design space should be provided. In this paper, a new approach for the interpretation of Pareto solutions is proposed based on multidimensional visualization and clustering. The proposed method is applied to a thermal robustness and mass optimization problem of heat pipe shape design for an artificial satellite. The information gleaned from the propose approach can support the engineering decision for the design of artificial satellite heat pipe.

A comparative study of the use of Gray coding in multicriteria evolutionary optimisation is performed using the SPEA2 and NSGAII algorithms and applied to a frame structural optimisation problem. A double minimization is handled: constrained mass and number of different cross-section types. Influence of various mutation rates is considered. The comparative statistical results of the test case cover a convergence study during evolution by means of certain metrics that measure front amplitude and distance to the optimal front. Results in a 55 bar-sized frame test case show that the use of the Standard Binary Reflected Gray code compared versus Binary code allows to obtain fast and more accurate solutions, more coverage of non-dominated fronts; both with improved robustness in frame structural multiobjective optimum design.

Feature selection for ensembles has shown to be an effective strategy for ensemble creation due to its ability of producing good subsets of features, which make the classifiers of the ensemble disagree on difficult cases. In this paper we present an ensemble feature selection approach based on a hierarchical multi-objective genetic algorithm. The algorithm operates in two levels. Firstly, it performs feature selection in order to generate a set of classifiers and then it chooses the best team of classifiers. In order to show its robustness, the method is evaluated in two different contexts: supervised and unsupervised feature selection. In the former, we have considered the problem of handwritten digit recognition while in the latter, we took into account the problem of handwritten month word recognition. Experiments and comparisons with classical methods, such as Bagging and Boosting, demonstrated that the proposed methodology brings compelling improvements when classifiers have to work with very low error rates.

With the invention of microarray technology, researchers are able to measure the expression levels of ten thousands of genes in parallel at various time points of a biological process. The investigation of gene regulatory networks has become one of the major topics in Systems Biology. In this paper we address the problem of finding gene regulatory networks from experimental DNA microarray data. We suggest to use a multi-objective evolutionary algorithm to identify the parameters of a non-linear system given by the observed data. Currently, only limited information on gene regulatory pathways is available in Systems Biology. Not only the actual parameters of the examined system are unknown, also the connectivity of the components is a priori not known. However, this number is crucial for the inference process. Therefore, we propose a method, which uses the connectivity as an optimization objective in addition to the data dissimilarity (relative standard error - RSE) between experimental and simulated data.

A large-scale, real-world application of Evolutionary Multi- Criterion Optimization (EMO) is reported in this paper. The Multidisciplinary Design Optimization among aerodynamics, structures and aeroelasticity for the wing of a transonic regional jet aircraft has been performed using high-.delity models. An Euler/Navier-Stokes (N-S) Computational Fluid Dynamics (CFD) solver is employed for the aerodynamic evaluation. The NASTRAN, a commercial software, is coupled with a CFD solver for the structural and aeroelastic evaluations. Adaptive Range Multi-Objective Genetic Algorithm is employed as an optimizer. The objective functions are minimizations of block fuel and maximum takeo. weight in addition to di.erence in the drag between transonic and subsonic .ight conditions. As a result, nine non-dominated solutions have been generated. They are used for tradeo. analysis among three objectives. One solution is found to have one percent improvement in the block fuel compared to the original geometry designed in the conventional manner. All the solutions evaluated during the evolution are analyzed by Self-Organizing Map to extract key features of the design space.

The optimization and design of two different types of photonic devices – a Fibre Bragg Grating and a Microstructured Polymer Optical Fibre is presented in light of multiple conflicting objectives in both problems. The fibre grating optimization uses a fixed length real valued representation, requiring the simultaneous optimization of four objectives along with variable bounds and a single objective constraint. This led to the human selection of a Pareto-optimal design which was manufactured. The microstructured fibre design process employs a new binary encoded variable length representation. An external embryogeny, or growth process is used to guarantee the creative generation of these complex designs which are automatically valid with respect to manufacturing constraints. Some initial results are presented for the case of two objectives which relate to the bandwidth and signal loss of a design.

The paper describes the application of multiobjective evolutionary algorithms in multicriteria optimization of operational production plans in a foundry, which produces iron castings and uses hand molding machines. A mathematical model that maximizes utilization of the bottleneck machines and minimizes backlogged production is presented. The model includes all the constraints resulting from the limited capacities of furnaces and machine lines, limited resources, customers requirements and the requirements of the manufacturing process itself. Test problems based on real production data were used for evaluation of the different evolutionary algorithm variants. Finally, the plans were calculated for a nine week rolling planning horizon and compared to real historical data.

We propose a new approach for multiobjective shape optimization based on the estimation of probability distributions. The algorithm improves search space exploration by capturing landscape information into the probability distribution of the population. Correlation among design variables is also used for the computation of probability distributions. The algorithm uses finite element method to evaluate objective functions and constraints. We provide several design problems and we show Pareto front examples. The design goals are: minimum weight and minimum nodal displacement, without holes or unconnected elements in the structure.

Due to the environmental concerns that arise from the emissions produced by fossil-fueled electric power plants, the classical economic dispatch, which operates electric power systems so as to minimize only the total fuel cost, can no longer be considered alone. Thus, by environmental dispatch, emissions can be reduced by dispatch of power generation to minimize emissions. The environmental/economic dispatch problem has been most commonly solved using a deterministic approach. However, power generated, system loads, fuel cost and emission coefficients are subjected to inaccuracies and uncertainties in real-world situations. In this paper, the problem is tackled using both deterministic and stochastic approaches of different complexities. The Nondominated Sorting Genetic Algorithm – II (NSGA-II), an elitist multi-objective evolutionary algorithm capable of finding multiple Pareto-optimal solutions with good diversity in one single run is used for solving the environmental/economic dispatch problem. Simulation results are presented for the standard IEEE 30-bus system.

The integrated management of financial risks represents one of the main challenges in contemporary banking business. Deviating from a rather silo-based approach to risk management banks put increasing efforts into aggregating risks across different risk types and also across different business units to obtain an overall risk picture and to manage risk and return on a consolidated level. Up to now no state-of-the-art approach to fulfill this task has emerged yet. Risk managers struggle with a number of important issues including unstable and weakly founded correlation assumptions, inconsistent risk metrics and differing time horizons for the different risk types. In this contribution we present a novel approach that overcomes parts of these unresolved issues. By defining a multi-objective optimization problem we avoid the main drawback of other approaches which try to aggregate different risk metrics that do not fit together. A MOEA is a natural choice in our multi-objective context since some common real-world objective functions in risk management are non-linear and non-convex. To illustrate the use of a MOEA, we apply the NSGA-II to a sample real-world instance of our multi-objective problem. The presented approach is flexible with respect to modifications and extensions concerning real-world risk measurement methodologies, correlation assumptions, different time horizons and additional risk types.

The vast majority of the developed planning methods for power distribution systems consider only one objective function to optimize. This function represents the economical costs of the systems. However, there are other planning aspects that should be considered but they can not be expressed in terms of costs; therefore, they need to be formulated as separate objective functions. This paper presents a new multi-objective planning method for power distribution systems. The method is based on the Strength Pareto Evolu-tionary Algorithm 2. The edge-set encoding technique and the constrain-domination concept were applied to handle the problem constraints. The method was tested on a real large-scale system with two objective functions: economical cost and energy non-supplied. From these results, it can be said that the proposed method is suitable to resolve the multi-objective problem of large-scale power distribution system expansion planning.

This paper deals with a two-objective rescheduling problem in a job shop for alteration of due date. One objective of this problem is to minimize the total tardiness, and the other is to minimize the difference of schedule. A genetic algorithm is proposed, and a new selection operation is particularly introduced to obtain the Pareto optimal solutions in the problem. At every generation in the proposed method, two solutions are picked up as the parents. While one of them is picked up from the population, the other is picked up from the archive solution set. Then, two solutions are selected from these parents and four children generated by means of the crossover and the mutation operation. The candidates selected are not only solutions close to the Pareto-optimal front but also solutions with a smaller value of the total tardiness, because the initial solutions are around the solution in which the total tardiness is zero. For this purpose, the solution space is ranked on the basis of the archive solutions. It is confirmed from the computational result that the proposed method outperforms other methods.

Purpose of the paper is to introduce a methodology for a parameter-free multi-criterion optimization of water distribution networks. It is based on a two-level approach, with a population of inner multi-objective genetic algorithms (MOGAs) and an outer simple GA (without crossover). The inner MOGAs represent the network optimizers, while the outer GA – the

meta

GA – is a supervisor process adapting mutation and crossover probabilities of the inner MOGAs. The hypervolume metric has been adopted as fitness for the individuals at the meta-level. The methodology has been applied to a small system often studied in the literature, for which an exhaustive search of the entire decision space has allowed the determination of all Pareto-optimal solutions of interest: the choice of this simple system was done in order to compare the hypervolume metric to two performance measures (a convergence and a sparsity index) introduced on purpose. Simulations carried out show how the proposed procedure proves robust, giving better results than a MOGA alone, thus allowing a considerable ease in the network optimization process.

It has been a controversial issue in the research of cognitive science and artificial intelligence whether signal-type representations (typically connectionist networks) or symbol-type representations (e.g., semantic networks, production systems) should be used. Meanwhile, it has also been recognized that both types of information representations might exist in the human brain. In addition, symbol-type representations are often very helpful in gaining insights into unknown systems. For these reasons, comprehensible symbolic rules need to be extracted from trained neural networks. In this paper, an evolutionary multi-objective algorithm is employed to generate multiple models that facilitate the generation of signal-type and symbol-type representations simultaneously. It is argued that one main difference between signal-type and symbol-type representations lies in the fact that the signal-type representations are models of a higher complexity (fine representation), whereas symbol-type representations are models of a lower complexity (coarse representation). Thus, by generating models with a spectrum of model complexity, we are able to obtain a population of models of both signal-type and symbol-type quality, although certain post-processing is needed to get a fully symbol-type representation. An illustrative example is given on generating neural networks for the breast cancer diagnosis benchmark problem.

This paper presents a methodology to generate representations for isolated handwritten symbols, modeled as a multi-objective optimization problem. We detail the methodology, coding domain knowledge into a genetic based representation. With the help of a model on the domain of handwritten digits, we verify the problematic issues and propose a hybrid optimization algorithm, adapted to needs of this problem. A set of tests validates the optimization algorithm and parameter settings in the model’s context. The results are encouraging, as the optimized solutions outperform the human expert approach on a known problem.

This paper investigates the use of a multi-objective genetic algorithm, MOEA, to solve the scheduling problem for aircraft engine maintenance. The problem is a combination of a modified job shop problem and a flow shop problem. The goal is to minimize the time needed to return engines to mission capable status and to minimize the associated cost by limiting the number of times an engine has to be taken from the active inventory for maintenance. Our preliminary results show that the chosen MOEA called GENMOP effectively converges toward better scheduling solutions and our innovative chromosome design effectively handles the maintenance prioritization of engines.

This paper presents a new search procedure to tackle multi-objective traveling salesman problem (TSP). This procedure constructs the solution at-tractor for each of the objectives respectively. Each attractor contains the best solutions found for the corresponding objective. Then, these attractors are merged to find the Pareto-optimal solutions. The goal of this procedure is not only to generate a set of Pareto-optimal solutions, but also to provide the infor-mation about these solutions that will allow a decision-maker to choose a good compromise solution.

The problem of computing spanning trees along with specific constraints is mostly NP-hard. Many approximation and stochastic algorithms which yield a single solution, have been proposed. In this paper, we formulate the generic multi-objective spanning tree (MOST) problem and consider edge-cost and diameter as the two objectives. Since the problem is hard, and the Pareto-front is unknown, the main issue in such problem-instances is how to assess the convergence. We use a multiobjective evolutionary algorithm (MOEA) that produces diverse solutions without needing a priori knowledge of the solution space, and generate solutions from multiple tribes in order to assess movement of the solution front. Since no experimental results are available for MOST, we consider three well known diameter-constrained minimum spanning tree (dc-MST) algorithms including randomized greedy heuristics (RGH) which represents the current state of the art on the dc-MST, and modify them to yield a (near-) optimal solution-fronts. We quantify the obtained solution fronts for comparison. We observe that MOEA provides superior solutions in the entire-range of the Pareto-front, which none of the existing algorithms could individually do.

In this paper, we experiment with a combination of innovative approaches to rule induction to encourage the production of interesting sets of classification rules. These include multi-objective metaheuristics to induce the rules; measures of rule dissimilarity to encourage the production of dissimilar rules; and rule clustering algorithms to evaluate the results obtained.

Our previous implementation of NSGA-II for rule induction produces a set of cc-optimal rules (coverage-confidence optimal rules). Among the set of rules produced there may be rules that are very similar. We explore the concept of rule similarity and experiment with a number of modifications of the crowding distance to increasing the diversity of the partial classification rules produced by the multi-objective algorithm.

The design of large scale water distribution systems is a very difficult optimisation problem which invariably requires the use of time-expensive simulations within the fitness function. The need to accelerate optimisation for such problems has not so far been seriously tackled. However, this is a very important issue, since as MOEAs become more and more recognised as the ‘industry standard’ technique for water system design, the demands placed on such systems (larger and larger water networks) will quickly meet with problems of scaleup. Meanwhile, LEM (Learnable Evolution Model’) has appeared in the Machine Learning literature, and provides a general approach to integrating machine learning into evolutionary search. Published results using LEM show very great promise in terms of finding near-optimal solutions with significantly reduced numbers of evaluations. Here we introduce LEMMO (Learnable Evolution Model for Multi-Objective optimization), which is a multi-objective adaptation of LEM, and we apply it to certain problems commonly used as benchmarks in the water systems community. Compared with NSGA-II, we find that LEMMO both significantly improves performance, and significantly reduces the number of evaluations needed to reach a given target. We conclude that the general approach used in LEMMO is a promising direction for meeting the scale-up challenges in multiobjective water system design.

This papers proposes an enhanced Particle Swarm Optimization algorithm with multi-objective optimization concepts to handle constraints, and operators to keep diversity and exploration. Our approach, PESDRO, is found robust at solving redundancy and reliability allocation problems with two objective functions: reliability and cost. The approach uses redundancy of components, diversity of suppliers, and incorporates a new concept called

Distribution Optimization

. The goal is the optimal design for reliability of coherent systems. The new technique is compared against algorithms representative of the state-of-the-art in the area by using a well-known benchmark. The experiments indicate that the proposed approach matches and often outperforms such methods.

Water systems often allow efficient water uses via water reuse and/or recirculation. Defining the network layout connecting water-using processes is a complex problem which involves several criteria to optimize, frequently accomplished using Water Pinch technology, optimizing freshwater flowrates entering the system. In this paper, a multiobjective optimization model considering two criteria is presented: (i)the minimization of freshwater consumption, and (ii) the minimization of the cost of the infrastructure required to build the network that make possible the reduction of freshwater consumption. The optimization model considers water reuse between operations and wastewater treatment as the main optimization mechanism. The operation of the Cuernavaca city water distribution system was analyzed under two different operation strategies considering: leak reduction, operation of wastewater treatment plants as they currently operate, operation of wastewater treatment plants at design capacity, and construction of new infrastructure to treat 100 % of discharged wastewater. Results were obtained with

MDQL

a multiobjective optimization algorithm based on a distributed reinforcement learning framework, and they were validated with mathematical programming.

In this paper, we focus on the importance of examining characteristics of non-dominated solutions especially when a user should select only one solution from non-dominated solutions at a time, and select another solution due to the change of problem conditions. Although he can select any solution from non-dominated solutions, the similarity of selected solutions should be considered in practical cases. We show simulation results on vehicle routing problems that have two demands of customers: Normal Demand Problem (NDP) and High Demand Problem (HDP). In our definition the HDP is an extended problem of NDP. We examined two ways of applying an EMO algorithm. One is to apply it to each problem independently. The other is to apply it to the HDP with initial solutions generated from non-dominated solutions for the NDP. We show that the similarity of the obtained sets of non-dominated solutions is enhanced by the latter approach.

This paper describes the application of a new multi-objective integrated turbomachinery blade design optimisation system. The system combines an existing geometry parameterisation scheme, a well-established CFD package and a novel multi-objective variant of the Tabu Search optimisation algorithm. Two case studies, in which the flow characteristics most important to the overall performance of turbomachinery blades are optimised, are investigated. Results are presented and compared with a previous (single-objective) investigation of the problem.