Review article Struct Multidisc Optim 26, 369–395 (2004)
DOI 10.1007/s00158-003-0368-6 Survey of multi-objective optimization methods for engineering
R.T. Marler and J.S. Arora Abstract A survey of current continuous nonlinear multiobjective optimization (MOO) concepts and methods is
presented. It consolidates and relates seemingly different terminology and methods. The methods are divided
into three major categories: methods with a priori articulation of preferences, methods with a posteriori articulation of preferences, and methods with no articulation of preferences. Genetic algorithms are surveyed as
well. Commentary is provided on three fronts, concerning the advantages and pitfalls of individual methods,
the different classes of methods, and the field of MOO
as a whole. The Characteristics of the most significant
methods are summarized. Conclusions are drawn that reflect often-neglected ideas and applicability to engineering problems. It is found that no single approach is superior. Rather, the selection of a specific method depends on
the type of information that is provided in the problem,
the user’s preferences, the solution requirements, and the
availability of software.
Key words optimization, multi-objective, multi-criteria,
engineering Finorm Normalized objective functions
Fs Primary objective function
Fitrans Transformed objective functions
F◦ Utopia point
F Vector of objective functions (point in the criterion
space)
gj Inequality constraints
hl Equality constraints
k Number of objective functions
λ Min-max parameter
m Number of inequality constraints
n Number of design variables
p Exponent for a global criterion
U Utility function
w Vector of weighting coefficients/exponents
x Vector of design variables (point in the design space)
X Feasible design space
z Aspiration point
Z Feasible criterion space 1
Introduction
1.1
Background and objectives List of key symbols
e Number of equality constraints
Fg Global criterion function
Fimax Maximum objective function values
Received: 25 September 2002
Revised manuscript received: 7 April 2003
Published online: 23 March 2004 Springer-Verlag 2004
R.T. Marler and J.S. Arorau
Optimal Design Laboratory, College of Engineering, The University of Iowa, Iowa City, Iowa 52242, USA
e-mail: tmarler@engineering.uiowa.edu,
jsarora@engineering.uiowa.edu The process of optimizing systematically and simultaneously a collection of objective functions is called multiobjective optimization (MOO) or vector optimization.
This paper is a survey of methods for MOO and is a condensation of the work by Marler and Arora (2003), which
provided a comprehensive review of methods (and their
variants) with an eye towards engineering applications.
In contrast, this survey excludes many of the technical
details and, instead, provides a road map of currently
available continuous nonlinear methods and literature.
General concepts are briefly described, and references are
included for further investigation. In addition, this paper
consolidates seemingly different concepts, methods, and
terminology stemming from diverse applications. 370
1.2
Definition of a multi-objective optimization problem
The general multi-objective optimization problem is
posed as follows:
T Minimize F (x) = [F1 (x) , F2 (x) , . . . , Fk (x)]
x (1) subject to gj (x) ≤ 0 ,
hl (x) = 0 , j = 1, 2, . . . , m , l = 1, 2, . . . , e , where k is the number of objective functions, m is the
number of inequality constraints, and e is the number of
equality constraints. x ∈ E n is a vector of design variables
(also called decision variables), where n is the number
of independent variables xi . F (x) ∈ E k is a vector of objective functions Fi (x) : E n → E 1 . Fi (x) are also called
objectives, criteria, payoff functions, cost functions, or
value functions. The gradient of Fi (x) with respect to
x is written as ∇x Fi (x) ∈ E n . xi ∗ is the point that
minimizes the objective function Fi (x). Any comparison
(≤, ≥, etc.) between vectors applies to corresponding vector components.
The feasible design space X (often called the feasible decision space or constraint set) is defined as the
set {x|gj (x) ≤ 0, j = 1, 2, ..., m; and hi (x) = 0, i = 1, 2,
..., e}. The feasible criterion space Z (also called the feasible cost space or the attainable set ) is defined as the
set {F(x)|x ∈ X}. Although the terms feasible criterion
space and attainable set are both used in the literature
to describe Z, there is a subtle distinction between the
ideas of feasibility and attainability. Feasibility implies
that no constraint is violated. Attainability implies that
a point in the criterion space maps to a point in the design space. Each point in the design space maps to a point
in the criterion space, but the reverse may not be true;
every point in the criterion space does not necessarily correspond to a single point x ∈ X. Consequently, even with
an unconstrained problem, only certain points in the criterion space are attainable. In this study, Z is used to
indicate points in the criterion space that are feasible and
attainable.
1.3
Motivation and overview of the literature
Although surveys of multi-objective optimization methods
are common, they are often incomplete in terms of comprehensive coverage, algorithm presentation, and general applicability to engineering design. For example,
many surveys only target specific applications (Jendo
et al. 1985; Psarras et al. 1990; Tseng and Lu 1990), while
others only address the critical literature in the field. As
opposed to presenting computational methods, some surveys focus on historical aspects (Stadler 1987). At the
opposite end of the spectrum are discussions that focus on mathematics (Yu 1985; Dauer and Stadler 1986). Surveys that do explicitly present a variety of algorithms
tend to incorporate minimal discussion of their advantages and disadvantages, and most surveys only target
a limited number of approaches (Boychuk and Ovchinnikov 1973; Gerasimov and Repko 1978; Roy and Vincke
1981; Koski 1984; Osyczka 1985; Stadler 1988; Stadler
and Dauer 1992). Much of the early pioneering work with
multi-objective optimization focuses specifically on structural design (Baier 1977; Leitmann 1977; Stadler 1977,
1978; Koski 1979, 1980; Carmichael 1980). There is a need
for a survey that is comprehensive in its consideration
of currently available methods, consolidating conceptual
and practical developments. Textbooks can be complete
in the treatment of a specific topic (Hwang and Md. Masud 1979; Salukvadze 1979; Goicoechea et al. 1982; Zeleny 1982; Chankong and Haimes 1983; Osyczka 1984;
Steuer 1989; Eschenauer et al. 1990; Miettinen 1999). Alternatively, a survey paper can provide a relatively quick
overview of the literature.
1.4
Scope of the survey
This survey addresses continuous nonlinear multi-objective optimization methods. Section 2 lays the foundation
of fundamental concepts. Then, because a primary goal
of multi-objective optimization is to model a decisionmaker’s preferences (ordering or relative importance of
objectives and goals), methods are categorized depending
on how the decision-maker articulates these preferences.
Section 3 contains methods that involve a priori articulation of preferences, which implies that the user indicates
the relative importance of the objective functions or desired goals before running the optimization algorithm.
Section 4 describes methods with a posteriori articulation
of preferences, which entail selecting a single solution from
a set of mathematically equivalent solutions. In Sect. 5,
methods that require no articulation of preferences are addressed. Algorithms that involve a progressive articulation
of preferences, in which the decision-maker is continually providing input during the running of the algorithm,
are not discussed. Section 6 addresses genetic global algorithms. Advantages and disadvantages of the different
methods are discussed throughout the paper. In addition,
each section is followed by a broader discussion of the
methods. Section 7 provides a summary and conclusions
relevant to multi-objective optimization as a whole.
2
Basic concepts and definitions
2.1
Definition of terms
Multi-objective optimization originally grew out of three
areas: economic equilibrium and welfare theories, game 371
theory, and pure mathematics. Consequently, many
terms and fundamental ideas stem from these fields.
The reader is referred to Stadler and Dauer (1992), and
Stadler (1987, 1988) for extensive discussions of these
topics and for the history of multi-objective optimization.
For the sake of brevity, only critical terms are defined below. Many of these terms have multiple definitions in the
literature stemming from the differences between engineering and economic jargon, and in such cases, the most
common and most appropriate definitions are used.
Preferences. Preferences refer to a decision-maker’s
opinions concerning points in the criterion space. With
methods that involve a posteriori articulation of preferences, the decision-maker imposes preferences directly on
a set of potential solution points. Then, theoretically the
final solution reflects the decision-maker’s preferences accurately. With a priori articulation of preferences, one
must quantify opinions before actually viewing points in
the criterion space. In this sense, the term preference often is used in relation to the relative importance of different objective functions. Nonetheless, this articulation of
preferences is fundamentally based on opinions concerning anticipated points in the criterion space.
Preference Function. A preference function is an abstract function (of points in the criterion space) in the
mind of the decision-maker, which perfectly incorporates
his/her preferences.
Utility Function. In the context of economics, utility,
which is modeled with a utility function, represents an
individual’s or group’s degree of contentment (Mansfield
1985). This is slightly different from the usual meaning of
usefulness or worth. Instead, in this case, utility emphasizes a decision-maker’s satisfaction. In terms of multiobjective optimization, an individual utility function is
defined for each objective and represents the relative importance of the objective. The utility function U is an
amalgamation of the individual utility functions and is
a mathematical expression that attempts to model the
decision-maker’s preferences. It is used to approximate
the preference function, which typically cannot be expressed in mathematical form.
Global Criterion. A global criterion is a scalar function
that mathematically combines multiple objective functions; it does not necessarily involve utility or preference.
Game theory. Stadler (1988) writes that “the mathematical and economic approaches [to multi-objective
problems] were eventually united with the inception of
game theory by Borel in 1921.” According to the traditional game theory interpretation, a game is any situation
of conflict or cooperation between at least two players
with multiple possible strategies or moves. Game theory represents multi-objective optimization with multiple
decision-makers, each controlling certain design variables
(Vincent 1983). If all players cooperate, the result is the
same as a single player acting as a decision-maker for
a multi-objective optimization problem.
One of the predominant classifications of multiobjective approaches is that of scalarization methods and vector optimization methods. Given a vector of objective functions, it is possible simply to combine the
components of this vector to form a single scalar objective function, hence the term scalarization. Although
few authors make the distinction, the term vector optimization loosely implies independent treatment of each
objective function. Both approaches are discussed in this
study. 2.2
Pareto optimality
In contrast to single-objective optimization, a solution
to a multi-objective problem is more of a concept than
a definition. Typically, there is no single global solution,
and it is often necessary to determine a set of points that
all fit a predetermined definition for an optimum. The
predominant concept in defining an optimal point is that
of Pareto optimality (Pareto 1906), which is defined as
follows:
Definition 1. Pareto Optimal: A point, x∗ ∈ X, is
Pareto optimal iff there does not exist another point,
x ∈ X, such that F (x) ≤ F (x∗ ), and Fi (x) < Fi (x∗ ) for
at least one function.
All Pareto optimal points lie on the boundary of the
feasible criterion space Z (Athan and Papalambros 1996;
Chen et al. 2000). Often, algorithms provide solutions
that may not be Pareto optimal but may satisfy other
criteria, making them significant for practical applications. For instance, weakly Pareto optimal is defined as
follows:
Definition 2. Weakly Pareto Optimal: A point, x∗ ∈ X,
is weakly Pareto optimal iff there does not exist another
point, x ∈ X, such that F (x) < F (x∗ ).
A point is weakly Pareto optimal if there is no other point
that improves all of the objective functions simultaneously. In contrast, a point is Pareto optimal if there is no
other point that improves at least one objective function
without detriment to another function. Pareto optimal
points are weakly Pareto optimal, but weakly Pareto optimal points are not Pareto optimal.
All Pareto optimal points may be categorized as being
either proper or improper . The idea of proper Pareto optimality and its relevance to certain algorithms is discussed
by Geoffrion (1968), Yu (1985), and Miettinen (1999). It
is defined as follows:
Definition 3. Properly Pareto Optimal: A point, x∗ ∈
X, is properly Pareto optimal (in the sense of Geoffrion)
if it is Pareto optimal and there is some real number
M > 0 such that for each Fi (x) and each x ∈ X satisfying Fi (x) < Fi (x∗ ), there exists at least one Fj (x) such
F (x∗ )−Fi (x)
that Fj (x∗ ) < Fj (x) and Fij (x)−Fj (x
∗ ) ≤ M . If a Pareto
optimal point is not proper, it is improper. 372
The quotient is referred to as a trade-off , and it represents the increment in objective function j resulting from
a decrement in objective function i. Definition 2.3 requires that the trade-off between each function and at
least one other function be bounded in order for a point to
be properly Pareto optimal.
Methods for determining whether a point is Pareto optimal or not are given in Benson (1978), and Brosowski
and da Silva (1994). Miettinen (1999) summarizes the
work of Benson (1978) with the following common simple
test for the point x∗ :
Minimize
δ ≥0
x∈X,δ k

