Aggregate Objective Functions and Pareto Frontiers: Required Relationships and Practical Implications

This paper addresses the problem of capturing Pareto optimal points on non-convex Pareto frontiers, which are encountered in nonlinear multiobjective optimization problems in computational engineering design optimization. The emphasis is on the choice of the aggregate objective function (AOF) of the objectives that is employed to capture Pareto optimal points. A fundamental property of the aggregate objective function, the admissibility property, is developed and its equivalence to the coordinatewise increasing property is established. Necessary and sufficient conditions for such an admissible aggregate objective function to capture Pareto optimal points are derived. Numerical examples illustrate these conditions in the biobjective case. This paper demonstrates in general terms the limitation of the popular weighted-sum AOF approach, which captures only convex Pareto frontiers, and helps us understand why some commonly used AOFs cannot capture desirable Pareto optimal points, and how to avoid this situation in practice. Since nearly all applications of optimization in engineering design involve the formation of AOFs, this paper is of direct theoretical and practical usefulness.     

Generating Well-Distributed Sets of Pareto Points for Engineering Design Using Physical Programming

Engineering design generally involves two, possibly integrated, phases: (i) generating design options, and (ii) choosing the most satisfactory option on the basis of some determined criteria. The depth, or lack, of integration between these two phases defines different design approaches, and differing philosophical views from the part of researchers in the field of computational design. Optimization-Based Design (OBD) covers the spectrum of this depth of integration. While most OBD approaches strongly integrate these two phases, some employ computational optimization only in the first or second phase. Regardless of where a method or researcher lies in this philosophical spectrum, some requisite characteristics are fundamental to the effectiveness of OBD methods. In particular, (i) the Aggregate Objective Function (AOF) used in the optimization must have the ability to generate all Pareto solutions, (ii) the generation of any existing Pareto solutions must be possible with reasonable ease, and (iii) even changes in the AOF parameters should yield a well distributed set of Pareto solutions. This paper examines the effectiveness of physical programming (PP) with respect to the latter, yielding favorable conclusions. Previous papers have led to similarly positive conclusions with respect to the former two. This paper also presents a comparative study featuring PP and other popular methods, where PP is shown to perform favorably. A PP-based method for generating the Pareto frontier is presented.     

A MULTIOBJECTIVE INTERACTIVE SEQUENTIAL HYBRID OPTIMIZATION TECHNIQUE FOR DESIGN DECISION MAKING

The paper proposes an interactive method for obtaining a solution to a multiple objective design decision making problem. The focus is on generating Pareto solutions including those that are in the non-convex region, and are desirable to obtain in an engineering design context. After the generation of a small subset of the Pareto solutions, the designer's feedback is elicited in order to eliminate part of the subset. The process is repeated until il iteratively narrows down the Pareto solution set to a size small enough so that the designer is able to easily select a final solution. The advantage of this approach is that the designer can view a few sample points from the Pareto set before zooming into the region preferred and without expending computation time in generating a complete Pareto set. The process has been demonstrated with the help of an example, the design of a fleet of ships, that has mixed-discrete variables and hence a genetic algorithm is used as the optimizer.     

Compromise design of stochastic dynamical systems: A reliability-based approach

This paper presents a procedure for obtaining compromise designs of structural systems under stochastic excitation. In particular, an effective strategy for determining specific Pareto optimal solutions is implemented. The design goals are defined in terms of deterministic performance functions and/or performance functions involving reliability measures. The associated reliability problems are characterized by means of a large number of uncertain parameters (hundreds or thousands). The designs are obtained by formulating a compromise programming problem which is solved by a first-order interior point algorithm. The sensitivity information required by the proposed solution strategy is estimated by an approach that combines an advanced simulation technique with local approximations of some of the quantities associated with structural performance. An efficient Pareto sensitivity analysis with respect to the design variables becomes possible with the proposed formulation. Such information is used for decision making and tradeoff analysis. Numerical validations show that only a moderate number of stochastic analyses (reliability estimations) has to be performed in order to find compromise designs. Two example problems are presented to illustrate the effectiveness of the proposed approach.     

Multi-objective genetic algorithm for solving N-version program design problem

