Two-Sided Pareto Front Approximations

A new approach to derive Pareto front approximations with evolutionary computations is proposed here. At present, evolutionary multiobjective optimization algorithms derive a discrete approximation of the Pareto front (the set of objective maps of efficient solutions) by selecting feasible solutions such that their objective maps are close to the Pareto front. However, accuracy of such approximations is known only if the Pareto front is known, which makes their usefulness questionable. Here we propose to exploit also elements outside feasible sets to derive pairs of such Pareto front approximations that for each approximation pair the corresponding Pareto front lies, in a certain sense, in-between. Accuracies of Pareto front approximations by such pairs can be measured and controlled with respect to distance between elements of a pair. A rudimentary algorithm to derive pairs of Pareto front approximations is presented and the viability of the idea is verified on a limited number of test problems.     

A novel evolution strategy for multiobjective optimization problem

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

Computing multiobjective Markov chains handled by the extraproximal method

This paper suggests a new method for generating the Pareto front in multi-objective Markov chains, which overcomes some existing drawbacks in multi-objective methods: a fundamental issue is to find strong Pareto policies which are policies whose cost-function value is the closest in Euclidean norm to the utopian point. Each strong Pareto policy is reached when each cost-function, constrained by the strategy of others, cannot improve further its own criterion. Constraints associated to the objective function are implemented formulating the problem as a bi-level optimization approach. We convert the problem into a single level optimization approach by introducing a generalized Lagrangian function to represent the original multi-objective problem in terms of a related nonlinear programming problem. Then, we apply the Tikhonov regularization method to the objective function. The regularization method ensures that all the possible Pareto policies to be generated along the Pareto front are strong Pareto policies. For solving the problem we employ the extra-proximal method. The method effectively approximates to every optimal Pareto point, which in this case is a strong Pareto point, in the Pareto front. The experimental result, applied to the route selection for counter-kidnapping problem, validates the effectiveness and usefulness of the method.     

A New Scalarization Technique to Approximate Pareto Fronts of Problems with Disconnected Feasible Sets

We introduce and analyze a novel scalarization technique and an associated algorithm for generating an approximation of the Pareto front (i.e., the efficient set) of nonlinear multiobjective optimization problems. Our approach is applicable to nonconvex problems, in particular to those with disconnected Pareto fronts and disconnected domains (i.e., disconnected feasible sets). We establish the theoretical properties of our new scalarization technique and present an algorithm for its implementation. By means of test problems, we illustrate the strengths and advantages of our approach over existing scalarization techniques such as those derived from the Pascoletti–Serafini method, as well as the popular weighted-sum method.     

A numerical method for nonconvex multi-objective optimal control problems

A numerical method is proposed for constructing an approximation of the Pareto front of nonconvex multi-objective optimal control problems. First, a suitable scalarization technique is employed for the multi-objective optimal control problem. Then by using a grid of scalarization parameter values, i.e., a grid of weights, a sequence of single-objective optimal control problems are solved to obtain points which are spread over the Pareto front. The technique is illustrated on problems involving tumor anti-angiogenesis and a fed-batch bioreactor, which exhibit bang–bang, singular and boundary types of optimal control. We illustrate that the Bolza form, the traditional scalarization in optimal control, fails to represent all the compromise, i.e., Pareto optimal, solutions.     

考虑加工效率变化的变速机干扰管理研究

在变速机生产排序中, 受来自企业外部可改变机器加工效率的突发性干扰事件影响, 初始最小化企业生产成本的加工时间表不再最优,需要对其调整并在生产成本和干扰事件扰动之间进行权衡。建立了同时考虑生产成本和干扰事件扰动的重排序模型, 生产成本为所有机器的负载之和, 干扰事件的扰动为工件在不同机器之间重新安排所产生的运输费用和。设计了求解该重排序问题有效前沿的算法, 以及利用决策者对两个目标的偏好将双目标转化成一个二元非线性函数后, 求解优化该函数的有效解的算法。通过数值算例验证与整个有效前沿相比,优化二元函数的算法只需搜索部分有效前沿即可求出最优解,降低了有效解的搜索比例和运行时间,提高了干扰管理问题的处理效率。     

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

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

Tracing the Pareto frontier in bi-objective optimization problems by ODE techniques

