2.1 Selection of a Pareto-optimal solution

     Multi-criteria optimization methods typically assume that a multi-criteria problem is converted into an auxiliary parametric single-objective problem whose solution provides a Pareto-optimal point.³ Different methods apply different conversions but most commonly known methods can be interpreted (see [Mak94b]) in the terms of Achievement Scalarizing Function ( ASF). The concept of  ASF has been introduced by Wierzbicki (see e.g. [Wie77,Wie86,Wie92,WMW99] for the mathematical foundations, interpretations and applications) and it is very useful for comparing different approaches to multi-criteria optimization.

The selection of  the Pareto-optimal solution depends on the definition of the  ASF, which - for the  aspiration-led model analysis - also includes a selected  aspiration point. Most of those methods use the maximization of an  ASF in the form:  

$$s(q, \bar{q}, w) = \min_{1\le i \le n} \{w_i (q_i - \bar{q_i}) \} +\epsilon \sum_{i = 1}^n w_i (q_i - \bar{q_i})$$ (1)

where $q(x) \in R^n$ is a vector of criteria, $x \in X_0$ are variables defined by the  core model, X₀ is a set of feasible solutions implicitly defined by the core model, $\bar{q} \in R^n$ is an  aspiration point, w_i > 0 are scaling coefficients and $\epsilon$ is a given small positive number. Maximization of (1) for $x \in X_0$ generates a properly efficient solution with the trade-off coefficients (as recomputed in terms of u_i defined below) smaller than $(1+1/\epsilon)$.For a non-attainable $\bar{q}$ the resulting  Pareto-optimal solution is the nearest (in the sense of a Chebyshev weighted norm) to the specified  aspiration level $\bar{q}$.If $\bar{q}$ is attainable, then the Pareto-optimal solution is uniformly better. Setting a value of $\epsilon$ is itself a trade-off between getting a too restricted set of  properly Pareto-optimal solutions or a too wide set practically equivalent to  weakly Pareto-optimal optimal solutions. Assuming the $\epsilon$ parameter to be of a technical nature, the selection of efficient solutions is controlled by the two vector parameters: $\bar{q}$ and w.

There is a common agreement that the  aspiration point is a very good controlling parameter for examining  a Pareto set (i.e. a set composed of Pareto-optimal solutions). Much less attention is given to the problem of defining the scaling coefficients⁴ coefficients w. A detailed discussion on scaling coefficients in a scalarizing function is beyond the scope of this paper. The four commonly used approaches are summarized in [Mak94b]. In practical applications the most promising approach is based on the calculation of scaling coefficients (that are used in definition of the weighted Chebyshev norm mentioned above) with help of the  aspiration level $\bar{q}$and a  reservation level $\underline{q}$ (the latter is composed of values of criteria that the user wants to avoid). This is the  ARBDS approach that has been introduced by the DIDAS family of  DSS described in [LeW89a].

The  ASF for the  ARBDS approach usually takes the form:  

$${\cal S}(q, \bar{q}, \underline{q}) = \min_{1 \le i \le n }... ...\epsilon \sum_{i = 1}^{n} u_i (q_i, \bar{q}_i, \underline{q}_i)$$ (2)

where $\bar{q}, \underline{q}$ are vectors (composed of $\bar{q_i}, \underline{q_i}$, respectively) of  aspiration and  reservation levels respectively, and $u_i(q_i, \bar{q}_i, \underline{q}_i)$ are the corresponding Component Achievement Functions  CAF (defined later in detail), which can be simply interpreted as nonlinear monotone transformations of q_i taking into account the information represented by $\bar{q}_i$ and $\underline{q}_i$.Maximization of the function (2) over the set of feasible solutions X₀ defined by the corresponding  core model provides a properly  Pareto-optimal solution with the properties discussed above for the function (1).

The  ASF implemented in  MCMA is a modification of the function (2). The modification has been stimulated by some applications for which it is often useful to temporarily disregard some of the  criteria. A criterion for which the user does not wish to define the corresponding component scalarizing function is called in  MCMA  an inactive criterion (see Section 4.4.3). Inactive criteria are also useful for computing a good approximation of a  Nadir point. However, completely disregarding a criterion from the  ASF may result in both numerical problems (caused by a degenerated problem) and in a random value of the  criterion (which may be unnecessarily bad and can in turn result in a bad approximation of a  Nadir point, see [Mak94b] for more details). Therefore, the following form of the  ASF is implemented in  MCMA in order to facilitate a proper handling of  inactive criteria:  

$${\cal S}(q, \bar{q}, \underline{q}) = \min_{i \in I} u_i (... ...q}_i) + \epsilon \sum_{i \in \bar{I}} u_i (q_i, q_i^U, q_i^N)$$ (3)

where I and $\bar{I}$ are sets of indices of active and inactive criteria, respectively, and q_i^U and q_i^N are  Utopia and approximation of  Nadir values, respectively. One can easily show that the treatment of a criterion as an inactive one has a similar effect to selecting the corresponding  aspiration level close to the approximation of  Nadir for that criterion. Note that for all criteria being active the  ASF defined by (3) is equivalent to that of (2).

Component achievement functions ( CAF) $u_i (\cdot)$ are strictly monotone (decreasing for minimized and increasing for maximized    criteria, respectively) functions of the objective vector component q_i with values  

$$u_i(q_i^U,\cdot) = 1 + \bar{\gamma}, \qquad u_i(\bar{q}_i,\c... ...{q}_i,\cdot) = 0, \qquad u_i(q_i^N,\cdot) = -\underline{\gamma}$$ (4)

