Evolutionary Multi-Criterion Optimization

Over the past decade our research group has worked to operationlize our “

many-objective visual analytics

” (MOVA) framework for the design and management of complex engineered systems. Successful applications include urban water portfolio planning, satellite constellation design, airline scheduling, and product family design. The MOVA framework has four core components: (1) elicited problem conception and formulation, (2) many-objective search, (3) interactive visualization, and (4) negotiated design selection. Problem conception and formulation is the process of abstracting a practical design problem into a mathematical representation. We build on the emerging work in visual analytics to exploit interactive visualization of both the design space and the objective space in multiple heterogeneous linked views that permit exploration and discovery. Many-objective search produces a Pareto-approximate set of solutions from problem formulations that consider up to ten objectives based on current computational search capabilities. Negotiated design selection uses interactive visualization, reformulation, and optimization to discover desirable designs for implementation. Each of the activities in the framework is subject to feedback, both within the activity itself and from the other activities in the framework. These feedback processes transition formerly marginalized activities of reformulating the problem, refining the conceptual model of the problem, and refining the optimization, to represent the most critical process for innovating real world systems (i.e., learning how to frame the problems themselves). This study demonstrates insights gained by evolving the formulation of a General Aviation Aircraft (GAA) product family design problem. This problem’s considerable complexity and difficulty, along with a history encompassing several formulations, make it well-suited to demonstrate the MOVA framework. Our MOVA framework results compare a single objective, a two objective, and a ten objective formulation for optimizing the GAA product family. Highly interactive visual analytics are exploited to demonstrate how decision biases can arise for lower dimensional, highly aggregated problem formulations. As part of our efforts to operationlize the MOVA framework, we have also created rigorous search diagnostics to distinguish the efficiency, controllability, reliability, and effectiveness of multiobjective evolutionary algorithms (MOEAs). These diagnostics have distinguished the auto-adaptive behavior of our recently introduced Borg MOEA relative to a broad sampling of traditional MOEAs when addressing the GAA product family design problem.

This talk will look at various aspects of uncertainty and how they can be addressed by evolutionary multiobjective optimization.

If there is uncertainty about the user preferences, evolutionary multiobjective optimization is traditionally used to generate a representative set of Pareto-optimal solutions that caters for all potential user preferences. However, it is also possible to take into account a distribution over possible utility functions to obtain a distribution of Pareto optimal solutions that better reflects the decision maker’s likely preferences. And furthermore, it may be possible to elicit and learn the decision maker’s preferences by interacting with the decision maker during the optimization process.

If there is a trade-off between a solution’s quality and associated risk or reliability, evolutionary multiobjective optimization can simply regard the problem as a two-objective problem and provide a set of alternatives with different quality/risk trade-offs.

If the objective functions of the multi-objective problem are noisy and an accurate evaluation is not possible, for example because the evaluation is done by means of a stochastic simulation, it is no longer possible to decide with certainty whether one solution dominates another. One might calculate the probability of one solution dominating the other, and use this for selection. Still, this is based on noisy observations, and does not allow to make a confident decision about which solutions to keep in an elitist algorithm, because the solution observed as better may only have been lucky in the evaluation process. In order to improve the accuracy of the fitness estimates, it is usually possible to average fitness values over a number of evaluations. However, this is time consuming, and so it raises the question how often each solution should be evaluated such that the algorithm can progress, but at the same time computational effort is minimized. Finally, if the goal is to optimize a quantile or even the worst case, it is not obvious how to even define such a concept in a multi-objective setting.

There are two key features to any MCDA intervention, namely the problem structuring and preference modelling to ensure that the analysis is directed at solving the right problem (

effectiveness

of the intervention), and the provision of computationally efficient decision support algorithms (

efficiency

of the intervention). There are, of course problems where either the computational aspects are unchallenging so that only effectiveness requires the analyst’s attention; or where the problem is in principle well-defined but computationally complex, so that efficiency concerns dominate.

Contexts do arise in which structuring and preference modelling (e.g. identifying criteria, assessing performance in terms of these criteria and aggregation of preferences across criteria) require careful attention, especially when the numbers of criteria are large,

and

the resulting models are computationally complex. In such contexts the two components of decision support need to work together. On the one hand, the problem structuring and selection of preference models should balance the need to represent decision maker preferences faithfully with the need for a model implementation which is sufficiently responsive and computationally effective to ensure that the decision maker derives useful support. On the other hand, computational methods and approaches must recognize the cognitive limitations of the decision maker in such complex settings. For example, unaided or undirected search across the Pareto set is unlikely to be cognitively meaningful for larger numbers of criteria even with inventive use of graphics.

This paper will focus primarily on reference point methods both for problem structuring and representation, and as a guide to computational identification and exploration of the Pareto frontier. Some comments will, however, be made on the role of other methods of MCDA in this context.

Quest for knowledge has always fascinated man. However, the knowledge associated with scientific problem solving tasks comes in different shades and colors and is largely dependent on the specific problem being solved. Moreover, the methodologies for harvesting knowledge is one of the least standardized domains in the scientific and technological endeavors. An optimization task thrives at finding special solutions (the ‘optimal’ solutions) in the search space which cannot be bettered by any other solution.

We consider a multiobjective optimization scenario in which one or more objective functions may be subject to delays (or longer evaluation durations) relative to the other functions. We motivate this scenario from the viewpoint of experimental optimization problems, and derive several simple strategies for dealing with population and/or archive updates under these conditions. These are embedded in a ranking-based EMO algorithm and tested on the WFG test problems augmented with delayed objective(s). Results indicate that good performance can be achieved when the most recently generated solutions are submitted for evaluation on the delayed objective functions, and missing objective values are approximated using a fitness inheritance-based approach. Also, in general one should wait for all evaluations to complete before resuming search if the delay is short, while a non-waiting strategy should be preferred for longer delays.

Dynamic optimization problems require constant tracking of the optimum. A solution for such a problem has to be adjustable in order to remain optimal as the optimum changes. The manner of changing design parameters to predefined values is dealt with in the field of control. Common control approaches do not consider the optimality of the design, in terms of the objective function, while adjusting to the new solution. This study highlights the issue of the optimality of adaptation, and defines a new optimization problem – ”Optimization of Adaptation”. It is a multiobjective problem that considers the cost of the adaptation and the optimality while the adaptation takes place. An evolutionary algorithm is proposed in order to solve this problem, and it is demonstrated, first, with an academic example, and then with a real life application of a robotic arm control.