N-version programming (NVP) is a programming approach for constructing fault tolerant software systems. Generally, an optimization model utilized in NVP selects the optimal set of versions for each module to maximize the system reliability and to constrain the total cost to remain within a given budget. In such a model, while the number of versions included in the obtained solution is generally reduced, the budget restriction may be so rigid that it may fail to find the optimal solution. In order to ameliorate this problem, this paper proposes a novel bi-objective optimization model that maximizes the system reliability and minimizes the system total cost for designing N-version software systems. When solving multi-objective optimization problem, it is crucial to find Pareto solutions. It is, however, not easy to obtain them. In this paper, we propose a novel bi-objective optimization model that obtains many Pareto solutions efficiently.We formulate the optimal design problem of NVP as a bi-objective 0–1 nonlinear integer programming problem. In order to overcome this problem, we propose a Multi-objective genetic algorithm (MOGA), which is a powerful, though time-consuming, method to solve multi-objective optimization problems. When implementing genetic algorithm (GA), the use of an appropriate genetic representation scheme is one of the most important issues to obtain good performance. We employ random-key representation in our MOGA to find many Pareto solutions spaced as evenly as possible along the Pareto frontier. To pursue improve further performance, we introduce elitism, the Pareto-insertion and the Pareto-deletion operations based on distance between Pareto solutions in the selection process.The proposed MOGA obtains many Pareto solutions along the Pareto frontier evenly. The user of the MOGA can select the best compromise solution among the candidates by controlling the balance between the system reliability and the total cost.     

Tradeoff analysis of non-linear dynamical systems under stochastic excitation

An efficient methodology to carry out multi-objective optimization of non-linear structural systems under stochastic excitation is presented. Specifically, an efficient determination of particular Pareto or non-inferior solutions is implemented. Pareto solutions are obtained by compromise programming which is based on the minimization of the distance between the point that contains the individual optima of each of the objective functions and the Pareto set. The response of the structural system is characterized in terms of the first two statistical moments of the response process, i.e. the mean and variance. An efficient sensitivity analysis of non-inferior solutions with respect to the design variables becomes possible with the proposed formulation. Such information is used for decision making and tradeoff analysis. The compromise programming problem is solved by an efficient procedure that combines a local statistical linearization approach, modal analysis, global approximation concepts, and a sequential optimization scheme. Numerical results show that the total number of stochastic analyses required during the multi-objective optimization process is in general very small. Hence, different compromise solutions including the design that best represents the outcome that the designer considers potentially satisfactory are obtained in an efficient manner. In this way, the analyst can conduct a decision-making analysis through an efficient interactive procedure.     

A multi-objective genetic algorithm approach to the design of cellular manufacturing systems

In this paper, a multi-objective integer programming model is constructed for the design of cellular manufacturing systems with independent cells. A genetic algorithm with multiple fitness functions is proposed to solve the formulated problem. The proposed algorithm finds multiple solutions along the Pareto optimal frontier. There are some features that make the proposed algorithm different from other algorithms used in the design of cellular manufacturing systems. These include: (1) a systematic uniform design-based technique, used to determine the search directions, and (2) searching the solution space in multiple directions instead of single direction. Four problems are selected from the literature to evaluate the performance of the proposed approach. The results validate the effectiveness of the proposed method in designing the manufacturing cells.     

Evolutionary multi-objective concurrent maximisation of process tolerances

Concurrent tolerancing which simultaneously optimises process tolerance based on constraints of both dimensional and geometrical tolerances (DGTs), and process accuracy with multi-objective functions is tedious to solve by a conventional optimisation technique like a linear programming approach. Concurrent tolerancing becomes an optimisation problem to determine optimum allotment of the process tolerances under the design function constraints. Optimum solution for this advanced tolerance design problem is difficult to obtain using traditional optimisation techniques. The proposed algorithms (elitist non-dominated sorting genetic algorithm (NSGA-II) and multi-objective differential evolution (MODE)) significantly outperform the previous algorithms for obtaining the optimum solution. The average fitness factor method and the normalised weighting objective function method are used to select the best optimal solution from Pareto optimal fronts. Two multi-objective performance measures namely solution spread measure and ratio of non-dominated individuals are used to evaluate the strength of the Pareto optimal fronts. Two more multi-objective performance measures namely optimiser overhead and algorithm effort are used to find the computational effort of the NSGA-II and MODE algorithms. Comparison of the results establishes that the proposed algorithms are superior to the algorithms in the literature.     

Multi-objective balancing of assembly lines by population heuristics

This paper is concerned with the solution of the multi-objective single-model deterministic assembly line balancing problem (ALBP). Two bi-criteria objectives are considered:

1. Minimising the cycle time of the assembly line and the balance delay time of the workstations.

2. Minimising the cycle time and the smoothness index of the workload of the line.

A new population heuristic is proposed to solve the problem based on the general differential evolution (DE) method. The main characteristics of the proposed multi-objective DE (MODE) heuristic are:

1. It formulates the cost function of each individual ALB solution as a weighted-sum of multiple objectives functions with self-adapted weights.

2. It maintains a separate population with diverse Pareto-optimal solutions.

3. It injects the actual evolving population with some Pareto-optimal solutions.

4. It uses a new modified scheme for the creation of the mutant vectors.

