Evolutionary Multi-Criterion Optimization

The trade-off solutions of a multi-objective optimization problem, as a whole, often hold crucial information in the form of rules. These rules, if predominantly present in most trade-off solutions, can be considered as the characteristic features of the Pareto-optimal front. Knowledge of such features, in addition to providing better insights to the problem, enables the designer to handcraft solutions for other optimization tasks which are structurally similar to it; thus eliminating the need to actually optimize.

Innovization

is the process of extracting these so called

design rules

. This paper proposes to move a step closer towards the complete

automation

of the innovization process through a niched clustering based optimization technique. The focus is on obtaining multiple design rules in a single knowledge discovery step using the niching strategy.

The use of multi-objective evolutionary algorithms for solving black-box problems with multiple conflicting objectives has become an important research area. However, when no gradient information is available, the examination of formal convergence or optimality criteria is often impossible. Thus, sophisticated heuristic online stopping criteria (OSC) have recently become subject of intensive research. In order to establish formal guidelines for a systematic research, we present a taxonomy of OSC in this paper. We integrate the known approaches within the taxonomy and discuss them by extracting their building blocks. The formal structure of the taxonomy is used as a basis for the implementation of a comprehensive MATLAB toolbox. Both contributions, the formal taxonomy and the MATLAB implementation, provide a framework for the analysis and evaluation of existing and new OSC approaches.

The Steady State variants of the Multi-Objective Covariance Matrix Adaptation Evolution Strategy (SS-MO-CMA-ES) generate one offspring from a uniformly selected parent. Some other parental selection operators for SS-MO-CMA-ES are investigated in this paper. These operators involve the definition of multi-objective rewards, estimating the expectation of the offspring survival and its Hypervolume contribution. Two selection modes, respectively using tournament, and inspired from the Multi-Armed Bandit framework, are used on top of these rewards. Extensive experimental validation comparatively demonstrates the merits of these new selection operators on unimodal MO problems.

In this paper, we examine the problem of maintaining an approximation of the set of nondominated points visited during a multiobjective optimization, a problem commonly known as archiving. Most of the currently available archiving algorithms are reviewed, and what is known about their convergence and approximation properties is summarized. The main scenario considered is the restricted case where the archive must be updated online as points are generated one by one, and at most a fixed number of points are to be stored in the archive at any one time. In this scenario, the

$\vartriangleleft$

-monotonicity of an archiving algorithm is proposed as a weaker, but more practical, property than negative efficiency preservation. This paper shows that hypervolume-based archivers and a recently proposed multi-level grid archiver have this property. On the other hand, the archiving methods used by SPEA2 and NSGA-II do not, and they may

$\vartriangleleft$

-deteriorate with time. The

$\vartriangleleft$

-monotonicity property has meaning on any input sequence of points. We also classify archivers according to limit properties, i.e. convergence and approximation properties of the archiver in the limit of infinite (input) samples from a finite space with strictly positive generation probabilities for all points. This paper establishes a number of research questions, and provides the initial framework and analysis for answering them.

Traditional Evolutionary Multiobjective Optimization techniques, based on derivative-free dominance-based search, allowed the construction of efficient algorithms that work on rather arbitrary functions, leading to Pareto-set sample estimates obtained in a single algorithm run, covering large portions of the Pareto-set. However, these solutions hardly reach the exact Pareto-set, which means that Pareto-optimality conditions do not hold on them. Also, in problems with high-dimensional objective spaces, the dominance-based search techniques lose their efficiency, up to situations in which no useful solution is found. In this paper, it is shown that both effects have a common geometric structure. A gradient-based descent technique, which relies on the solution of a certain stochastic differential equation, is combined with a multiobjective line-search descent technique, leading to an algorithm that indicates a systematic solution for such problems. This algorithm is intended to serve as a proof of concept, allowing the comparison of the properties of the gradient-search principle with the dominance-search principle. It is shown that the gradient-based principle can be used to find solutions which are truly Pareto-critical, satisfying first-order conditions for Pareto-optimality, even for many-objective problems.

Relaxed forms of Pareto dominance have been shown to be the most effective way in which evolutionary algorithms can progress towards the Pareto-optimal front with a widely spread distribution of solutions. A popular concept is the