δi (2) i=1 subject to Fi (x) + δi = Fi (x∗ ) , i = 1, 2, . . . , k. If all δi are zero, then x∗ is a Pareto optimal point.
For any given problem, there may be an infinite number of Pareto optimal points constituting the Pareto
optimal set. Therefore, one must distinguish between
methods that provide the Pareto optimal set or some portion of that set, and methods that actually seek a single
final point. Both approaches are considered in this survey. Theorem 1. Let F ∈ Z, x∗ ∈ X, and F∗ = F (x∗ ). Let
a scalar global criterion Fg (F) : Z → R1 be differentiable with ∇F Fg (F) > 0 ∀ F ∈ Z. Assume Fg (F∗ ) =
min {Fg (F) < F ∈ Z}. Then, x∗ is Pareto optimal.
Theorem 1 suggests that minimization of a global function Fg (F) is sufficient for Pareto optimality if Fg (F)
increases monotonically with respect to each objective
function. Furthermore, if x∗ is a Pareto optimal point,
then there exists a function Fg (F) that satisfies Theorem 1 and captures x∗ (Messac et al. 2000a). If minimizing Fg (F) is to provide a necessary condition for Pareto
optimality, the Hessian of Fg (F) with respect to F must
be negative definite (Athan and Papalambros 1996). 2.4
Efficiency and dominance
Efficiency, which is the same idea as admissibility or noninferiority (Steuer 1989), is another primary concept in
multi-objective optimization and is defined as follows:
Definition 4. Efficient and Inefficient: A point, x∗
∈ X, is efficient iff there does not exist another point,
x ∈ X, such that F (x) ≤ F (x∗ ) with at least one Fi (x) <
Fi (x∗ ). Otherwise, x* is inefficient. 2.3
Necessary and sufficient conditions Definition 5. Efficient Frontier: The set of all efficient
points is called the efficient frontier. Whether or not solving a particular multi-objective optimization formulation serves as a necessary and/or a sufficient condition for Pareto optimality is central to its
performance. However, these characterizations may veer
slightly from their meaning in terms of single-objective
optimization. If a formulation provides a necessary condition, then for a point to be Pareto optimal, it must
be a solution to that formulation. Consequently, every
Pareto optimal point is attainable with adjustments in
method parameters (exponents, weights, etc.), which
are discussed in Sect. 3. If a point is attainable using
a particular formulation, the formulation is said to capture that point. However, some solutions obtained using
this formulation may not be Pareto optimal. On the
other hand, if a formulation provides a sufficient condition, then its solution is always Pareto optimal, although certain Pareto optimal points may be unattainable. Many authors discuss theoretical necessary and
sufficient conditions as a means of qualifying Pareto optimality, and surveys on such conditions are available
(Vincent and Grantham 1981; Miettinen 1999). However, in this paper, the terms necessary and sufficient are
used in a more practical sense to describe the ability of
a method/formulation to provide Pareto optimal points.
In terms of a global criterion Fg , Stadler (1988)
presents the following sufficiency condition for a Pareto
optimal point, which is useful for evaluating the effectiveness of a scalarization method: Steuer also provides the following definition for nondominated and dominated points:
Definition 6. Non-Dominated and Dominated Points:
A vector of objective functions, F (x∗ ) ∈ Z, is nondominated iff there does not exist another vector, F (x) ∈
Z, such that F (x) ≤ F (x∗ ) with at least one Fi (x) <
Fi (x∗ ). Otherwise, F (x∗ ) is dominated.
For all practical purposes, Definitions 4 and 6 are the
same. However, efficiency typically refers to a vector of
design variables in the design space, whereas dominance
refers to a vector of functions in the criterion space.
The definition of Pareto optimality is similar to that
of efficiency, and a Pareto optimal point in the criterion
space is often considered the same as a non-dominated
point. However, efficiency and dominance were originally
given more general, less common definitions in terms of
domination structures and convex cones (Yu 1974; Yu
and Leitmann 1974). Pareto optimality is a subtly distinguishable special case of efficiency, but this distinction is
irrelevant in terms of practical applications. 2.5
Compromise solution
An alternative to the idea of Pareto optimality and efficiency, which yields a single solution point, is the idea 373
of a compromise solution (Salukvadze 1971a,b). It entails
minimizing the difference between the potential optimal
point and a utopia point (also called an ideal point), which
is defined as follows (Vincent and Grantham 1981):
Definition 7. Utopia Point: A point, F◦ ∈ Zk , is a utopia point iff for each i = 1, 2 . . . , k, Fi◦ = minimum
x
{Fi (x) |x ∈ X}.
In general, F◦ is unattainable. The next best thing is a solution that is as close as possible to the utopia point. Such
a solution is called a compromise solution and is Pareto
optimal. A difficulty with the idea of a compromise solution is the definition of the word close. The term close
usually implies that one minimizes the Euclidean distance
N (x), which is defined as follows:
◦ N (x) = |F (x) − F | =  k

 12
