Proper inequality constraints and maximization of index vectors

For obtaining the set of all quasi-supremal index vectors (or all maximal index vectors, or all Pareto-optimal solutions) of a multiple-objective optimization problem, we present, in this paper, the method of proper inequality constraints, which does not rely on any convexity condition at all, but by which one can obtain the entire desired set. This method is based on the observation that optimizing the index of one of the objectives, with some arbitrary bounds assigned to all other objectives, may still result in inferior solutions, unless these bounds areproper. Various necessary and/or sufficient conditions are presented for the properness test.This work was supported by the National Science Foundation under Grant No. GK-32701.     

A Hybrid Meta-Heuristic for Multi-Objective Optimization: MOSATS

Real optimization problems often involve not one, but multiple objectives, usually in conflict. 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, called the Pareto-optimal front. Thus, the goal of multi-objective strategies is to generate a set of non-dominated solutions as an approximation to this front. However, the majority of problems of this kind cannot be solved exactly because they have very large and highly complex search spaces. In recent years, meta-heuristics have become important tools for solving multi-objective problems encountered in industry as well as in the theoretical field. This paper presents a novel approach based on hybridizing Simulated Annealing and Tabu Search. Experiments on the Graph Partitioning Problem show that this new method is a better tool for approximating the efficient set than other strategies also based on these meta-heuristics.     

Improving the non-dominated sorting genetic algorithm using a gene-therapy method for multi-objective optimization

The non-dominate sorting genetic algorithmic-II (NSGA-II) is an effective algorithm for finding Pareto-optimal front for multi-objective optimization problems. To further enhance the advantage of the NSGA-II, this study proposes an evaluative-NSGA-II (E-NSGA-II) in which a novel gene-therapy method incorporates into the crossover operation to retain superior schema patterns in evolutionary population and enhance its solution capability. The merit of each select gene in a crossover chromosome is estimated by exchanging the therapeutic genes in both mating chromosomes and observing their fitness differentiation. Hence, the evaluative crossover operation can generate effective genomes based on the gene merit without explicitly analyzing the solution space. Experiments for nine unconstrained multi-objective benchmarks and four constrained problems show that E-NSGA-II can find Pareto-optimal solutions in all test cases with better convergence and diversity qualities than several existing algorithms.     

Pareto-optimal solutions for a wastewater treatment problem

In this paper we present an application of optimal control theory of partial differential equations combined with multi-objective optimization techniques to formulate and solve an economical-ecological problem related to the management of a wastewater treatment system. The problem is formulated as a parabolic multi-objective optimal control problem, and it is studied from a non-cooperative point of view (looking for a Nash equilibrium), and also from a cooperative point of view (looking for Pareto-optimal solutions “better” than the Nash equilibrium). In both cases we state the existence of solutions, give a useful characterization of them, and propose a numerical algorithm to solve the problem. Finally, a numerical experience for a real world situation in the estuary of Vigo (NW Spain) is presented.     

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.     

Approximating the Pareto optimal set using a reduced set of objective functions

Real-world applications of multi-objective optimization often involve numerous objective functions. But while such problems are in general computationally intractable, it is seldom necessary to determine the Pareto optimal set exactly. A significantly smaller computational burden thus motivates the loss of precision if the size of the loss can be estimated. We describe a method for finding an optimal reduction of the set of objectives yielding a smaller problem whose Pareto optimal set w.r.t. a discrete subset of the decision space is as close as possible to that of the original set of objectives. Utilizing a new characterization of Pareto optimality and presuming a finite decision space, we derive a program whose solution represents an optimal reduction. We also propose an approximate, computationally less demanding formulation which utilizes correlations between the objectives and separates into two parts. Numerical results from an industrial instance concerning the configuration of heavy-duty trucks are also reported, demonstrating the usefulness of the method developed. The results show that multi-objective optimization problems can be significantly simplified with an induced error which can be measured.     

A linear optimization problem to derive relative weights using an interval judgement matrix

