Exploitation of a Medium-Sized Fuzzy Outranking Relation Based on Multi-objective Evolutionary Algorithms to Derive a Ranking

Juan Carlos Leyva López; Jesús Jaime Solano Noriega; Jorge Luis García Alcaraz; Diego Alonso Gastélum Chavira

doi:10.1080/18756891.2016.1204122

<Previous Article In Issue

Download article (PDF)

Next Article In Issue>

Volume 9, Issue 4, August 2016, Pages 745 - 764

Exploitation of a Medium-Sized Fuzzy Outranking Relation Based on Multi-objective Evolutionary Algorithms to Derive a Ranking

Authors

Juan Carlos Leyva López¹^{, 3}^,juan.leyva@udo.mx, Jesús Jaime Solano Noriega²^,al127821@alumnos.uacj.mx, Jorge Luis García Alcaraz²^,jorge.garcia@uacj.mx, Diego Alonso Gastélum Chavira¹^,diego.gastelum@udo.mx

¹Universidad de Occidente, Blvd. Lola Beltrán y Blvd. Rolando Arjona Culiacán, Sinaloa, México

²Universidad Autónoma de Ciudad Juárez, Ave. Del Charro 450 Norte Ciudad Juárez, Chihuahua, México

³Universidad Autónoma de Sinaloa, Ciudad Universitaria, Culiacán, Sinaloa, México

Received 22 November 2015, Accepted 11 April 2016, Available Online 1 August 2016.

DOI: 10.1080/18756891.2016.1204122 How to use a DOI?
Keywords: Multi-criteria Decision Analysis; Outranking Relations; Multi-objective Evolutionary Algorithms; Ranking Procedures
Abstract: We present a multi-objective evolutionary algorithm to exploit a medium-sized fuzzy outranking relation to derive a partial order of classes of alternatives (we call it RP²-NSGA-II). To measure the performance of RP²-NSGA-II, we present an empirical study over a set of simulated multi-criteria ranking problems. The result of this study shows that RP²-NSGA-II can effectively exploit a medium-sized fuzzy outranking relation. Finally, we present a real-case study for ranking the municipalities of the state of Guanajuato, Mexico by their levels of marginalization.
Copyright: © 2016. the authors. Co-published by Atlantis Press and Taylor & Francis
Open Access: This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

1. Introduction

The multi-criteria ranking problem arises when a finite set of alternatives A = {a₁,a₂,…,a_m} needs to be evaluated by several criteria G = {g₁,g₂,…,g_n} to derive a partial preorder on A that reflects the priority of each alternative. Multi-Criteria Decision Analysis (MCDA) is an activity with a diversity of approaches, methods and techniques, which helps Decision Makers (DMs or DM for a unique Decision Maker) to solve this type of problem¹. In the outranking approach of MCDA for the ranking problem, no prior information regarding the structure of the set of alternatives is known and the aim lies in constructing and understanding this structure. Within MCDA, the methods related to the outranking approach are attractive and suitable for ranking problems due to their simplicity². Usually, these methods are performed in two main steps. First, a pairwise comparison of the alternatives is made taking into consideration the evaluation criteria, to build one or several outranking relations. Normally, these outranking relations do not have remarkable mathematical properties such as completeness and/or transitivity. This is the reason for the second step, which addresses the intransitivities in the outranking relation to derive a ranking as close as possible to the original outranking relation.

Generally, exploiting a fuzzy outranking relation is a complex task. Several techniques to derive a ranking from a fuzzy outranking relation have been proposed in the literature of MCDA^3–10.

Although some of these methods allow for building a transitive relation in an easy, fast and intuitive way, they have two main disadvantages ^11,12:

•
Oversimplification of the information in the outranking relation; thus, they do not fully respect the preferences of the DM.
•
They lack a mechanism to detect and/or minimize the inconsistencies in the outranking relation, so do not adequately exploit the wealth of information. The most significant of the ranking methods based on choice or score functions is the pair-wise rank reversal effect ¹³.

In addition, most of these ranking approaches focus on ranking problems with small cardinality, which could be explored exhaustively by a real DM. Nevertheless, although certain approaches are able to consider larger sets of alternatives, many of them do not scale well due to complexity issues related to execution times and memory requirements. This is the case for optimization approaches (i.e., Slater-optimal ranking and ranking based on distances).

Because ranking is seen as a multicriteria decision analysis problem, it may be useful when considering larger MCDA ranking problem instances. Ranking may be used to reduce the larger preference-sets to a more manageable size by condensing and ordering the preferential information that is present in the original set of alternatives. A natural approach to extract preferential information from a medium-sized set of alternatives is to organize the set into classes that display certain properties. These properties may be derived from grouping the alternatives using preference relations. The application of a meta-heuristic approach is performed as an alternative to using traditional ranking procedures.

In the proposed ranking approach, to give meaning to a comprehensive model of preferences, the DM is mostly viewed as a mythical, inaccessible or vaguely defined person whose preferences can be used to enlighten the decision problem. The comprehensive model of preferences is only a system of preferences with which it is possible to work to bring forward elements of a response to certain questions¹⁴.

References 11 and 12 presented an approach that addresses the limitations of traditional methods by formulating the exploitation of the fuzzy outranking relation as a multi-objective combinatorial optimization problem and solving it by developing a Multi-objective Evolutionary Algorithm (MOEA). Although this approach has showed advantages over traditional ranking procedures, it was designed to address small-sized sets of alternatives to derive a total order or preorder of alternatives. References 15 and 16 presented an evolutionary approach following Refs. 11 and 12, which can handle medium-sized sets of alternatives to derive a partial order of classes of alternatives. This approach aims to find the closest anti-symmetric crisp outranking relation to the fuzzy outranking relation. Then, it applies a ranking procedure based on the repeated use of a choice function to derive a final ranking of the classes of alternatives. Although this approach showed positive results, the search space it explores is given by the set of all anti-symmetric crisp outranking relations from A. With the same purpose of exploiting a medium-sized fuzzy outranking relation to construct a recommendation for a multi-criteria ranking problem, Ref. 17 presents a MOEA based on Refs. 15 and 16 with the particular advantage that it integrates a partial preorder of alternatives into the optimization process performed by the multi-objective evolutionary algorithm. This last approach explores a search space given by the set of all partial orders of classes of alternatives from the set A.

The purpose of this paper is to detail, in a formal way, the MOEA presented in Ref. 17 and to present an empirical study to demonstrate its performance, a performance comparison with other MOEAs, and a new case study. The MOEA is a ranking procedure based on the hybridization of the reference point method with the non-dominated sorting genetic algorithm (NSGA-II); we call it RP²-NSGA-II, a MOEA procedure for grouping alternatives that are indifferent while also separating the classes that are strictly preferred to others or incomparable so that a partial order between them is found.

In RP²-NSGA-II, the reference point method is not applied in the classical way, (i.e., together with an achievement scalarising function¹⁸), but rather by establishing a biased crowding scheme. Solutions near the reference point are emphasized by the selection mechanisms. The modified crowded comparison operator prefers solutions that are closer to a specified reference point while preserving the order induced by the Pareto-dominance relation. The extent and the distribution of the solutions are maintained by an additional parameter σ. This parameter, controlling the spread range of the obtained solutions, is easy to configure.

In RP²-NSGA-II, the non-dominated sorting mechanism of NSGA-II is extended to accommodate preferences (reference point) as an additional criterion. Individuals are sorted based on this modified sorting mechanism. The preferences are incorporated a priori. With the supplied preferences, the search is gradually guided towards the region of interest of the DM.

Section 2 presents a way in which alternatives and classes of alternatives can be compared; in Sec. 3, we propose the RP²-NSGA-II procedure to exploit a fuzzy outranking relation of a medium-sized set of alternatives to derive a ranking. The empirical evaluation of RP²-NSGA-II and its comparison with other algorithms is presented in Sec. 4. Section 5 shows a real case study, and Sec. 6 presents some conclusions and discusses future research.

2. Modelling the Exploitation of a Fuzzy Outranking Relation

We present a way in which the exploitation of a fuzzy outranking relation in MCDA can be modelled. This is motivated by the definition given by Ref. 19 for the multicriteria ranking problem. We begin by defining a credibility calculus that is further used to model the indifference, preference and incomparability relations.

2.1. Credibility Calculus

The credibility calculus defined in this section is based on Refs. 20 and 21. The calculus contains two logical states: true and false. It is a Boolean calculus. Considering a set Π of propositional statements, we associate with them the credibility function η : Π → [0,1]. For example, given a proposition p ∈ Π, if η(p) = 1, then p is considered to be true, whereas if η(p) = 0, then p is considered to be false. All possible values of η between zero and one, show a lower or higher degree of credibility with respect to the truth of proposition p. To extract the Boolean statements with respect to the truth of preposition p, we attach a cutting level λ ∈ [1/ 2,1). This level is motivated by the fact that a larger value of the credibility function is required to validate the statement. Such fact, can be modeled with a crisp credibility function η^* : Π → {0,1} defined as:

(1)η*(p)={1,if η(p)>λ0,otherwise

Let ¬ ∧ and ∨ denote the logical operators negation, conjunction, and disjunction, respectively. Consider a finite set Π of ground statements, the grouping brackets, and the basic logical operators negation, conjunction and disjunction. With these elements, we may generate the set E of all well-formed finite statements as:

(2)∀ p ∈ Π: p ∈ E,

(3)∀ x, y ∈ E: ¬x|(x)|x∨y|x∧y∈E

The credibility denotation can be extended to all well-formed finite statements x, y ∈ E through:

(4),η(¬x)=1−η(x)

(5),η(x∨y)=max(η(x),η(y))

(6).η(x∧y)=min(η(x),η(y))

2.2. Modeling the Preference Relations

Consider a set A = {a₁,a₂,…,a_m} of decision alternatives and SAσ as a fuzzy outranking relation defined on A × A, which models the preferences of the DM. For each pair of alternatives (ai,aj)∈SAσ, σ(a_i,a_j) is interpreted as the credibility degree of the predicate “ a_i is at least as good as a_j ”.

Let λ ∈ [0,1] be a cutting level that is associated with SAσ, such that if σ(a_i,a_j) ≥ λ, the predicate “ a_i outranks a_j, with credibility level λ” is true a_iS_Aa_j; otherwise, it is false a_i¬S_Aa_j. Such association induces a crisp outranking relation SAλ, which can deduce the following preference relations in the sense of ²²:

•
Indifference (I_A): a_iI_Aa_j ↔ a_iS_Aa_j ∧ a_jS_Aa_i
•
Preference (PA+): aiPA+aj↔aiSAaj∧aj¬SAai
•
Preference (PA−): aiPA−aj↔ai¬SAaj∧ajSAai
•
Incomparability(R_A): a_iR_Aa_j ↔ a_i¬S_Aa_j ∧ a_j¬S_Aa_i

This 4-tuple {IA,PA+,PA−,RA} of preference relations forms a preference structure on A such that each preference relation satisfies the following properties: I_A is reflexive (a_iI_Aa_i) and symmetric (a_iI_Aa_j ⇒ a_jI_Aa_i); PA+ and PA− are asymmetric (aiPA+aj⇒aj¬PA+ai), (aiPA−aj⇒aj¬PA−ai); and R_A is irreflexive (a_i¬R_Aa_i) and symmetric (a_iR_Aa_j ⇒ a_jR_Aa_i)²².

We may apply the credibility calculus and define the credibility of the I_A, PA+, PA−, and R_A relations in a Boolean setting as:

(7)η*(aiIAaj)=min(η*(aiSAλaj),η*(ajSAλai))

(8)η*(aiPA+aj)=min(η*(aiSAλaj),η*(aj¬SAλai))

(9)η*(aiPA−aj)=min(η*(ai¬SAλaj),η*(ajSAλai))

(10).η*(aiRAaj)=min(η*(ai¬SAλaj),η*(aj¬SAλai))

Reference 23 defines the credibility degree of the indifference relation in a similar way. The relations I_A, PA+, PA−, and R_A are mutually exclusive.

2.3. Comparing Classes of Alternatives

The proposed approach of constructing the relation between two classes of alternatives is based on aggregating all the relations between the alternatives of the two classes. The preference relation that appears most frequently between the alternatives of two classes is selected as the preference relation between the two classes of alternatives. This approach has also been used in Ref. 24.

Let P_k (A) = {C₁,C₂,…,C_k} be a partition of A into k classes of alternatives. SAλ induces a preference structure (IPk(A),PPk(A)+,PPk(A)−,RPk(A)) on P_k (A) in the following way:

We define the credibility of any preferential relation OPk(A)∈{IPk(A),PPk(A)+,PPk(A)−,RPk(A)} between two classes C_r,C_q ⊆ P_k (A) as:

(11)ηPk(A)(CrOPk(A)Cq)=1|Cr||Cq|∑ai∈Cr∑aj∈CqηA*(aiOAaj)

Then, the crisp credibility degree ηPk(A)* of any preferential relation OPk(A)∈{IPk(A),PPk(A)+,PPk(A)−,RPk(A)} between two classes C_r,C_q ⊆ P_k (A) is defined as:

(12),ηPk(A)*(CrOPk(A)Cq)={1, if ηPk(A)(CrOPk(A)Cq)=max(ηPk(A)(CrP+Pk(A)Cq), ηPk(A)(CrP−Pk(A)Cq), ηPk(A)(CrRPk(A)Cq))0, otherwise

(13)∀ OPk(A) ∈{PPk(A)+,PPk(A)−,RPk(A)}

By definition of the ranking problem, the alternatives that are indifferent are grouped together, whereas those that are not indifferent are separated. By construction, the relation between any pair of classes is restricted to exclude the indifference relation I_{P_k(A)}. Then, the relation between classes can either be of a preference in one direction or the other, or of incomparability. However, finding an alternative from C_q that is strictly preferred to one from C_r may put serious doubt on the fact that C_r O_{P_k(A)} C_q. Any two classes C_r and C_q are preferentially consistent if a preference relation can be expressed between them and no alternative from C_r is in a preference relation with any alternative from C_q, which contradicts the preference relation between the two classes. The search for a partial order of classes that hold this property is a difficult task, and in the outranking approach, most of the cases are impossible. Nonetheless, it is useful to reduce the number of such contradictions between the proposed relation between classes and the individual relations between the alternatives inside them.

3. Proposed Ranking Procedure RP²-NSGA-II to Exploit a Fuzzy Outranking Relation

The aim of RP²-NSGA-II, is to find the closest partial order of classes of alternatives OPk(A)* of a given fuzzy outranking relation SAσ. The rules for reflecting the consistence between SAσ and OPk(A)* are as follows:

(i)
If a_i is indifferent to a_j in SAσ, then both alternatives should belong to the same class in OPk(A)*,
(ii)
If a_i is preferred to a_j in SAσ, then both alternatives should not belong to the same class in OPk(A)*,
(iii)
If a_i is preferred to a_j in SAσ and a_i ∈ C_r and a_j ∈ C_q, then C_r should be preferred to C_q in OPk(A)*, where C_r and C_q are classes of alternatives.

Because RP²-NSGA-II searches for a partial order of classes of alternatives close to SAσ, an individual in its population represents a partial order of classes of alternatives. To compare two individuals in the population, the algorithm should assign a better fitness value to the individual with the least number of inconsistencies, such as: a_iIa_j in SAσ, which belong to different classes in OPk(A)*; a_iP⁺a_j in SAσ, which belong to the same class in OPk(A)*. Situations like these should be penalized. RP²-NSGA-II should discriminate the “different” (not indifferent) alternatives and at the same time group “similar” (indifferent) alternatives.

Given a fuzzy outranking relation SAσ, RP²-NSGA-II must search a partial order of classes of alternatives in such a way that the classes Cr∈OPk(A)* reflect the best compromise between the conflicting objectives, “discriminate the different alternatives in terms of preferences” but at the same time “group similar alternatives in terms of preferences.” While the first objective tends to maximize the number of classes, the second attempts to minimize them. The solution can be interpreted as the best compromise between conflicting objectives.

3.1. The MOEA RP²-NSGA-II

RP²-NSGA-II seeks the closest possible partial order of classes of alternatives OPk(A)* from a given fuzzy outranking relation SAσ to generate a ranking recommendation of a medium-sized set of alternatives. It takes the basic structure from the NSGA-II²⁵ and some of its principal characteristics. The following subsections present further details of the fundamental aspects of RP²-NSGA-II.

3.1.1. Representation of a potential solution in the ranking problem

An individual p˜ (or potential solution) of the population in RP²-NSGA-II suggests a matrix representation of a crisp outranking relation SAλ (λ is a cutting level that is associated with SAσ and p˜) and can be decoded to form a partial order of classes of alternatives. The structure of p˜ is composed by m(m − 1)/2 genes p₁, p₂, …, p_m(m—1)/2, where m is the cardinality of A. The set of possible values that every single gen might have is s ∈ {0,1,2,3}, where 0 → a_iI_Aa_j, 1→aiPA+aj, 2→aiPA−aj and 3 → a_iR_Aa_j (i.e., the preference relation of an ordered pair (a_i,a_j) is described by the s value of the p_r gen) (Fig. 1a). The initial m − 1 genes depict the top row of the upper triangular matrix of SAλ; the next (m − 2) genes depict the following row and so on until the last row (Fig. 1b). The structure of the individual p˜ is completed by inferring the lower triangular matrix of SAλ from the mathematical properties that the preference relations satisfy.

3.1.1.1. Decoding process to obtain a partial order of classes of alternatives

The decoding process to obtain a partial order of classes of alternatives OPk(A)* from an individual p˜, is performed by the following steps:

Step 1. From the crisp binary relation SAλ that p˜ represents, calculate the number of alternatives that are preferred to each alternative (i.e., μ(ai)=|{(ai,aj)∈SAλ : aiP−aj}|). μ(a_i) reflects the rank of each alternative.
Step 2. Using a Bread-First Search algorithm, identify the connected components within each rank. Each connected component represents a class of alternatives (see Fig. 1c). These connected components represent the partition of classes of alternatives P_k (A) = {C₁,C₂,…,C_k}.
Step 3. From SAλ, deduce the antisymmetric crisp outranking relation SPk(A)* between the classes of alternatives as follows: For each pair of classes (C_r,C_q) ⊆ P_k (A), r = 1,2,…, k, q ≥ r compute the crisp preference relation using Eq. (12). We construct SPk(A)* in a form that fulfills the properties of reflexivity and is anti-symmetric. SPk(A)* is anti-symmetric because the indifference relation I_{P_k(A)} is reduced to an identical pair of classes.
Step 4. Let S¯Pk(A)* be the set of initial classes to be ordered. Let r = 1 be the current rank.
Step 5. Identify the classes in S¯Pk(A)* that are not preferred by anyone and assign to them the actual rank r.
Step 6. These classes, not preferred by anyone, are removed from S¯Pk(A)*.
Step 7. Current rank r is incremented by one, this is r = r + 1.
Step 8. If S¯Pk(A)*≠∅, go back to Step 5. Otherwise, the process is complete.

Once the decoding process is completed, a Hasse diagram can be drawn to represent the OPk(A)* from SPk(A)*. First, classes are drawn from top to bottom according to their ranking. Then, for each pair of classes (Cr,Cq)∈SPk(A)* a straight line is drawn connecting both classes if it is a cover relation. A class C_r covers a class C_s, if CrPPk(A)+Cs and there is not any class Cq∈SPk(A)* for which CrPPk(A)+Cq∧CqPPk(A)+Cs (see Figs. 1d and 1e).

3.1.2. Objective Functions

We now define objective functions that can be used to reflect the quality of a particular ranking result.

To compare individuals with different numbers of classes, we consider their fitness to be reflected by the degree with which each preference relation between two alternatives fits in the structure that the individual proposes. Ideally, all alternatives inside the same class are indifferent to each other, whereas those in different classes are not indifferent. If one class is preferred or incomparable to another, then all alternatives in the first class are preferred or incomparable to the alternatives of the second class. Furthermore, the degree of credibility of these relations is maximal.

3.1.2.1. Maximizing the cutting level

This approach considers the association of SAσ with a λ − cut to define a crisp outranking relation SAλ to induce a preference structure that models the DM preferences.

A high λ − cut value reflects a high credibility of SAλ but may increase the incomparability of the pairs of alternatives. A λ − cut ∈ [0.60, 0.75] is seen as satisfactory to deduce the outranking⁸.

Each individual p˜ is randomly associated with a λ − cut that is connected with the credibility level of a crisp outranking relation SAλ defined A.

We would like to find potential solutions for which the credibility level λ is near one. This indicates the solution is more trustworthy. We call this objective the maximum cutting level objective.

3.1.2.2. The min cut objective

This objective function counts the alternatives that are not indifferent to each other in each class. The aim is to minimize these inconsistencies to form solutions that maximize the indifference inside each class.

(14)fPk(A)=f(Pk(A))=∑Cr∈Pk (A)∑ai,aj∈Crη*(aiIAaj)

3.1.2.3. The minimum pair-wise preference disagreement objective

From a given pair of classes of alternatives (Cr,Cq)∈OPk(A)*, let C_rOC_q be a preference relation between two pairs of classes, where O∈{PPk(A)+,PPk(A)−,RPk(A)}. Supposing that CrPPk(A)+Cq, it is natural that, in the beginning of the procedure, the preference relation of some pair of alternatives (a_i,a_j), a_i ∈ C_r, a_j ∈ C_q will contradict the relation between the two classes (C_r,C_q), i.e., [while CrPPk(A)+Cq in OPk(A)*], [a_iI_Aa_j, or aiPA−aj, or a_iR_Aa_j in SAλ]. In these conditions, we have an inconsistency between the aggregation model of preferences SAλ and the partial order of classes OPk(A)*. The quality of the final partial order OPk(A)* should also be judged according to the number of its discrepancies and concordances with SAσ and the crisp outranking relations SAλ. We define the following objective function:

(15)gPk(A)=∑Cr,Cq∈Pk(A)∑ai∈Craj∈CqminO1≠O2(η*(CrO1Cq),η*(aiO2aj))

where O₁ ≠ O₂ means that the preference relation O₁ of C_r over C_q in OPk(A)* is different to the preference relation O₂ of a_i over a_j in SAλ.

(16)O1∈{PPk(A)+,PPk(A)−,RPk(A)},O2∈{IA,PA+,PA−,RA}

g_{P_k(A)} is a function that counts the number of the pair-wise preference disagreements. The numbers of preferences between alternatives in the crisp outranking relation SAλ that are in disagreement in the sense of the partial order of classes of alternatives OPk(A)* are quantified.

f_{P_k(A)} and g_{P_k(A)} are minimized to come closer to a preferentially consistent partial order of classes of alternatives. This may be addressed as a multiobjective optimization problem.

3.1.3. The Multi-Objective Combinatorial Optimization Problem

Based on the objective functions defined previously, the multi-objective combinatorial optimization problem is formulated as follows:

(17)Min(fPk(A)(p˜)), Min(gPk(A)(p˜)), Max(λ(p˜))Subject to:p˜∈Ωλ∈[0,1], λ≥λ0

where Ω is the set of partial orders of classes of alternatives of A, p˜ is a partial order of classes of alternatives of a given set of alternatives A and λ₀ is a minimum level of credibility.

Because there are not constraints with respect to how the alternatives have to be grouped together, which would in some way reduce the complexity of this problem, the only clear way of finding the true Pareto front, with respect to a particular fitness measure, is to consider the entire polytope of potential solutions. This means that all possible partitions P_k (A) of A need to be explored, leading to the selection of the best ones with respect to the considered fitness measures. Because the number of partitions of a set is equal to the Bell number, this approach to solving this problem is exponential in complexity.

Due to complexity issues related to the problem of ranking in MCDA, in RP²-NSGA-II, the decoding process to obtain a partial order of classes of alternatives OPk(A)* from an individual p˜ is divided into two steps: first, it partitions a medium-sized set of alternatives into k classes; and second, based solely on the initially provided information, it elicits a partial order between the determined classes of alternatives as a recommendation for ranking problems from a medium-sized set of alternatives. An improvement of the proposed approach is to integrate partitions and relations between classes into the optimization process that RP²-NSGA-II performs.

We present the remaining steps of the proposed approach below:

3.1.4. Initialization procedure

Typically, evolutionary algorithms begin with an initial population composed of N individuals. Each individual in the population represents a potential solution to a particular problem. Frequently, this population is randomly generated, which in our case does not result in favorable initial partitions because it is likely that the classes are mixed to a high degree.

The initialization procedure that this approach proposes is based on ²⁶, which uses two algorithms: Prim’s algorithm²⁷ and an extension of the K-means algorithm²⁸. This procedure obtains initial spread solutions close to the Pareto front. Solutions with high connectivity grade are generated using the Minimum Spanning Tree (MST). At most, half of the population is generated using the MST. Solutions with good performance under the compactness are generated by the extension of the K-means algorithm.

3.1.4.1. Multi-criteria distance between alternatives

The distance d(a_i,a_j) among pairs of alternatives is essential for the initialization procedure of the population. This approach maintains the MCDA distance definition of Ref. 28, which is defined as follows:

(18)d(ai,aj)=1−∑k=14|Qk(ai)∩Qk(aj)|m

In Eq. (18), Q is a 4-tuple 〈IA(ai),PA+(ai),PA−(ai),RA(ai)〉 that defines the profile for a given alternative a_i ∈ A where:

(19)IA(ai)={aj∈A|aiIAaj}=Q1(ai)

(20),PA+(ai)={aj∈A|aiPA+aj}=Q2(ai)

(21),PA−(ai)={aj∈A|ajPA−ai}=Q3(ai)

(22).RA(ai)={aj∈A|aiRAaj}=Q4(ai)

3.1.4.2. Generating solutions based on MST

To generate individuals for the initial population based on the Minimum Spanning Tree (MST), first, a dissimilarity D matrix is calculated by computing distances for ∀(a_i,a_j) ∈ A × A using Eq. (18). Once D is generated, Prim’s algorithm is used to find the MST.

The idea behind this procedure is to create a graph and detect its connected components. These connected components represent the partition P_k (A) = {C₁,C₂,…,C_k} of classes of alternatives that can be decoded to an individual genotype. Because the obtained MST corresponds to a solution with a single class, more solutions are generated by dividing the class into different numbers of classes. To do so, it is necessary to cut the links of the MST until the desired number of classes is reached. Special attention has to be paid to the selection of the link to cut. Cutting any link can produce undesirable results, i.e., could lead to the separation of “outliers” that could be part of a class²⁶. To avoid this effect, the definition of “interesting links” is used, which involves the discovery of a real class structure. For a set of data, an interesting set of classes derived from the MST can be constructed as follows:

(i)
All interesting links of MST are detected and sorted by their degree of interest in a list.
(ii)
A set of classes is built using the ordered list: ∀n ∈ {0,..,min(I,[0.5· fsize]−1)}, where fsize is the total number of initial solutions.
(iii)
A class C_n is generated by cutting the first interesting link n.

Once the partition on the set of alternatives P_k (A) is generated, Eq. (12) is used to deduce the antisymmetric crisp outranking relation SPk(A)* between the classes of alternatives. Next, the procedure continues to step 4 of the “Decoding process to obtain a partial order of classes of alternatives” (Sec. 3.1.1.1 of this document) to create a partial order of classes of alternatives OPk(A)*. Finally, OPk(A)* (phenotype) is encoded into an individual (genotype) of the initial population p˜.

3.1.4.3. Generating solutions based on the K-means algorithm

By using the Prim’s algorithm, only half of the initial population is generated. To complete this population, an extension of K-means is used. This algorithm generates classes of decision alternatives in terms of MCDA, as described in the following steps:

1.
Generate the initial partition P_k (A) = {C₁,C₂,…,C_k} of the set of alternatives A: randomly select k alternatives as the initial centroids (c₁,c₂,…,c_k) for the k classes. Then, assign each alternative a_i ∈ A to the class C_l with the nearest centroid c_l (e.g., min d(a_i,c_l)).
2.
Update the centroid for each class C_l ∈ P_k (A) through a profile Q(r_l) defined as:
(23)∀ai∈A:ai∈Qp(rl)
where
(24)p=arg maxq∈{1,2,3,4}|{aj:ai∈Qq(aj),∀aj∈Cl}|

The centroid c_l of class C_l is defined as a fictitious alternative r_l.
3.
Assign each alternative a_i ∈ A to the class C_l whose c_l centroid has the minimal distance to it d(a_i,c_l).
4.
Repeat steps 2 and 3 until the partition P_k (A) no longer changes or a certain number of iterations have been performed.

This procedure is performed to obtain different numbers of classes of alternatives k ∈ {2,..,fsize − min(I_A,[0.5· fsize]−1)}. At most, half of the population is generated by the K-means algorithm. With the resulting partition P_k (A), it is necessary to deduce the antisymmetric crisp outranking relation SPk(A)*, to create a partial order of classes of alternatives OPk(A)* and to encode it into an individual of the population, as with the solutions based on MST.

3.1.5. Crossover and Mutation Operators

The uniform crossover²⁹ is used because it is unbiased with respect to the ordering of genes and can generate any combination of alleles from the two parents in a single crossover event³⁰.

For the mutation operator, a modified version of the Uniform Mutation is employed. The Uniform Mutation operator requires a single parent and produces a single offspring. This operator randomly selects a gen p_r from the individual p˜ and randomly alters its allele value s to produce an offspring, where r ∈ {1,2,…,p_m(m—1)/2} is a random value with a uniform probability distribution. Modifying a single gene in the individual might not alter the structure of the final solution using the proposed decoding process. Therefore, a mutation probability pm (usually 1%) is used to randomly determine the number of genes to be mutated. Hence, the mutation has more chances to alter the structure of the individual.

3.1.6. Preference incorporation in NSGA II

Most approaches in the evolutionary multi-objective optimization literature concentrate mainly on adapting an evolutionary algorithm to generate an approximation of the Pareto frontier. However, this does not solve the problem. We present an idea previously introduced in the literature^31–33: incorporate into NSGA II the DM’s preferences, expressed as a set of solutions assigned to ordered categories. In RP²-NSGA-II, we modified the NSGA II to include selective pressure toward non-dominated solutions that belong to the Region of Interest (ROI).

Along with convergence to the Pareto-optimal set, it is also desired that an evolutionary algorithm maintains a good spread of solutions in the obtained set of solutions. The original NSGA II used the crowded-comparison approach, which maintains sustainable diversity in a population by controlling crowding of solutions in a deterministic and prespecified number of equal-sized cells in the search space.

To solve the multi-criteria ranking problem using NSGA II, it is not necessary to search the entire Pareto optimal set P_true or the associated Pareto front PF_true because many of the non-dominated solutions are not of interest to the DM. In RP²-NSGA-II, we use the strategy of attempting to find in each NSGA II generation the most promising and attractive solutions for the DM, which in our case are those individuals p˜(fPk(A),gPk(A)) whose f_{P_k(A)} and g_{P_k(A)} scores are close to zero and have an acceptably high value of λ. It is sufficient to seek a restricted Pareto optimal set, which for our purpose is defined as follows:

(25)Ptruerestricted{p˜∈Ptrue:‖(fPk(A)(p˜),gPk(A)(p˜))‖∞≤ε,where ε is a smallnon−negative number, λ>0.5}

Based on this strategy, the proposed method attempts to evolve a population toward the true restricted Pareto frontier (PFtruerestricted) by means of a succession of the restricted non-dominated solutions subset PFcurrentrestricted(t)={p˜1(t),p˜2(t),…,p˜n(t)}. At each generation, the method computes the non-dominated solutions for the ranking problem that is closest to the fixed aspiration level (f_{P_k (A)}, g_{P_k (A)}), with fPk(A)(p˜)=0 and gPk(A)(p˜)=0 according to the Tchebycheff metric.

The true restricted Pareto frontier (PFtruerestricted) is the Region Of Interest (ROI) of the Pareto front for the DM, i.e., the privileged zone of the Pareto frontier that best matches the DM’s preferences.

In RP²-NSGA-II, we use a modified crowded-comparison approach to identify a small, privileged subset of the Pareto front (PFtruerestricted). The new approach does not require user-defined parameters to identify the subset of the Pareto front. To describe this approach, we first define a Fixed Aspiration Point (FAP) metric and then present the FAP-comparison operator.

Fixed Aspiration Point distance: To identify the solutions surrounding the fixed aspiration level (f_{P_k (A)}, g_{P_k (A)}), with fPk(A)(p˜)=0 and gPk(A)(p˜)=0 according to the Tchebycheff metric, we calculate the center of mass of the set p˜(r)={p˜1r,p˜2r,…,p˜μ(r)r of solutions in rank r. The infinity norm of this point σr=‖p˜CM (r)‖∞ serves as the threshold value.

The Center of Mass of a group of points is defined as the weighted mean of the points’ positions. The weight applied to each point is the point’s mass. ‖•‖_∞ is the maximum holder metric. Note that p˜(1)=PFcurrentrestricted.

For each solution i in rank r, calculate the distance count d _ fal_i using the following equation:

(26)d _ fal(p˜ir)=d _ fali={‖p˜ir‖∞σr,if ‖p˜ir‖∞> σr1 , otherwise

This quantity serves to measure the proximity of solution p˜ir to the fixed aspiration level (FAL) (call this the distance to the fixed aspiration level (d _ fal_i)).

The d _ fal_i -distance computation requires sorting the population according to each objective function value in ascending order of magnitude.

After all population members in the set are assigned a distance, we compare two solutions by their extent of proximity with the fixed aspiration level. A solution with a smaller value of this distance measure is, in some sense, less crowded and closest to the fixed aspiration point. This value is what we compare in the fixed_Aspiration_Point-Comparison Operator described below.

Crowded-Fixed_Aspiration_Point (C-FAP)-Comparison Operator: The C-FAP-comparison operator (≺_n) guides the selection process at the various stages of the algorithm toward the Region of Interest of the Pareto optimal front. Assume that every individual p˜i in the population has three attributes:

1.
Non domination rank (i_rank),
2.
Crowding distance (idistancecrowding),
3.
FAP to distance (idistanceFAP).

We define a partial order ≺_n as:

p˜i<np˜j if (irank is less to jrank) or ((irank is equalto jrank) and (idistanceFAP is less to jdistanceFAP)) or ((irank isequal to jrank) and (idistanceFAP is equal to jdistanceFAP) and(idistancecrowding) is greater to (jdistancecrowding)),

where n is the number of non-domination ranks.

Between two solutions with different non-domination ranks, we prefer the solution with the lower (better) rank. Otherwise, if both solutions belong to the same front, then we prefer the solution that is closest to the FAP or is located in a less crowded region and is equal to the FAP.

The ROI of the Pareto front for the DM is reached using the FAP comparison procedure, which is used in tournament selection and during the population reduction phase.

4. Empirical Evaluation

The aim of this empirical evaluation is to analyze how the RP²-NSGA-II performs when solving ranking problems with different structures and sizes. We attempt to capture essential MOEA characteristics and analyze any interesting observations resulting from the experiment execution and result analysis. To achieve this goal, a set of simulated fuzzy outranking relations were randomly generated in such a way that for a given λ − value, there is a partial order (i.e., a reflexive, antisymmetric and transitive preference relation) of classes of alternatives without inconsistencies, that is, the objective functions f_{P_k (A)} and g_{P_k (A)} are equal to zero. Thus, RP²-NSGA-II was executed to exploit each of the generated fuzzy outranking relations and was evaluated with respect to whether it was successful in finding the best solution.

In addition, we exploited the simulated instances problems with other evolutionary approaches with the aim to have a comparison point to analyse the performance of the RP²-NSGA-II and to discuss its advantages (or disadvantages). The first approach is a ranking procedure based on the MOGA-H¹⁵; as the RP²-NSGA-II is an extended version of it, a second approach is the use of the original NSGA-II with random initialization and using the original crowded comparison operator; a third approach is the R-NSGA-II³¹, which uses one, or several, reference points to guide the search to a specific region(s) of the Pareto’s front. This allowed us to compare the quality of the solution with the RP²-NSGA-II with other approaches in the literature.

4.1. Generating the Simulated Fuzzy Outranking Relations

The construction of the set of simulated fuzzy outranking relations was performed using an instances generator developed in the C programming language. Algorithm 1 shows the general procedure to simulate each of the fuzzy outranking relations. The fuzzy outranking relations were generated based on a previously simulated ranking with different sizes and structures of a medium-sized set of alternatives with the indication that the rankings were consistent with the fuzzy outranking relation, i.e., each simulated instance of the ranking problem is a fuzzy outranking relation constructed in such a way that, for a given interval of lambda values, λ′ (λ′ = λ ± ε, λ ≥ 0.5 and 0 < ε << 1), there is a partial or complete order of classes of alternatives without inconsistencies (Appendix A presents a general outline of this algorithm.).

This evaluation was performed on a combination of different numbers of alternatives and different numbers of classes. Table 1 shows the values for the input parameters of Algorithm 1 used to generate the simulated fuzzy outranking relations for this study (F1: number of alternatives and F2: number of classes). For each combination of the two defined factors with their respective levels (4 levels in F1 and 5 levels in F2, 20 combinations in total), 100 fuzzy outranking relations were generated to obtain 2,000 in all.

Input: Number of classes of alternatives N_C and number of alternatives N_A.

Output: Fuzzy Outranking Relation SAσ.

1.
Randomly compute a partially ordered set O of size N_C × N_C (i.e., Reflexive, Transitive and Antisymmetric preference relations).
2.
Create a vector V of alternatives of size N_A and randomly assign a class to each alternative.
3.
Randomly generate a

λ − cut (0.60 ≤ λ − cut ≤ 0.75).
4.
Fill SAσ according with V and λ − cut.

Algorithm 1.

Instances generator algorithm

Factors	Levels
F1: Number of alternatives	15, 30, 45, 60
F2: Number of classes	3, 5, 7, 9, 11

Table 1.

Factors considered in the empirical study.

4.2. Response Variable

The response variable defined to analyze RP²-NSGA-II is the number of solutions that it finds per combination (F₁,F₂). Each combination (F₁,F₂) has 100 different fuzzy outranking relations. For each run i of RP²-NSGA-II on a single fuzzy outranking relation, we define an auxiliary binary variable x_i (F₁,F₂) which takes a value of one if the algorithm finds the best solution or zero otherwise. Therefore, the response variable X(F1,F2)=∑i=1100xi(F1,F2) is the sum of all the 100 auxiliary binary variables per combination (F₁, F₂).

4.3. Results

The stochastic nature of the evolutionary algorithms could lead to a good (or bad) result due to chance. To minimize this error and to obtain results with statistical significance, we exploited all 100 fuzzy outranking relations per combination (F₁,F₂) with each of the evolutionary approaches (RP²-NSGA-II, MOGA-H, NSGA-II, R-NSGA-II) ten times using the parameter values shown in Table 2.

	RP²-NSGA-II	MOGA-H
# of generations	1000
Population size	40	50
Crossover probability	0.9	1
Mutation probability	0.005
Lambda range values	[0.60, 0.85]

Note: For the R-NSGA-II, We set the reference point to (0,0) and the ε value to control the extent of the obtained solutions near the reference point to 0.0001.

Table 2.

Parameters for the MOEAs

4.3.1. RP²-NSGA-II Study

In this section, we evaluated and describe the performance of the RP²-NSGA-II on the simulated problems.

Table 3 shows some descriptive statistics for the results of the evaluation for the ten runs of each set of combinations (F₁, F₂). Figure 2 depicts boxplots for the number of solutions found in the ten repetitions for each set of combinations.

Class	Alts.	Mean	StDev	Min	Med	Max
3	15	99.9	0.3	99.0	100.0	100.0
	30	100.0	0.0	100.0	100.0	100.0
	45	100.0	0.0	100.0	100.0	100.0
	60	83.5	19.7	32.0	89.5	98.0

5	15	99.9	0.3	99.0	100.0	100.0
	30	100.0	0.0	100.0	100.0	100.0
	45	100.0	0.0	100.0	100.0	100.0
	60	73.1	24.2	23.0	81.0	97.0

7	15	100.0	0.0	100.0	100.0	100.0
	30	100.0	0.0	100.0	100.0	100.0
	45	100.0	0.0	100.0	100.0	100.0
	60	68.4	24.9	19.0	78.0	94.0

9	15	99.9	0.3	99.0	100.0	100.0
	30	100.0	0.0	100.0	100.0	100.0
	45	100.0	0.0	100.0	100.0	100.0
	60	70.3	29.0	13.0	81.0	95.0

11	15	100.0	0.0	100.0	100.0	100.0
	30	100.0	0.0	100.0	100.0	100.0
	45	100.0	0.0	100.0	100.0	100.0
	60	71.3	27.7	17.0	83.0	97.0

Table 3.

Mean, standard deviation (StDev), min value (Min), median (Med) and max value (Max) for the ten runs of the sets of combinations F₁ and F₂. Descriptive statistics for the ten runs of each number of classes (Class)-alternatives (Alts) combinations.

Figure 2 shows that RP²-NSGA-II had excellent results for all class sizes with 15, 30 and 45 alternatives. In all of these sets, RP²-NSGA-II found all of the solutions in each of the ten runs (for the sets of 15 alternatives and 3, 5 and 9 classes, we can see outliers resulting in a mean of 99.9; in one of the ten runs for these cases, RP²-NSGA-II found 99 solutions). For the case of 60 alternatives (all classes’ size), the results were not as good. For this particular case, RP²-NSGA-II shows a mean number of solutions of 83.5, 73.1, 68.4, 70.3 and 71.3 for 3, 5, 7, 9, and 11 classes, respectively.

The size of the classes does not affect the performance of RP2-NSGA-II, but the number of alternatives does to affect the performance.

To test the statistical significance of this hypothesis, we compare across the groups of classes and across the groups of alternatives using the Kruskal-Wallis H-Test with a significance level of α = 0.05. We formulate the following hypothesis for different numbers of classes:

•
H₀: The distributions of the results are equal across all groups of class size.
•
H_α: At least one of the distributions of the results differs.

The hypothesis to test for different numbers of alternatives is:

•
H₀: The distributions of the results are equal across all groups of numbers of alternatives.
•
H_α: At least one of the distributions of the results differs.

Tables 3 and 4 show the results for the Kruskal-Wallis H-Test for both comparisons.

Classes	N	Median	Av. Rank
3	40	100	102.1
5	40	100	99.5
7	40	100	100.1
9	40	100	99.2
11	40	100	101.6

Overall	200		100.5

H = 0.08 DF = 4 P = 0.999
H = 0.13 DF = 4 P = 0.998 (adjusted for ties)

Table 3.

Kruskal-Wallis Test for the number of best-known solutions found in ten runs for the sets of 3, 5, 7, 9 and 11 classes.

Alternatives	N	Median	Av. Rank
15	50	100	122.5
30	50	100	127
45	50	100	127
60	50	82	25.5

Overall	200		100.5

H = 112.14 DF = 3 P = 0.000
H = 186.00 DF = 3 P = 0.000 (adjusted for ties)

Table 4.

Kruskal-Wallis Test for the number of best-known solutions found in ten runs for the sets of 15, 30, 45 and 60 alternatives.

For the case of the groups of classes, the Kruskal-Wallis H-Test shows that there is no statistically significant difference (p-value > 0.05) in the results across different numbers of classes. This result suggests that there is sufficient evidence to conclude that the size of the classes does not affect the performance of the MOEA. For the case of the groups with different numbers of alternatives, the Kruskal-Wallis H-Test shows that there is a statistically significant difference (p-value < 0.05) in the results for at least one of the groups; thus, we reject the null hypothesis that the number of alternatives does not affect the performance of the MOEA. Figure 1 shows that the group of alternatives that differs is the one with 60 alternatives. Hence, we did not consider a post-hoc pairing analysis to determine which of the groups made the difference.

MOEAs Comparison Study

For each test problem, the four rankings derived by using the four ranking procedures were analyzed with the following method. The method (denoted as “Rate 1”, “Rate 2”, “Rate 3” and “Rate 4” in Table 5) aimed to record the number of times each of the four rankings, derived from RP²-NSGA-II, R-NSGA-II, NSGA-II and MOGA-H, respectively, were different from the reference ranking (error rate). That is, when two rankings are compared, this rate would be equal to zero if the two rankings are identical, otherwise it would be equal to one (i.e., it is binary valued). For instance, in Table 5, when the RP²-NSGA-II method is used with 60 alternatives and three classes, “Rate 1” is equal to 16.5, which means that 16.5% of the simulated problems with 60 alternatives and three classes were different from the reference ranking when using such method. The error rates obtained using the reference sets provide an estimation of the generalized performance of the methods measuring their ability to provide correct recommendations on the ranking of alternatives.

Classes	Alternatives	Rate 1	Rate 2	Rate 3	Rate 4
3	15	0.1	97.6	100	0
	30	0	94.9	100	0
	45	0	99.1	100	0
	60	16.5	100	100	0.3
5	15	0.1	100	100	2.4
	30	0	100	100	0.5
	45	0	100	100	0.5
	60	26.9	100	100	0.9
7	15	0	100	100	58
	30	0	100	100	5.2
	45	0	100	100	2.1
	60	31.6	100	100	4.4
9	15	0.1	100	100	99.7
	30	0	100	100	33.8
	45	0	100	100	8.3
	60	29.7	100	100	12
11	15	0	100	100	100
	30	0	100	100	74.1
	45	0	100	100	29.4
	60	28.7	100	100	20.5

Table 5.

Error rates for the four ranking procedures for different alternatives and classes.

The results in Table 5, show that the RP²-NSGA-II has lower error rates than the rest of the methods in all cases, except for the MOGA-H, which shows better results in the cases for 60 alternatives with any number of classes.

To test if the difference in the results for the ranking procedures is statistically significant and thus to determine if the RP²-NSGA-II ranking procedure has the best performance, a Wilcoxon signed-rank test with a significant level of α = 0.05 was used. Note that this test discarted the R-NSGA-II and NSGA-II procedures due their low performance and only focused on comparing the MOGA-H and the RP²-NSGA-II procedures, which showed positive results. In Table 5 the statistically best performer method, in each combination (F₁,F₂), is highlighted in bold face.

In general, the results of this statistical test show that RP²-NSGA-II has better performance than the MOGA-H in the majority of the reference sets. Given these results, the RP²-NSGA-II procedure can be considered the most efficient ranking method for deriving a ranking from a medium-sized valued outranking relation in cases where the assumptions for these techniques are met in the data under consideration.

In addition to this experiment, we exploited a sampling of the set of outranking relations with the distillation ranking procedure of ELECTRE III¹⁴. For the sampling, we randomly selected 9 outranking relations from each combination (F₁, F₂). In total, we had a sampling of 180 fuzzy outranking relations. For this test, from the 180 fuzzy outranking relations, the distillation ranking procedure generated only one ranking without inconsistencies, corresponding to a ranking with 3 classes, 30 alternatives and λ = 0.72.

5. Real Case Example

In this section, we present the application of RP²-NSGA-II to a real problem: ranking the municipalities of the State of Guanajuato, Mexico by their marginalization level. Marginalization is a problem that occurs in different regions of Mexico and is one of the causes of the socio-economic inequality in the country. Related social, economic and demographic indicators have forced the Mexican government to endorse the commitment to fight conditions that disadvantage certain population groups and certain regions of the country. In this example, the problem is addressed as a multi-criteria ranking problem using as evaluation criteria the socio-demographic indicators constructed by the Mexican National Population Council (CONAPO). From the ranking of the municipalities that we obtained with RP²-NSGA-II, we made a comparison with the ordered stratifications created by Ref. 34 to analyze the consistency of our results. Finally, we also obtained a set of rankings with the R-NSGA-II to make a comparative analysis with the solutions obtained with the RP²-NSGA-II.

5.1. Data Source

The data used in this study are part of the socio-demographic indicators constructed by CONAPO based on data obtained from the 2010 Census of Population and Housing for the 2010 marginalization index. The indicators from the CONAPO study (shown in Table 6) are used as evaluation criteria to model the marginalization level of the 46 municipalities of the State of Guanajuato (Table 7 lists these municipalities). Due to lack of space, the performance of the municipalities in each indicator (performance matrix) is omitted in this paper but can be found in Ref. 34.

Label	Criterion
g1	% Illiterate Population 15 years and older.
g2	% Population with incomplete elementary school education, 15 years and older
g3	% Occupants in dwellings without sanitation
g4	% Occupants in dwellings without electricity
g5	% Occupants in dwellings without running water
g6	% Overcrowded dwellings
g7	% Occupants in dwellings with only dirt floor
g8	% Population in localities with less than 5,000 inhabitants
g9	% People employed with income less than double minimum wage

Table 6.

Indicator created by CONAPO and used as evaluation criteria.

ID	Municipality	ID	Municipality
1	Abasolo	24	Pueblo Nuevo
2	Acámbaro	25	Purísima del Rincón
3	San Miguel de Allende	26	Romita
4	Apaseo el Alto	27	Salamanca
5	Apaseo el Grande	28	Salvatierra
6	Atarjea	29	San Diego de la Unión
7	Celaya	30	San Felipe
8	Manuel Doblado	31	San Francisco del Rincón
9	Comonfort	32	San José Iturbide
10	Coroneo	33	San Luis de la Paz
11	Cortazar	34	Santa Catarina
12	Cuerámaro	35	Santa Cruz de Juventino Rosas
13	Doctor Mora	36	Santiago Maravatío
14	Dolores Hidalgo	37	Silao
15	Guanajuato	38	Tarandacuao
16	Huanímaro	39	Tarimoro
17	Irapuato	40	Tierra Blanca
18	Jaral del Progreso	41	Uriangato
19	Jerécuaro	42	Valle de Santiago
20	León	43	Victoria
21	Moroleón	44	Villagrán
22	Ocampo	45	Xichú
23	Pénjamo	46	Yuriria

Table 7.

The 46 municipalities of the State of Guanajuato, México.

5.2. Computations with the ELECTRE III- RP²-NSGA-II Methodology

As a first step, the fuzzy outranking relation was computed with the performance of the municipalities in each criterion using the ELECTRE-III aggregation procedure. The weights for the criteria were taken from the CONAPO study. For the Indifferent and Preference thresholds, we made an analysis to determine their values. We did not consider a Veto threshold, and the preference direction of the criteria was to minimize. Table 8 shows the values for these parameters.

Criterion	Weight (W)	Indifference (q)	Preference (p)
g₁	0.140	2.00	4.00
g₂	0.141	4.00	7.00
g₃	0.073	2.00	4.00
g₄	0.092	0.80	2.50
g₅	0.092	2.00	4.00
g₆	0.115	4.00	7.00
g₇	0.108	2.50	5.00
g₈	0.102	10.00	20.00
g₉	0.137	7.50	12.50

Table 8.

Values for the Weights (W) and the Indifference (q) and Preference (p) Thresholds.

After the fuzzy outranking relation was computed, we proceeded to exploit it with RP²-NSGA-II to find the closest partial order of classes to this model of preferences. Due to the stochastic nature of the evolutionary algorithms, the solutions found from different runs of the algorithm can vary in quality. Therefore, with the aim to find the best possible solution(s), we performed RP²-NSGA-II ten times with a number of generations of 1,000, a population size of 40, a crossover probability of 0.9, a mutation probability of 0.005 and a lambda value ranging from 0.60 ∼ 0.69. Then, we compared all of the solutions in the restricted Pareto front found by the algorithm in each of the runs to select the one with the lowest number of inconsistencies (sum of f_{P_k (A)} and g_{P_k (A)} objective values). In Table 9, we present the top five solutions with the lowest number of inconsistencies in this comparison. We selected solution 1, which had 137 inconsistencies and 7 classes, for the corresponding analysis.

Solution	λ	f_{P_k (A)}	g_{P_k (A)}	f_{P_k (A)} + g_{P_k (A)}	#Classes
1	0.69	68	68	136	7
2	0.69	79	62	141	7
3	0.68	66	75	141	7
4	0.68	77	68	145	7
5	0.67	70	78	148	7

Table 9.

Objective values, overall inconsistencies (f_{P_k (A)} + g_{P_k (A)}), and number of classes (#Classes) of the top five solutions with the lowest numbers of inconsistencies found by RP²-NSGA-II in the ten runs.

5.3. Analysis of the Results

As a result of this analysis, the selected solution has an inconsistency rate of 13.23% with respect to the crisp outranking relation SAλ=.69, with a λ value of 0.69. To analyze the quality of the results of RP²-NSGA-II, we take as a reference point the ordered categories (stratifications) made by CONAPO (2011) for the 46 municipalities of the State of Guanajuato, México. Because CONAPO proved and validated its results, we believe this is a trustworthy comparison to determine if RP²-NSGA-II can construct a coherent ranking of the municipalities with the same data used by CONAPO.

Figure 3 shows both rankings, including the coherence between rankings. In the ranking of RP²-NSGA-II, the first class, C1, groups all the municipalities from the “Very Low” and “Low” classifications from the CONAPO ranking, except for municipalities 2 and 18. The C2 class of RP²-NSGA-II only has municipality 18, which is in the “Low” classification of the CONAPO rankings. The municipalities in classes C3, C4, C5 and C6 of RP²-NSGA-II are in concordance with the “Medium” stratification of CONAPO. The municipalities in class C7 agree with the last two stratifications of “High” and “Very High” of the CONAPO ranking.

Additionally, in this analysis, the consistency of the ranking of CONAPO was evaluated using the objective functions defined in RP²-NSGA-II, considering the same outranking relation, with a lambda cut of 0.69 to evaluate the solution of the MOEA. From this evaluation, we obtained the values of f_{P_k (A)} =240 and g_{P_k (A)} =48, representing a total of 288 inconsistencies with respect to SAλ=.69. The results of this evaluation suggest that the ranking structure of the seven classes from the RP²-NSGA-II represents a more consistent solution than the five ordered classes of the CONAPO study.

5.4. Comparison against R-NSGA-II algorithm

In this section, we illustrate the distribution of the solutions of the RP²-NSGA-II, in the objective space, for the ranking of the municipalities of the State of Guanajuato, Mexico. We also, show the distributions for the R-NSGA-II results to make a comparison of both algorithms when looking to those solutions near the ROI.

For this comparison, we exploited the valued outranking relation obtained for the municipalities of the state of Guanajuato, México, ten times with the R-NSGA-II, using the same parameters used for the RP²-NSGA-II (number of generations of 1,000, a population size of 40, a crossover probability of 0.9, a mutation probability of 0.005 and a lambda value ranging from 0.60 ∼ 0.69) and an ε value of 0.0001. Then, from the set of non dominated solutions obtained in each of the ten executions, we obtained a final set of non dominated solutions to make the comparison with the results obtained with the RP²-NSGA-II. Figure 4 shows a general view, over the three objectives functions, of the non dominated solutions found with both methods. In this figure we can observe that most of the solutions, for both methods, were found with a lambda value of 0.69. In Fig. 5, we show a projection for two objective functions (f_{P_k (A)} and g_{P_k (A)}) for the λ − value of 0.69. In this projection we can see that the set of non dominated solutions of the RP²-NSGA-II dominates the set of non dominated solutions of the R-NSGA-II; we can also observe that the non dominated set of the RP²-NSGA-II has solutions closer to the ROI than the R-NSGA-II.

Table 10 shows the ten solutions in each non dominated set (R-NSGA-II and RP²-NSGA-II) showed in Fig. 5 with the lowest distance to the ROI. This distance is the Normalized Euclidean Distance (NED) used in Ref. 31 to measure the distance of one solution to the reference point. The NED was calculated using the following equation:

(27)NED=∑i=1Mwi(fi(x)−z¯ifimax−fimin)2

where M is the number of objective functions; w_i is the relative weight of the i-th objective function; fimax and fimin are the population maximum and minimum values of the i-th objective function; and z¯i is the reference point to the ROI of the i-th objective function. We should note, that we only use the f_{P_k (A)} and g_{P_k (A)} objectives function to calculate the NED.

R-NSGA-II			RP2-NSGA-II
f_{P_k (A)}	g_{P_k (A)}	NED	f_{P_k (A)}	g_{P_k (A)}	NED
52	94	2.1785	55	78	1.0235
50	98	2.1908	57	76	1.0243
54	92	2.1936	58	75	1.0251
49	100	2.1983	60	73	1.0274
44	107	2.2067	54	80	1.0312
45	106	2.2093	53	81	1.0314
38	116	2.2460	52	82	1.0319
37	119	2.2772	50	84	1.0337
36	120	2.2792	42	91	1.0412
33	130	2.3966	49	86	1.0431

Table 10.

The ten closest solutions to the ROI in each non dominated set (R-NSGA-II and RP²-NSGA-II) showed in Fig. 5.

6. Conclusions

This paper addressed the problem of multi-criteria ranking with a medium-sized set of alternatives. We formulated this problem as a multi-objective combinatorial optimization problem and proposed the RP²-NSGA-II procedure to solve it. The main objective in this paper was to propose an improved version of the MOEA presented in Ref. 15 that is capable of directly exploring a search space of partial orders of classes of alternatives instead of a search space of anti-symmetric crisp outranking relations from a medium-sized set of alternatives.

We proposed a representation of an individual for the evolutionary algorithm that can be decoded to form a partial order of classes of alternatives and studied the proposed RP²-NSGA-II by simulating several ranking problems with different sized sets and class structures.

The proposed RP²-NSGA-II is compared with the MOGA-H, NSGA-II, and R-NSGA-II algorithms on a set of simulated medium-sized ranking problems. The experiment results demonstrate that the proposed ranking procedure achieves good performances on the simulated ranking problems, and importantly outperforms the compared algorithms on finding the reference solutions. Based on the results from the empirical evaluation, we consider that this approach can be effectively used to exploit fuzzy outranking relations, with up to 60 alternatives to derive a ranking, which is highly consistent with the DM’s model of preferences.

In addition, the real case study we presented shows that we can apply the method with good results to problems where it is desirable to rank a medium-sized set of alternatives evaluated by multiple criteria under the outranking approach.

Appendix A.

References

1.J Figueira, S Greco, and M Ehrgott, Multiple Criteria Decision Analysis: State of the Art Surveys, Springer Science & Business Media, Vol. 78, 2005. http://dx.doi.org/10.1007/b100605

2.L Del Vasto-Terrientes, A Valls, R Slowinski, and P Zielniewicz, ELECTRE-III-H: An outranking-based decision aiding method for hierarchically structured criteria, Expert Syst Appl., Vol. 42, No. 11, 2015, pp. 4910-4926. http://dx.doi.org/10.1016/j.eswa.2015.02.016

3.P Vincke, Exploitation of a crisp relation in a ranking problem, Theory Decis., Vol. 32, No. 3, 1992, pp. 221-240. http://dx.doi.org/10.1007/bf00134150

4.J Fodor and M Roubens, Fuzzy Preference Modelling and Multicriteria Decision Support, Kluwer Academic Publishers, Dordrecht, 1994. http://dx.doi.org/10.1007/978-94-017-1648-2

5.M Pirlot, A characterization of “min” as a procedure for exploiting valued preference relations and related results, J Multi-Criteria Decis Anal., Vol. 4, No. 1, 1995, pp. 37-56. http://dx.doi.org/10.1002/mcda.4020040104

6.J Fodor, S Orlovski, P Perny, and M Roubens, The Use of Fuzzy Preference Models in Multiple Criteria Choice, Ranking and Sorting, R Słwiński (editor), Fuzzy Sets in Decision Analysis, Operations Research and Statistics SE - 3, Springer, US, Vol. 1, 1998, pp. 69-101. http://dx.doi.org/10.1007/978-1-4615-5645-9_3

7.JC Leyva López and E Fernández González, A genetic algorithm for deriving final ranking from a fuzzy outranking relation, Found Comput Decis Sci., Vol. 24, 1999, pp. 33-47. http://dx.doi.org/10.1007/978-3-540-31880-4_17

8.E Fernández González and JC Leyva López, A method based on multiobjective optimization for deriving a ranking from a fuzzy preference relation, Eur J Oper Res., Vol. 154, No. 1, 2004, pp. 110-124. http://dx.doi.org/10.1016/s0377-2217(02)00705-1

9.D Bouyssou, T Marchant, M Pirlot, A Tsoukiàs, and P Vincke, Evaluation and Decision Models with Multiple Criteria: Stepping Stones for the Analyst, Springer Science & Business Media, Vol. 86, 2006. http://dx.doi.org/10.1007/978-3-662-46816-6_4

10.LC Dias and C Lamboray, Extensions of the prudence principle to exploit a valued outranking relation, Eur J Oper Res., Vol. 201, No. 3, 2010, pp. 828-837. http://dx.doi.org/10.1016/j.ejor.2009.03.026

11.JC Leyva López and MA Aguilera Contreras, A multiobjective evolutionary algorithm for deriving final ranking from a fuzzy outranking relation, CA Coello Coello, E Zitzler, and A Hernández Aguirre (editors), Evolutionary Multi-Criterion Optimization, Springer, Guanajuato, México, Vol. 3410, 2005, pp. 235-249. http://dx.doi.org/10.1007/978-3-540-31880-4_17

12.JC Leyva López and M Araoz Medina, A multi-objective extension of the net flow rule for exploiting a valued outranking relation, Int J Multicriteria Decis Mak., Vol. 3, No. 1, 2013, pp. 36-54. http://dx.doi.org/10.1504/ijmcdm.2013.052464

13.B Mareschal, Y De Smet, and P Nemery, Rank reversal in the PROMETHEE II method: some new results, IEEE, Singapore, in Proceedings of the IEEE International Industrial Engineering and Engineering Management, IEEM 2008 (2008), pp. 959-963. Vol http://dx.doi.org/10.1109/ieem.2008.4738012

14.B Roy, The outranking approach and the foundations of ELECTRE methods, Theory Decis., Vol. 31, No. 1, 1991, pp. 49-73. http://dx.doi.org/10.1007/bf00134132

15.JC Leyva López, JJ Solano Noriega, DA Gastélum Chavira, and MD Sanchez Castañeda, A multiobjective evolutionary approach to a medium-Sized multicriteria ranking problem, JC Leyva López, R Espin Andrade, R Bello Pérez, and PA Álvarez Carrillo (editors), Studies on Knowledge Discovery, Knowledge Management, and Decision Making, Atlantis Press, Mazatlan, Mexico, 2013, pp. 188-197. http://dx.doi.org/10.2991/.2013.23

16.JJ Solano Noriega, JC Leyva López, and DA Gastélum Chavira, Marginalization in Mexico: An Application of the ELECTRE III–MOEA Methodology, A Gaspar-Cunha, C Henggeler Antunes, and CC Coello (editors), Evolutionary Multi-Criterion Optimization, Springer International Publishing, Vol. 9019, 2015, pp. 473-486. http://dx.doi.org/10.1007/978-3-319-15892-1_32

17.JC Leyva López, DA Gastelum Chavira, and JJ Solano Noriega, A multiobjective genetic algorithm based on NSGA II for deriving final ranking from a medium-sized fuzzy outranking relation, in Computational Intelligence in Multi-Criteria Decision-Making (MCDM), 2014 IEEE Symposium on (2014), pp. 24-31. Vol IEEE http://dx.doi.org/10.1109/mcdm.2014.7007184

18.K Miettinen and MM Mäkelä, On scalarizing functions in multiobjective optimization, OR Spectr., Vol. 24, No. 2, 2002, pp. 193-213. http://dx.doi.org/10.1007/s00291-001-0092-9

19.B Roy, Multicriteria Methodology for Decision Aiding, Kluwer Academic Publishers, The Netherlands, 1996. http://dx.doi.org/10.1007/978-1-4757-2500-1_6

20.R Bisdorff, Logical foundation of fuzzy preferential systems with application to the electre decision aid methods, Comput Oper Res., Vol. 27, No. 7, 2000, pp. 673-687. http://dx.doi.org/10.1016/s0305-0548(99)00112-4

21.AL Olteanu, On clustering in multiple criteria decision aid: theory and applications, 2013. http://dx.doi.org/10.1007/978-3-642-41575-3_22

22.M Öztürké, A Tsoukiàs, and P Vincke, Preference Modelling, Multiple Criteria Decision Analysis: State of the Art Surveys, Springer, New York, Vol. 78, 2005, pp. 27-59. http://dx.doi.org/10.1007/0-387-23081-5_2

23.E Fernández González, J Navarro, and S Bernal, Handling multicriteria preferences in cluster analysis, Eur J Oper Res., Vol. 202, No. 3, 2010, pp. 819-827. http://dx.doi.org/10.1016/j.ejor.2009.05.034

24.Y De Smet and S Eppe, Multicriteria relational clustering: The case of binary outranking matrices, Evolutionary Multi-Criterion Optimization, Springer, Heidelberg, Vol. 5467, 2009, pp. 380-392. http://dx.doi.org/10.1007/978-3-642-01020-0_31

25.K Deb, A Pratap, S Agarwal, and T Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-II, Evol Comput IEEE Trans., Vol. 6, No. 2, 2002, pp. 182-197. http://dx.doi.org/10.1109/4235.996017

26.J Handl and J Knowles, Improvements to the scalability of multiobjective clustering, IEEE, in The 2005 IEEE Congress on Evolutionary Computation, 2005 (2005), Vol. 3, pp. 2372-2379. http://dx.doi.org/10.1109/cec.2005.1554990

27.RC Prim, Shortest connection networks and some generalizations, Bell Syst Tech J., Vol. 36, No. 6, 1957, pp. 1389-1401. http://dx.doi.org/10.1002/j.1538-7305.1957.tb01515.x

28.Y De Smet and L Montano Guzmán, Towards multicriteria clustering: An extension of the k-means algorithm, Eur J Oper Res., Vol. 158, No. 2, 2004, pp. 390-398. http://dx.doi.org/10.1016/j.ejor.2003.06.012

29.G Syswerda, Uniform crossover in genetic algorithms, Morgan Kaufmann Publishers, San Francisco, CA, in Proceedings of the Third International Conference on Genetic Algorithms (1989), pp. 2-9. Vol http://dx.doi.org/10.1016/b978-0-08-094832-4.50021-0

30.D Whitley, A genetic algorithm tutorial, Stat Comput., Vol. 4, No. 2, 1994, pp. 65-85. http://dx.doi.org/10.1007/bf00175354

31.K Deb, J Sundar, N Udaya Bhaskara Rao, and S Chaudhuri, Reference point based multi-objective optimization using evolutionary algorithms, Int J Comput Intell Res., Vol. 2, No. 3, 2006, pp. 273-286. http://dx.doi.org/10.5019/j.ijcir.2006.67

32.K Deb and A Kumar, Interactive evolutionary multiobjective optimization and decision-making using reference direction method, ACM, in Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation (2007), pp. 781-788. Vol http://dx.doi.org/10.1145/1276958.1277116

33.K Deb and A Kumar, Light beam search based multiobjective optimization using evolutionary algorithms, IEEE, in Evolutionary Computation, 2007. CEC 2007. IEEE Congress on (2007), pp. 2125-2132. Vol http://dx.doi.org/10.1109/cec.2007.4424735

34.CONAPO, Índice de marginación por entidad federativa y municipio (2010), 2011. http://www.conapo.gob.mx/work/models/CONAPO/indices_margina/mf2010/CapitulosPDF/1_4.pdf http://dx.doi.org/10.24201/edu.v25i1.1371

<Previous Article In Issue

Download article (PDF)

Next Article In Issue>

Journal: International Journal of Computational Intelligence Systems
Volume-Issue: 9 - 4
Pages: 745 - 764
Publication Date: 2016/08/01
ISSN (Online): 1875-6883
ISSN (Print): 1875-6891
DOI: 10.1080/18756891.2016.1204122 How to use a DOI?
Open Access: This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

Cite this article

ris enw bib

TY  - JOUR
AU  - Juan Carlos Leyva López
AU  - Jesús Jaime Solano Noriega
AU  - Jorge Luis García Alcaraz
AU  - Diego Alonso Gastélum Chavira
PY  - 2016
DA  - 2016/08/01
TI  - Exploitation of a Medium-Sized Fuzzy Outranking Relation Based on Multi-objective Evolutionary Algorithms to Derive a Ranking
JO  - International Journal of Computational Intelligence Systems
SP  - 745
EP  - 764
VL  - 9
IS  - 4
SN  - 1875-6883
UR  - https://doi.org/10.1080/18756891.2016.1204122
DO  - 10.1080/18756891.2016.1204122
ID  - LeyvaLópez2016
ER  -

download .riscopy to clipboard

International Journal of Computational Intelligence Systems

Exploitation of a Medium-Sized Fuzzy Outranking Relation Based on Multi-objective Evolutionary Algorithms to Derive a Ranking

1. Introduction

2. Modelling the Exploitation of a Fuzzy Outranking Relation

2.1. Credibility Calculus

2.2. Modeling the Preference Relations

2.3. Comparing Classes of Alternatives

3. Proposed Ranking Procedure RP2-NSGA-II to Exploit a Fuzzy Outranking Relation

3.1. The MOEA RP2-NSGA-II

3.1.1. Representation of a potential solution in the ranking problem

3.1.1.1. Decoding process to obtain a partial order of classes of alternatives

3.1.2. Objective Functions

3.1.2.1. Maximizing the cutting level

3.1.2.2. The min cut objective

3.1.2.3. The minimum pair-wise preference disagreement objective

3.1.3. The Multi-Objective Combinatorial Optimization Problem

3.1.4. Initialization procedure

3.1.4.1. Multi-criteria distance between alternatives

3.1.4.2. Generating solutions based on MST

3.1.4.3. Generating solutions based on the K-means algorithm

3.1.5. Crossover and Mutation Operators

3.1.6. Preference incorporation in NSGA II

4. Empirical Evaluation

4.1. Generating the Simulated Fuzzy Outranking Relations

4.2. Response Variable

4.3. Results

4.3.1. RP2-NSGA-II Study

MOEAs Comparison Study

5. Real Case Example

5.1. Data Source

5.2. Computations with the ELECTRE III- RP2-NSGA-II Methodology

5.3. Analysis of the Results

5.4. Comparison against R-NSGA-II algorithm

6. Conclusions

Appendix A.

References

Cite this article

3. Proposed Ranking Procedure RP²-NSGA-II to Exploit a Fuzzy Outranking Relation

3.1. The MOEA RP²-NSGA-II

4.3.1. RP²-NSGA-II Study

5.2. Computations with the ELECTRE III- RP²-NSGA-II Methodology