Moreover, special representation and encoding schemes are developed and discussed which adapt MODE on ALBPs. The efficiency of MODE is measured over known ALB benchmarks taken from the open literature and compared to that of two other previously proposed population heuristics, namely, a weighted-sum Pareto genetic algorithm (GA), and a Pareto-niched GA. The experimental comparisons showed a promising high quality performance for MODE approach.     

Practical solutions for multi-objective optimization: An application to system reliability design problems

For multiple-objective optimization problems, a common solution methodology is to determine a Pareto optimal set. Unfortunately, these sets are often large and can become difficult to comprehend and consider. Two methods are presented as practical approaches to reduce the size of the Pareto optimal set for multiple-objective system reliability design problems. The first method is a pseudo-ranking scheme that helps the decision maker select solutions that reflect his/her objective function priorities. In the second approach, we used data mining clustering techniques to group the data by using the k-means algorithm to find clusters of similar solutions. This provides the decision maker with just k general solutions to choose from. With this second method, from the clustered Pareto optimal set, we attempted to find solutions which are likely to be more relevant to the decision maker. These are solutions where a small improvement in one objective would lead to a large deterioration in at least one other objective. To demonstrate how these methods work, the well-known redundancy allocation problem was solved as a multiple objective problem by using the NSGA genetic algorithm to initially find the Pareto optimal solutions, and then, the two proposed methods are applied to prune the Pareto set.     

A new algorithm for the robust optimization of rotor-bearing systems

This article presents a new algorithm for the robust optimization of rotor-bearing systems. The goal of the optimization problem is to find the values of a set of parameters for which the natural frequencies of the system are as far away as possible from the rotational speeds of the machine. To accomplish this, the penalization proposed by Ritto, Lopez, Sampaio, and Souza de Cursi in 2011 is employed. Since the rotor-bearing system is subject to uncertainties, such a penalization is modelled as a random variable. The robust optimization is performed by minimizing the expected value and variance of the penalization, resulting in a multi-objective optimization problem (MOP). The objective function of this MOP is known to be non-convex and it is shown that its resulting Pareto front (PF) is also non-convex. Thus, a new algorithm is proposed for solving the MOP: the normal boundary intersection (NBI) is employed to discretize the PF handling its non-convexity, and a global optimization algorithm based on a restart procedure and local searches are employed to minimize the NBI subproblems tackling the non-convexity of the objective function. A numerical analysis section shows the advantage of using the proposed algorithm over the weighted-sum (WS) and NSGA-II approaches. In comparison with the WS, the proposed approach obtains a much more even and useful set of Pareto points. Compared with the NSGA-II approach, the proposed algorithm provides a better approximation of the PF requiring much lower computational cost.     

PARETO OPTIMAL SERIAL DYNAMIC PROGRAMMING

A method for generating the Pareto optimal set, or an approximation to it for multi-criteria (multi-objective) problems capable of being formulated as serial stage-state discrete dynamic programs, is presented. It is shown that this set may be produced by using Pareto optimality as the optimization selection mechanism in dynamic programming, Worked examples are presented.     

Norm methods and partial weighting in multicriterion optimization of structures

Methods for generating Pareto optimal solutions to a multicriterion optimization problem are considered. The norm methods based on the scalarization of the original multicriterion problem by using the l-norm are discussed in a unified form and a parametrization suitable for different interactive design systems is suggested. In addition, an alternative approach which, instead of scalarization, reduces the dimension of the multicriterion problem is proposed. This is called the partial weighting method and it can beinterpreted as a generalization of the traditional scalarization technique where the weighted sum of the criteria is used as the objective function. The first of these two approaches (norm method) is very flexible from a designer's point of view and it can be applied also in non-convex cases to the determination of the Pareto optimal set whereas the latter (partial weighting method) is especially suitable for problems where the number of criteria is large. Throughout the article several illustrative truss examples are presented to augment the scanty collection of multicriterion problems treated in the literature of optimum structural design.     

Multi-objective due-date setting in a make-to-order environment

This paper presents a new dual-objective problem of due-date setting over a rolling planning horizon in make-to-order manufacturing and proposes a bi-criterion integer programming formulation for its solution. In the proposed model the due-date setting decisions are directly linked with available capacity. A simple critical load index is introduced to quickly identify the system bottleneck and the overloaded periods. The problem objective is to select a maximal subset of orders that can be completed by the customer requested dates and to quote delayed due dates for the remaining acceptable orders to minimise the number of delayed orders or the total number of delayed products as a primary optimality criterion and to minimise total or maximum delay of orders as a secondary criterion. A weighted-sum program based on a scalarisation approach is compared with a two-level due-date setting formulation based on the lexicographic approach. In addition, a mixed-integer programming model is provided for scheduling customer orders over a rolling planning horizon to minimise the maximum inventory level. Numerical examples modeled after a real-world make-to-order flexible flowshop environment in the electronics industry are provided and, for comparison, the single-objective solutions that maximise total revenue subject to service level constraints are reported.     

