ISSN 0101-7438 INTERACTIVE SIMULATED ANNEALING FOR SOLVING IMPRECISE DISCRETE MULTIATTRIBUTE PROBLEMS UNDER RISK Antonio Jiménez * Sixto Ríos-Insua Alfonso Mateos Department of Artificial Intelligence School of Computer Science Madrid Technical University Madrid – Spain E-mail: [email protected] * Corresponding author / autor para quem as correspondências devem ser encaminhadas Received September 2001; accepted October 2002 after one revision. Abstract We consider the multiattribute decision-making problem under risk with partial information of the decision-makers’ preferences modelled through an imprecise vectorial utility function and where the consequences are assumed under uncertainty. In this framework under imprecision, we introduce the appropriate utility efficient set that plays a fundamental role because it is where the decision-maker must look for a solution. However, this set can be difficult to determine. So, we provide a decision support system with a solution strategy based on interactive simulated annealing for generating a subset of efficient solutions that gives a fair representation of the whole set, to progressively derive one or several satisfying solutions to aid the decision-maker in his/her final choice. Keywords: imprecise vectorial utility function, efficient set, simulated annealing. Pesquisa Operacional, v.22, n.2, p.265-280, julho a dezembro de 2002 265 Jiménez, Ríos-Insua & Mateos – Interactive simulated annealing for solving imprecise discrete multiattribute problems under risk 1. Introduction Multiattribute expected utility theory can be considered as a leading paradigm for normative decision theory. However, multiattribute utility theory calls for the decision-maker (DM) to provide all the information describing the decision situation to assess on the one hand, the component scalar utility functions u, von Neumann & Morgenstern (1947), Savage (1954) i and Fishburn (1970) and, on the other, to determine an appropriate functional form of the global utility function u including these components u, Keeney & Raiffa (1976). It is i obvious that these information requirements can be far too strict in most practical situations. This could lead to the consideration of imprecise components utility functions in the first case, see e.g., Weber (1987) and Ríos et al. (2000), and in the second one, a vectorial utility function u, Roberts (1972, 1979) and Rietveld (1980), due to the difficulty in testing certain independence conditions, thus being u a proxy for the underlying utility function u. In this case, what could be called the set of imprecise utility efficient strategies plays an important role because of its well known property, analogous to the precise scalar case: the DM can restrict his attention to it, discarding the remaining strategies, because a nonefficient strategy can never be optimal. However, this set can be difficult to determine and, in many cases, it is not considered the resolution of the problem because this set can have many elements and is not totally ordered. Thus, intelligent approaches are needed to generate a representative approximation of the whole set. Moreover, we consider the situation where the consequences of the strategies could have associated uncertainty in their policy effects, as it is considered in Mateos et al. (2001). In order to provide the DM under this framework with a manageable number of strategies under risk for evaluation, we introduce a method for approximating the imprecise utility efficient set and its reduction for the case of a vectorial utility function, if it is possible that the DM can improve his assessments through an interactive process, Colson & de Bruyn (1989), Mateos & Ríos-Insua (1997, 1998) and Ríos-Insua & Mateos (1998), that adapts multi- objective simulated annealing, Serafini (1992), Ulungu et al. (1998) and Teghem et al. (2000). The paper includes four more sections. In section 2, we formally introduce the problem, some basic concepts and the imprecise approximation set. Section 3 deals with some theory and concepts describing multi-objective simulated annealing and its application to our problem, multiattribute decision-making problem under risk with imprecise information. An interactive simulated annealing approach to construct ‘good compromises’ taking into account DM preferences is described in section 4. Finally, in section 5, some conclusions are provided. 2. Problem Formulation: the approximation set Throughout the paper we employ the following notation: for two scalars a and b, a ≥ b denotes a > b or a = b. For two vectors x, y in ℜm, x ≥ y denotes x ≥ y for i = 1,...,m, and i i x ≥ y denotes x ≥ y but x ≠ y. Let us consider a decision-making problem under risk with imprecision concerning the consequences of each decision strategy. We define the imprecise consequence of certain strategy in a particular state of nature, in such a way that it is characterised by a vector of intervals z = ([zL,zU] ,..., [zL,zU]) , 1 1 m m 266 Pesquisa Operacional, v.22, n.2, p.265-280, julho a dezembro de 2002 Jiménez, Ríos-Insua & Mateos – Interactive simulated annealing for solving imprecise discrete multiattribute problems under risk where [zL,zU] define the imprecise consequence of the strategy for attribute Z of the whole i i i set of attributes {Z ,...,Z }. Note that the situation under precision or under certainty is the 1 m particular case where the endpoints of each interval are the same, i.e., zL= zU, for i i i = 1,...,m. Let Z be the set of imprecise outcomes with elements z, and P the set of simple Z probability distributions over Z (probability distributions with a finite number of imprecise outcomes), with elements p, q, p’... also called strategies, lotteries or risky prospects: p=p1Kps, z1Kzs where z1 = ([z1L,z1U],...,[z1L,z1U]) 1 1 m m ……. zs = ([zsL,zsU],...,[zsL,zsU]) , 1 1 m m with pt ≥ 0, t = 1..,s, and ∑pt = 1. The consideration of this type of mixed strategies is important in different areas among we can cite portfolio management, medicine and environment. For each attribute Z it is necessary to assess a utility function u that reflects DM preferences i i about their possible values. It is well known the difficulty in assessing utility functions even though good software is available to aid in conducting such process, see e.g., Logical Decisions (1998). Several authors, see e.g., Hershey et al. (1982), McCord & de Neufville (1986) or Jaffray (1989), have suggested that elicited utility functions are generally method- dependent, and bias and inconsistencies can be generated in the assignment process. To overcome these problems the system uses two slightly modified standard procedures jointly: a certainty equivalent method (CE) and a probability equivalent method (PE), see Farquhar (1984). It assumes imprecision concerning the scalar utility functions allowing the decision maker to provide a range of responses, instead of only one precise number in each probability question, as these methods demand. This is less stressful on experts, since they are allowed to provide incomplete preference statements by means of intervals rather than unique numbers, see von Nitzsch & Weber (1988) and Ríos et al. (1994). Therefore, a class of utility functions is obtained, rather than a single one, for each method. The intersection of both ranges provides the range where preferences elicited by the above methods agree. Should such intersections be empty for an interval, the DM would be inconsistent and he should reelicit his preferences. The process ends when a consistent range is provided. It is interesting to note that the use of imprecise utility functions facilitates the assignment process as we have experimented in real cases, as shown in Mateos et al. (2001) and Jiménez et al. (2002). Of course, this is not the definitive solution to overcome all the objections to the elicitation process, but we consider that it is an important aid and an interesting starting point to motivate a more deep study of the assessment problem. Specifically, we have implemented a CE-method, known as the fractile method, see e.g., Fishburn (1964, 1970), Holloway (1979) and Hull et al. (1973), where the DM is asked to provide certainty equivalent intervals or ranges of attributes for lotteries, whose results are the extreme values z* and z , that represent the most and less preferred outcomes for i i* Pesquisa Operacional, v.22, n.2, p.265-280, julho a dezembro de 2002 267 Jiménez, Ríos-Insua & Mateos – Interactive simulated annealing for solving imprecise discrete multiattribute problems under risk attribute Z and with probabilities pt and 1 – pt, respectively. We take p1 = .25, p2 = .50 and i p3 = .75. This means that the DM considers pt 1− pt   ~ zt zi* zi*  i for all amounts zt∈[zL ,zU ], for t = 1, 2, 3. Figure 1 shows in the z/u(z)-diagram this class i pt pt i i i of utility functions drawn between the dotted lines and represented by the bounding utility functions uLCE and uUCE , where L (U) means Lower (Upper). i i The PE-method included in the system is the extreme gambles method, see e.g., Schlaifer (1969) and Mosteller & Nogee (1951), where the DM has to specify probability intervals [pL, pU], t = 1, 2, 3, such that t t p 1− p   t t ~ zt zi* zi*  i for all p∈[ pL, pU ], for some selected amounts zt∈[z ,z*]. By default, these selected t t t i i* i amounts for attributes Z are the upper endpoints of the intervals proposed by the DM in the i CE method. Other points can be used for comparison. To obtain these probability intervals, the system includes a routine implementing a wheel of fortune, see French (1986), that provides the probabilistic questions and guides the expert until an interval of indifference probabilities is obtained. A number of additional questions are included as consistency checks. Figure 1 also shows this class of utility functions drawn with continuous lines and represented by the bounding utility functions uLPE and uUPE , with L and U as above. i i As mentioned above, should the intersection of both ranges be empty for some values, the DM would have provided inconsistent responses and he should reassess his preferences. Thus, the intersection will be the range for the DM’s utility functions. The system is able to detect the possible inconsistencies and suggests what the DM could change to achieve the consistency. Thus, for each attribute Z, instead of having a unique utility u (z), we have a i i i utility interval [uL(z ),uU(z )], which represents the elicited imprecision of the DM i i i i concerning the utility of value z. This is also shown by the striped area in Figure 1. i Figure 1 – Class of utility functions for an attribute Z i 268 Pesquisa Operacional, v.22, n.2, p.265-280, julho a dezembro de 2002 Jiménez, Ríos-Insua & Mateos – Interactive simulated annealing for solving imprecise discrete multiattribute problems under risk The second point is related to the kind of decomposition of the global utility function u(z) = u(z ,…, z ). Assuming precision, as in the classic case, the general setting is that the 1 m DM looks for a global utility function of the form u(z) = f(u (z ),...,u (z )), 1 1 m m where z is a specific amount of Z, f is a scalar-valued function and u are precise utility i i i functions. To obtain a specific structure for f, it is necessary to fulfil independence conditions among the attributes (additive independence, preferential independence or other possible independence conditions related to the set or subsets of attributes), Keeney & Raiffa (1976). This can be difficult in complex problems because it could be possible to verify only some of these independence conditions among certain attributes in such a way that we consider a vectorial utility function instead of a scalar one as above (possibly with a more reduced dimension). Thus, to maintain the notation, assume that no independence condition is fulfilled and thus we have a vectorial utility function (dimension m remains for ease) u(z) =(u (z ),...,u (z )). 1 1 m m From both imprecision sources, we have associated to each consequence in a particular state of nature z = ([zL,zU ],...,[zL,zU ]) an imprecise vectorial utility function given by 1 1 m m u(z) =([uL(zL),uU(zU)],...,[uL(zL),uU(zU)]), 1 1 1 1 m m m m where uL(zL) = max {uLPE(zL),uLCE(zL)} and uU(zU) = min {uUPE(zU),uUCE(zU)} i i i i i i i i i i i i provided that all the classes of utility functions for the attributes Z are monotone increasing, see Figure 2. In case these classes of utility functions for attribute Z were monotone i decreasing, the corresponding utility interval would be [uL(zU),uU(zL)]. The approach we i i i i present requires that all the utility functions are monotone, what it is not an important practical limitation. For simplicity, let us suppose from now on that the classes of utility functions are monotone increasing for all the attributes. Figure 2 – An imprecise utility interval for an imprecise consequence when the class of utility functions u is monotone increasing i Pesquisa Operacional, v.22, n.2, p.265-280, julho a dezembro de 2002 269 Jiménez, Ríos-Insua & Mateos – Interactive simulated annealing for solving imprecise discrete multiattribute problems under risk Now, given a strategy under risk with imprecise consequences, p, the imprecise expected utility vector is defined as the vector of intervals with endpoints the lower and upper expected utilities for each attribute (or utility component in the vectorial utility function), given by E (u, p) = ([E(uL,p),E(uU,p)],...,[E(uL,p),E(uU,p)]) I 1 1 m m  s s   s s  = ∑piuL(ziL),∑piuU(ziU) ,..., ∑piuL(ziL),∑piuU(ziU) ,  1 1 1 1   m m m m  i=1 i=1  i=1 i=1  denoted by p and where the subscript I in E means imprecision. Thus, u =([u1L(⋅),u1U(⋅)],...,[umL(⋅),uUm(⋅)]) represents a preference relation fuon PZ, leading to a dominance principle defined as pfu q⇔{EI (u, p) ≥ EI (u, q) or p ≥ q}  s s  ∑piuL(ziL)≥∑qiuU(ziU)  1 1 1 1  i=1 i=1  ⇔ ... and E (u,p)≠E (u,q). I I  s s  ∑piumL(zmiL) ≥∑qiuUm(zmiU)  i=1 i=1  The relation fuis a strict partial order on PZ (transitive and asymmetric), and, hence, we state the imprecise vector optimization problem under risk as max E (u, p) I s.t. p∈P Z A natural concept is the one of efficient strategy, p∈P is an imprecise utility efficient vector Z strategy if there is no q∈P such that E (u, q) ≥ E (u, p). This set of strategies is called Z I I imprecise utility efficient vector set and denoted ε(u, p). The above definition first extends I the one for precise problems under certainty and then under uncertainty. Note that, if we consider a sure prospect p = (1, z) ∈ P or a strategy p = (p1, z1;...; pn, zn) ∈P , z Z Z with a precise vectorial utility function u, it also makes sense to consider the utility efficient set for Z given u for the first case, denoted ε (Z, u) = { z ∈ Z : there not exists z’∈Z such that u(z’) ≥ u(z)} , or the utility efficient set for P given u for the second case, denoted Z ε (P , u) = { p ∈ P : there not exists p’∈ P such that E(u, p’) ≥ E(u, p)} . Z Z Z Thus, we are led to the problem “Given PZ and fu, find εI (PZ, u)”. Clearly, if εI (PZ, u) had a unique element p, it would be the most preferred strategy for DM. However, this is not the case in most real problems, as ε(P , u) could contain a lot of elements. The generation of I Z this set can be difficult and, usually, it is not the resolution of the problem because it does not provide the DM with a small enough number of decision strategies to facilitate the choice. Thus, our problem should be restated as “select a single element from the set ε(P , u)”. I Z 270 Pesquisa Operacional, v.22, n.2, p.265-280, julho a dezembro de 2002 Jiménez, Ríos-Insua & Mateos – Interactive simulated annealing for solving imprecise discrete multiattribute problems under risk One way to solve this decision problem, favoured by behavioural approaches, will be possible if the DM is able to reveal more information of his preferences to provide additional structural assumptions obtaining a subset of the imprecise utility efficient vector set. So, we provide an interactive method based on multi-objective simulated annealing, Serafini (1992), Czyzak & Jaszkiewicz (1997) and Teghem et al. (2000), to aid the DM to progressively build a subset of the approximation set in collaboration with the DM. 3. Multi-objective Simulated Annealing The idea of this method we propose is based on the set of imprecise expected utility vectors. We generate then an approximation set A(P , u) of the utility efficient set ε(P , u), i.e., Z I Z strategies not dominated by any other generated strategy. The basic idea of multi-objective simulated annealing (MSA) is simple, the method begins with a first iteration providing an initial strategy or solution p , and thus the set A(P , u) is 0 Z initialized containing only p . In the next iterations, another strategy q from the 0 neighbourhood of the current iteration is considered and is accepted if it is not dominated by any solution currently in the approximation set. In this case, we add q to the set A(P , u) and Z throw out any solution in A(P , u) dominated by q. On the other hand, if q is dominated by Z any solution in A(P , u), we would continue considering q for the next iteration with certain Z probability. In this way, according to the movement in the iterations through the space, we simultaneously build the set A(P , u). Z Next, we introduce the phases of the method in more detail. For this purpose, let us now see the steps to be applied from a general point of view and some adaptations to our specific case, the imprecise multiattribute problem under risk. The clarifications of some concepts that appear in the algorithm, as the neighbourhood of a solution, will be considered later. Parameters and stopping conditions that are typically used in simulated annealing are the following: • n, is the number of iterations in the algorithm. • T , initial temperature (or alternatively, it defines the initial acceptance probability). 0 • N , number of iterations throughout the temperature is held at the same value. step • N , number of iterations without having found new solutions. count • α (<1), cooling factor. The updating of the temperature depends on it. If the decreasing of the temperature is slow, the performance is also slow. The usual scheme is to maintain the temperature for a number of iterations, in this case N iterations. After that, step decreases by multiplying it by α. A typical value for α is 0.95, Hajek (1988). • T , final temperature. stop • N , maximum number of iterations without improvement. It is used as stopping rule. stop More information of these parameters and stopping conditions for the standard algorithm can be found in Pirlot (1996). Now, MSA algorithm can be formulated as follows: • Initialisation: We set N = n = 0 and A(P , u) = {p }, where p is drawn at P . count Z 0 0 Z Pesquisa Operacional, v.22, n.2, p.265-280, julho a dezembro de 2002 271 Jiménez, Ríos-Insua & Mateos – Interactive simulated annealing for solving imprecise discrete multiattribute problems under risk • Step n: Let p be the solution in the current iteration, V(p ) a neighbourhood of p and q a n n n solution drawn at random in V(p ). Let us consider the difference between the imprecise n expected utilities in each component k, for k=1,..,m. Given the respective imprecise expectations p = E (u, p ) = ([E(uL, p ), E(uU, p )],...,[E(uL, p ), E(uU, p )]) , n I n 1 n 1 n m n m n q = E (u, q) = ([E(uL, q), E(uU, q)],...,[E(uL, q), E(uU, q)]) , I 1 1 m m there will be the next three possibilities, see Figure 3: 1. for all k 3. for all k E(uU, pn ) E(uL p ) k k , n pn E(ukL, q) E(ukU, q) pn q q q dominates to pn pn dominates to q 2. - for some k’ - for some k E(uL p ) , n k' E(uU, pn ) k p p E(uU , q) n n E(uL q) k' k , q q Non dominance between q and p n Figure 3 – Possible relations between two strategies p and q n 1. For all k, E(uL, q) – E(uU, p ) ≥ 0, what implies that q dominates to p . Then p ← q. k k n n n+1 2. There are k, k’ such that E(uL, q) – E(uU, p ) < 0 and E(uU, q) – E(uL, p ) > 0, i.e., k k n k' k' n no dominance between q and p is fulfilled. Then p ← q. n n+1 3. For all k, E(uU, q) – E(uL, p ) ≤ 0, what implies that p dominates to q. In this case k k n n we have: (a) p ← q with probability τ. n+1 (b) p ← p with probability 1–τ. n+1 n In both cases the number of consecutive iterations without having obtained a new solution is increased: N = N + 1. count count Probability τ depends on the differences E(uU, q) – E(uL, p ) and on the k k n temperature, as we shall next see. 272 Pesquisa Operacional, v.22, n.2, p.265-280, julho a dezembro de 2002 Jiménez, Ríos-Insua & Mateos – Interactive simulated annealing for solving imprecise discrete multiattribute problems under risk Moreover, in the first two cases, the A(P , u) is updated by comparing q with the Z solutions in the list: • If q is not dominated by any solution in A(P , u) (cid:198) we add q to the set A(P , u), Z Z throw out any solution in A(P , u) dominated by q and N = 0. Z count • Else (cid:198) N = N + 1. count count One possible difficulty related to the dominance principle is the fact that it could be far too strict in the sense that, for real applications, cases 1 and 3 arise in a very reduced number of occasions, not allowing an adequate search in the utility efficient set. To overcome this inconvenience, we propose to relax these kind of comparisons allowing the DM to introduce a percentage quantity σ. Observe that whether the percentage quantity is equal to zero, we are in the initial setting. Thus, for a given p , instead of the intervals n [E(uL, p ), E(uU, p )], for each k=1,...,m , we would use the intervals k n k n [E(uL, p ) + (σ/100) ψk , E(uU, p ) – (σ/100) ψk ], k n pn k n pn where ψk =(E(uU, p )–E(uL, p ))/2, i.e., is the half of the expected utility interval length pn k n k n in component k for the solution p . Figure 4 displays the involvement of this consideration n for case 2. We have the relationship between p and q before (including the dotted lines) and n after introducing a percentage quantity σ (only the continuous lines). E(uU, p ) - (σ/100) ψk k n pn E(uU, p ) k n p n E(uL q) q k , E(uL q)+( σ /100) ψk k , q q dominates to p for a given σ n Figure 4 – Less strict dominance principle The stopping condition makes reference to the present value of the temperature and to the number of iterations carried out without having obtained new solutions. The algorithm stops when the temperature takes a value under T or after N consecutive iterations without stop count having obtained new solutions. • (Updating of temperature) If (n mod N ) = 0 then T = α T step n n-1, otherwise, T = T . n n-1 • (Stopping condition) If N = N or T < T , then stop. count stop stop Fortemps et al. (1994) have proposed several multi-objective rules for the acceptance probability to deal with the third case. These rules are based on two different criteria to Pesquisa Operacional, v.22, n.2, p.265-280, julho a dezembro de 2002 273 Jiménez, Ríos-Insua & Mateos – Interactive simulated annealing for solving imprecise discrete multiattribute problems under risk accept with probability one the chosen point in the neighbourhood. On the one hand, we have the strong criterion in which only points q that dominates to p will be accepted with n probability one and, on the other, the weak criterion in which only dominated points will be accepted with probability strictly smaller than one. A rule based on the strong criterion is P-rule (Product) defined in our context as: P(pn, q, T, λ) = ∏m min1,eλj(E(uUj,q)−E(uLj,pn))/T ,   i=1 where the amount T/λ plays the role of the temperature T. This is like having a different j j temperature factor for each component. Another rule is the W-rule (Weak) that as its own name indicates it uses the weak criterion. It is defined as: W(pn, q, T, λ) = min1,maxeλj(E(uUj,q)−E(uLj,pn))/T .  j  By reasons described in Serafini (1992), we have decided to use a combination of both rules, that keeps the advantages of both, leading to the M-rule (Mixed), defined as: M(pn, q, T, λ) = ρ∏m min1,eλj(E(uUj,q)−E(uLj,pn))/T +   i=1 +(1−ρ)min1,maxeλj(E(uUj,q)−E(uLj,pn))/T ,  j  where ρ is a weighting factor provided by the DM. In all the formulas, T represents the temperature parameter and a set of weights λ is necessary to define each function. Moreover, taking into account the less strict dominance principle, see Figure 4, we obtain the next modified M-rule: M(pn, q, T, λ) = ρ∏m min1,eλj((E(uUj,q)−(σ/100)ψqj)−(E(uLj,pn)+(σ/100)ψpjn))/T + i=1   +(1−ρ)min1,maxeλj((E(uUj,q)−(σ/100)ψqj)−(E(uLj,pn)+(σ/100)ψpjn))/T ,  j  where ψpjn= (E(uUj , pn)–E(uLj , pn))/2 and ψqj= (E(uUj , q)–E(uLj , q))/2. The set A(P , u) depends on λ, so we denote it from now on by A(P , u, λ). Thus, A(P , u, λ) Z Z Z contains all the potential efficient imprecise utility vector solutions generated by MSA using the weights λ. Note that by controlling the weights, we can increase or decrease the acceptance probability of new solutions, which means to select a certain set of weights that could lead us towards certain region formed by the potential efficient imprecise utility vector solutions. The procedure for obtaining a good approximation of the set A(P , u) could be as follows: Z A(P , u, λ) is the list of potential efficient imprecise utility vectors obtained with the weights Z λ. Taking several sets of weights λ(l), l∈L generated in an extensively diversified way, for 274 Pesquisa Operacional, v.22, n.2, p.265-280, julho a dezembro de 2002