ε

-dominance technique, which has been employed as an archive update strategy in some multiobjective evolutionary algorithms. In spite of the great usefulness of the

ε

-dominance concept, there are still difficulties in computing an appropriate value of

ε

that provides the desirable number of nondominated points. Additionally, several viable solutions may be lost depending on the hypergrid adopted, impacting the convergence and the diversity of the estimate set. We propose the concept of cone

ε

-dominance, which is a variant of the

ε

-dominance, to overcome these limitations. Cone

ε

-dominance maintains the good convergence properties of

ε

-dominance, provides a better control over the resolution of the estimated Pareto front, and also performs a better spread of solutions along the front. Experimental validation of the proposed cone

ε

-dominance shows a significant improvement in the diversity of solutions over both the regular Pareto-dominance and the

ε

-dominance.

Decision making in the presence of multiple and conflicting objectives requires preference from the decision maker. The decision maker’s preferences give rise to a domination structure. Till now, most of the research has been focussed on the standard domination structure based on the Pareto-domination principle. However, various real world applications like medical image registration, financial applications, multi-criteria

n

-person games, among others, or even the preference model of decision makers frequently give rise to a so-called

variable

domination structure, in which the domination itself changes from point to point. Although variable domination is studied in the classical community since the early seventies, we could not find a single study in the evolutionary domain, even though, as the results of this paper show, multi-objective evolutionary algorithms can deal with the vagaries of a variable domination structure. The contributions of this paper are multiple-folds. Firstly, the algorithms are shown to be able to find a well-diverse set of the optimal solutions satisfying a variable domination structure. This is shown by simulation results on a number of test-problems. Secondly, it answers a hitherto open question in the classical community to develop a numerical method for finding a well-diverse set of such solutions. Thirdly, theoretical results are derived which facilitate the use of an evolutionary multi-objective algorithm. The theoretical results are of importance on their own. The results of this paper adequately show the niche of multi-objective evolutionary algorithms in variable preference modeling.

The attainment function provides a description of the location of the distribution of a random non-dominated point set. This function can be estimated from experimental data via its empirical counterpart, the empirical attainment function (EAF). However, computation of the EAF in more than two dimensions is a non-trivial task. In this article, the problem of computing the empirical attainment function is formalised, and upper and lower bounds on the corresponding number of output points are presented. In addition, efficient algorithms for the two and three-dimensional cases are proposed, and their time complexities are related to lower bounds derived for each case.

Given a finite set Y ⊂ ℝ

d

of

n

mutually non-dominated vectors in

d

 ≥ 2 dimensions, the hypervolume contribution of a point y ∈ Y is the difference between the hypervolume indicator of Y and the hypervolume indicator of Y ∖ {y}. In multi-objective metaheuristics, hypervolume contributions are computed in several selection and bounded-size archiving procedures.

This paper presents new results on the (time) complexity of computing all hypervolume contributions. It is proved that for

d

= 2,3 the problem has time complexity Θ(

n

log

n

), and, for

d

 > 3, the time complexity is bounded below by Ω(

n

log

n

). Moreover, complexity bounds are derived for computing a single hypervolume contribution.

A dimension sweep algorithm with time complexity

$\mathcal{O}$

(

n

log

n

) and space complexity

$\mathcal{O}(n)$

is proposed for computing all hypervolume contributions in three dimensions. It improves the complexity of the best known algorithm for

d

= 3 by a factor of

$\sqrt{n}$

. Theoretical results are complemented by performance tests on randomly generated test-problems.

The simultaneous optimisation of four or more conflicting objectives is now recognised as a challenge for evolutionary algorithms seeking to obtain full representations of trade-off surfaces for the purposes of a posteriori decision-making. Whilst there is evidence that some approaches can outperform both random search and standard Pareto-based methods, best-in-class algorithms have yet to be identified. We consider the concept of co-evolving a population of decision-maker preferences as a basis for determining the fitness of competing candidate solutions. The concept is realised using an existing co-evolutionary approach based on goal vectors. We compare this approach and a variant to three realistic alternatives, within a common optimiser framework. The empirical analysis follows current best practice in the field. As the number of objectives is increased, the preference-driven co-evolutionary approaches tend to outperform the alternatives, according to the hypervolume indicator, and so make a strong claim for further attention in many-objective studies.

