Patrick Meyer

Alexandru-Liviu Olteanu
email: alexandru.olteanu@univ-ubs.fr

Handling imprecise and missing evaluations in multi-criteria majority-rule sorting

Keywords: multi-criteria decision aiding, majority-rule sorting, missing values, intervals of categories

In this paper we propose an extension of a multi-criteria majority-rule sorting model that allows the handling of problems where the decision alternatives contain imprecise or even missing evaluations. Due to the imprecise nature of the evaluations we offer the possibility of assigning an alternative to one or more neighboring categories, both as input for inferring the model parameters as well as the output of the classification. Our contribution also contains an algorithmic approach for extracting the parameters of this model during an elicitation process, which is validated across a wide range of generated datasets.

Introduction

We consider in this article a decision situation in which a finite set of alternatives is evaluated on a finite set of criteria. When comparing two alternatives from a preferential point of view, a decision maker (DM) uses a majorityrule in accordance with the Multi-criteria Decision Aiding (MCDA) outranking paradigm [START_REF] Roy | Classement et choix en présence de points de vue multiples: La méthode ELECTRE[END_REF]. This means that (s)he considers that an alternative a outranks an alternative b when a weighted majority of criteria validates the fact that a is performing at least as good as b and there is no criterion where b seriously outperforms a. The first condition is called concordance or majority rule, whereas the second condition is called discordance or veto rule. Various implementations of these conditions, and their combination, have been proposed in the literature (see for example [START_REF] Roy | Aide Multicritère à la Décision : Méthodes et Cas[END_REF]), together with additional concepts such as "reinforced preference", "counter-veto" (see [START_REF] Roy | Handling effects of reinforced preference and counter-veto in credibility of outranking[END_REF]) or "dictator" (see [START_REF] Meyer | Integrating large positive and negative performance differences in multicriteria majority-rule sorting models[END_REF]).

In this paper, we restrict our discourse to a specific type of decision problems, called sorting, which aims to assign the decision alternatives into a set of predefined ordered categories or classes, according to the preferences of the DM, represented by a majority rule model. The work in this article is based on a simplified version of the classical Electre Tri method [16; 30; 35], called MR-Sort [START_REF] Leroy | Learning the parameters of a multiple criteria sorting method[END_REF], which is close to the version axiomatized in [3; 4], and which does not consider the previously mentioned discordance or veto principle. The MR-Sort procedure takes thus into account the preferences of the DM, which are represented through the following preferential parameters :

• weights, which give the relative importance of criteria;

• a majority threshold, which indicates the weight of a coalition of criteria in order to be considered sufficient;

• category limits, which are used to segment the evaluations scales into performance ranges appropriate for assignment into each category.

In this context, we focus on the problem raised by imprecise and incomplete evaluations in the performances of the alternatives on the criteria. We therefore propose an extension of the MR-Sort procedure, which handles both this imprecision and the lack of evaluations, and which possibly provides assignments into one or several neighboring categories. In order to determine the parameters of the model, the DM is asked to assign some alternatives, which may also contain missing or imprecise evaluations, to one or more contiguous categories. The proposed elicitation method then determines the preferential parameters of the model via an approximative approach.

The rest of the article is structured as follows. In Section 2 we start this paper by presenting an overview of sorting techniques in the outranking paradigm and related work on imprecise and missing evaluations in MCDA. Section 3 details the sorting model that we propose, whereas Section 4 shows how its parameters can be determined from assignment examples. In Section 5 we test this learning algorithm on artificially generated benchmarks . Finally, we draw some conclusions in Section 6 and present perspectives for future work.

State of the art

Majority-rule sorting

In this section, we introduce formally the MR-Sort assignment procedure, on which the work of this article is based. It is a simplified version of the classical Electre Tri method [16; 30; 35] and close to the version axiomatized in [3; 4].

Let us consider a finite set of alternatives A, a finite set of criteria indexes J and a set of category limits separating profiles B = {b 1 , . . . b k-1 }. Each alternative and each category limit is a vector of evaluations with respect to all criteria. The evaluation with respect to criterion j can be viewed as a function g j : A ∪ B → R, where g j (a) denotes the evaluation of alternative a ∈ A on criterion j and g j (b h ) denotes the evaluation of category limit b h , ∀h ∈ {1, . . . , k -1}, on criterion j. The set of category limits are used to define a set of k categories {c 1 , . . . , c k }, ordered by their desirability, from c 1 being the worst category to c k being the best one. Each category c h is defined through its upper limit, b h , and its lower limit, b h-1 , with the exception of the worst and best categories, which have only one limit. We assume, without loss of generality, that the performances are supposed to be such that a higher value denotes a better performance. Furthermore the performances of the category limits are non-decreasing, i.e. ∀j ∈ J, 1 < h < k : g j (b h-1 ) ≤ g j (b h ).

MR-Sort uses two assignment rules for placing the alternatives into categories: the pessimistic and the optimistic assignment rules [37; 5]. The pessimistic rule assigns an alternative a to the highest possible category c h such that a outranks the category's lower frontier b h-1 . The optimistic rule assigns a to the lowest possible category c h such that the category's upper frontier b h outranks a. The pessimistic rule is the most commonly used in practice.

An alternative a is said to outrank a frontier b h-1 if and only if there is a sufficient coalition of criteria supporting the assertion "a is at least as good as b h-1 ". To measure this, we define for each criterion j a function C j : A × B → {0, 1} which assesses whether criterion j supports that statement or not:

∀j ∈ J, a ∈ A, 1 ≤ h ≤ k : C j (a, b h-1 ) = 1, if g j (a) ≥ g j (b h-1 ), 0, otherwise. (1)
To assess whether a coalition of criteria is in favor of the outranking or not, ∀a ∈ A, 1 ≤ h ≤ k, we first define the overall concordance as:

C(a, b h-1 ) = j∈J w j C j (a, b h-1 ), (2)
where w j is the weight of criterion j. The weights are defined so that they are positive (w j 0, ∀j ∈ J) and sum up to one ( j∈J w j = 1). This overall concordance is then compared to a majority threshold λ ∈ [0.5, 1] extracted from the decision-maker's preferences along with the weights. As we do not consider any veto rule here, the outranking relation S is then defined as:

a S b h-1 ⇐⇒ C(a, b h-1 ) λ. (3)
If C(a, b h-1 ) < λ, the coalition of criteria is not sufficient, the alternative does not outrank the frontier b h-1 and will therefore be assigned in a category lower than c h .

Alternative a is assigned to the highest category it outranks, hence this rule can be written as:

a ∈ c h ⇐⇒ a S b h-1 and a S b h . (4)
In order for this assignment rule to be used for the limit categories, two dummy profiles b 0 and b k need to be added to B, the first holding the lowest possible evaluations on all criteria, while the second holding the highest possible ones.