In this paper, we propose a new Decision Making model, enabling to assess a finite number of alternatives according to a set of bounds on the preference ratios for the pairwise comparisons between alternatives, that is, an “interval judgement matrix”. In the case in which these bounds cannot be achieved by any assessment vector, we analyze the problem of determining of an efficient or Pareto-optimal solution from a multi-objective optimization problem. This multi-objective formulation seeks for assessment vectors that are near to simultaneously fulfil all the bound requirements imposed by the interval judgement matrix. Our new model introduces a linear optimization problem in order to define a consistency index for the interval matrix. By solving this optimization problem it can be associated a weakly efficient assessment vector to the consistency index in those cases in which the bound requirements are infeasible. Otherwise, this assessment vector fulfils all the bound requirements and has geometrical properties that make it appropriate as a representative assessment vector of the set of feasible weights.     

A hybrid method for solving multi-objective global optimization problems

Real optimization problems often involve not one, but multiple objectives, usually in conflict. 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 optimums, which constitute the so called Pareto-optimal front. Thus, the goal of multi-objective strategies is to generate a set of non-dominated solutions as an approximation to this front. However, most problems of this kind cannot be solved exactly because they have very large and highly complex search spaces. The objective of this work is to compare the performance of a new hybrid method here proposed, with several well-known multi-objective evolutionary algorithms (MOEA). The main attraction of these methods is the integration of selection and diversity maintenance. Since it is very difficult to describe exactly what a good approximation is in terms of a number of criteria, the performance is quantified with adequate metrics that evaluate the proximity to the global Pareto-front. In addition, this work is also one of the few empirical studies that solves three-objective optimization problems using the concept of global Pareto-optimality.     

基于种群自适应调整的多目标差分进化算法

为提高已有多目标进化算法在求解复杂多目标优化问题上的收敛性和解集分布性,提出一种基于种群自适应调整的多目标差分进化算法。该算法设计一个种群扩增策略,它在决策空间生成一些新个体帮助搜索更优的非支配解;设计了一个种群收缩策略,它依据对非支配解集的贡献程度淘汰较差的个体以减少计算负荷,并预留一些空间给新的带有种群多样性的扰动个体;引入精英学习策略,防止算法陷入局部收敛。通过典型的多目标优化函数对算法进行测试验证,结果表明所提算法相对于其他算法具有明显的优势,其性能优越,能够在保证良好收敛性的同时,使获得的Pareto最优解集具有更均匀的分布性和更广的覆盖范围,尤其适合于高维复杂多目标优化问题的求解。     

Control-space properties of cooperative games

If two or more players agree to cooperate while playing a game, they help one another to minimize their respective costs as long as it is not to their individual disadvantages. This leads at once to the concept of undominated solutions to a game. Anundominated orPareto-optimal solution has the property that, compared to any other solution, at least one playerdoes worse or alldo the same if they use a solution other than the Pareto-optimal one.Closely related to the concept of a Pareto-optimal solution is theabsolutely cooperative solution. Such a solution has the property that, compared to any other permissible solution,every playerdoes no better if a solution other than the absolutely cooperative one is employed.This paper deals with control-space properties of Pareto-optimal and absolutely cooperative solutions for both static, continuous games and differential games. Conditions are given for cases in which solutions to the Pareto-optimal and absolutely cooperative games lie in the interior or on the boundary of the control set.The solution of a Pareto-optimal or absolutely cooperative game is related to the solution of a minimization problem with avector cost criterion. The question of whether or not a problem with a vector cost criterion can be reduced to a family of minimization problems with ascalar cost criterion is also discussed.An example is given to illustrate the theory.This research was supported in part by NASA Grant No. NGR-03-002-011 and ONR Contract No. N00014-69-A-0200-1020.     

Minmax robustness for multi-objective optimization problems