In a previous work we proposed a scheme for partitioning the objective space using the conflict information of the current Pareto front approximation found by an underlying multi-objective evolutionary algorithm. Since that scheme introduced additional parameters that have to be set by the user, in this paper we propose important modifications in order to automatically set those parameters. Such parameters control the number of solutions devoted to explore each objective subspace, and the number of generations to create a new partition. Our experimental results show that the new adaptive scheme performs as good as the non-adaptive scheme, and in some cases it outperforms the original scheme.

Recently MOEA/D (multi-objective evolutionary algorithm based on decomposition) was proposed as a high-performance EMO (evolutionary multi-objective optimization) algorithm. MOEA/D has high search ability as well as high computational efficiency. Whereas other EMO algorithms usually do not work well on many-objective problems with four or more objectives, MOEA/D can properly handle them. This is because its scalarizing function-based fitness evaluation scheme can generate an appropriate selection pressure toward the Pareto front without severely increasing the computation load. MOEA/D can also search for well-distributed solutions along the Pareto front using a number of weight vectors with different directions in scalarizing functions. Currently MOEA/D seems to be one of the best choices for multi-objective optimization in various application fields. In this paper, we examine its performance on multi-objective problems with highly correlated objectives. Similar objectives to existing ones are added to two-objective test problems in computational experiments. Experimental results on multi-objective knapsack problems show that the inclusion of similar objectives severely degrades the performance of MOEA/D while it has almost no negative effects on NSGA-II and SPEA2. We also visually examine such an undesirable behavior of MOEA/D using many-objective test problems with two decision variables.

Multi-objective random one-bit climbers (moRBCs) are one class of stochastic local search-based algorithms that maintain a reference population of solutions to guide their search. They have been shown to perform well in solving multi-objective optimization problems. In this work, we analyze the performance of moRBCs when modified by introducing tabu moves. We also study their behavior when the selection to update the reference population and archive is replaced with a procedure that provides an alternative mechanism for preserving the diversity among the solutions. We use several MNK-landscape models as test instances and apply statistical testings to analyze the results. Our study shows that the two modifications complement each other in significantly improving moRBCs’ performance especially in many-objective problems. Moreover, they can play specific roles in enhancing the convergence and spread of moRBCs.

Test problems have played a fundamental role in understanding the strengths and weaknesses of the existing Evolutionary Multi-objective Optimization (EMO) algorithms. A range of test problems exist which have enabled the research community to understand how the performance of EMO algorithms is affected by the geometrical shape of the

Pareto front

(PF), i.e., PF being convex, concave or mixed. However, the shapes of the

Pareto Set

(PS) of most of these test problems are rather simple (linear or quadratic), even though the real-world engineering problems are expected to have complicated PS shapes. The state-of-the-art in many-objective optimization problems (those involving four or more objectives) is rather worse. There is a dearth of test problems (even those with simple PS shapes) and the algorithms that can handle such problems. This paper proposes a framework for continuous many-objective test problems with arbitrarily prescribed PS shapes. The behavior of two popular EMO algorithms namely NSGAII and MOEA/D has also been studied for a sample of the proposed test problems. It is hoped that this paper will promote an integrated investigation of EMO algorithms for their scalability with objectives and their ability to handle complicated PS shapes with varying nature of the PF.

This paper describes a new Preference-based Interactive Evolutionary (PIE) algorithm for multi-objective optimization which exploits the advantages of both evolutionary algorithms and multiple criteria decision making approaches. Our algorithm uses achievement scalarizing functions and the potential of population based evolutionary algorithms to help the decision maker to direct the search towards the desired Pareto optimal solution. Starting from an approximated nadir point, the PIE algorithm improves progressively the objective function values of a solution by finding a better solution at each iteration that improves the previous one. The decision maker decides from which solution, in which direction, and at what distance from the Pareto front to find the next solution. Thus, the PIE algorithm is guided interactively by the decision maker. A flexible approach is obtained with the use of archive sets to store all the solutions generated during an evolutionary algorithm’s run, as it allows the decision maker to freely navigate and inspect previous solutions if needed. The PIE algorithm is demonstrated using a pollution monitoring station problem and shown to be effective in helping the decision maker to find a solution that satisfies her/his preferences.