All standard Artifical Intelligence (AI) planners to-date can only handle a single objective, and the only way for them to take into account multiple objectives is by aggregation of the objectives. Furthermore, and in deep contrast with the single objective case, there exists no benchmark problems on which to test the algorithms for multi-objective planning.

Divide-and-Evolve

(

DaE

) is an evolutionary planner that won the (single-objective) deterministic temporal satisficing track in the last International Planning Competition. Even though it uses intensively the classical (and hence single-objective) planner YAHSP (

Yet Another Heuristic Search Planner

), it is possible to turn

DaEyahsp

into a multiobjective evolutionary planner.

A tunable benchmark suite for multi-objective planning is first proposed, and the performances of several variants of multi-objective

DaE

YAHSP

are compared on different instances of this benchmark, hopefully paving the road to further multi-objective competitions in AI planning.

Topic Modeling (TM) is a rapidly-growing area at the interfaces of text mining, artificial intelligence and statistical modeling, that is being increasingly deployed to address the ‘information overload’ associated with extensive text repositories. The goal in TM is typically to infer a rich yet intuitive summary model of a large document collection, indicating a specific collection of topics that characterizes the collection – each topic being a probability distribution over words – along with the degrees to which each individual document is concerned with each topic. The model then supports segmentation, clustering, profiling, browsing, and many other tasks. Current approaches to TM, dominated by Latent Dirichlet Allocation (LDA), assume a topic-driven document generation process and find a model that maximizes the likelihood of the data with respect to this process. This is clearly sensitive to any mismatch between the ‘true’ generating process and statistical model, while it is also clear that the quality of a topic model is multi-faceted and complex. Individual topics should be intuitively meaningful, sensibly distinct, and free of noise. Here we investigate multi-objective approaches to TM, which attempt to infer coherent topic models by navigating the trade-offs between objectives that are oriented towards coherence as well as coverage of the corpus at hand. Comparisons with LDA show that adoption of MOEA approaches enables significantly more coherent topics than LDA, consequently enhancing the use and interpretability of these models in a range of applications, without significant degradation in generalization ability.

Various real world problems, especially in financial applications, medical engineering, and game theory, involve solving a multi-objective optimization problem with a variable ordering structure. This means that the ordering relation at a point in the (multi-)objective space depends on the point. This is a striking difference from usual multi-objective optimization problems, where the ordering is induced by the Pareto-cone and remains constant throughout the objective space. In addition to variability, in many applications (like portfolio optimization) the ordering is induced by a non-convex set instead of a cone. The main purpose of this paper is to provide theoretical and algorithmic advances for general set-based variable orderings. A hypervolume based indicator measure is also proposed for the first time for such optimization tasks. Theoretical results are derived and properties of this indicator are studied. Moreover, the theory is also used to develop three indicator based algorithms for approximating the set of optimal solutions. Computational results show the niche of population based algorithms for solving multi-objective problems with variable orderings.

In multi-objective optimization, set-based performance indicators have become the state of the art for assessing the quality of Pareto front approximations. As a consequence, they are also more and more used within the design of multi-objective optimization algorithms. The

R

2 and the Hypervolume (HV) indicator represent two popular examples. In order to understand the behavior and the approximations preferred by these indicators and algorithms, a comprehensive knowledge of the indicator’s properties is required. Whereas this knowledge is available for the HV, we presented a first approach in this direction for the

R

2 indicator just recently. In this paper, we build upon this knowledge and enhance the considerations with respect to the integration of preferences into the

R

2 indicator. More specifically, we analyze the effect of the reference point, the domain of the weights, and the distribution of weight vectors on the optimization of

μ

solutions with respect to the

R

2 indicator. By means of theoretical findings and empirical evidence, we show the potentials of these three possibilities using the optimal distribution of

μ

solutions for exemplary setups.

Decreases in dominated hypervolume w.r.t a fixed reference point for the (

μ

 + 1)-SMS-EMOA are able to appear. We examine the impact of these decreases and different reference point handling techniques by providing four different algorithmic variants for selection. In addition, we show that yet further decreases can occur due to numerical instabilities that were previously not being expected. Fortunately, our findings do indicate that all detected decreases do not have a negative effect on the overall performance.

In this paper we discuss cone-based hypervolume indicators (CHI) that generalize the classical hypervolume indicator (HI) in Pareto optimization. A family of polyhedral cones with scalable opening angle

γ

is studied. These

γ

-cones can be efficiently constructed and have a number of favorable properties. It is shown that for

γ

-cones dominance can be checked efficiently and the CHI computation can be reduced to the computation of the HI in linear time with respect to the number of points

μ

in an approximation set. Besides, individual contributions to these can be computed using a similar transformation to the case of Pareto dominance cones.

Furthermore, we present first results on theoretical properties of optimal

μ

-distributions of this indicator. It is shown that in two dimensions and for linear Pareto fronts the optimal

μ

-distribution has uniform gap. For general Pareto curves and

γ

approaching zero, it is proven that the optimal

μ

-distribution becomes equidistant in the Manhattan distance. An important implication of this theoretical result is that by replacing the classical hypervolume indicator by CHI with

γ

-cones in hypervolume-based algorithms, such as the SMS-EMOA, the distribution can be shifted from a distribution that is focussed more on the knee point region to a distribution that is uniformly distributed. This is illustrated by numerical examples in 2-D. Moreover, in 3-D a similar dependency on

γ

is observed.

Optimization of problems spanning more than three objectives, called many-objective optimization, is often hard to achieve using modern algorithm design and currently available computational resources. In this paper a multiobjective evolutionary algorithm, called the Surface Evolutionary Algorithm, is extended into many-objective optimization by utilizing, for the first time, the taxi-cab metric in the optimizer. The Surface Evolutionary Algorithm offers an alternative to multi-objective optimizers that rely on the principles of domination, hypervolume and so forth. The taxi-cab metric, or Manhattan distance, is introduced as the selection criterion and the basis for calculating attraction points in the Surface Evolutionary Algorithm. This allows for fast and efficient many-objective optimization previously not attainable using this method. The Taxi-Cab Surface Evolutionary Algorithm is evaluated on a set of well-known many-objective benchmark test problems. In problems of up to 20 dimensions, this new algorithm of low complexity is tested against several modern multi-objective evolutionary algorithms. The results reveal the Taxi- Cab Surface Evolutionary Algorithm as a conceptually simple, yet highly efficient many-objective optimizer.