In this paper we present a deterministic method for tracing the Pareto frontier in non-linear bi-objective optimization problems with equality and inequality constraints. We reformulate the bi-objective optimization problem as a parametric single-objective optimization problem with an additional Normalized Normal Equality Constraint (NNEC) similar to the existing Normal Boundary Intersection (NBI) and the Normalized Normal Constraint method (NNC). By computing the so called Defining Initial Value Problem (DIVP) for segments of the Pareto front and solving a continuation problem with a standard integrator for ordinary differential equations (ODE) we can trace the Pareto front. We call the resulting approach ODE NNEC method and demonstrate numerically that it can yield the entire Pareto frontier to high accuracy. Moreover, due to event detection capabilities available for common ODE integrators, changes in the active constraints can be automatically detected. The features of the current algorithm are illustrated for two case studies whose Matlab® code is available as Electronic Supplementary Material to this article.     

Approximating Pareto curves using semidefinite relaxations

We approximate as closely as desired the Pareto curve associated with bicriteria polynomial optimization problems. We use three formulations (including the weighted sum approach and the Chebyshev approximation) and each of them is viewed as a parametric polynomial optimization problem. For each case is associated a hierarchy of semidefinite relaxations and from an optimal solution of each relaxation one approximates the Pareto curve by solving an inverse problem (first two cases) or by building a polynomial underestimator (third case).     

Hybrid adaptive methods for approximating a nonconvex multidimensional Pareto frontier

New hybrid methods for approximating the Pareto frontier of the feasible set of criteria vectors in nonlinear multicriteria optimization problems with nonconvex Pareto frontiers are considered. Since the approximation of the Pareto frontier is an ill-posed problem, the methods are based on approximating the Edgeworth-Pareto hull (EPH), i.e., the maximum set having the same Pareto frontier as the original feasible set of criteria vectors. The EPH approximation also makes it possible to visualize the Pareto frontier and to estimate the quality of the approximation. In the methods proposed, the statistical estimation of the quality of the current EPH approximation is combined with its improvement based on a combination of random search, local optimization, adaptive compression of the search region, and genetic algorithms.     

The influence of the fitness evaluation method on the performance of multiobjective search algorithms

In this paper we are concerned with finding the Pareto optimal front or a good approximation to it. Since non-dominated solutions represent the goal in multiobjective optimisation, the dominance relation is frequently used to establish preference between solutions during the search. Recently, relaxed forms of the dominance relation have been proposed in the literature for improving the performance of multiobjective search methods. This paper investigates the influence of different fitness evaluation methods on the performance of two multiobjective methodologies when applied to a highly constrained two-objective optimisation problem. The two algorithms are: the Pareto archive evolutionary strategy and a population-based annealing algorithm. We demonstrate here, on a highly constrained problem, that the method used to evaluate the fitness of candidate solutions during the search affects the performance of both algorithms and it appears that the dominance relation is not always the best method to use.     

Solution methods for the bi-objective (cost-coverage) unconstrained facility location problem with an illustrative example

The Colombian coffee supply network, managed by the Federación Nacional de Cafeteros de Colombia (Colombian National Coffee-Growers Federation), requires slimming down operational costs while continuing to provide a high level of service in terms of coverage to its affiliated coffee growers. We model this problem as a biobjective (cost-coverage) uncapacitated facility location problem (BOUFLP). We designed and implemented three different algorithms for the BOUFLP that are able to obtain a good approximation of the Pareto frontier. We designed an algorithm based on the Nondominated Sorting Genetic Algorithm; an algorithm based on the Pareto Archive Evolution Strategy; and an algorithm based on mathematical programming. We developed a random problem generator for testing and comparison using as reference the Colombian coffee supply network with 29 depots and 47 purchasing centers. We compared the algorithms based on the quality of the approximation to the Pareto frontier using a nondominated space metric inspired on Zitzler and Thiele's. We used the mathematical programming-based algorithm to identify unique tradeoff opportunities for the reconfiguration of the Colombian coffee supply network. Finally, we illustrate an extension of the mathematical programming-based algorithm to perform scenario analysis for a set of uncapacitated location problems found in the literature.     

Genetic algorithm approach on multi-criteria minimum spanning tree problem

Minimum Spanning Tree (MST) problem is of high importance in network optimization. The multi-criteria MST (mc-MST) is a more realistic representation of the practical problem in the real world, but it is difficult for the traditional network optimization technique to deal with. In this paper, a genetic algorithm (GA) approach is developed to deal with this problem. Without neglecting its network topology, the proposed method adopts the Prüfer number as the tree encoding and applies the Multiple Criteria Decision Making (MCDM) technique and nondominated sorting technique to make the GA search give out all Pareto optimal solutions either focused on the region near the ideal point or distributed all along the Pareto frontier. Compared with the enumeration method of Pareto optimal solution, the numerical analysis shows the efficiency and effectiveness of the GA approach on the mc-MST problem.     

An approach to generate comprehensive piecewise linear interpolation of pareto outcomes to aid decision making