In recent years, multi-objective evolutionary algorithms have diversified their goal from finding an approximation of the complete efficient front of a multi-objective optimization problem, to integration of user preferences. These user preferences can be used to focus on a preferred region of the efficient front. Many such user preferences come from so called proper Pareto-optimality notions. Although, starting with the seminal work of Kuhn and Tucker in 1951, proper Pareto-optimal solutions have been around in the multi-criteria decision making literature, there are (surprisingly) very few studies in the evolutionary domain on this. In this paper, we introduce new ranking schemes of various state-of-the-art multi-objective evolutionary algorithms to focus on a preferred region corresponding to proper Pareto-optimal solutions. The algorithms based on these new ranking schemes are successfully tested on extensive benchmark test problems of varying complexity, with the aim to find the preferred region of the efficient front. This comprehensive study adequately demonstrates the efficiency of the developed multi-objective evolutionary algorithms in finding the complete preferred region for a large class of complex problems.

We present a new methodology for dealing with interactive multiobjective optimization in case of mixed-integer variables. The preference information elicited by the Decision Maker (DM) in course of the interaction is processed using the Dominance-based Rough Set Approach (DRSA). This permits to ask the DM simple questions and obtain in return a decision model expressed in terms of easily understandable “if..., then...” decision rules. In each iteration, the current set of decision rules is presented to the DM with the proposal of selecting one of them considered the most representative. The selected decision rule specifies some minimal requirements that the DM desires to be achieved by the objective functions. This information is translated into a set of constraints which are added to the original problem restricting the space of feasible solutions. Moreover, we introduce one simple but effective algorithm, called bound-and-cut, that efficiently reduces the set of feasible values of the integer variables. This process continues iteratively until the part of the Pareto front that is interesting for the DM can be exhaustively explored with respect to the integer variables. The bound-and-cut algorithm can be embedded in an Evolutionary Multiobjective Optimization (EMO) method, which permits to compute a reasonable approximation of the considered part of the Pareto front. A subset of representative solutions can be selected from this approximation and presented to the DM in the dialogue phase of each iteration.

Very large-scale neighborhood search (VLSNS) is a technique intensively used in single-objective optimization. However, there is almost no study of VLSNS for multiobjective optimization. We show in this paper that this technique is very efficient for the resolution of multiobjective combinatorial optimization problems. Two problems are considered: the multiobjective multidimensional knapsack problem and the multiobjective set covering problem. VLSNS are proposed for these two problems and are integrated into the two-phase Pareto local search. The results obtained on biobjective instances outperform the state-of-the-art results for various indicators.

Bilevel multi-objective optimization problems are known to be highly complex optimization tasks which require every feasible upper-level solution to satisfy optimality of a lower-level optimization problem. Multi-objective bilevel problems are commonly found in practice and high computation cost needed to solve such problems motivates to use multi-criterion decision making ideas to efficiently handle such problems. Multi-objective bilevel problems have been previously handled using an evolutionary multi-objective optimization (EMO) algorithm where the entire Pareto set is produced. In order to save the computational expense, a progressively interactive EMO for bilevel problems has been presented where preference information from the decision maker at the upper level of the bilevel problem is used to guide the algorithm towards the most preferred solution (a single solution point). The procedure has been evaluated on a set of five DS test problems suggested by Deb and Sinha. A comparison for the number of function evaluations has been done with a recently suggested Hybrid Bilevel Evolutionary Multi-objective Optimization algorithm which produces the entire upper level Pareto-front for a bilevel problem.

In general, Multi-objective Evolutionary Algorithms do not guarantee find solutions in the

Pareto-optimal set

. We propose a new approach for solving decomposable deceptive multi-objective problems that can find all solutions of the

Pareto-optimal set