The Pareto envelope-based selection algorithm II (PESA-II) is a classic evolutionary multiobjective optimization (EMO) algorithm that has been widely applied in many fields. One attractive characteristic of PESA-II is its grid-based fitness assignment strategy in environmental selection. In this paper, we propose an improved version of PESA-II, called IPESA-II. By introducing three improvements in environmental selection, the proposed algorithm attempts to enhance PESA-II in three aspects regarding the performance: convergence, uniformity, and extensity. From a series of experiments on two sets of well-known test problems, IPESA-II is found to significantly outperform PESA-II, and also be very competitive against five other representative EMO algorithms.

A multi-objective optimization problem involves multiple and conflicting objectives. These conflicting objectives give rise to a set of Pareto-optimal solutions. However, not all the members of the Pareto-optimal set have equally nice properties. The classical concept of proper Pareto-optimality is a way of characterizing good Pareto-optimal solutions. In this paper, we metrize this concept to induce an ordering on the Pareto-optimal set. The use of this metric allows us to define a

proper knee

region, which contains solutions below a user-specified threshold metric. We theoretically analyze past definitions of knee points, and in particular, reformulate a commonly used nonlinear program, to achieve convergence results. Additionally, mathematical properties of the proper knee region are investigated. We also develop two multi-objective evolutionary algorithms towards finding proper knees and present simulation results on a number of test problems.

Vector evaluated particle swarm optimization (VEPSO) is a multi-swarm variant of the traditional particle swarm optimization (PSO) algorithm applied to multi-objective problems (MOPs). Each sub-objective is allocated a single sub-swarm and knowledge transfer strategies (KTSs) are used to pass information between swarms. The original VEPSO used a ring KTS, and while VEPSO has shown to be successful in solving MOPs, other algorithms have been shown to produce better results. One reason for VEPSO to perform worse than other algorithms may be due to the inefficiency of the KTS used in the original VEPSO. This paper investigates new KTSs for VEPSO in order to improve its performance. The results indicated that a hybrid strategy using parent-centric crossover (PCX) on global best solutions generally lead to a higher hypervolume while using PCX on archive solutions generally lead to a better distributed set of solutions.

This paper presents a hypervolume-based multi-objective path relinking algorithm for approximating the Pareto optimal set of multi-objective combinatorial optimization problems. We focus on integrating path relinking techniques within a multi-objective local search as an initialization function. Then, we carry out a range of experiments on bi-objective flow shop problem and bi-objective quadratic assignment problem. Experimental results and a statistical comparison are reported in the paper. In comparison with the other algorithms, one version of our proposed algorithm is very competitive. Some directions for future research are highlighted.

In this work we deal with a multiobjective biclustering problem applied to microarray data.

MOBI

nsga

[21] is one of the multiobjective metaheuristics that have been proposed to solve a new multiobjective formulation of the biclustering problem. Using

MOBI

nsga

, biclusters of good quality can be extracted. However, the generated front approximation contains a lot of gaps. Using path relinking strategies, our aim is to improve the generated front’s quality by filling the gaps with new solutions. Therefore, we propose a general scheme PR-

MOBI

nsga

of different possible hybridization of

MOBI

nsga

with path relinking strategies. A comparison of different PR-

MOBI

nsga

hybridizations is performed. Experimental results on reel data sets show that PR-

MOBI

nsga

allows to extract new interesting solutions and to improve the Pareto front approximation generated by

MOBI

nsga

.

We analyze here some properties of the maximin fitness function, which has been used by several researchers, as an alternative to Pareto optimality, for solving multi-objective optimization problems. As part of this analysis, we identify some disadvantages of the maximin fitness function and then propose mechanisms to overcome them. This leads to several selection operators for multi-objective evolutionary algorithms which are further analyzed. We incorporate them into an evolutionary algorithm, giving rise to the so-called Maximin-Clustering Multi-Objective Evolutionary Algorithm (MC-MOEA) approach. Our proposed approach is validated using standard test problems taken from the specialized literature, having from two to eight objectives. Our preliminary results indicate that our proposed approach is a good alternative to solve multi-objective optimization problems having both low dimensionality (two or three) and high dimensionality (more than three) in objective function space.

Objective functions are discrete in combinatorial optimization. In general, the number of possible values of a discrete objective is totally different from problem to problem. That is, discrete objectives have totally different granularities in different problems (In this paper, “granularity” means the width of discretization intervals). In combinatorial multiobjective optimization, a single problem has multiple discrete objectives with different granularities. Some objectives may have fine granularities with many possible values while others may have very coarse granularities with only a few possible values. Handling of such a combinatorial multiobjective problem has not been actively discussed in the EMO community. In our former study, we showed that discrete objectives with coarse granularities slowed down the search by NSGA-II, SPEA2, MOEA/D and SMS-EMOA on two-objective problems. In this paper, we first discuss why such a discrete objective deteriorates the search ability of those EMO algorithms. Next we propose the use of strong Pareto dominance in NSGA-II to improve its search ability. Then we examine the effect of discrete objectives on the performance of the four EMO algorithms on many-objective problems. An interesting observation is that discrete objectives with coarse granularities improve the search ability of NSGA-II and SPEA2 on many-objective problems whereas they deteriorate their search ability on two-objective problems. The performance of MOEA/D and SMS-EMOA is always deteriorated by discrete objectives with coarse granularities. These observations are discussed from the following two viewpoints: One is the difficulty of many-objective problems for Pareto dominance-based EMO algorithms, and the other is the relation between discrete objectives and the concept of

ε

-dominance.

In this paper, a multi-objective optimal interception problem is proposed and solved using a Multi-Objective Evolutionary Algorithm. The traditional setting of an interception engagement between pursuer and evader is targeted either at minimizing a miss distance for a given interception duration or at minimizing an interception time for a given miss distance. Such a setting overlooks an important aspect — the purpose of launching the evader in the first place. Naturally, the evader seeks to evade the pursuer (by keeping away from it), but what about hitting its target? In contrast with the traditional setting, in this paper a multi-objective game is played between a pursuer and an evader. The pursuer aims at keeping a minimum final distance between itself and the evader, which it attempts to keep away from its target. The evader, on the other hand, aims at coming as close as possible to a predefined target while keeping as far away as possible from the pursuer. Both players (pursuer and evader) utilize neural net controllers that evolve during the proposed evolutionary optimization. The game is shown to involve very interesting issues related to the decision-making process while the dilemmas of both opponents are taken into consideration.