In Table 1 we provide a simple illustrative example for this assignment rule.

At the top we observe the parameters of the sorting model, involving 5 criteria and 3 classes. The first parameter (λ) is the majority threshold, followed by the vector of the criteria weights (w) and two category separating profiles (b 1

λ = 3 5 w = ( 1 5 , 1 5 , 1 5 , 1 5 , 1 5 ) b1 = (1, 1, 1, 1, 1) b2 = (2, 2, 2, 2 , 2)
A g1 g2 g3 g4 g5 ai S b0 ai S b1 ai S b1 ai S b2 ai S b2 ai S b3 assignment a1 2 2 2 0 0 c3 a2 2 2 1 0 0 c2 a3 2 2 0 0 0 c1 and b 2 ). Each criterion is defined on a scale from 0 to 2. Below the parameters we illustrate the assignment of three alternatives using the assignment rule from Equation (4). In the case of the first and last categories we have added two fictive limits in order to simplify the example. The lower category limit of the worst category (b 0 ) is considered to be always worse than all the alternatives in A on each criterion, while the upper profile of the best category (b 3 ) is considered to be always better than all alternatives in A on each criterion. The first alternative outranks both b 1 and b 2 , as it is at least as good as these profiles on the first three criteria, hence it is assigned to the highest category. The second alternative is at least as good as b 1 on the first three criteria, but it is at least as good as b 2 on only the first two, therefore it is assigned to the second category. Finally, the last alternative is not at least as good as b 1 , nor b 2 , since it is at least as good as them on only two out of the 5 criteria, therefore it is placed in the lowest category.

The parameters of this model (and similar Electre Tri -like sorting procedures) may be both directly and indirectly elicited. However, in order to overcome the difficulties of eliciting these parameters directly from the decisionmaker, several works have focused on the indirect approach. Mousseau and S lowiński [START_REF] Mousseau | Inferring an ELECTRE TRI model from assignment examples[END_REF] have proposed to find the entire model through the use of assignment examples. Mousseau et al. [START_REF] Mousseau | Using assignment examples to infer weights for ELECTRE TRI method: Some experimental results[END_REF] only sought to find the criteria importance weights with the other parameters being supposedly known, while Ngo The and Mousseau [START_REF] Ngo The | Using assignment examples to infer category limits for the ELECTRE TRI method[END_REF] only looked for the category limits. Other more robust approaches compute for each alternative a range of possible categories to which they may be assigned when the parameters of the model are not completely determined [9; 10; 12]. Approaches that deal with inconsistent sets of assignment examples leading to non existing preference model solutions have also been explored in [27; 26].

In most cases, the approaches of inferring the parameters of majority-rule sorting models use mathematical programming techniques involving binary variables, such as in Leroy et al. [START_REF] Leroy | Learning the parameters of a multiple criteria sorting method[END_REF]. As these approaches find the optimal solution, they may also require large amounts of computational resources and time, making their use limited when large sets of assignment examples are considered. Sobrie et al. [START_REF] Sobrie | Learning a majority rule model from large sets of assignment examples[END_REF] have suggested to use a technique based on a metaheuristic to learn the parameters of the sorting model, which has been adapted and extended by Olteanu and Meyer [START_REF] Olteanu | Inferring the parameters of a majority rule sorting model with vetoes on large datasets[END_REF] in order to additionally take into account veto thresholds. More recently, population-based metaheuristics have also been proposed in order to learn MR-Sort models with coalitional veto [START_REF] Sobrie | A population-based algorithm for learning a majority rule sorting model with coalitional veto[END_REF].

In most cases, the assignments take the form of a single category in which the DM places each alternative. An approach that extends these assignments to include multiple categories, in order to account for the possible hesitation of the DM, has been explored by Dias and Mousseau [START_REF] Dias | IRIS: A DSS for multiple criteria sorting problems[END_REF].

Imprecision and incompleteness

Some of the earliest detailed studies on data or information imperfection may be found in [14; 25]. Tacnet [START_REF] Tacnet | Prise en compte de l'incertitude dans l'expertise des risques naturels en montagne par analyse multicritères et fusion d'information[END_REF] borrows from these sources and proposes a taxonomy of data or information imperfection. Based on the literature, he considers that this imperfection can take four main forms : inconsistency, imprecision, incompleteness and uncertainty. Inconsistency is a type of imperfection which originates in conflicting information, and usually produces incoherent conclusions. Imprecision is related to information which is not sufficient for an agent (in this context a decision maker or a model of his/her preferences) to answer the question at hand. Either the numerical values are poorly known due to a flaw in the observation, or because natural language is used to vaguely describe the problem. Incompleteness corresponds to an absence of information on the underlying problem. Uncertainty is related to the knowledge that the agent has about an information, and more specifically it's validity or truth.

In most of the scientific disciplines, incompleteness or imprecision on the data occur very regularly. Very often, they are approached in a very simple and convenient way, by, e.g., excluding incomplete cases or replacing (imputing) missing values with the mean. Similarly, imprecision is also handled simply by considering that an imprecise evaluation can be represented by an average or median value of the possible evaluations.

More evolved techniques however exist, and they can be found in seminal books on incomplete (or missing) data analyses, as, e.g., [22; 39] : maximum likelihood estimation and multiple imputation. Regarding imprecision, classically such information is expressed as either a set of possible values, an interval of values, or as fuzzy numbers in case of a linguistic variable [START_REF] Tacnet | Prise en compte de l'incertitude dans l'expertise des risques naturels en montagne par analyse multicritères et fusion d'information[END_REF].

In MCDA, Roy [START_REF] Roy | Main sources of inaccurate determination, uncertainty and imprecision in decision models[END_REF] analyzes the main sources of difficulties linked to imprecision and uncertainty. In summary, these various types of imperfection can either be found in the performances of the alternatives on the criteria, in the values of the preferential parameters (weights of the criteria, discrimination thresholds, utility functions, . . .), or in the recommendation that is proposed to the decision maker. As stated in [START_REF] Roy | Paradigms and challenges[END_REF], many approaches have been proposed to tackle imperfection issues in MCDA. Without being exhaustive, they make use of probability theory as in Multi-Attribute Utility Theory (see, e.g., [START_REF] Dyer | MAUT multiattribute utility theory[END_REF] for a detailed overview), possibility theory [START_REF] Dubois | Théorie des possibilités: application à la représentation des connaissances en informatique[END_REF], multi-valued logic, discrimination thresholds mainly used in outranking methods [START_REF] Figueira | ELECTRE methods[END_REF], fuzzy or valued binary relations, fuzzy numbers, or rough sets [START_REF] Greco | Decision rule approach[END_REF].