. Basically, the proposed approach starts by decomposing the problem into subproblems and, then, combining the found solutions. The resultant approach is a Multi-objective Estimation of Distribution Algorithm for solving relatively complex multi-objective decomposable problems, using a probabilistic model based on a phylogenetic tree. The results show that, for the tested problem, the algorithm can efficiently find all the solutions of the

Pareto-optimal set

, with better scaling than the hierarchical Bayesian Optimization Algorithm and other algorithms of the state of art.

The objective values information can be incorporated into the evolutionary algorithms based on probabilistic modeling in order to capture the relationships between objectives and variables. This paper investigates the effects of joining the objective and variable information on the performance of an estimation of distribution algorithm for multi-objective optimization. A joint Gaussian Bayesian network of objectives and variables is learnt and then sampled using the information about currently best obtained objective values as evidence. The experimental results obtained on a set of multi-objective functions and in comparison to two other competitive algorithms are presented and discussed.

Equality constraints are difficult to handle by any optimization algorithm, including evolutionary methods. Much of the existing studies have concentrated on handling inequality constraints. Such methods may or may not work well in handling equality constraints. The presence of equality constraints in an optimization problem decreases the feasible region significantly. In this paper, we borrow our existing hybrid evolutionary-cum-classical approach developed for inequality constraints and modify it to be suitable for handling equality constraints. This modified hybrid approach uses an evolutionary multi-objective optimization (EMO) algorithm to find a trade-off frontier in terms of minimizing the objective function and the constraint violation. A suitable penalty parameter is obtained from the frontier and then used to form a penalized objective function. The procedure is repeated after a few generations for the hybrid procedure to adaptively find the constrained minimum. Unlike other equality constraint handling methods, our proposed procedure does not require the equality constraints to be transformed into an inequality constraint. We validate the efficiency of our method on six problems with only equality constraints and two problems with mixed equality and inequality constraints.

This paper presents a new memory-based variable-length encoding genetic algorithm for solving multiobjective optimization problems. The proposed method is a binary implementation of the NSGA2 and it uses a Hash Table for storing all the solutions visited during algorithm evolution. This data structure makes possible to avoid the re-visitation of solutions and it provides recovering and storage of data with low computational cost. The algorithm memory is used for building crossover, mutation and local search operators with a parameterless variable-length encoding. These operators control the neighborhood based on the density of points already visited on the region of the new solution to be evaluated. Two classical multiobjective problems are used to compare two variations of the proposed algorithm and two variations of the binary NSGA2. A statistical analysis of the results indicates that the memory-based adaptive neighborhood operators are able to provide significant improvement of the quality of the Pareto-set approximations.

Until recently, the main focus of researchers that develop algorithms for evolutionary multi-objective optimization has been the creation of mechanisms capable of obtaining sets of solutions that are as close as possible to the true Pareto front of the problem and also as diverse as possible in the objective space, to properly cover such front. However, an adequate maintenance of diversity in the decision space is also important, to efficiently solve several classes of problems and even to facilitate the post-optimization decision making process. This aspect has been widely studied in evolutionary single-objective optimization, what led to the development of several diversity maintenance techniques. Among them, the recently proposed concentration-based artificial immune network (cob-aiNet), which is capable of self-regulating the population size, presented promising results in multimodal problems. So, it is extended here to deal with multi-objective problems that require a proper maintenance of diversity in the decision space.

Bi-objective portfolio optimization for minimizing risk and maximizing expected return has received considerable attention using evolutionary algorithms. Although the problem is a quadratic programming (QP) problem, the practicalities of investment often make the decision variables discontinuous and introduce other complexities. In such circumstances, usual QP solution methodologies can not always find acceptable solutions. In this paper, we modify a bi-objective evolutionary algorithm (NSGA-II) to develop a customized hybrid NSGA-II procedure for handling situations that are non-conventional for classical QP approaches. By considering large-scale problems, we demonstrate how evolutionary algorithms enable the proposed procedure to find fronts, or portions of fronts, that can be difficult for other methods to obtain.