Many-objective optimization has been gaining increasing attention in the evolutionary multiobjective optimization community, and various approaches have been developed to solve many-objective problems in recent years. However, the existing empirically comparative studies are often restricted to only a few approaches on a handful of test problems. This paper provides a systematic comparison of eight representative approaches from the six angles to solve many-objective problems. The compared approaches are tested on four groups of well-defined continuous and combinatorial test functions, by three performance metrics as well as a visual observation in the decision space. We conclude that none of the approaches has a clear advantage over the others, although some of them are competitive on most of the problems. In addition, different search abilities of these approaches on the problems with different characteristics suggest a careful choice of approaches for solving a many-objective problem in hand.

This paper examines the effect of dominance balance in many-objective optimization. The dominance balance can be defined by the ratio of the dominating space to the objective space. Here, CDAS, which is one of the most powerful evolutionary many-objective optimization algorithms, is known to be able to change the ratio of the dominating space by relaxing the definition of Pareto dominance with its user-specified parameter. However, the dominance balance is too difficult to control for the parameter in the higher-dimensional objective space. Therefore, we analyze the performance of CDAS by changing the ratio of the dominating space directly in even steps from the minimum to the maximum according to the number of objectives. The corresponding user-specified parameter in CDAS can be obtained from an equation which we assume in the paper. As benchmark test problems, we use DTLZ1, DTLZ2, DTLZ3, and DTLZ4 with two to ten objectives. From computational experiments, we can conclude that the optimal ratio of the dominating space differs depending on the problem at hand. It can be also said that the performance of CDAS is good especially when the ratio of the dominating space is small enough but not the minimum. Based on these observations, we propose a new version of CDAS called CDAS-D which controls the ratio of the dominating space dynamically during optimization.

In this paper, we use an alternative preference relation that couples an achievement function and the

ε

-indicator in order to improve the scalability of a Multi-Objective Evolutionary Algorithm (

moea

) in many-objective optimization problems. The resulting algorithm was assessed using the Deb-Thiele-Laumanns-Zitzler (

dtlz

) and the Walking- Fish-Group (

wfg

) test suites. Our experimental results indicate that our proposed approach has a good performance even when using a high number of objectives. Regarding the

dtlz

test problems, their main difficulty was found to lie on the presence of dominance resistant solutions. In contrast, the hardness of

wfg

problems was not found to be significantly increased by adding more objectives.

NSGA-II and its contemporary EMO algorithms were found to be vulnerable in solving many-objective optimization problems having four or more objectives. It is not surprising that EMO researchers have been concentrating in developing efficient algorithms for many-objective optimization problems. Recently, authors suggested an extension of NSGA-II (NSGA-III) which is based on the supply of a set of reference points and demonstrated its working in three to 15-objective optimization problems. In this paper, NSGA-III’s reference point allocation task is made adaptive so that a better distribution of points can be found. The approach is compared with NSGA-III and a previous adaptive approach on a number of constrained and unconstrained many-objective optimization problems. NSGA-III and its adaptive extension proposed here open up new directions for research and development in the area of solving many-objective optimization problems.

Many-objective problems are becoming common in several real-world application domains and there is a growing interest to develop evolutionary many-objective optimizers that can solve them effectively. Studies on selection for many-objective optimization and most recently studies on the characteristics of many-objective landscapes, the effectiveness of operators of variation, and the effects of large populations have proved successful to advance our understanding of evolutionary many-objective optimization. This work proposes an evolutionary many-objective optimization algorithm that uses adaptive

ε

-dominance principles to select survivors and also to create neighborhoods to bias mating, so that solutions will recombine with other solutions located close by in objective space. We investigate the performance of the proposed algorithm on DTLZ continuous problems, using a short number of generations to evolve the population, varying population size from 100 to 20000 individuals. Results show that the application of adaptive

ε

-dominance principles for survival selection as well as for mating selection improves considerably the performance of the optimizer.

Various multi-objective evolutionary algorithms (MOEAs) have been developed to help a decision maker (DM) search for his/her preferred solutions to multi-objective problems. However, none of these approaches has catered simultaneously for the two fundamental ways that DM can specify his/her preferences: weights and aspiration levels. In this paper, we propose an approach named iPICEA-g that allows the DM to specify his preference in either format. iPICEA-g is based on the preference-inspired co-evolutionary algorithm (PICEA-g). Solutions are guided toward regions of interest (ROIs) to the DM by co-evolving sets of goal vectors exclusively generated in the ROIs. Moreover, a friendly decision making technique is developed for interaction with the optimization process: the DM specifies his preferences easily by interactively brushing his preferred regions in the objective space. No direct elicitation of numbers is required, reducing the cognitive burden on DM. The performance of iPICEA-g is tested on a set of benchmark problems and is shown to be good.

Indicator-based evolutionary algorithms are amongst the best performing methods for solving multi-objective optimization (MOO) problems. In reinforcement learning (RL), introducing a quality indicator in an algorithm’s decision logic was not attempted before. In this paper, we propose a novel on-line multi-objective reinforcement learning (MORL) algorithm that uses the hypervolume indicator as an action selection strategy. We call this algorithm the

hypervolume-based MORL

algorithm or

HB-MORL

and conduct an empirical study of the performance of the algorithm using multiple quality assessment metrics from multi-objective optimization. We compare the hypervolume-based learning algorithm on different environments to two multi-objective algorithms that rely on scalarization techniques, such as the linear scalarization and the weighted Chebyshev function. We conclude that HB-MORL significantly outperforms the linear scalarization method and performs similarly to the Chebyshev algorithm without requiring any user-specified emphasis on particular objectives.

Various notions of preferences exist in multi-objective optimization and the decision making community. On the one hand, preferences appear as domination relations that are stronger than the classical Pareto-domination, while on the other hand, they introduce relative importance on the objective functions. In this way, preferences can appear in both domination relations and objectives. In this paper, we analyze and put together different preference models and classify them into two groups. We theoretically analyze many preference models within these groups. In particular, we are interested in curvature/ slope based models where the preferred set depend upon the curvature of efficient front. This amounts to having a direct control on trade-offs among the objective functions. A related concept of cone-based hypervolume is also theoretically investigated in this paper. Special emphasis is placed on equitable efficiency and its applications. Furthermore, we present two algorithms for finding solutions that are compatible with a given preference model.