When it comes more specifically to missing (or incomplete) data in the evaluation of the alternatives, to our knowledge, this topic has only been poorly explored. Bisdorff et al. [START_REF] Bisdorff | Rubis: a bipolar-valued outranking method for the choice problem[END_REF] propose an outranking-based method which allows to take into account missing values for the choice problem. The validation of an outranking relation is extended to a three value logic by adding a second majority threshold. The first threshold is used in order to validate whether an alternative outranks another, while the second threshold is used in order to invalidate this statement. If the value of the coalition of criteria that support the outranking statement falls within these two thresholds then it cannot be asserted whether the first alternative outranks the second one (indetermination). These two majority thresholds are constrained so that they are symmetrical with respect to the 50% support level. Greco et al. [START_REF] Greco | Dealing with missing data in rough set analysis of multi-attribute and multi-criteria decision problems[END_REF] deal with the same issue, using however a rough sets-based approach for the sorting problem. In both cases, no assumption is made on the values of the missing data. Brans and Mareschal [START_REF] Brans | PROMETHEE methods[END_REF] handle the missing data issue by considering that in the pairwise comparison, in case of a missing value on a criterion, both alternatives have equal evaluations on that criterion. Corrente et al. [START_REF] Corrente | Handling imprecise evaluations in multiple criteria decision aiding and robust ordinal regression by n-point intervals[END_REF] handle imprecise evaluations using n-point intervals consisting of nested interval evaluations and their associated increasing levels of plausibility. Finally, dominance-based rough set approaches [START_REF] Stefanowski | Incomplete information tables and rough classification[END_REF] have also recently explored the topic of handling incomplete information in classification.

In this article we wish to tackle more specifically the problem of imprecise performances of alternatives on the criteria, represented by interval evaluations, as well as missing performances. This latter case can in this framework be seen as a special case of interval evaluations, where the lower and upper bounds of the intervals correspond to the lowest and highest possible values of the evaluation scale of the considered criterion.

Handling imprecise or missing evaluations

The proposed MR-Sort extension

In order to express the imprecision of the evaluations of the alternatives, we propose to define two new performance functions for each criterion : g min j , g max j : A → R. These functions correspond to the minimum, respectively maximum evaluations that an alternative may take on criterion j. This leads to the definition of two versions of alternative a: an optimistic version evaluated using g min and an optimistic version evaluated using g max .

The initially defined g j functions are still used to give the evaluations of the category limits, as we do not introduce any imprecision in their evaluations.

Like in the case of the MR-Sort method, we will be using outranking relations in order to assess whether an alternative is at least as good as a category separating profile b h-1 . However, as we are now considering two versions of the same alternative, i.e. a pessimistic version evaluated using g min and an optimistic version evaluated using g max , we also define two corresponding outranking relations. These relations may ultimately be identical, however they may also differ in order to illustrate the potential change in the perspective of the DM when considering the worst and best possible versions of the decision alternative.

We define the pessimistic and optimistic local concordance indexes between an alternative a and a category profile b h , ∀h ∈ {1, . . . , k} on any criterion j ∈ J, as:

C pes j (a, b h ) = 1 , if g min j (a) ≥ g j (b h ), 0 , otherwise.
(5)

C opt j (a, b h ) = 1 , if g max j (a) ≥ g j (b h ), 0 , otherwise. (6)
We define the overall support of a outranking a category profile b h in the pessimistic and optimistic cases respectively as:

C pes (a, b h ) = j∈J w j C pes j (a, b h ) (7) C opt (a, b h ) = j∈J w j C opt j (a, b h ) (8)
We say that a outranks the category profile b h in the pessimistic case, i.e. a S pes b h , when C pes (a, b h ) λ pes . We also say that a outranks the category profile b h in the optimistic case, i.e. a S opt b h , when

C opt (a, b h ) λ opt .
The λ pes and λ opt thresholds are used to determine when a coalition of criteria is sufficient in order to validate their corresponding outranking relation. We relax the constraint that λ 0.5, which usually accompanies MR-Sort, making λ pes , λ opt ∈]0, 1]. In this way, the two relations are now governed by a generalized qualified weak majority rule (a term proposed in [START_REF] Marchant | An axiomatic characterization of different majority concepts[END_REF]).

The assignment rule that we propose computes a lower bound and an upper bound for the assignment of a using its pessimistic and its optimistic versions respectively.:

• the lower bound c h pes corresponds to the highest category whose lower profile is outranked by a in the pessimistic case;

• the upper bound c h opt corresponds to the lowest category whose upper profile is not outranked by a in the optimistic case.

Additional considerations

Based on the definition of a pessimistic and optimistic versions of an alternative containing imprecise evaluations, as well as two associated outranking relations, we find the following potential situations when comparing it to a precisely defined category profile:

• a S pes b h and a S opt b h
In this situation a is considered to be globally at least as good as b h , despite any imprecise evaluations it may have. In this case a can be assigned only to category c h+1 or above.

• a S pes b h and a S opt b h In this case a is globally not at least as good as b h , despite any imprecise evaluations it may have. In this case a can be assigned only to category c h or below.

• (a S pes b h and a S opt b h ) or (a S pes b h and a S opt b h ) This situation corresponds to a state of indetermination, since one version of a (pessimistic or optimistic) is not considered at least as good as b h while at the same time the other version (optimistic or pessimistic) is. In this case a can be assigned to both categories c h and c h+1 , as well as to any other categories above or below them based on how a compares to the other profiles.

In order to better illustrate the range of problems that our proposed extension is able to model, we present the following scenarios as described through the choice of the λ pes and λ opt thresholds:

• 0.5 λ opt = λ pes :
This scenario is identical to the classical MR-Sort method when alternatives do not have imprecise evaluations. Multi-category assignments only occur when imprecision in alternatives' evaluations is considered;

• λ opt < 0.5 λ pes : A strong coalition of criteria is needed for validating the pessimistic outranking relation while a weak one is needed to validate the optimistic outranking relation, leading to potentially many situations of indetermination (a particular case where λ opt > 0.5 and λ pes = 1 -λ opt is very similar to the β-cut polarization described by Bisdorff in [START_REF] Bisdorff | Logical foundation of fuzzy preferential systems with application to the electre decision aid methods[END_REF]);

• λ pes λ opt :

The DM is imprecision averse and requires a higher level of support for validating the outranking relations of the optimistic version of an alternative as opposed to its pessimistic version. It is possible, in this case, to have an alternative outrank in the pessimistic case a category profile, while at the same time not outrank in the optimistic case the same profile;

• λ opt < λ pes :
The DM is less imprecision averse and accepts a lower level of support for validating the outranking relations of the optimistic version of an alternative as opposed to its pessimistic version. The range between λ opt and λ pes may be seen as levels of support for which the DM is hesitant to either validate or invalidate an assignment;

It is also worth noting that missing evaluations may be easily handled as they are a special case of handling imprecise evaluations. A missing evaluation of a on criterion j may be summarized by g pes j (a) taking the smallest possible value on the scale of criterion j and g opt j (a) taking the highest possible value on the scale of criterion j.