Computation of pareto optima in structural design

The structural design problem is acknowledge to be commonly multi-criteria in nature. The various bases for multi-criteria optimization methodologies are outlined and a computationally viable method for generating Pareto optimal solutions is adopted for the structural design problem where the criteria may be non-commensurable. A numerical example on optimal truss design illustrating non-commensurable criteria is given.     

Redundancy allocation for multi-state systems using physical programming and genetic algorithms

This paper proposes a multi-objective optimization model for redundancy allocation for multi-state series–parallel systems. This model seeks to maximize system performance utility while minimizing system cost and system weight simultaneously. We use physical programming as an effective approach to optimize the system structure within this multi-objective optimization framework. The physical programming approach offers a flexible and effective way to address the conflicting nature of these different objectives. Genetic algorithm (GA) is used to solve the proposed physical programming-based optimization model due to the following three reasons: (1) the design variables, the number of components of each subsystems, are integer variables; (2) the objective functions in the physical programming-based optimization model do not have nice mathematical properties, and thus traditional optimization approaches are not suitable in this case; (3) GA has good global optimization performance. An example is used to illustrate the flexibility and effectiveness of the proposed physical programming approach over the single-objective method and the fuzzy optimization method.     

Function-transformation methods for multi-objective optimization

It is useful with multi-objective optimization (MOO) to transform the objective functions such that they all have similar units and orders of magnitude. This article evaluates various transformation methods using simple example problems. Viewing these methods as different means to restrict function values sheds light on how the methods perform. The weighted sum approach for MOO is used to study how well different methods aid in depicting the Pareto optimal set. Whereas using unrestricted weights is well suited for providing a single solution that reflects preferences, it is found that using a convex combination of functions is desirable when generating the Pareto set. In addition, it is shown that some transformation methods are detrimental to the process of generating a diverse spread of points, and criteria are proposed for determining when the methods fail to generate an accurate representation of the Pareto set. Advantages of using a simple normalization–modification are demonstrated.     

A simulation-based multi-objective genetic algorithm (SMOGA) procedure for BOT network design problem

Solving optimization problems with multiple objectives under uncertainty is generally a very difficult task. Evolutionary algorithms, particularly genetic algorithms, have shown to be effective in solving this type of complex problems. In this paper, we develop a simulation-based multi-objective genetic algorithm (SMOGA) procedure to solve the build-operate-transfer (BOT) network design problem with multiple objectives under demand uncertainty. The SMOGA procedure integrates stochastic simulation, a traffic assignment algorithm, a distance-based method, and a genetic algorithm (GA) to solve a multi-objective BOT network design problem formulated as a stochastic bi-level mathematical program. To demonstrate the feasibility of SMOGA procedure, we solve two mean-variance models for determining the optimal toll and capacity in a BOT roadway project subject to demand uncertainty. Using the inter-city expressway in the Pearl River Delta Region of South China as a case study, numerical results show that the SMOGA procedure is robust in generating ‘good’ non-dominated solutions with respect to a number of parameters used in the GA, and performs better than the weighted-sum method in terms of the quality of non-dominated solutions.     

Adapting the Hypervolume Quality Indicator to Quantify Trade‐offs and Search Efficiency for Multiple Criteria Decision Making Using Pareto Fronts

When choosing a best solution based on simultaneously balancing multiple objectives, the Pareto front approach allows promising solutions across the spectrum of user preferences for the weightings of the objectives to be identified and compared quantitatively. The shape of the complete Pareto front provides useful information about the amount of trade‐off between the different criteria and how much compromise is needed from some criterion to improve the others. Visualizing the Pareto front in higher (3 or more) dimensions becomes difficult, so a numerical measure of this relationship helps capture the degree of trade‐off. The traditional hypervolume quality indicator based on subjective scaling for multiple criteria optimization method comparison provides an arbitrary value that lacks direct interpretability. This paper proposes an interpretable summary for quantifying the nature of the relationship between criteria with a standardized hypervolume under the Pareto front (HVUPF) for a flexible number of optimization criteria, and demonstrates how this single number summary can be used to evaluate and compare the efficiency of different search methods as well as tracking the search progress in populating the complete Pareto front. A new HVUPF growth plot is developed for quantifying the performance of a search method on completeness, efficiency, as well as variability associated with the use of random starts, and offers an effective approach for method assessment and comparison. Two new enhancements for the algorithm to populate the Pareto front are described and compared with the HVUPF growth plot. The methodology is illustrated with an optimal screening design example, where new Pareto search methods are proposed to improve computational efficiency, but is broadly applicable to other multiple criteria optimization problems. Copyright © 2012 John Wiley & Sons, Ltd.