In order to approximate the set of Pareto optimal solutions, several evolutionary multi-objective optimization (EMO) algorithms transfer the multi-objective problem into several independent single-objective ones by means of scalarizing functions. The choice of the scalarizing functions’ underlying search directions, however, is typically problem-dependent and therefore difficult if no information about the problem characteristics are known before the search process. The goal of this paper is to present new ideas of how these search directions can be computed

adaptively

during the search process in a

cooperative

manner. Based on the idea of Newton’s law of universal gravitation, solutions attract and repel each other

in the objective space

. Several force-based EMO algorithms are proposed and compared experimentally on general bi-objective

ρ

MNK landscapes with different objective correlations. It turns out that the new approach is easy to implement, fast, and competitive with respect to a (

μ

 + 

λ

)-SMS-EMOA variant, in particular if the objectives show strong positive or negative correlations.

Selection plays a key role in a

multiobjective evolutionary algorithm (MOEA)

. The dominance based selection operators or indicator based ones are widely used in most current MOEAs. This paper studies another kind of selection, in which a model is firstly built to approximate the Pareto front and then guides the selection of promising solutions into the next generation. Based on this idea, we propose two

approximation model guided selection (AMS)

operators in this paper: one uses a zero-order model to approximate the Pareto front, and the other uses a first-order model. The experimental results show that the new AMS operators performs well on some test instances.

Decomposition based evolutionary approaches such as MOEA/D and its variants have been quite successful in solving various classes of two and three objective optimization problems. While there have been some attempts to modify the dominance based approaches such as NSGA-II and SPEA2 to deal with many-objective optimization, there are few attempts to extend the capability of decomposition based approaches. The performance of a decomposition based approach is dependent on (a) the mechanism of reference points generation i.e. one which needs to be scalable and computationally efficient (b) the method to simultaneously deal with conflicting requirements of convergence and diversity and finally (c) the means to use the information of neighboring subproblems efficiently. In this paper, we introduce a decomposition based evolutionary algorithm, wherein the reference points are generated via systematic sampling and an adaptive epsilon scheme is used to manage the balance between convergence and diversity. To deal with constraints efficiently, an adaptive epsilon formulation is adopted. The performance of the algorithm is highlighted using standard benchmark problems i.e. DTLZ1 and DTLZ2 for 3, 5, 8, 10 and 15 objectives, the car side impact problem, the water resource management problem and the constrained ten-objective general aviation aircraft (GAA) design problem. The study clearly highlights that the proposed algorithm is better or at par with recent reference direction based approaches.

Decomposition-based algorithms seem promising for many-objective optimization problems. However, the issue of selecting a set of weighting vectors for more than two objectives is still unresolved and

ad-hoc

methods are predominantly used. In the present work, a novel concept is introduced which we call generalized decomposition. Generalized decomposition enables the analyst to adapt the generated distribution of Pareto optimal points, according to the preferences of the decision maker. Also it is shown that generalized decomposition unifies the three performance objectives in multi-objective optimization algorithms to only one, that of convergence to the Pareto front.

In some technical applications like multiobjective online control an evenly spaced approximation of the Pareto front is desired. Since standard evolutionary multiobjective optimization (EMO) algorithms have not been designed for that kind of approximation we propose an archive-based plug-in method that builds an evenly spaced approximation using averaged Hausdorff measure between archive and reference front. In case of three objectives this reference font is constructed from a triangulated approximation of the Pareto front from a previous experiment. The plug-in can be deployed in online or offline mode for any kind of EMO algorithm.

MOEA/D is a simple but powerful scalarizing function-based EMO algorithm. Its high search ability has been demonstrated for a wide variety of multiobjective problems. MOEA/D can be viewed as a cellular algorithm. Each cell has a different weight vector and a single solution. A certain number of the nearest cells are defined for each cell as its neighbors based on the Euclidean distance between weight vectors. A new solution is generated for each cell from current solutions in its neighboring cells. The generated solution is compared with the current solutions in the neighboring cells for solution replacement. In this paper, we examine the relation between the neighborhood size and the performance of MOEA/D. In order to examine the effect of local mating and local replacement separately, we use a variant of MOEA/D with two different neighborhoods: One is for local mating and the other is for local replacement. The performance of MOEA/D with various combinations of two neighborhoods is examined using the hypervolume in the objective space and a diversity measure in the decision space for many-objective problems. Experimental results show that MOEA/D with a large replacement neighborhood has high search ability in the objective space. However, it is also shown that small replacement and mating neighborhoods are beneficial for diversity maintenance in the decision space. It is also shown that the appropriate specification of two neighborhoods strongly depends on the problem.

Interaction between criteria and hierarchical structure of criteria are nowadays two important issues in Multiple Criteria Decision Analysis (MCDA). Interaction between criteria is often dealt with fuzzy integrals, especially the Choquet integral. To handle the hierarchy of criteria in MCDA, a methodology called Multiple Criteria Hierarchy Process (MCHP) has been recently proposed. It permits consideration of preference relations with respect to a subset of criteria at any level of the hierarchy. In this paper, we propose to apply MCHP to the Choquet integral. In this way, using the Choquet integral and the MCHP, it is possible to compare two alternatives not only globally, but also partially, taking into account a particular subset of criteria and the possible interaction between them.

In the context of complex equipment, inspection has an important role to play in maintaining operations at a suitable performance. In fact, for this kind of system, failures are not immediate. Therefore, the concept of delay time is very useful as a two-step failure process, as a basis for constructing inspection models. Another aspect worth noticing is the fact that, in practice, when the decision-maker decides on the time between inspections, he/she takes different aspects into account in a non-structured way. This happens because the majority of inspection models deal with the problem using an optimization approach, where only one aspect is considered. So, the main contribution of this article is to put forward a multicriteria decision model in order to aid maintenance planning. This model takes the decision maker’s preferences into account, as well as, the most important aspects, when considering setting the inspection intervals for periodic condition monitoring, and which are the cost and downtime associated with the inspection policy.

This paper introduces the concept of a ranking veto based on two new data provided by decision makers (DMs) in an additive model approach: the veto threshold and a value reduction factor (VRF). The use of additive models for aggregating group preferences over available alternatives implies the existence of compensatory effects in the process. In traditional approaches, the final result may assign undesirable or unacceptable alternatives to higher positions in the ranking, thus causing conflicts among DMs. The model proposed softens the compensatory effects on additive models. By way of illustration, a base station allocation problem for a Telecommunication Company is presented as a numerical application. In addition to the model proposed being simple to use, it enables a group to form a collective and/or consensual view on a decision problem.