Illustrative example

We illustrate the proposed MR-Sort extension when considering precisely defined alternatives as well as several containing imprecision in their evaluations, as depicted in Table 2.

λ opt = λ pes = 3 5 w = ( 1 5 , 1 5 , 1 5 , 1 5 , 1 5 ) b1 = (1, 1, 1, 1, 1) b2 = (2, 2, 2, 2, 2) ai S pes b h ai S opt b h A g1 g2 g3 g4 g5 h 0 1 2 3 0 1 2 3 h pes h opt a1 2 2 2 0 0 3 3 a2 2 2 1 0 0 2 2 a3 2 2 0 0 0 1 1 a4 2 2 [0, 1] 0 0 1 2 a5 2 2 ? 0 0 1 3 a6 2 2 2 0 ? 3 3
This example is similar to the example from Table 1, depicting a model with 5 equally weighted criteria and three categories defined using the category limits b 1 and b 2 . The evaluations on each criterion can vary between 0 and 2, while the majority thresholds of the pessimistic and optimistic outranking relations are equal to 3 5 . This model is identical to the MR-Sort model from the previous example, as seen through the first three alternatives, which are classified in the same way. We have indicated here the indexes of the lower and upper bound category assignments through h pes and h opt . This extended MR-Sort model, however, is also able to properly handle imprecise or missing evaluations, as seen through the following three alternatives.

Alternative a 4 is identical to the first three alternatives with the exception that its evaluation on the third criterion is not precisely defined, potentially falling anywhere between 0 and 1. As in the pessimistic scenario a 4 could be identical to a 3 , while in the optimistic scenario it could be identical to a 2 , it appears natural that this alternative should be classified in either c 1 or c 2 . The illustrated model achieves this exact result. The following alternative adds even more imprecision to its evaluation on the third criterion. As this evaluation may fall anywhere within our evaluation scale from 0 to 2, the pessimistic version of this alternative does not outrank any of the category profiles (except the fictitious bottom profile), while its pessimistic version outranks all of them (except the fictitious top profile). Hence, this alternative may be assigned to any of the three categories. Finally, alternative a 6 is similar to alternative a 1 , except that the value for g 5 is missing. Still, this last example illustrates that even when imprecision within an alternative's evaluations is present, it's precise evaluations may still be sufficient in order to allow its assignment to a single category.

Inferring the parameters of the sorting model

In order to use the model presented in Section 3, the preferences of the DM need to be elicited. In particular, the criteria importance parameters, the majority thresholds, and the profiles separating the categories on each criterion have to be determined. These parameters can either be obtained directly from the DM (which in most practical situations is not realistic), or learned from assignment examples provided by the DM for each of the categories. When assignment examples are employed, algorithms are used to find a set of parameters such that the classification accuracy over the set of assignment examples is maximized.

The fitness measure

We denote a classical MR-Sort model instance, represented by its parameters, with Ω = λ, w = (w j , j ∈ J), B . Let a ∈ A be an alternative which is used by the DM as an assignment example. Let assig Ω (a) be the category to which a is assigned by Ω and assig DM (a) the category to which the DM assigns it.

We remind below the definition of the classification accuracy:

CA = 1 |A| a∈A CA(a), CA(a) = 1 , if assig Ω (a) = assig DM (a) 0 , if assig Ω (a) = assig DM (a). (9)
The MR-Sort model for handling missing and imprecise evaluations allows the assignment of alternatives to more than one category. Furthermore, in the preference elicitation process, the DM may also wish to assign examples to more than one category, especially when the alternative contains missing evaluations. Therefore the classification accuracy, which simply gives the percentage of alternatives in the assignment examples which were correctly assigned to the single category expressed by the DM needs to be extended to this case.

Let Ω * = λ pes , λ opt , w = (w j , j ∈ J), B be an extended MR-Sort model. We expand the definition of assig Ω * (a) and assig DM (a) to sets of categories to which the DM, respectively the MR-Sort model, assigns an alternative a.

The classification accuracy defined in Equation ( 9) could still be used in this context if we replaced the equality and inequality operations with set operations. Nevertheless, this may be seen as too strict, as only missing one category from a multi-category assignment would immediately lower this measure to 0. We may therefore consider the following modification to this measure:

CA = 1 |A| a∈A CA (a), CA (a) = 1 , if assig Ω * (a) ∩ assig DM (a) = ∅ 0 , if assig Ω * (a) ∩ assig DM (a) = ∅. (10
) This measure, on the other hand, may be considered not strict enough, as even a slight overlap in the two sets of assignments will maximize it.

We present below several properties that we consider our fitness measure should hold, so that it can effectively discriminate between a multi-category assignment of an alternative by the DM and the multi-category assignment provided by an inferred model.

Property 1 (Maximality). The fitness measure for an alternative a reaches its maximum value only when two corresponding sets of category assignments are identical, i.e. assig Ω * (a) = assig DM (a). than the fitness of a is strictly lower than that of b, while if c l ∈ assig DM (a) than the fitness of a is strictly higher than that of b.

In order to illustrate how different fitness measures satisfy these properties, we refer to Table 3.

The measure from Equation (9) satisfies Property 1 since it is equal to 1 only when the assignment of the model is identical to that of the DM (examples 1 and 3 from Table 3). However it does not satisfy Property 2, as it is 0 for overlapping assignments (examples 5 to 10). The measure from Equation [START_REF] Dias | ELECTRE TRI for groups with imprecise information on parameter values[END_REF] satisfies Property 2 since it is 0 only when the two assignments are completely disjoint (examples 2 and 4). It does not, however, satisfy Property 1 as it is 1 for partially overlapping assignments (examples 5 to 10). Both these measures do not satisfy Property 3 (examples 5 to 7), nor Property 4 (examples 6, 8 and 9).

In order to construct a measure satisfying all four properties, we borrow several concepts from statistical analysis, such as precision and recall [START_REF] Kent | Machine literature searching viii. operational criteria for designing information retrieval systems[END_REF], and adapt them to our problem:

P r(a) = |assig Ω * (a) ∩ assig DM (a)| |assig Ω * (a)| , Re(a) = |assig Ω * (a) ∩ assig DM (a)| |assig DM (a)| (11)
In this case, Precision corresponds to the percentage of correctly identified categories among all assignments proposed by Ω * , while Recall corresponds to the percentage of correctly identified categories among all assignments proposed by the DM. Recall satisfies Property 2 (examples 2 and 4), while it also satisfies Prop-erty 4. The latter is due to the fact that adding (removing) a category c l to assig DM (a) has an effect of raising (lowering) Recall when c l ∈ assig Ω * (a) as seen in examples 6 and 8 while when c l ∈ assig Ω * (a) the effect on Recall is reversed as seen in examples 6 and 9. However, Property 1 is not satisfied since the measure is 1 also for partially overlapping assignments (example 9), and neither is Property 3 as seen through examples 5 and 7 (adding or removing a category in the model assignment which does not correspond to the DM assignment has no effect on the performance metric).