The use of computational methodologies for the optimization of aesthetic parameters is not frequent mainly due to the fact that these parameters are not quantifiable and are subjective. In this work an interactive methodology based on the use of multi-objective optimization algorithms is proposed. This strategy associates the results of different optimization runs considering the existent quantifiable objectives and different sets of boundary conditions concerning the decision variables, as defined by an expert decision maker. The associated results will serve as initial population of solutions for a final optimization run. The idea is that a more global picture of potential “good” solutions can be found. At the end this will facilitate the work of the expert decision maker since more solutions are available. The method was applied to a case study and the preliminary results obtained showed the potentially of the strategy adopted.

Considering uncertainties in engineering optimum design is often a requirement. Here, the use of the deterministic optimum design as the reference point in g-dominance is proposed. The multiobjective optimum robust design in a structural engineering test case where uncertainties in the external loads are taken into account is proposed as application, where the simultaneous minimization of the constrained weight average and the standard deviation of the constraints violation are the objective functions. Results include a comparison between both non-dominated sorting genetic algorithm II (NSGA-II) and strength Pareto evolutionary algorithm (SPEA2), including S-metric (hypervolume) statistical comparisons with and without the g-dominance approach. The methodology is capable to provide robust optimum structural frame designs successfully.

The planning of vaccination campaigns has the purpose of minimizing both the number of infected individuals in a time horizon and the cost to implement the control policy. This planning task is stated here as a multiobjective dynamic optimization problem of impulsive control design, in which the number of campaigns, the time interval between them and the number of vaccinated individuals in each campaign are the decision variables. The SIR (Susceptible-Infected-Recovered) differential equation model is employed for representing the epidemics. Due to the high dimension of the decision variable space, the usual evolutionary computation algorithms are not suitable for finding the efficient solutions. A hybrid optimization machinery composed by the canonical NSGA-II coupled with a local search procedure based on Convex Quadratic Approximation (CQA) models of the objective functions is used for performing the optimization task. The final results show that optimal vaccination campaigns with different trade-offs can be designed using the proposed scheme.

This paper presents an innovative method to solve the reconfiguration problem in a distribution network. The main motivation of this work is to take advantage of the power flow analysis repetition when reconfiguration leads the network to a previous configuration due to cyclical loading pattern. The developed methodology combines an optimization technique with fuzzy theory to gain efficiency without losing robustness. In this methodology, the power flow is estimated by well-trained neo-fuzzy neuron network to achieve computing time reduction in the evaluation of individuals during evolutionary algorithm runs. It is noteworthy that the proposed methodology is scalable and its benefits increase as larger feeders are dealt. The effectiveness of the proposed method is demonstrated through examples. The overall performance achieved in the experiments has proved that it is also proper to real time context.

This paper proposes an algorithm to optimize multiple indices of Quality of Service of Multi Protocol Label Switching (MPLS) IP networks. The proposed algorithm, the Variable Neighborhood Multiobjective Genetic Algorithm (VN-MGA), is a Genetic Algorithm based on the NSGA-II, with the particular feature that different parts of a solution are encoded differently, at Level 1 and Level 2. In order to improve the results, both representations are needed. At Level 1, the first part of the solution is encoded, by considering as decision variables, the arrows that form the routes to be followed by each request (whilst the second part of the solution is kept constant), whereas at Level 2, the second part of the solution is encoded, by considering as decision variables, the sequence of requests, and first part is kept constant. The preliminary results shown here indicate that the proposed approach is promising, since the Pareto-fronts obtained by VN-MGA dominate the fronts obtained by fixed-neighborhood encoding schemes. Besides the potential benefits of the application of the proposed approach to the optimization of packet routing in MPLS networks, this work raises the theoretical issue of the systematic application of variable encodings, which allow variable neighborhood searches, as generic operators inside general evolutionary computation algorithms.

Estimation of optical flow is required in many computer vision applications. These applications often have to deal with strict time constraints. Therefore, flow algorithms with both high accuracy and computational efficiency are desirable. Accordingly, designing such a flow algorithm involves multi-objective optimization. In this work, we build on a popular algorithm developed for real-time applications. It is originally based on the Census transform and benefits from this encoding for table-based matching and tracking of interest points. We propose to use the more universal Haar wavelet features instead of the Census transform within the same framework. The resulting approach is more flexible, in particular it allows for sub-pixel accuracy. For comparison with the original method and another baseline algorithm, we considered both popular benchmark datasets as well as a long synthetic video sequence. We employed evolutionary multi-objective optimization to tune the algorithms. This allows to compare the different approaches in a systematic and unbiased way. Our results show that the overall performance of our method is significantly higher compared to the reference implementation.