Automated innovization is an unsupervised machine learning technique for extracting useful design knowledge from Pareto-optimal solutions in the form of mathematical relationships of a certain structure. These relationships are known as design principles. Past studies have shown the applicability of automated innovization on a number of engineering design optimization problems using a multiplicative form for the design principles. In this paper, we generalize the structure of the obtained principles using a tree-based genetic programming framework. While the underlying innovization algorithm remains the same, evolving multiple trees, each representing a different design principle, is a challenging task. We also propose a method for introducing dimensionality information in the search process to produce design principles that are not just empirical in nature, but also meaningful to the user. The procedure is illustrated for three engineering design problems.

We propose a new type of multi-objective genetic programming (MOGP) for multi-objective design exploration (MODE). The characteristic of the new MOGP is the simultaneous symbolic regression to multiple objective functions using correlation coefficients. This methodology is applied to non-dominated solutions of the multi-objective design optimization problem to extract information between objective functions and design parameters. The result of MOGP is symbolic equations that are highly correlated to each objective function through a single GP run. These equations are also highly correlated to several objective functions. The results indicate that the proposed MOGP is capable of finding new design parameters more closely related to the objective functions than the original design parameters. The proposed MOGP is applied to the test problem and the practical design problem to evaluate the capability.

Multiobjective approaches to data clustering return sets of solutions that correspond to trade-offs between different clustering objectives. Here, an established ensemble technique (evidence-accumulation) is applied to the identification of shared features within the set of clustering solutions returned by the multiobjective clustering method MOCK. We show that this approach can be employed to achieve a four-fold reduction in the number of candidate solutions, whilst maintaining the accuracy of MOCK’s best clustering solutions. We also find that the resulting knowledge provides a novel design basis for the visual exploration and comparison of different clustering solutions. There are clear parallels with recent work on ‘innovization’, where it was suggested that the design-space analysis of the solution sets returned by multiobjective optimization may provide deep insight into the core design principles of good solutions.

In this paper two novel methods for projecting high dimensional data into two dimensions for visualisation are introduced, which aim to limit the loss of

dominance

and

Pareto shell

relationships between solutions to multi-objective optimisation problems. It has already been shown that, in general, it is impossible to completely preserve the dominance relationship when mapping from a higher to a lower dimension – however, approaches that attempt this projection with minimal loss of dominance information are useful for a number of reasons. (1) They may represent the data to the user of a multi-objective optimisation problem in an intuitive fashion, (2) they may help provide insights into the relationships between solutions which are not immediately apparent through other visualisation methods, and (3) they may offer a useful visual medium for

interactive

optimisation. We are concerned here with examining (1) and (2), and developing relatively rapid methods to achieve visualisations, rather than generating an entirely new search/optimisation problem which has to be solved to achieve the visualisation– which may prove infeasible in an interactive environment for real time use. Results are presented on randomly generated data, and the search population of an optimiser as it progresses. Structural insights into the evolution of a set-based optimiser that can be derived from this visualisation are also discussed.

Recently, Evolutionary Trace Transform (ETT) has been developed to extract efficient features (called triple features) for invariant image identification using multi-objective evolutionary algorithms. This paper compares two methods of Evolutionary Trace Transform (method I and II) evolved through similar objectives by minimizing the within-class variance (

S

w

) and maximizing the between-class variance (

S

b

) of image features. However, each solution on the Pareto front of method I represents one triple features (i.e. 1D) to be combined with another solution to construct 2D feature space, whereas each solution on the Pareto front of method II represents a complete pair of triple features (i.e. 2D). Experimental results show that both methods are able to produce stable and consistent features. Moreover, method II has denser solutions distributed in the convex region of the Pareto front than in method I. Nevertheless, method II takes longer time to evolve than method I. Although the Trace transforms are evolved offline on one set of low resolution (64×64) images, they can be applied to extract features from various standard 256×256 images.

Instrument identification in polyphonic audio recordings is a complex task which is beneficial for many music information retrieval applications. Due to the strong spectro-temporal differences between the sounds of existing instruments, different instrument-related features are required for building individual classification models. In our work we apply a multi-objective evolutionary feature selection paradigm to a large feature set minimizing both the classification error and the size of the used feature set. We compare two different feature selection methods. On the one hand we aim at building specific tradeoff feature sets which work best for the identification of a particular instrument. On the other hand we strive to design a generic feature set which on average performs comparably for all instrument classification tasks. The experiments show that the selected generic feature set approaches the performance of the selected instrument-specific feature sets, while a feature set specifically optimized for identifying a particular instrument yields degraded classification results if it is applied to other instruments.

Tool selection for roughing components is a complex problem. Attempts to automate the process are further complicated by computationally expensive evaluations. In previous work we assessed the performance of several single-objective metaheuristic algorithms on the tool selection problem in rough machining and found them to successfully return optimal solutions using a low number of evaluations, on simple components. However, experimenting on a more complex component proved less effective. Here we show how search success can be improved by multi-objectivizing the problem through constraint relaxation. Operating under strict evaluation budgets, a multiobjective algorithm (NSGA-II) is shown to perform better than single-objective techniques. Further improvements are gained by the use of guided search. A novel method for guidance, “Guided Elitism”, is introduced and compared to the Reference Point method. In addition, we also present a modified version of NSGA-II that promotes more diversity and better performance with small population sizes.

Resin Transfer Molding (RTM) and Compression RTM (CRTM) are popular methods for high volume production of superior quality composite parts. However, the design parameters of these methods must be carefully chosen in order to reduce cycle time, capital layout and running costs, while maximizing final part quality. These objectives are principally governed by the filling and curing phases of the manufacturing cycle, which are strongly coupled in the case of completely non-isothermal processing. Independently optimizing either phase often leads to conditions that adversely affect the progress of the other. In light of this fact, this work models the complete manufacturing cycle as a static Stackelberg game with two virtual decision makers (DMs) monitoring the filling and curing phases, respectively. The model is implemented through a Bi-level Multi-objective Genetic Algorithm (BMOGA), which is integrated with an Artificial Neural Network (ANN) for rapid function evaluations. The obtained results are thus efficient with respect to the objectives of both DMs and provide the manufacturer with a diverse set of solutions to choose from.