In order to overcome these issues, we propose to use the F-measure, which combines both precision and recall as follows:

F β = 1 |A| a∈A F β (a), F β (a) = (1 + β 2 ) P r(a) • Re(a) β 2 • P r(a) + Re(a) , β > 0 ( 12
)
The special case in which β = 1 corresponds to the harmonic average between Precision and Recall. The F 1 score is illustrated together with all the other presented measures in Table 3.

F 1 = 2 |assig Ω * ∩ assig DM | |assig Ω * | + |assig DM | (13)
We observe from these examples that the F 1 measure satisfies all four properties. Property 1 is satisfied since the measure is maximal only when assig DM = assig Ω * (examples 1 and 3). Property 2 is satisfied due to the measure being minimal only when assig DM ∩ assig Ω * = ∅ (examples 2 and 4). Property 3 is satisfied since, for the same DM assignment, F 1 increases (decreases) with the inclusion (exclusion) of categories in the model assignment which also belong to assig DM (examples 5 and 6), while the effect is reversed for categories not belonging to assig DM (examples 6 and 7). Finally, Property 4 is satisfied since, for the same model assignment, F 1 increases (decreases) with the inclusion (exclusion) of categories to the DM assignment which also belong to assig Ω * (examples 6 and 8), while the effect is reversed for categories not belonging to assig Ω * (examples 6 and 9).

The β parameter may be used in order to place more emphasis on finding more of the correct assignments while allowing at the same time more incorrect assignments (β > 1), or proposing fewer incorrect assignments while at the same time also fewer correct ones (β < 1).

We also wish to note that the proposed fitness measure becomes identical to the classification accuracy when both the assignments of the DM and those of the inferred model become single-category.

The inference approach

Due to the F β measure containing fractions in its definition, mathematical programs containing linear constraints may not be employed in order to solve the problem of maximizing it over a set of assignment examples. As such programs may not scale well with the size of the set of assignment examples, we propose to extend the mixed linear program and metaheuristic approach proposed in [START_REF] Olteanu | Inferring the parameters of a majority rule sorting model with vetoes on large datasets[END_REF]. The main structure of the algorithm is presented in Algorithm 1.

Algorithm 1 Proposed approach. Input: Initial temperature T 0 and temperature decrease dT . The algorithm starts by initializing the model parameters followed by several iterations composed of a linear program and a metaheuristic. The fitness corresponds to the average F β measure across all provided assignment examples.

The initialization step

The initialization step fixes the majority thresholds to 0.5 and sets the weights for all criteria to be equal, which is a standard practice when no additional preferential information is considered. The category profiles are constructed using a greedy heuristic which considers each criterion independently from the rest and places the value of a profile b h so that it separates as much as possible the values of the alternatives that are classified in categories above the profile and the values of the alternatives that are classified in categories below:

g j (b h ) = arg max R a∈A h init (a, h), ∀j ∈ J, ∀h ∈ {1, . . . , k -1} ,where (14)
h init (a, h) =      1 , if ∀l ∈ assig DM (a), l > h and g min j (a) g j (b h ) or ∀l ∈ assig DM (a), l h and g max j (a) < g j (b h ) 0 , otherwise. (15)

The linear programming step

By fixing the category profiles, a linear program may be employed in order to find the optimal values of the majority thresholds and the criteria weights, for the given category profiles. The program is presented in Fig. 1.

Since we try to fix the lower and upper limits of the category assignments of each alternative a, we only require to impose constraints on the relations between a and profiles b min Parameters:

A, A , A , J C pes j (a, b h min -1 ), C opt j (a, b h min -1 ), C pes j (a, b h max ), C opt j (a, b h max ) ∀a ∈ A, ∀j ∈ J C pes j (a, b h min ), C opt j (a, b h min ∀a ∈ A , ∀j ∈ J C pes j (a, b h max -1 ), C opt j (a, b h max -1 ) ∀a ∈ A , ∀j ∈ J γ ∈ [0, 1] Variables: λ pes , λ opt ∈]0, 1] w j ∈ [0, 1] ∀j ∈ J x(a), y(a) ∈ [0, 1] ∀a ∈ A z(a), z 1 (a), z 2 (a) ∈ [0, 1] ∀a ∈ A t(a), t 1 (a), t 2 (a) ∈ [0, 1] ∀a ∈ A Objective: min a∈A x(a) + y(a) + a∈A z(a) + a∈A t(a)
Constraints:

s.t. j∈J w j = 1 j∈J w j • C pes j (a, b h min -1 ) +(1 -x(a)) λ pes ∀a ∈ A j∈J w j • C opt j (a, b h min -1 ) +(1 -x(a)) λ opt ∀a ∈ A j∈J w j • C pes j (a, b h max ) -(1 -y(a)) λ pes -γ ∀a ∈ A j∈J w j • C opt j (a, b h max ) -(1 -y(a)) λ opt -γ ∀a ∈ A j∈J w j • C pes j (a, b h min ) +(1 -z 1 (a)) λ pes ∀a ∈ A j∈J w j • C opt j (a, b h min ) -(1 -z 1 (a)) λ opt -γ ∀a ∈ A j∈J w j • C opt j (a, b h min ) +(1 -z 2 (a)) λ opt ∀a ∈ A j∈J w j • C pes j (a, b h min ) -(1 -z 2 (a)) λ pes -γ ∀a ∈ A z(a) z 1 (a) ∀a ∈ A z(a) z 2 (a) ∀a ∈ A z(a) z 1 (a) + z 2 (a) ∀a ∈ A j∈J w j • C pes j (a, b h max -1 ) +(1 -t 1 (a)) λ pes ∀a ∈ A j∈J w j • C opt j (a, b h max -1 ) -(1 -t 1 (a)) λ opt -γ ∀a ∈ A j∈J w j • C opt j (a, b h max -1 ) +(1 -t 2 (a)) λ opt ∀a ∈ A j∈J w j • C pes j (a, b h max -1 ) -(1 -t 2 (a)) λ pes -γ ∀a ∈ A t(a) t 1 (a) ∀a ∈ A t(a) t 2 (a) ∀a ∈ A t(a) t 1 (a) + t 2 (a) ∀a ∈ A C opt j (a, b h min -1 ), C pes j (a, b h min ), C opt j (a, b h min ), C pes j (a, b h max -1 ), C opt j (a, b h max -1
), C pes j (a, b h max ) and C opt j (a, b h max ) are 0-1 flags corresponding to the result of the pair-wise comparison between the pessimistic and optimistic versions of an alternative and the profiles of it's lower and upper-bound category assignments. We have one flag per criterion, with 0 meaning that the alternative is strictly worse than the profile on that criterion, and 1 meaning that it is at least as good as the profile. These flags can be computed before executing the linear program since both the alternatives and the category profiles evaluations are fixed at this stage.