Feature Selection may be viewed as a search for optimal feature subsets considering one or more importance criteria. This search may be performed with Multi-objective Genetic Algorithms. In this work, we present an application of these algorithms for combining different filter approach criteria, which rely on general characteristics of the data, as feature-class correlation, to perform the search for subsets of features. We conducted experiments on public data sets and the results show the potential of this proposal when compared to mono-objective genetic algorithms and two popular filter algorithms.

Cultural Algorithms (CAs) are one of the metaheuristics which can be adapted in order to work in multi-objectives optimization environments. On the other hand, Bi-Objective Uncapacitated Facility Location Problem (BOUFLP) and particularly Uncapacitated Facility Location Problem (UFLP) are well know problems in literature. However, only few articles have applied evolutionary multi-objective (EMO) algorithms to these problems and articles presenting CAs applied to the BOUFLP have not been found. In this article we presents a Bi-Objective Cultural Algorithm (BOCA) which was applied to the Bi-Objective Uncapacitated Facility Location Problem (BOUFLP) and it obtain an important improvement in comparison with other well-know EMO algorithms such as PAES and NSGA-II. The considered criteria were cost minimization and coverage maximization. The different solutions obtained with the CA were compared using an hypervolume

S

metric.

In this paper, we examine the p-median problem from a bi-objective point of view. Since this is a NP-Hard problem, an efficient algorithm based on the Iterated Local Search heuristic (ILS) is proposed to determine non-dominated solutions (an approximation of the Pareto-optimal solutions). ILS is a simple and powerful stochastic method that has shown very good results for a variety of single-objective combinatorial problems. In each component of the ILS, we use the concept of Pareto dominance. An intensification component based on the Path-Relinking is used to improve the quality of the found non-dominated solutions. To test the performance of the proposed algorithm, we develop a Mathematical Programming Algorithm, called

ε

-Constraint, that finds a subset of Pareto-optimal solutions by solving iteratively the mathematical model of the problem with additional constraints. The results show that the proposed approach is able to generate good approximations to the non-dominated frontier of the bi-objective problem efficiently.

Locating logistic facilities, such as plants and distribution centres, in an optimal way, is a crucial decision for manufacturers, particularly those that are operating in large developing countries which are experiencing a process of fast economic change. Traditionally, such decisions have been supported by optimising network models, which search for the configuration with the minimum total cost. In practice, other intangible factors, which add or reduce value to a potential configuration, are also important in the location choice. We suggest in this paper an alternative way to analyse such problems, which combines the value from the topology of a network (such as total cost or resilience) with the value of its discrete nodes (such as specific benefits of a particular location). In this framework, the focus is on optimising the overall logistic value of the network. We conclude the paper by discussing how evolutionary multi-objective methods could be used for such analyses.

Scheduling problems have been studied from many years ago. Most of the papers which were published in this domain are different in one or many of issues as following: objective functions, machine environment, constraints and methodology for solving the problems. In this paper we address the problem of single machine scheduling in which due to some constraints like capacity, rejection of a set of jobs is accepted. The problem is considered as bi-objective one: minimization of the sum of weighted completion times for the accepted jobs and minimization of the sum of penalties for the rejected jobs. We find that in this problem, the solutions are not handled in a satisfactory way by general Pareto-dominance rule, so we suggest the application of Lorenz-dominance to an adapted bi-objective simulated annealing algorithm. Finally we justify the use of Lorenz-dominance as a useful refinement of Pareto-dominance by comparing the results.