In the automotive industry the calibration of the engine control unit is getting more and more complex because of many various boundary conditions, like the demand on

CO

2

and fuel reduction. One important calibration problem is the parameter estimation for the model of the intake system of the combustion engine. This system is modeled by a physically motivated system, which can be parameterized by black-box models, like neural nets and characteristic diagrams, whose parameters must be set by an intelligent optimizer. Further, two contradictory aims must be considered and the engineer expects at the end of the optimization a pareto-front, where he can choose the best settings for the application from the pareto-optimal parameter estimations. To solve this multi-criteria optimization task an evolutionary algorithm is used, which is a combination of a genetic algorithm and an evolutionary strategy. This evolutionary algorithm is like all other stochastic searching methods leaned on the naturally biological evolution. It combines the well-known covariance matrix adaption for the mutation of the individuals with the S-metric selection for the multi-criteria fitness assignment of the individuals. It also improves these combination by the use of many subpopulations, which work parallel on various clusters, and by the use of an intelligent

DoE

-strategy for the initialization of the start individuals. With these improvements the developed evolutionary algorithm can easily fit the model of the intake system to test bed measurements and can provide the user a pareto-optimal set of parameters, on which he can choose on his own that ones, which he find most plausible.

In this paper a real-world automotive engine calibration problem has been distilled into a ten-objective many-objective optimisation problem. The objectives include dynamic measures of combustion quality as well as sensitivity quantities related to a control system actuator, which exhibits significant variation. To address the computational demands of such a high-dimensional problem, use was made of parallel computing. The objective reduction process consisted of four stages and progressively reduced objective dimensionality where evidence of local objective harmony existed. It involved the advice of the calibration engineer at various stages on objective priorities and on whether to discard clusters containing solutions of no apparent interest. This process culminated in two sub-problems, one of three and one of four conflicting objectives. From the corresponding Pareto-optimal populations (POPs), visualisation together with objective priorities was used to identify preferred solutions. A comparison of the resulting POP, preferred solution and an independently generated, manually tuned calibration was made for each of the two sub-problems. In general, the preferred solution outperformed the independent calibration.

An multi-objective optimization (MOO) and knowledge extraction were conducted for a structural design of a regional jet horizontal tail using Multi-Objective Design Exploration (MODE). MODE reveals the structure of the design space from the trade-off information and visualizes it as a panorama for a Decision Maker. The present form of MODE consists of Kriging model, Adaptive Range Multi-Objective Genetic Algorithm and Self-Organizing Map (SOM). Combination between the stringer-pitch and the rib-pitch was optimized based on detailed buckling evaluation and MSC/NASTRAN static analysis using realistic aircraft structural model. The resulting Kriging model provided several solutions with improvements, both in the structural weight and the number of structural components, compared with the baseline design. Furthermore, SOM divided the design space into clusters with specific design features. The acquired design knowledge from the present application has been utilized for the horizontal tail design of Mitsubishi Regional Jet (MRJ).

This paper presents a satellite constellation refueling optimization problem. The design variables, composed of both serial integers and real numbers, are the refueling sequence, service time and orbital transfer time, while the objectives are the mean mission completion time and propellant consumed by orbital maneuvers. The problem is solved by a mixed-integer version of the MOAA, a recently introduced multi-objective variant of the Alliance Algorithm. This approach is compared, using the epsilon and hypervolume indicators, with a hybrid-encoding genetic algorithm (GA) composed of NSGA-II and an integer-coded GA for classical traveling salesman problems (TSP). The results show that the MOAA is able to outperform the hybrid approach based on NSGA-II by finding a better Pareto front which provides more useful information to the decision-maker.

The problem of design optimisation for planetary landing systems, which must address multiple criteria and constraints covering, for example, mass, trajectory, risk, and the cost of technology developments, is introduced. The approach used to solve this problem in the context of the real world issues faced and the decisions made is presented, and we demonstrate a tool which has been used in this way to explore the parametric space of possible landing systems for a number of planned and possible European missions to Mars, for use in early phase sizing studies.

We compare the ability of single and multi-objective evolutionary algorithms to evolve tunable self-sustained genetic oscillators. Our research is focused on the influence of objective setup on the success rate of evolving self-sustained oscillations and the tunability of the evolved oscillators. We compare temporal and frequency domain fitness functions for single and multi-objective evolution of the parameters in a three-gene genetic regulatory network. We observe that multiobjectivization can hinder convergence when decomposing a period specific based single objective setup in to a multi-objective setup that includes a frequency specific objective. We also find that the objective decomposition from a frequency specified single objective setup to a multi-objective setup, which also specifies period, enable the synthesis of oscillatory dynamics. However this does not help to enhance tunability. We reveal that the use of a helper function in the frequency domain improves the tunability of the oscillators, compared to a time domain based single objective, even if no desired frequency is specified.

In this paper, a multicriteria approach for ranking the performance of the economic sectors of the Sinaloa economy is proposed, and the most attractive sectors are identified. To achieve this goal, the software SADAGE was used for solving ranking problems, which require one to rank a set of alternatives - given evaluations in terms of several criteria - in decreasing order of preference. The approach uses the ELECTRE III method to construct a valued outranking relation and then a multiobjective evolutionary algorithm (MOEA) to exploit the relation to obtain a recommendation. The retail and manufacturing sectors were ranked first in all the rankings; the utilities sector was ranked second in all the rankings; the mining sector and the management of companies and enterprises sector were ranked lowest. The results of this application can be useful for investors, business leaders, and policy-makers. This study also contributes to an important, yet relatively new, body of application-based literature that investigates multicriteria approaches to decision making that use fuzzy theory and evolutionary multi-objective optimization methods.

Social cost benefit analysis often involves consideration of non-monetary outcomes. Multi-objective optimisation is an appropriate method for handling problems of this type, but many decision-makers have a strong mistrust of the approach. Reflections by the authors on real experiences supporting decision-makers suggest that the key barriers to using multi-objective methods for social cost benefit analysis include: (i) the inadequacy of current social systems models for measuring the end benefits provided by a candidate solution; (ii) the lack of appropriate societal preference estimates for resolving the inherent trade-offs between objectives; and (iii) the lack of practical examples, case studies and guidance which demonstrate that the approach works well.