The linear program seeks to enforce that c h min is the lowest category in which a is assigned (by making a outrank profile b h min -1 in both optimistic and pessimistic cases and not outrank b h min either in the optimistic or the pessimistic case) and that c h max is the highest one (by making a not outrank profile b h max in both optimistic and pessimistic cases and outrank profile b h max -1 either in the optimistic or the pessimistic case). The x and y variables are used to ensure the limits with respect to the lower profile of the bottom category and respectively the upper profile of the top category. These variables will be 1 when their corresponding constraint is fulfilled and between 0 and 1 otherwise. Variables z 1 and z 2 are used to determine whether an alternative outranks the upper profile of its bottom category in the pessimistic case and at the same time does not outrank it in the optimistic case, or vice-versa. The z variable computes the logical OR operation between these statements. Variables t 1 , t 2 and t do exactly the same for the lower profile of the top category.

Notice that some variables and constraints are limited to sets A, A and A . Set A contains all of the alternatives, set A contains those that have been assigned to more than one category while A contains alternatives assigned to more than two categories. This is done in order to properly apply the constraints corresponding to intermediate category profiles.

The metaheuristic step

This step of the approach is used to find the category profiles while the majority thresholds and the criteria weights are fixed. The algorithm corresponds to a slight adaptation of the simulated annealing algorithm [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF], as seen in Algorithm 2.

The metaheuristic performs changes to the category profiles across several iterations. Each iteration is linked to a temperature parameter which decreases over time. In the beginning, at high temperatures, the algorithm may perform more frequently changes to the profiles which would lead to a decrease of the model fitness, while towards the end, as the temperature decreases, such changes get less frequent. Every iteration gives the opportunity for each profile to have each of its values on the set of criteria changed. The heuristic function is used to determine the amount of increase or decrease in the fitness of the model given a new value on a criterion for a category profile. This function would normally be computed as the difference between the F-measures of each of the two models, however, we propose a simplification. Having already computed the initial cat-Algorithm 2 Simulated annealing. Input: Initial model parameters λ pes , λ opt , w, b and T 0 , dT and α.

1: T = T 0 ; 2: while T > 0 do

3:
for all j ∈ J do

4:

for all h ∈ {1, . . . , k -1} do 5:

pick α random values X in the interval [g j (b h-1 ), g j (b h+1 )]

6:

x = arg max x∈X (Heuristic(x))

7:

if Heuristic(x) > 0 or random < e -1 T then 8:

g j (b h ) = x 9: T = T -dT ; Output: b.
egory assignments of all alternatives a ∈ A as assig Ω * (a) = {c h min , . . . , c h max }, we infer the new sets of assignments {c h min , . . . , c h max } as follows:

h min =                h+1, if g j (b h ) > g max j (a) x and C pes (a, b h ) λ pes and C opt (a, b h ) < λ opt C opt (a, b h )+w j or g j (b h ) > g min j (a) x and C opt (a, b h ) λ opt and C pes (a, b h ) < λ pes C pes (a, b h )+w j ; h , if x > g max j (a) g j (b h ) and C pes (a, b h ) λ pes and C opt (a, b h )-w j < λ opt C opt (a, b h ) or x > g min j (a) g j (b h ) and C opt (a, b h ) λ opt and C pes (a, b h )-w j < λ pes C pes (a, b h ) ; h min , otherwise. (16)
h max =          h+1 , if g j (b h ) > g max
The first line of the first term in Equation ( 16) considers the case where a decrease in the evaluation of b h on criterion j, from g j (b h ) to x, leads to a change in the optimistic outranking relation between a and b h from false to true. If at the same time the pessimistic outranking relation is also true, then a becomes at least as good as profile b h both pessimistically and optimistically, therefore category c h+1 becomes the lowest category to which a is assigned. The second line of the first term considers the opposite case, where the change in evaluation of the profile leads to a outranking the profile in the pessimistic case when originally it was not, while also outranking the profile in the optimistic case.

The second term from Equation ( 16) considers the case where an increase in the evaluation of b h on criterion j invalidates either the optimistic or the pessimistic outranking relation between a and the profile, when previously both the optimistic and pessimistic relations were in effect. This means that while profile b h was initially bounding a from below, it no longer does so, and therefore the lower limit of categories to which a is assigned becomes category c h . In all other cases, the index of the lowest category to which a is assigned does not change from the previous value of h min .

Equation [START_REF] Greco | Dealing with missing data in rough set analysis of multi-attribute and multi-criteria decision problems[END_REF] illustrates similar situations where a change in the evaluation of b h on one criterion leads to a change in the upper limit of the categories to which a is assigned by the model.

Computing the difference between the fitness of the original extended MR-Sort model and the new one using the previously computed ranges of categories to which all alternatives in A are assigned, gives us the value of the heuristic function used in Algorithm 2. When this value is positive, changing the evaluation of profile b h on criterion j improves the fitness of the model, therefore the metaheuristic would more likely choose to perform this operation. Conversely, when the heuristic function is negative, the fitness of the model would decrease as a result of this operation, therefore the metaheuristic would less likely choose to perform this operation.

In the description of the heuristic we have made abstraction of the bottom (resp. top) categories which do not have a lower (resp. top) profile.

Finally, we have included an adaptive parameter dT , which increases or decreases based on each iteration improving or not the overall fitness of the best found model. The increase and decrease ratios are extracted empirically, as well as the initial temperature parameter.

Empirical validation

In order for the extended MR-Sort model and the proposed inference approach to be successfully used in practice, we address the following issues:

• The effect of adding missing evaluations on the range of categories to which alternatives are assigned;

• The capacity of the proposed inference approach to restore the provided assignment examples;

• The relation between the original model and the inferred one;

• The relation between problem size and required computational resources.

We will consider the most extreme case of imprecision with respect to the evaluations of the alternatives, the case of missing evaluations.

Design of the experiments

In order to address the previously listed issues, the experimental design presented in Fig. 2 was set up.

