Information Technology Reference
In-Depth Information
Despite these results which constitute the es-
sence of the difficulty of MOCO problems, many
published works ignore the existence of NE.
Concerning computational complexity, in
obtaining the set of efficient solutions MOCO
problems are in general NP-complete. Results are
presented by Ehrgott (2000). The cardinality of E
for a MOCO problem may be exponential in the
problem size (Emelichev & Perepelista, 1992),
therefore algorithms could determine just an ap-
proximation of E in many cases. Thus, methods
may be exact or approximate, and metaheuristics
and hyperheuristics are nowadays being applied
intensively to MOCO problems.
ences. The choice of a solution from the
set of efficient solutions is an
a posteriori
approach.
If the problem criteria show a hierarchical
structure, more important criteria should be mini-
mized before less important ones. Thus, optimiza-
tion methods can be classified as hierarchical or
simultaneous.
In bi-criteria models, if
z
1
is more important
than
z
2
, then it seem to be natural to minimize with
respect to
z
1
first, and choose, from among these
optimal solutions, the optimum with respect to
z
2
.
This hierarchical approach is called
lexicographic
optimization, and is denoted by
α/β/Lex
(
z
1
,
z
2
).
In a general case, lexicographic minimization
consists in comparing the objective values of a
feasible solution
X
, with respect to another
Y
, in a
lexicographical order, denoted by <
lex
. Objective
functions are ranked according to their importance.
We say
X
<
lex
Y
, if, and only if, there is a
j
such that
z
j
(
X
)<
j
z
j
(
Y
), and there is not any
h
<
j
, such that
z
h
(
Y
)<
h
z
h
(
X
). This means that the first objective
function index,
i
Multicriteria optimization Methods
The minimization concept in the above formula-
tion is not restricted to one meaning. Besides the
typical classification of optimization methods
into exact or approximate, multicriteria opti-
mization methods can be classified by different
characteristics.
The MDM always assumes that subjective
considerations, such as the decision-maker pref-
erences, have to intervene. Thus, it is usual to
distinguish the MDM methods according to when
the decision-maker intervenes in the resolution
process, as follows:
{1,…,
K
}, for which
z
i
(
X
), is not
equal to
z
i
(
Y
),
z
i
(
X
)<
z
i
(
Y
).
Simultaneous optimization has to be applied
when there is no dominant relation among the
criteria. Optimizing with respect to one criterion
at a time leads to unbalanced results. It is com-
mon, in a case such as this, to use a composite
objective function with the original criteria. It
gives rise to another classification, because we
can generate solutions by means of scalarization
and non-scalarizing methods.
Scalarization is made by means of a real-
valued scalarizing on the objective functions of
the original problem (Wierzbicki, 1980). Well-
known examples of scalarization methods are
commented in the following.
The
weighted sum
approach consists in building
a new objective criterion with the original ones
(Isermann, 1977). This composite function can be
linear (in the majority of cases), where the scalar
coefficients represent the relative importance of
∈
•
a priori
: All the preferences are known at
the beginning of the decision-making pro-
cess. The search for the solution is carried
out on the basis of the known information.
•
interactive
: The decision-maker intervenes
during the search process. Computing steps
alternate with dialogue steps. At each step
a satisfying compromise determination is
achieved. It requires the intensive partici-
pation of the decision-maker.
•
a posteriori
: The set of efficient solutions
(the complete set or an approximation of
it) is generated. This set can be analyzed
according to the decision-maker prefer-
Search WWH ::
Custom Search