In real-world applications of optimization, optimal solutions are often of limited value, because disturbances of or changes to input data may diminish the quality of an optimal solution or even render it infeasible. One way to deal with uncertain input data is robust optimization, the aim of which is to find solutions which remain feasible and of good quality for all possible scenarios, i.e., realizations of the uncertain data. For single objective optimization, several definitions of robustness have been thoroughly analyzed and robust optimization methods have been developed. In this paper, we extend the concept of minmax robustness (Ben-Tal, Ghaoui, & Nemirovski, 2009) to multi-objective optimization and call this extension robust efficiency for uncertain multi-objective optimization problems. We use ingredients from robust (single objective) and (deterministic) multi-objective optimization to gain insight into the new area of robust multi-objective optimization. We analyze the new concept and discuss how robust solutions of multi-objective optimization problems may be computed. To this end, we use techniques from both robust (single objective) and (deterministic) multi-objective optimization. The new concepts are illustrated with some linear and quadratic programming instances.     

Primal and dual algorithms for optimization over the efficient set

ABSTRACT

Optimization over the efficient set of a multi-objective optimization problem is a mathematical model for the problem of selecting a most preferred solution that arises in multiple criteria decision-making to account for trade-offs between objectives within the set of efficient solutions. In this paper, we consider a particular case of this problem, namely that of optimizing a linear function over the image of the efficient set in objective space of a convex multi-objective optimization problem. We present both primal and dual algorithms for this task. The algorithms are based on recent algorithms for solving convex multi-objective optimization problems in objective space with suitable modifications to exploit specific properties of the problem of optimization over the efficient set. We first present the algorithms for the case that the underlying problem is a multi-objective linear programme. We then extend them to be able to solve problems with an underlying convex multi-objective optimization problem. We compare the new algorithms with several state of the art algorithms from the literature on a set of randomly generated instances to demonstrate that they are considerably faster than the competitors.     

Higher and lower-level knowledge discovery from Pareto-optimal sets

Innovization (innovation through optimization) is a relatively new concept in the field of multi-objective engineering design optimization. It involves the use of Pareto-optimal solutions of a problem to unveil hidden mathematical relationships between variables, objectives and constraint functions. The obtained relationships can be thought of as essential properties that make a feasible solution Pareto-optimal. This paper proposes two major extensions to innovization, namely higher-level innovization and lower-level innovization. While the former deals with the discovery of common features among solutions from different Pareto-optimal fronts, the latter concerns features commonly occurring among solutions that belong to a specified (or preferred) part of the Pareto-optimal front. The knowledge of such lower-level information is extremely beneficial to a decision maker, since it focuses on a preferred set of designs. On the other hand, higher-level innovization reveals interesting knowledge about the general problem structure. Neither of these crucial aspects concerning multi-objective designs has been addressed before, to the authors’ knowledge. We develop methodologies for handling both levels of innovization by extending the authors’ earlier automated innovization algorithm and apply them to two well-known engineering design problems. Results demonstrate that the proposed methodologies are generic and are ready to be applied to other engineering design problems.     

Bi-objective project portfolio selection and staff assignment under uncertainty

We formulate a project portfolio selection problem under uncertainty with two optimization criteria: a weighted average of economic and strategic gains, and a risk measure expressed as the expected total overtime cost. The optimal assignment of personnel with given skills to the tasks of the selected projects is incorporated as a subproblem. Searching for Pareto-optimal portfolios satisfying the given constraints amounts to a stochastic multi-objective combinatorial optimization problem, a problem type for which only a few general solution approaches are available at present. We apply a recently developed technique called adaptive Pareto sampling, solve a linear subproblem with an LP solver and use the NSGA-II algorithm for deterministic multi-objective optimization as an auxiliary procedure. A convergence result applicable in a more general context is also shown. To obtain objective function estimates, importance sampling is applied. The technique is tested on a benchmark derived from a real-world application case provided by the E-Commerce Competence Center Austria.     

Multi-strategy ensemble evolutionary algorithm for dynamic multi-objective optimization