We begin by generating an initial extended MR-Sort model, denoted with Ω o . We start by fixing the majority thresholds λ pes and λ opt , which are randomly generated within the ]0, 1[ interval. The criteria weights w j , ∀j ∈ J are randomly generated within a ]0, 1[ interval scale using the approach of [START_REF] Butler | Simulation techniques for the sensitivity analysis of multi-criteria decision models[END_REF]. In order to construct the set of category profiles, b h , ∀h ∈ {1, ..., k -1}, for each criterion we generate k -1 values within ]0, 1[ and assign them to each category profile in ascending order.

The second step consists in generating a training set of alternatives (A tr ) of size n tr , with the evaluations on each of the m criteria generated randomly. A given ratio r is used in order to randomly remove a part of these evaluations. Using the previously generated extended MR-Sort model, the assignments of the alternatives in A tr are generated.

The inferred extended MR-Sort model Ω i is constructed using the provided assignment examples by applying the proposed elicitation approach.

The following step involves the generation of a larger set of alternatives, A te , constructed in the same way as A tr and using the same ratio r of included missing evaluations. This set of alternatives is used in conjunction with both the original model and the inferred one in order to construct two sets of assignments.

Throughout the experiments, we have used the F 1 fitness measure, placing equal emphasis on the precision and recall of a given set of category assignments.

Effect of including missing evaluations

In order to test the effect of including missing data within the alternatives' evaluations, we generated 100 problem instances for each value of m = {5, 10}, with n te = 10, 000 and k = 5. For each problem instance, we removed evaluations in proportion r, with r = {0.00, 0.15, 0.30, 0.45}. In Table 4 we present the distribution of the extended MR-Sort model assignments with respect to the number of categories of these assignments and the proportion r of removed evaluations.

We observe that, for 5 criteria, when all the alternatives have precise evaluations, the generated problem instances assign around 60% of the alternatives to a single category. Nevertheless, due to allowing the majority thresholds of the pessimistic and optimistic outranking relations to differ one from another, we also find 15% of the alternatives assigned to two categories, 15% to three categories, 5% to four categories and around one percent to all five. Similar values may be found for 10 criteria, with a slight increase in the percentage of alternatives assigned to two categories. When including missing evaluations in our data, we observe that more and more alternatives are assigned to more than one category. When 15% of the evaluations within the generated problem instances are removed (illustrated by the white dots in the images from Table 4), around 10% of the alternatives that were initially assigned to a single category are now assigned to more than one. Reaching 45% missing values lowers the percentage of single category assignments to around 30%. In addition it appears that the largest shift occurs with respect to alternatives assigned to all categories, a trend which decreases in strength when more criteria are involved. Nevertheless, considering the standard deviations, the differences between problem instances with 5 or 10 criteria are not significant.

Restoring the assignment examples

We continue by exploring the capacity of the proposed inference approach to construct extended MR-Sort models that restore the assignment examples provided as input. For this, we again use m = {5, 10} and k = {5}, but also consider multiple sizes of the learning set, n tr = {100, 300, 500}. For each combination of these parameters 20 problem instances were randomly generated.

We execute the proposed approach 50 times over each problem instance. The parameters corresponding the temperature step of the simulated annealing algorithm are extracted using a prior series of executions of the algorithm, giving us an initial value for dT of 0.2, which decreases or increases by a factor of 20% following the improvement or non-improvement of the overall best solution during each iteration. We present below a summary of our findings, while a detailed presentation of the results, containing the number of iterations and time needed for 05% and 95% of the algorithm executions to reach a solution fitness of 90% and 95% respectively, may be found in the Appendix, in Tables A.5 andA. [START_REF] Brans | PROMETHEE methods[END_REF].

Throughout all of the experiments, we do not find a significant link between the number of needed iterations / execution time and the percentage of missing evaluations. This may be due to a high variability between the actual distributions of category assignments (alternatives assigned to one category, two, etc.). Nevertheless, we find that as the size of the learning set increases, fewer iterations of the algorithm are needed. We attribute this to the fact that one iteration makes use of more information as we increase the size of the assignment examples, therefore fewer iterations are needed in total. Despite this decreasing trend in the number of iterations, the execution time continues to increase with the learning set size, as each iteration needs to consider more alternatives and therefore takes longer to process.

When considering problem instances containing alternatives characterized by fewer or more criteria, we find that the number of needed iterations is inversely proportional to the size of the criteria set. This may also be due to the increased amount of information present within a set of assignment examples. Because of this, the execution time for problems with 10 criteria may be lower than for problems with 5 criteria.

Restoring the original generated model

We have also tested the ability of the proposed approach to find back the initially generated extended MR-Sort models. For every execution of the inference approach, we took the inferred preference model Ω i as well as the original model Ω o and used the test set of alternatives A te of size n te = 10, 000 in order to compute the F 1 fitness measure. This measure allows us to accurately compare the two models by measuring the differences in their assignments of the alternatives in A te . The results are presented in Fig 3.

We observe that by increasing the size of the learning set we are able to more accurately restore the original extended MR-Sort model, in some cases almost reaching the maximum accuracy. Even with 100 assignment examples, we are able to reach an overall high fitness of around 90%, while as we increase the number of criteria, we notice that the effect of increasing the number of assignment examples becomes slightly more significant. Adding missing evaluations to each dataset generally has an effect of raising the overall values of the fitness measure, which is understandable due to the fact that more and more alternatives are assigned to multiple categories, and therefore raising the probability of the final model matching some of them.

Conclusion and perspectives

The contributions of this paper consist in the proposal of a multi-criteria sorting model which can handle both imprecise and missing evaluations, an algorithmic solution for inferring its parameters from assignment examples given by a DM, as well as a detailed analysis of both of them. The imprecision in the alternatives evaluations is modeled in this case through intervals where all values within them are considered equally likely to occur if the imprecision source were to be removed. The proposed MR-Sort extension allows the alternatives to be assigned into one or several neighboring categories, both as input during a preference elicitation process as well as output of the classification. We furthermore consider more general assignment rules which may lead to alternatives being assigned into more than one category despite having precise evaluations on all criteria. Adding imprecision in the alternatives' evaluations has the effect of increasing the number of categories to which they are assigned, however there is no significant difference when considering problem instances characterized by fewer or more criteria.

The proposed algorithmic inference approach composed of two steps (a linear program and a simulated annealing algorithm) builds on previous work and is validated through experiments over a large set of generated problem instances. The approach scales particularly well when increasing the number of criteria. When increasing the number of assignment examples fewer iterations of the algorithm are needed, and the computation time does not increase drastically. The inferred models may also be seen to resemble well the original models, reaching fitness values close to 100% when 500 assignment examples are considered.

We further wish to consider the practical application of this approach to real-life scenarios, by extending this work in order to provide more readable model parameters as well as the integration of confidence degrees with respect to both the classification output and the assignments of the DM. We would also like to address the topic of integrating large performance differences inside the model, such as vetoes and dictators, which may increase its expressiveness. These issues will be explored in the future.

Appendix A. Experiments results

Property 2 (

 2 Minimality). The fitness measure for an alternative a reaches its minimum value only when two corresponding sets of category assignments are exclusive, i.e. assig Ω * (a) ∩ assig DM (a) = ∅. Property 3 (Monotonicity w.r.t. model assignments). Let a and b be two alternatives with the same DM assignments (assig DM (a) = assig DM (b)) and with assig Ω * (b) ⊂ assig Ω * (a) and c l = assig Ω * (a)\assig Ω * (b). If c l ∈ assig DM (a) than the fitness of a is strictly lower than that of b, while if c l ∈ assig DM (a) than the fitness of a is strictly higher than that of b. Property 4 (Monotonicity w.r.t. DM assignments). Let a and b be two alternatives with the same model assignments (assig Ω * (a) = assig Ω * (b)) and with assig DM (b) ⊂ assig DM (a) and c l = assig DM (a)\assig DM (b). If c l ∈ assig DM (a)

Table 3 :

 3 Illustrative example of assignment scenarios and associated fitness measures. # Assignments CA(a) CA (a) P r(a) Re(a) F1(a) Precision satisfies Property 2, as it is 0 only when the assignments are disjoint (examples 2 and 4). It also satisfies Property 3 since adding (removing) a category c l to assig Ω * (a) has an effect of raising (lowering) Precision when c l ∈ assig DM (a) as seen in examples 5 and 6, while when c l ∈ assig DM (a) the effect on Precision is reversed as seen in examples 5 and 7. However, Property 1 is not satisfied since the measure is 1 also for partially overlapping assignments (example 10), and neither is Property 4 as seen through examples 6 and 9.

1 : 8 :

 18 λ pes , λ opt , w, b = Initialize(); 2: best f = Fitness(λ, w, b, v); 3: while not StoppingCondition() do 4: /* Linear program for weights and majority threshold */ 5: λ pes , λ opt , w = LP(); if best f < Fitness(λ pes , λ opt , w , b ) then 9: best f = Fitness(λ pes , λ opt , w , b ); 10: λ pes , λ opt , w, b = λ pes , λ opt , w , b ; 11: dT = Update(); Output: λ pes , λ opt , w, b.

h - 1

 1 , b min h , b max h -1 and b max h . C pes j (a, b h min -1 ),

Figure 1 :

 1 Figure 1: Linear program for the first step.

j

  (a) x and C pes (a, b h ) < λ pes and C opt (a, b h ) < λ opt C opt (a, b h )+w j or g j (b h ) > g min j (a) x and C opt (a, b h ) < λ opt and C pes (a, b h ) < λ pes C pes (a, b h )+w j ; or x > g min j (a) g j (b h ) and C opt (a, b h ) < λ opt and C pes (a, b h )-w j < λ pes C pes (a, b h ) ; h max , otherwise.

Figure 2 :

 2 Figure 2: Design of experiments.

10 0%

 10 missing data 15% missing data 30% missing data 45% missing data

Figure 3 :

 3 Figure 3: Average F 1 measure of the inferred model (at 95% fitness) over the test set of alternatives as a factor of the size of the learning set.

Table 1 :

 1 Illustrative example for the MR-Sort assignment procedure.

Table 2 :

 2 Illustrative example for the extended MR-Sort assignment procedure.

Table 4 :

 4 Percentage of alternatives assigned to one or more classes (average result with standard deviation between parentheses).

	Missing data
			0%	15%	30%	45%
		1 categ.	63.25 (31.61) 52.85 (21.23) 42.06 (16.70) 31.07 (15.39)
		2 categ.	15.95 (12.85) 16.10 (8.52)	14.39 (5.59)	11.45 (4.24)
	m = 5	3 categ.	15.03 (14.52) 13.93 (8.91)	12.25 (4.88)	9.56 (2.69)
		4 categ.	4.90 (6.11)	7.33 (4.72)	8.08 (3.80)	7.70 (3.32)
		5 categ.	0.86 (1.45)	9.79 (7.42)	23.21 (12.08) 40.20 (14.24)
		1 categ.	60.61 (28.22) 49.85 (20.84) 38.21 (20.65) 26.27 (18.50)
		2 categ.	24.64 (15.00) 22.39 (10.98) 16.99 (8.36)	11.24 (6.72)
	m = 10	3 categ.	12.27 (12.36) 15.22 (7.59)	15.80 (6.29)	14.01 (5.47)
		4 categ.	2.39 (3.54)	6.48 (4.47)	9.86 (6.23)	10.42 (5.00)
		5 categ.	0.08 (0.12)	0.61 (4.94)	19.13 (11.03) 38.05 (16.42)

Table A .

 A 5: Minimum number of iterations and time needed to reach a given fitness value for problem instances containing 5 criteria. Table A.6: Minimum number of iterations and time needed to reach a given fitness value for problem instances containing 10 criteria.

	Learning Fitness Missing data set size	90% algorithm executions iterations time (s)	95% algorithm executions iterations time (s)
		0%	74	516.79	350	2469.11
	90%	15% 30%	2 100	11.13 536.33	21 159	122.12 789.31
		45%	26	118.77	82	372.01
	100
		0%	355	2269.65	434	2650.97
	Learning Fitness Missing data set size 15% 95% 30% 45%	90% algorithm executions iterations time (s) 54 281.93 1 3.16 81 362.06	95% algorithm executions iterations 63 365.00 2 7.57 time (s) 236 1117.31
		0%	167	563.99	246	878.56
	90% 90%	15% 0% 30% 45% 15% 30%	726 80 787 727 38 154	2028.71 1686.32 2145.02 1536.67 683.01 2564.95	833 110 1256 921 93 154	2145.43 1998.00 3246.32 1995.83 1685.28 2564.95
	100	45%	1	10.66	1	10.66
	300	0%	373	1157.42	428	1513.82
	95% 95%	15% 0% 30% 45% 15% 30%	677 117 1466 1356 154 3	1925.11 2382.42 3264.23 3070.59 2696.21 40.16	1108 117 1466 1356 154 3	3143.83 2589.20 3264.23 3070.59 2696.21 40.16
		45%	2	19.24	2	19.24
		0%	115	1189.96	150	1223.30
	90% 90%	15% 0% 30% 45% 15% 30%	321 81 112 219 53 96	2886.65 2739.81 885.79 1410.42 1647.10 2871.62	357 98 451 385 88 96	3115.58 3145.44 3554.13 2741.08 2783.04 2871.62
	300	45%	6	129.24	6	129.24
	500	0%	150	1463.26	171	1628.57
	95% 95%	15% 0% 30% 45% 15% 30%	313 24 237 509 1 96	2839.55 880.23 1639.50 3202.62 28.37 2871.62	313 88 237 509 1 96	2839.55 3025.18 1639.50 3202.62 28.37 2871.62
		45%	6	129.24	6	129.24
		0%	108	1741.22	135	2526.64
	90%	15% 30%	159 212	2502.02 2726.21	202 220	3137.77 3153.58
		45%	115	1267.79	123	1328.02
	500
		0%	126	1926.71	158	2683.49
	95%	15% 30%	214 235	3606.37 3074.14	214 235	3606.37 3074.14
		45%	216	2467.25	216	2467.25