[Fi (x) − Fi◦ ]2 . (3) 1 However, it is not necessary to restrict closeness to the
case of a Euclidean norm (Vincent 1983). In addition, if
different objective functions have different units, the Euclidean norm or a norm of any degree becomes insufficient
to represent closeness mathematically. Consequently, the
objective functions should be transformed such that they
are dimensionless. 2.6
Function transformations Fitrans (x) = Fi (x)
,
|Fimax | (4) which results in a non-dimensional objective function
with an upper limit of one (or negative one) and an unbounded lower limit (note that Fimax = 0 is assumed).
There are two approaches for determiningFimax
 . One can
define Fimax such that Fimax = max Fi x∗j , where x∗j
1≤j≤k is the point that minimizes the jth objective function.
x∗j is a vertex
 of the Pareto optimal set in the design
space, and F x∗j is a vertex of the Pareto optimal set in
the criterion space. This approach of determining Fimax
has been used in the development of membership functions for fuzzy multi-objective optimization (Marler and
Arora 2003) and for Rao’s method, which is discussed
in Sect. 5.3. Alternatively, the denominator in (4) may Fi (x) − Fi◦
.
Fi◦ (5) This approach also provides a non-dimensional objective function. However, in this case, the lower value of
Fitrans (x) is restricted to zero, while the upper value is
unbounded. (5) is often referred to as the relative deviation or fractional deviation. Computational difficulties
can arise not only if the denominator is zero but also if it is
negative. Consequently, one assumes that the denominator is positive (Koski and Silvennoinen 1987; Eschenauer
et al. 1990), or uses its absolute value (Osyczka 1981).
The following is a variation on (5) (Koski and Silvennoinen 1987; Chen et al. 1999):
Fitrans (x) = Fi (x)
,
Fi◦ Fi◦ > 0 . (6) This approach yields non-dimensional objective function
values with a lower limit of one.
The most robust approach to transforming objective
functions, regardless of their original range, is given as follows (Koski 1984; Koski and Silvennoinen 1987; Rao and
Freiheit 1991):
Fitrans = For the sake of consistent comparison between methods,
it is assumed that the objective functions shown in (1)
are not modified. However, in many cases it is advantageous to transform the original objective functions. This
is especially true with scalarization methods that involve
a priori articulation of preferences. Therefore, we present
some common function transformation methods.
The first approach is given as follows (Proos et al.
2001):
Fitrans = also be determined using the absolute maximum (if it exists) of Fi (x) or its approximation based on engineering
intuition.
An alternative to (4) is given as follows (Osyczka 1978;
Salukvadze 1979; Hwang and Md. Masud 1979): Fi (x) − Fi◦
.
Fimax − Fi◦ (7) This approach is consistently referred to as normalization. In this case, Fitrans (x) generally has values between
zero and one, depending on the accuracy and method
with which Fimax (x) and Fi◦ (x) are determined.
It may be prohibitively expensive to compute the
utopia point used in the foregoing approaches; therefore,
one may use its approximation. 3
Methods with a priori articulation of preferences
The methods in this section allow the user to specify preferences, which may be articulated in terms of goals or the
relative importance of different objectives. Most of these
methods incorporate parameters, which are coefficients,
exponents, constraint limits, etc. that can either be set
to reflect decision-maker preferences, or be continuously
altered in an effort to represent the complete Pareto optimal set. The latter approach is discussed in Sect. 4.
Consideration of more than one objective function in
an optimization problem introduces additional degrees
of freedom. Unless these degrees of freedom are constrained, mathematical theory indicates a set of solution
points rather than a single optimal point. Preferences 374
dictated by the decision-maker provide constraints. The
most common approach to imposing such constraints is to
develop a utility function as defined earlier. Thus, most
of the formulations in this section are based on different
utility functions.
3.1
Weighted global criterion method
One of the most common general scalarization methods
for multi-objective optimization is the global criterion
method in which all objective functions are combined to
form a single function. The term global criterion technically can refer to any scalarized function, but it often is
reserved for the formulations presented in this subsection.
Although a global criterion may be a mathematical function with no correlation to preferences, a weighted global
criterion is a type of utility function in which method parameters are used to model preferences. One of the most
general utility functions is expressed in its simplest form
as the weighted exponential sum:
U=
U= k