Dynamic optimization and multi-objective optimization have separately gained increasing attention from the research community during the last decade. However, few studies have been reported on dynamic multi-objective optimization (dMO) and scarce effective dMO methods have been proposed. In this paper, we fulfill these gabs by developing new dMO test problems and new effective dMO algorithm. In the newly designed dMO problems, Pareto-optimal decision values (i.e., Pareto-optimal solutions: POS) or both POS and Pareto-optimal objective values (i.e., Pareto-optimal front: POF) change with time. A new multi-strategy ensemble multi-objective evolutionary algorithm (MS-MOEA) is proposed to tackle the challenges of dMO. In MS-MOEA, the convergence speed is accelerated by the new offspring creating mechanism powered by adaptive genetic and differential operators (GDM); a Gaussian mutation operator is employed to cope with premature convergence; a memory like strategy is proposed to achieve better starting population when a change takes place. In order to show the advantages of the proposed algorithm, we experimentally compare MS-MOEA with several algorithms equipped with traditional restart strategy. It is suggested that such a multi-strategy ensemble approach is promising for dealing with dMO problems.     

On finding multiple Pareto-optimal solutions using classical and evolutionary generating methods

In solving multi-objective optimization problems, evolutionary algorithms have been adequately applied to demonstrate that multiple and well-spread Pareto-optimal solutions can be found in a single simulation run. In this paper, we discuss and put together various different classical generating methods which are either quite well-known or are in oblivion due to publication in less accessible journals and some of which were even suggested before the inception of evolutionary methodologies. These generating methods specialize either in finding multiple Pareto-optimal solutions in a single simulation run or specialize in maintaining a good diversity by systematically solving a number of scalarizing problems. Most classical generating methodologies are classified into four groups mainly based on their working principles and one representative method from each group is chosen in the present study for a detailed discussion and for its performance comparison with a state-of-the-art evolutionary method. On visual comparisons of the efficient frontiers obtained for a number of two and three-objective test problems, the results bring out interesting insights about the strengths and weaknesses of these approaches. The results should motivate researchers to design hybrid multi-objective optimization algorithms which may be better than each of the individual methods.     

Characterizations of set order relations and constrained set optimization problems via oriented distance function

Set-valued optimization problems are important and fascinating field of optimization theory and widely applied to image processing, viability theory, optimal control and mathematical economics. There are two types of criteria of solutions for the set-valued optimization problems: the vector criterion and the set criterion. In this paper, we adopt the set criterion to study the optimality conditions of constrained set-valued optimization problems. We first present some characterizations of various set order relations using the classical oriented distance function without involving the nonempty interior assumption on the ordered cones. Then using the characterizations of set order relations, necessary and sufficient conditions are derived for four types of optimal solutions of constrained set optimization problem with respect to the set order relations. Finally, the image space analysis is employed to study the c-optimal solution of constrained set optimization problems, and then optimality conditions and an alternative result for the constrained set optimization problem are established by the classical oriented distance function.     

An Adaptive Algorithm for Vector Partitioning

The vector partition problem concerns the partitioning of a set A of n vectors in d-space into p parts so as to maximize an objective function c which is convex on the sum of vectors in each part. Here all parameters d, p, n are considered variables. In this paper, we study the adjacency of vertices in the associated partition polytopes. Using our adjacency characterization for these polytopes, we are able to develop an adaptive algorithm for the vector partition problem that runs in time O(q(L)v) and in space O(L), where q is a polynomial function, L is the input size and v is the number of vertices of the associated partition polytope. It is based on an output-sensitive algorithm for enumerating all vertices of the partition polytope. Our adjacency characterization also implies a polynomial upper bound on the combinatorial diameter of partition polytopes. We also establish a partition polytope analogue of the lower bound theorem, indicating that the output-sensitive enumeration algorithm can be far superior to previously known algorithms that run in time polynomial in the size of the worst-case output.     

Weak Pareto-optimal necessary conditions in a nondifferentiable multiobjective program on a Banach space

The nondifferentiable optimization theory with equality and inequality constraints is extended to a multiobjective program on a Banach space. We derive generalized conditions of the Fritz-John type given by Clarke's generalized gradient formula, which are necessary for weak Pareto-optimal solutions.