The Multi-objective Shortest Path Problem (MSP) is a widely studied NP-Hard problem. A few exact algorithms were already proposed to solve this problem, however none is able to solve large instances with three or more objectives. Recently, some metaheuristics have been proposed for the MSP, but little can be said about their efficiency regarding each other, since no comparisons among them are presented in the literature. In this paper an Ant Colony Optimization (ACO) algorithm, called GRACE, is proposed for the MSP. The proposed approach is compared to the well-known evolutionary algorithm NSGA-II. Furthermore, GRACE is compared to another ACO algorithm proposed previously for the MSP. Results of a computational experiment with eighteen instances, with three objectives each, show that the proposed approach is able to produce high quality results for the tested instances.

In this paper, we present a method based on the multiattribute utility theory to approximate the decision-maker preference function. A feature of the proposed methodology is its ability to represent arbitrary preference functions, including functions in which there are non-linear dependencies among different decision criteria. The preference information extracted from the decision-maker involves ordinal description only, and is structured using a partial ranking procedure. An artificial neural network is constructed to approximate the decision-maker preferences, reproducing the level sets of the underlying utility function. The proposed procedure can be useful when recurrent decisions are to be performed, with the same decision-maker over different sets of alternatives. It is shown here that the inclusion/exclusion of information causes only local rank reversals instead of large scale ones that may occur in several existing methodologies. The proposed method is also robust to relatively large levels of wrong answers of the decision maker.

This paper proposes a MCDM model based on the SMARTER method for the problem of urban water conservation strategies. The main contribution of this decision model is the use of Simos procedure adapted for evaluating alternatives intra-criteria, specifically on qualitative attributes. In fact, analyses of water resources problems are normally very complex, not only because this involves multiple alternative actions and objectives, but also because many attributes are subjective or need to be evaluated qualitatively. Nevertheless, there are many approaches to dealing with a semantic scale so as to make evaluation easier. However, it is often the case that the DM does not feel comfortable with the fixed nominal scale adopted or with the number of evaluations since the alternatives often need to be compared pairwise. On the other hand, a simple conversion from a nominal to an ordinal scale normally loses information. For these reasons, this paper proposes an adaptation of Simos procedure, associating ’playing cards’ to evaluate alternatives on qualitative attributes, in order to facilitate the elicitation process. To show the applicability of the model proposed, a Brazilian case study is conducted.

This paper considers a multicriteria model for a combined burn-in and replacement process for a simple system comprising a single component from a heterogeneous population, consisting of two sub-populations that possess different failure characteristics. There are several papers that have dealt with mixed distributions. Nevertheless, suitable procedures for dealing with the distinct failure behaviours from these two sub-populations are limited. Furthermore, some combined policies of burn-in and replacement have not achieved consensus on their efficiency. Therefore, we consider a multicriteria model for supporting the decision-maker in a combined burn-in-replacement policy. This model enables the decision-maker to set up a combined burn-in-replacement policy by taking advantage of the broader view provided by a simultaneous evaluation of cost and post-burn-in reliability while also providing the possibility of inserting the decision-maker’s preferences into the model. A case study is used to illustrate some advantages in comparison with results from the classical model (minimum cost).

Competitiveness among organizations, resulting from globalization, has seen to it that the introduction of or improvement in new processes and methodologies has substantially intensified in recent years. In this context, this paper puts forward a model application that incorporates a multicriteria decision approach to RCM (Reliability-centered Maintenance) methodology. In this model, a quantitative analysis of the consequences of failures is presented, which provides the maintenance manager with important data so that management decisions can be taken based on the decision maker’s preferences. Thus, the model seeks to contribute to an approach that has become well-established within the maintenance area, since it provides more structured decision making, by using a quantitative multidimensional approach that takes into account the uncertainties associated with the problem.

Nowadays, supplier selection has become a strategic activity for many companies that wish to increase the competitiveness of their supply chain. The tendency is to maintain a long-term relationship based on trust and commitment. To achieve this aim, it is necessary to re-structure the supplier selection process, incorporate more criteria in the evaluation and deal in an appropriate way with the preferences of the decision-makers (DMs) involved. Thus, this paper presents a structure for selecting suppliers that considers the preferences of multiple DMs involved in the process. It is considered that their preferences do not present great variation, it therefore being possible to deal with them adequately and to select the supplier who presents the best compromise using the PROMETHEE VI method. A numerical application is presented.