wi [Fi (x)]p , Fi (x) > 0 ∀i , (8) [wi Fi (x)]p , Fi (x) > 0 ∀i . (9) i=1
k


i=1 The most common extensions of (8) and (9) are (Yu
and Leitmann 1974; Zeleny 1982; Chankong and Haimes
1983) U=  k

 p1
wi [Fi (x) − Fi◦ ] p i=1 U=  k

, (10) . (11)  p1
wip [Fi p
(x) − Fi◦ ] i=1 Here, w is a vector
of weights typically set by the decisionk
maker such tha...

• 1493954958-xid.pdf

SuperTutor

(15)

Status NEW Posted 05 May 2017 02:05 AM My Price 20.00

-----------

Attachments

file 1493954960-Solutions file.docx preview (56 words )

S-----------olu-----------tio-----------ns -----------fil-----------e -----------Hel-----------lo -----------Sir-----------/Ma-----------dam----------- T-----------han-----------k y-----------ou -----------for----------- yo-----------ur -----------int-----------ere-----------st -----------and----------- bu-----------yin-----------g m-----------y p-----------ost-----------ed -----------sol-----------uti-----------on.----------- Pl-----------eas-----------e p-----------ing----------- me----------- on----------- ch-----------at -----------I a-----------m o-----------nli-----------ne -----------or -----------inb-----------ox -----------me -----------a m-----------ess-----------age----------- I -----------wil-----------l b-----------e q-----------uic-----------kly----------- on-----------lin-----------e a-----------nd -----------giv-----------e y-----------ou -----------exa-----------ct -----------fil-----------e a-----------nd -----------the----------- sa-----------me -----------fil-----------e i-----------s a-----------lso----------- se-----------nt -----------to -----------you-----------r e-----------mai-----------l t-----------hat----------- is----------- re-----------gis-----------ter-----------ed -----------on�-----------�th-----------is -----------web-----------sit-----------e. ----------- H-----------YPE-----------RLI-----------NK -----------&qu-----------ot;-----------htt-----------p:/-----------/wo-----------rkb-----------ank-----------247-----------.co-----------m/&-----------quo-----------t; -----------\t -----------&qu-----------ot;-----------_bl-----------ank-----------&qu-----------ot;----------- -----------Tha-----------nk -----------you----------- -----------

Not Rated(0)

• Buy Answer