where $\bar{\gamma}$ and $\underline{\gamma}$, are given positive constants, typically equal to 0.1 and 10, respectively. In  MCMA the values of $\bar{\gamma}$ and $\underline{\gamma}$ are computed for each criterion in such a way that the ratios of the slopes⁵ of the adjoint segments to the slopes of segments defined by the  Utopia and  aspiration points, and by the  Nadir and  reservation points, respectively (see Figure 1 for the illustration) have given values. These values are in the current implementation of  MCMA set to 10 and 0.1, for the segments adjoint to the  aspiration and to the  reservation point, respectively. Such an approach assures a correct handling of cases, in which a user specifies a flat or a steep segment (adjoint to the  aspiration and to the reservation point, respectively) of the  CAF.

The piece-wise linear component achievement functions ( CAF) u_i proposed by [Wie86] are defined by (5) and by (6) for minimized    and maximized criteria, respectively.  

$$u_i (q, \bar{q}, \underline{q}) = \left \{ \begin {array}{l... ... -q_i ) & {\rm if} & \underline{q}_i < q_i\end{array} \right .$$ (5)

 

$$u_i (q, \bar{q}, \underline{q}) = \left \{ \begin {array}{l... ...i - q_i) + 1, & {\rm if} & \bar{q}_i < q_i\end{array} \right .$$ (6)

where $w_i = 1/(\underline{q}_i - \bar{q}_i)$, and $\zeta_i$, $\eta_i$$(i=1,2,\ldots,n)$ are given parameters, which are set in such a way that u_i takes the values defined by (4).

However, in order to allow for either specification of only  aspiration and  reservation levels or for additional specification of preferences (for the criteria values between  aspiration and reservation levels), the  ISAAP supports specification of the component achievement functions in a more general form than that of eq. (5, 6). For this purpose, the piece-wise linear  CAF u_i are defined by segments u_ji:  

$$u_{ji} = \alpha_{ji} q_i + \beta_{ji},\qquad q_{ji} \le q_i \le q_{j+1,i} \qquad j = 1, \dots, p_i$$ (7)

where p_i is a number of segments for i-th criterion. Such a function for a minimized criterion is illustrated in Figure 1. The thin line corresponds to a function that is composed by three segments, which are defined by four points, namely     U, A${}^\prime$,R and N (that correspond to the  Utopia,  aspiration,  reservation and  Nadir points, respectively). The solid line represents a modified function for which the previously defined  aspiration level A${}^\prime$ was moved to the point A and two more points P¹ and P² were interactively defined.

 

Figure 1: Illustration of the piece-wise linear component achievement function for a minimized criterion.

Practical applications show that sometimes it is useful to set $\bar{q}_i = q_i^U$ and/or $\underline{q}_i = q_i^N$.Therefore, in order to handle also component achievement functions composed of only one segment (in cases where an  aspiration level is set to the  Utopia value and a  reservation level is equal to an approximation of  Nadir)  ISAAP allows for $p_i \ge 1$.

The coefficients defining the segments are given by:  

$$\alpha_{ji} = \frac {u_{j+1,i} - u_{ji}} {q_{j+1,i} - q_{ji}}$$ (8)

$$\beta_{ji} = u_{ji} - \alpha_{ji} q_{ji}$$ (9)

where points (u_ji,q_ij) are interactively defined with the help of  ISAAP (see Section 4.3.1 for details). Concavity of the piece-wise linear functions u_i(q_i) defined by segments (7) can be assured by a condition:  

$$\alpha_{1i} \gt \alpha_{2i} \gt \dots \gt \alpha_{p_ii}$$ (10)

Note that the component achievement functions u_i defined by (7) take the same form for minimized and maximized   criteria. However, one should add (in addition to the condition (10) that assures concavity) a condition:  

$$\alpha_{1i} < 0 \qquad i \in I^{\rm min}$$ (11)

 

$$\alpha_{p_ii} \gt 0 \qquad i \in I^{\rm max}$$ (12)

where $I^{\rm min}$ and $I^{\rm max}$ are sets of indices of criteria minimized and maximized, respectively. The conditions (11, 12) are fulfilled automatically for the component achievement functions u_i specified with the help of  ISAAP.

 

Figure 2: Illustration of the piece-wise linear component achievement function for a goal type (or stabilized) criterion.

A goal-type criterion can be used when a distance from a given   target value (which can be changed during the interaction) is to be minimized. For such a criterion a component achievement function is composed of two parts: the first part is defined for the criterion values smaller than the  target value, and the second part for the criterion values larger than the given target. Such a function is illustrated in Figure 2. The conditions specified above for maximized and minimized criteria hold for the first and second function, respectively. There is obviously only one point i, for which $\alpha_{i-1,i} \gt 0$ and $\alpha_{i,i+1} < 0$ and the criterion value for such a point corresponds to   a target value (denoted by T) for the goal type criterion. The function shown in Figure 2 is symmetric, but for many applications an asymmetric function is appropriate and therefore both types of functions for the goal type of criteria are supported by  ISAAP. Figure 35 (on page ) illustrates an asymmetric  CAF.

...point.³

A solution is called Pareto-optimal (or efficient) solution, if there is no other solution for which at least one criterion has a better value while values of remaining criteria are the same or better. In other words, one can not improve any    criterion without deteriorating a value of at least one other criterion.

...coefficients⁴

Note that the scaling coefficients w should not (see e.g. [Mak94b,Nak94] for a detailed discussion and examples) be used as weights for a conversion of a multi-criteria problem into a single criterion problem with a weighted sum of criteria. In the function (1) they play a different role than in a weighted sum of  criteria.

...slopes⁵

Defined by eq. (8).

Janusz Granat	- Institute of Control and Computation Engineering
Marek Makowski	- International Institute for Applied Systems Analysis