The protection of the environment against pollutants produced by aviation is of great concern in the 21st century. Among the multiplicity of proposed solutions, modifying flight profiles for existing aircraft is a promising approach. The aim is to deliver and understand the trade-off between environmental impact and operating costs. This work will illustrate the optimisation process of aircraft trajectories by minimising fuel consumption and flight time for the climb phase of an aircraft that belongs to A320 category. To achieve this purpose a new variant of a multi-objective Tabu Search optimiser was evolved and integrated within a computational framework, called GATAC, that simulates flight profiles based on altitude and speed.

Several methods were developed to solve cost-extensive multi-criteria optimization problems by reducing the number of function evaluations by means of surrogate optimization. In this study, we apply different multi-criteria surrogate optimization methods to improve (tune) an event-detection software for water-quality monitoring. For tuning two important parameters of this software, four state-of-the-art methods are compared: S-Metric-Selection Efficient Global Optimization (SMS-EGO), S-Metric-Expected Improvement for Efficient Global Optimization SExI-EGO, Euclidean Distance based Expected Improvement Euclid-EI (here referred to as MEI-SPOT due to its implementation in the Sequential Parameter Optimization Toolbox SPOT) and a multi-criteria approach based on SPO (MSPOT).

Analyzing the performance of the different methods provides insight into the working-mechanisms of cutting-edge multi-criteria solvers. As one of the approaches, namely MSPOT, does not consider the prediction variance of the surrogate model, it is of interest whether this can lead to premature convergence on the practical tuning problem. Furthermore, all four approaches will be compared to a simple SMS-EMOA to validate that the use of surrogate models is justified on this problem.

The network reconfiguration for service restoration in distribution systems is a combinatorial complex optimization problem that usually involves multiple non-linear constraints and objectives functions. For large networks, no exact algorithm has found adequate restoration plans in real-time, on the other hand, Multi-objective Evolutionary Algorithms (MOEA) using the Node-depth enconding (MEAN) is able to efficiently generate adequate restorations plans for relatively large distribution systems. An MOEA for the restoration problem should provide restoration plans that satisfy the constraints and reduce the number of switching operations in situations of one fault. For diversity of real-world networks, those goals are met by improving the capacity of the MEAN to explore both the search and objective spaces. This paper proposes a new method called MEA2N with Strength Pareto table (MEA2N-STR) properly designed to restore a feeder fault in networks with significant different bus sizes: 3 860 and 15 440. The metrics

R

2

,

R

3

, Hypervolume and

ε

-indicators were used to measure the quality of the obtained fronts.

This paper presents a real world application that lead to the construction of a decision support system built to support maintenance planning in an electrical power distribution company. The outcome of the DSS is to determine the order of priority in which potential failure repair orders should be conducted. This company-specific problem has been structured and is similar to that of most electrical power distribution companies, since this company has a complex distribution network with different types of customers which leads it to considering different criteria such as income losses, the probability of service interruptions, national regulation criteria, and so forth. There is a specific budget for potential failure repair orders, while functional failure repairs are not modeled at this managerial level since once the service should not be interrupted and involves long term planning. During periodical inspections the entire distribution network is inspected and a database with all this data is maintained. Thereafter, the potential failures in the distribution network are converted into maintenance orders which typically amount to more than 4 times the annual sum allocated for potential failure repairs budget. After having structured the problem, a DSS was built to support maintenance planning that will result in an annual maintenance plan based on the company´s strategic criteria and national regulations.

In the process of multi-objective optimization of real-world systems, uncertainties have to be taken into account. We focus on a particular type of uncertainties, related to uncertain objective functions. In the literature, such uncertainties are considered as noise that should be eliminated to ensure convergence of the optimization process to the most accurate solutions. In this paper, we adopt a different point of view and propose a new framework to handle uncertain objective functions in a Pareto-based multi-objective optimization process: we consider that uncertain objective functions are not only biasing errors due to the optimization, but also contain useful information on the impact of uncertainties on the system to optimize. From the Probability Density Function (PDF) of random variables modeling uncertainties of objective functions, we determine the ”Uncertain Pareto Front”, defined as a ”tradeoff probability function” in objective space and a ”solution probability function” in decision space. Then, from the ”Uncertain Pareto Front”, we show how the reliable solutions,

i

.

e

. the most probable solutions, can be identified. We propose a Monte Carlo process to approximate the ”Uncertain Pareto Front”. The proposed process is illustrated through a case study of a famous engineering problem: the welded beam design problem aimed at identifying solutions featuring at the same time low cost and low deflection with respect to an uncertain Young’s modulus.

This work presents a methodology for modeling the information concerning preferences which is acquired from a Decision-Maker (DM), in the course of one run of an interactive evolutionary multiobjective optimization algorithm. Specifically, the Interactive Territory Defining Evolutionary Algorithm (iTDEA) is considered here. The preference model is encoded as a Neural Network (the NN-DM) which is trained using ordinal information only, as provided by the queries to the DM. With the NN-DM model, the preference information becomes available, after the first run of the interactive evolutionary multiobjective optimization algorithm, for being used in other decision processes. The proposed methodology can be useful in those situations in which a recurrent decision process must be performed, associated to several runs of a multiobjective optimization algorithm over the same problem with different parameters in each run, assuming that the utility function is not dependent on the changing parameters. The main point raised here is: the information obtained from the DM should not be discarded, leading to a new complete interaction with the DM each time a new run of a problem of the same class is required.

An algorithm that returns as low-cost solutions as possible at any moment of its execution is said to have a good anytime behaviour. The problem of optimising anytime behaviour can be modelled as a bi-objective non-dominated front, where the goal is to minimise both time and cost. Using a unary quality measure such as the hypervolume indicator, the analysis of the anytime behaviour can be converted into a single-objective problem. In this manner, available automatic configuration tools can be applied to improve the anytime behaviour of an algorithm. If we want to optimise the anytime behaviour of multi-objective algorithms, we may apply again unary quality measures to obtain a scalar value for measuring the obtained approximation to the Pareto front. Thus, for multi-objective algorithms, the anytime behaviour may be described in terms of the curve of the hypervolume over time, and the quality of this bi-objective tradeoff curve be evaluated according to its hypervolume. Using this approach, we can automatically improve the anytime behaviour of multi-objective evolutionary algorithms (MOEAs). In this article, we first introduce this approach and then experimentally study the improvements obtained considering three MOEAs, namely, IBEA, NSGA-II and SPEA2.