Multiple criteria decision making is a well established field encompassing aspects of search for solutions and selection of solutions in presence of more than one conflicting objectives. In this paper, we discuss an approach aimed towards the latter. The decision maker is presented with a limited number of Pareto optimal outcomes and is required to identify regions of interest for further investigation. The inherent sparsity of the given Pareto optimal outcomes in high dimensional space makes it an arduous task for the decision maker. To address this problem, an existing line of thought in literature is to generate a set of approximated Pareto optimal outcomes using piecewise linear interpolation. We present an approach within this paradigm, but one that delivers a comprehensive linearly interpolated set as opposed to its subset delivered by existing methods. We illustrate the advantage in doing so in comparison to stricter non-dominance conditions imposed in existing PAreto INTerpolation method. The interpolated set of outcomes delivered by the proposed approach are non-dominated with respect to the given Pareto optimal outcomes, and additionally the interpolated outcomes along uniformly distributed reference directions are presented to the decision maker. The errors in the given interpolations are also estimated in order to further aid decision making by establishing confidence in achieving true Pareto outcomes in their vicinity. The proposed approach for interpolation is computationally less demanding (for higher number of objectives) and also further amenable to parallelization. We illustrate the performance of the approach using six well established tri-objective test problems and two real-life examples. The problems span different types of fronts, such as convex, concave, mixed, degenerate, highlighting the wide applicability of the approach.     

The Pareto fitness genetic algorithm: Test function study

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

Non-dominated sorting procedure for Pareto dominance ranking on multicore CPU and/or GPU

Evolutionary multi-objective optimization algorithms aim at finding an approximation of the Pareto set. For hard to solve problems with many conflicting objectives, the number of functions evaluations to represent the Pareto front can be large and time consuming. Parallel computing can reduce the wall-clock time of such algorithms. Previous studies tackled the parallelization of a particular evolutionary algorithm. In this research, we focus on improving one of the most time consuming procedures—the non-dominated sorting—, which is used in the state-of-the-art multi-objective genetic algorithms. Here, three parallel versions of the non-dominated sorting procedure are developed: (1) a multicore (based on Pthreads); (2) a Graphic Processing Unit (GPU) (based on CUDA interface); and (3) a hybrid (based on Pthreads and CUDA). The user can select the most suitable option to efficiently compute the non-dominated sorting procedure depending on the available hardware. Results show that the use of GPU computing provides a substantial improvement in terms of performance. The hybrid approach has the best performance when a good load balance is established among cores and GPU.     

The hypervolume based directed search method for multi-objective optimization problems

We present a new hybrid evolutionary algorithm for the effective hypervolume approximation of the Pareto front of a given differentiable multi-objective optimization problem. Starting point for the local search (LS) mechanism is a new division of the decision space as we will argue that in each of these regions a different LS strategy seems to be most promising. For the LS in two out of the three regions we will utilize and adapt the Directed Search method which is capable of steering the search into any direction given in objective space and which is thus well suited for the problem at hand. We further on integrate the resulting LS mechanism into SMS-EMOA, a state-of-the-art evolutionary algorithm for hypervolume approximations. Finally, we will present some numerical results on several benchmark problems with two and three objectives indicating the strength and competitiveness of the novel hybrid.     

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

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

Annealing-tabu PAES: a multi-objective hybrid meta-heuristic

Most real-life optimization problems require taking into account not one, but multiple objectives simultaneously. In most cases these objectives are in conflict, i.e. the improvement of some objectives implies the deterioration of others. In single-objective optimization there exists a global optimum, while in the multi-objective case no optimal solution is clearly defined, but rather a set of solutions. In the last decade most papers dealing with multi-objective optimization use the concept of Pareto-optimality. The goal of Pareto-based multi-objective strategies is to generate a front (set) of non-dominated solutions as an approximation to the true Pareto-optimal front. However, this front is unknown for problems with large and highly complex search spaces, which is why meta-heuristic methods have become important tools for solving this kind of problem. Hybridization in the multi-objective context is nowadays an open research area. This article presents a novel extension of the well-known Pareto archived evolution strategy (PAES) which combines simulated annealing and tabu search. Experiments on several mathematical problems show that this hybridization allows an improvement in the quality of the non-dominated solutions in comparison with PAES, and also with its extension M-PAES.     

Variable preference modeling with ideal-symmetric convex cones

Based on the concept of general domination structures, this paper presents an approach to model variable preferences for multicriteria optimization and decision making problems. The preference assumptions for using a constant convex cone are given, and, in remedy of some immanent model limitations, a new set of assumptions is presented. The underlying preference model is derived as a variable domination structure that is defined by a collection of ideal-symmetric convex cones. Necessary and sufficient conditions for nondominance are established, and the problem of finding corresponding nondominated solutions is addressed and solved on examples.