Effect of the Profile of the Decision Maker in the Search for Solutions in the Decision-Making Process

Abstract

Many real-world optimization problems involving several conflicting objective functions frequently appear in current scenarios and it is expected they will remain present in the future. However, approaches combining multi-objective optimization with the incorporation of the decision maker’s (DM’s) preferences through multi-criteria ordinal classification are still scarce. In addition, preferences are rarely associated with a DM’s characteristics; the preference selection is arbitrary. This paper proposes a new hybrid multi-objective optimization algorithm called P-HMCSGA (preference hybrid multi-criteria sorting genetic algorithm) that allows the DM’s preferences to be incorporated in the optimization process’ early phases and updated into the search process. P-HMCSGA incorporates preferences using a multi-criteria ordinal classification to distinguish solutions as good and bad; its parameters are determined with a preference disaggregation method. The main feature of P-HMCSGA is the new method proposed to associate preferences with the characterization profile of a DM and its integration with ordinal classification. This increases the selective pressure towards the desired region of interest more in agreement with the DM’s preferences specified in realistic profiles. The method is illustrated by solving real-size multi-objective PPPs (project portfolio problem). The experimentation aims to answer three questions: (i) To what extent does allowing the DM to express their preferences through a characterization profile impact the quality of the solution obtained in the optimization? (ii) How sensible is the proposal to different profiles? (iii) How much does the level of robustness of a profile impact the quality of final solutions (this question is related with the knowledge level that a DM has about his/her preferences)? Concluding, the proposal fulfills several desirable characteristics of a preferences incorporation method concerning these questions.

1. Introduction

A variety of real-world problems, known as multi-objective optimization problems (MOPs), involve optimizing many objective functions simultaneously [1]. Multi-objective evolutionary algorithms (MOEAs) have been widely used for solving MOPs because of their effectiveness in solving problems in many fields. Nowadays, MOPs solved with metaheuristics like evolutionary algorithms are an important active research field [1,2].

Although the aim in Evolutionary Multi-objective Optimization (EMO) is to find a set of solutions that evenly spread around the Pareto front of a given MOP, it is also equally important to identify the solution to be implemented which best satisfies the preferences of the decision-maker (DM) [3]. Selecting the most preferred Pareto solution requires evaluates many solutions simultaneously, demanding a high cognitive effort, especially in problems with many objectives.

One alternative to reduce the DM’s cognitive effort is to incorporate preferences information of the DM into a multi-objective metaheuristic to identify progressively the region of interest (RoI), defined as the set of non-dominated solutions that the DM prefers over the other solutions [4,5]. There is a growing interest in the solution of MOPs with preferences.

The promising variants in the decision-making process are incorporating preferences using the a priori and interactive approaches, which have the advantage of delimiting the search space for searching an optimal solution, avoiding unnecessary exploration of the entire search space. Preferences integration narrows the search space in optimization problems so that the selective pressure directs evolutionary algorithms close to a region of interest [6]. However, the specialized literature starts from arbitrary reference sets, which are examples of random solutions introduced as preference information into the search process of a metaheuristic. In this work, it is proposed that these sets of references are generated from profiles that characterize DMs preferences simpler and realistically.

So far, there is no general definition that associates the mechanisms of incorporation of preferences with the region of interest. Each author captures preferences in different ways, for example, using fuzzy numbers [7], reference points [4,8], weights based [9,10,11], solution ranking-based [12] and outranking based models [13]. In addition, each captures preferences at different times in the search process, for example, a priori [14,15], a posteriori [16] or interactively [8]. Those differences difficult to make a fair comparison among them. A detailed review on types of approaches for preference incorporation can be seen in [17,18,19].

In our opinion, a multi-objective optimization metaheuristic proposed for solving MOPs with preferences should satisfy these features: (1) to allow the DM to introduce a priori preferences information with minimum cognitive effort; (2) interactivity, to allow the DM to specify new preference information to adjust his/her preferences. This paper proposes P-HMCSGA (preference hybrid multi-criteria sorting genetic algorithm), a new MOEA that satisfies these requirements; preferences are specified in a preferential profile. The proposed method holds for both multi-objective and many objective problems.

The experimentation was designed to respond to some questions related to the impact of the proposed algorithm in the solution of a real-world problem with nine and sixteen objectives. The results were satisfactory, particularly in the solution quality, sensibility to a profile and robustness.

This paper is organized as follows: Section 2 formalizes the theoretical background of the algorithm proposed. Section 3 contains the description of P-HMCSGA and its phases. Section 4 presents the experimental results that demonstrate the performance of our approach. Finally, Section 5 presents the conclusions and the possible areas of opportunity in the future.

2. Theoretical Background

2.1. Public Portfolio Problem (PPP)

A project is a unique, unrepeatable and temporary process that seeks to achieve a specific set of objectives. A set of projects that can be done in the same period of time is called a portfolio [19]. However, organizations generally do not have sufficient resources to support all proposed projects. In such circumstances, the difficulty is choosing the set of projects that offer the greatest benefit.

The public project portfolio (PPP) problem is defined below [20]:

Consider a set of N projects, where the i-th project is represented by a p-dimensional vector f(i) = ⟨f₁(i), f₂(i), …, f_p(i)⟩, where each f_j(i) indicates the contribution of project i to the j-th objective. Each project has an associated cost expressed by c_i. Each objective indicates the number of people benefited who belong to a social category, who will receive a level of benefit from the i-th project.

A portfolio x is a subset of projects generally modeled as a binary vector x = ⟨x₁, x₂, …, x_N⟩, where N indicates the number of projects. In this vector, x_i is a binary variable where x_i = 1 if the i-th project is supported and x_i = 0 otherwise.

There is a total budget that the organization is willing to invest, which is denoted as B. Portfolios are subject to the following budget restriction:

$$\left({\displaystyle \sum }_{i=1}^N{x}_i{c}_i\right)\le B$$

(1)

The i-th project corresponds to an area (health, education, etc.) indicated by a_i. Each area has a budget limit defined by the DM. For each area k, a lower and upper budget limit, L_k and U_k, respectively, is considered. Based on this, the constraint of each area k is

$$L_k\le {\displaystyle \sum }_{i=1}^N{x}_i{g}_i\left(k\right)c_i\le U_k$$

(2)

where g_i(k) is defined as

$$g_i\left(k\right)=\left\{\begin{array}{ccc}1\hfill & if& a_i=k,\\ 0\hfill & \mathrm{otherwise}& \end{array}\right.$$

(3)

Each i-th project corresponds to a geographic region indicated by r_i. For each region m, a lower and upper budget limit, L_m and U_m, respectively, is also considered. The restriction by region is defined as follows

$$L_m\le {\displaystyle \sum }_{i=1}^N{x}_i{h}_i\left(m\right)c_i\le U_m$$

(4)

where h_i(m) is defined as

$$h_i\left(m\right)=\left\{\begin{array}{ccc}1\hfill & if& r_i=m.\\ 0\hfill & \mathrm{otherwise}& \end{array}\right.$$

(5)

The quality of the portfolio x is determined by the union of the benefits of each one of the projects that compose it. This can be expressed as

$$z\left(x\right)=z_1\left(x\right),z_2\left(x\right),\dots ,z_p\left(x\right)$$

(6)

where z_j(x) is defined as

$$z_j\left(x\right)={\displaystyle \sum }_{i=1}^N{x}_i{f}_j\left(i\right)$$

(7)

If we denote by R_F the region of feasible portfolios, the project portfolio problem is to identify one or more portfolios that solve

$${max}_{x\in R_F}\left\{z\left(x\right)\right\}.$$

(8)

To select a portfolio many conflicting attributes are considered. Due to the nature of the problem, it has been approached by multi-criteria algorithms that generate a set of solutions that presumably are on the Pareto frontier, which would be the set of optimal non-dominated portfolios in PPP. The DM should choose only one portfolio from the set of good solutions, such a decision depends on the DM’s preferences.

2.2. Multi-Objective Optimization

In Multi-objective Optimization Problems (MOP), when the objectives are in conflict with each other, the compromise solutions are usually sought rather than a single solution.

A MOP can be defined as a vector of decision variables $\overrightarrow{x}={\left[x_1,x_2,\dots ,x_n\right]}^T$, which optimizes (maximizes or minimizes) a vector function $F\left(x\right)$ whose elements represent the objective functions of problem [2], where:

$$F\left(x\right)=\left[f_1\left(x\right),f_2\left(x\right),\dots ,f_k\left(x\right)\right], f_i:{ℝ}^n\to ℝ$$

(9)

subject to:

$$g_i\left(x\right)\le 0; i=1,2,\dots ,m$$

$$h_j\left(x\right)=0; j=1,2,\dots ,p$$

where:

• n is the number of decision variables,
• k is the number of objective functions,
• m is the number of inequality constraints,
• p is the number of equality constraints.

Therefore, the notion of optimum is different in these cases. The notion of optimum was generalized by Pareto [21]. This notion is commonly known under the term pareto optimality.

In multi-objective algorithms, the concept of Pareto dominance is frequently used when comparing two solutions and determining whether one dominates the other.

One solution $\overrightarrow{x_a}$ is said to dominate another $\overrightarrow{x_b}$ if the following conditions are met (for the minimization case):

• The solution $\overrightarrow{x_a}$is no worse than $\overrightarrow{x_b}$ in all objectives:

  $$f_i\left(\overrightarrow{x_a}\right) \le f_j\left(\overrightarrow{x_b}\right), \forall i \in \left[1, 2, \dots ., k\right]$$

  (10)
• The solution $\overrightarrow{x_a}$ is strictly better than $\overrightarrow{x_b}$ in at least one objective:

  $$f_i\left(\overrightarrow{x_a}\right) < f_j\left(\overrightarrow{x_b}\right), \exists i \in \left[1, 2, \dots ., k\right]$$

  (11)

If any of the conditions (1) or (2) are violated, the solution $\overrightarrow{x_a}$ does not dominate the $\overrightarrow{x_b}$ solution. That is, for one solution to dominate another, it needs to be strictly better in at least one objective and not worse in any of the rest. Within a set, a non-dominated solution has no other solution that dominates it. When comparing two solutions $\overrightarrow{x_a}$ and $\overrightarrow{x_b}$, there can only be three possible solutions:

• $\overrightarrow{x_a}$ dominates $\overrightarrow{x_b}$
• $\overrightarrow{x_a}$ is dominated by $\overrightarrow{x_b}$
• $\overrightarrow{x_a}$ and $\overrightarrow{x_b}$ are mutually non-dominated.

Pareto optimal set. For a given MOP, the Pareto optimal set is defined as $P^{*}=\left\{x\in S/\nexists x^{\prime }\in S,F\left(x^{\prime }\right)\prec F\left(x\right)\right\}$.

Pareto front. For a given MOP and its Pareto optimal set $P^{*}$,the Pareto front is defined as $P{F}^{*}=\left\{F\left(x\right),x\in P^{*}\right\}$.

2.3. Elitist Non-Dominated Sorting Genetic Algorithm-II (NSGA-II)

Elitist Non-dominated Sorting Genetic Algorithm-II (NSGA-II) [22] is one of the most popular algorithms for solving multi-objective problems due to its simplicity and effectiveness. The algorithm first generates a competitive population of individuals that is then ordered according to the level of dominance that the individual has in the population. This level of dominance generates different fronts, in the first front are the non-dominated solutions. Solutions from this first front, the elite solutions, are passed on to the next generation along with other solutions in such a way that there is diversity.

Like any genetic algorithm, evolutionary operators (cross and mutation, among others) are applied to it. The non-dominated solutions of the last generation will be an approximation to the Pareto front.

2.4. Fernandez’s Preference Model

Fernandez et al. [3] assumed that there are methods for assigning a degree of truth σ(x,y) in [0, 1] to the predicate xSy “x is at least as good as y”. Outranking methods such as ELECTRE-III [23,24] and PROMETHEE [25] can be used for this purpose. This work computes σ(x,y) based on ELECTRE-III and it uses the thresholds λ, β and ε to transform the fuzzy preference relations into the crisp preference relations.

The resulting relational system of preference defines five crisp relations. This system considers that: (1) ε < β < λ < 1; (2) the value λ > 0.5 is the outranking credibility threshold; (3) the value β is the asymmetry parameter; and (4) the value ε is the symmetry parameter. The formal definition of the relations are the following ones:

Strict Preference: This corresponds to the existence of clear and positive reasons that justify significant preference in favor of one (identified) of the two actions. The statement x is strictly preferred to y is denoted by xPy and exists if at least one of the following conditions holds.

(1)

x dominates y

(2)

σ(x,y) ≥ λ ∧ σ(y,x) < 0.5

(3)

σ(x,y) ≥ λ ∧ [0.5 ≤ σ (y,x) < λ] ∧ [σ(x,y) − σ(y,x)] ≥ β

Indifference: This corresponds to the existence of clear and positive reasons that justify equivalence between the two actions. The statement x is indifferent to y is denoted by xIy and it occurs if all the following conditions are met:

(1)

σ(x,y) ≥ λ ∧ σ(y,x) ≥ λ

(2)

|σ(x,y) − σ(y,x)| < ε

Weak Preference: This arises when indifference and strict preference cannot be distinguished appropriately. The statement x is weakly preferred to y is denoted by xQy and it occurs if all the following conditions are satisfied.

(1)

σ(x,y) ≥ λ ∧ σ(x,y) > σ(y,x)

(2)

¬ xPy

(3)

¬ xIy

Incomparability: This corresponds to a high heterogeneity among alternatives causing that none of the preceding situations predominates. The statement x is incomparable to y is denoted by xRy and it must satisfy the following condition:

(1)

σ(x,y) < 0.5 ∧ σ(y,x) < 0.5.

K-preference: This arises when strict preference and incomparability cannot be distinguished appropriately. The statement x is k-preferred to y is denoted by xKy and it exists if the following conditions are satisfied:

• 0.5 ≤ σ (x,y) < λ
• σ (y,x) < 0.5
• (σ(x,y) − σ(y,x)) > β/2

Fernandez et al. [3] used the above relations over a feasible set of solutions O of an optimization problem to define the best compromise according to the DM’s preferences. The elements to determine the model include the following ones:

• The non-strictly outranked frontier N_S = {x ∈ O|card (S_O)_x = 0}, where x ∈ O is a feasible solution and (S_O)_x = {y ∈ O|yPx} is the set of solutions y that are strictly preferred to x, i.e., the non-strictly outranked solutions;
• The non-weakly outranked frontier N_W = {x ∈ O|card (W_O)_x = 0}, where x ∈ O is a feasible solution and (W_O)_x= {y ∈ N_S|yQx ∨ yKx} is the set of non-strict outranked solutions y that have a weak preference or k-preference with x; and,
• The net-flow-score outranked frontier N_F = {x ∈ O|card (F_O)_x = 0}, where x ∈ O is a feasible solution and (F_O)_x = card {y ∈ N_S|F_n(y) > F_n(x)} is the set of non-strict outranked solution with larger net flow score than x. The net flow score F_n(x) = ∑ _{y ∈ NS−{x}} [σ(x,y) − σ(y,x)] is a popular measure in the literature and in this work offers a further ranking on the solution inside the non-strictly outranked frontier.

Hence, based on the previous sets, the best compromise for the DM is any solution to the optimization problem defined in Equation (12), with a preemptive priority favoring card(S_O).

$$mi{n}_{x\in O}\left\{⟨\left|S\left(O,x\right)\right|,\left|W\left(O,x\right)\right|,\left|F\left(O,x\right)\right|⟩\right\}$$

(12)

In summary, the preferences model is the relational system of preferences previously presented. Based on it, the best compromise is any solution in the Pareto frontier of the optimization problem shown in Equation (12).

2.5. Preference-Disaggregation Analysis (PDA)

The parameters of an outranking model (weights and thresholds, etc.) must be elicited, such as the preference model used in the present work. Direct procedures that ask a DM for proper values to be assign are commonly used; however, in such approaches, the DMs reveal difficulties when they are asked to assign values to parameters whose meanings are not understood for them [26]. On the other hand, indirect procedures, which compose the so-called preference-disaggregation analysis (PDA), use regression-like methods for inferring a set of parameters from a battery of decision examples [27]. In [28], a new optimization model for PDA is solved with the NSGA-II algorithm. According to Greco et al. in [29], MCDA approaches based on disaggregation paradigms are of interest because their simplicity and the reduced cognitive effort required from the DM. The use of an ordinal classification on the examples is an easy way for a DM to provides his/her preferences.

2.6. THESEUS

Fernandez proposed in [30] the THESEUS approach that is based on transforming the sorting problem into a particular case of the selection problem. THESEUS assigns new objects to the categories already defined in the set of references, comparing the object with the inconsistencies of the possible assignment and the information of various preference relations that can be strict, weak or indifferent; these are derived from a fuzzy outranking relation, described in Section 2.4. The category assignment is the consequence of comparisons with other objects whose categories are known.

The THESEUS method is based on the following premises:

• there is a set of ordered categories Ct = {C₁, …, C_M}, (M ≥ 2), where C_M is the preferred category;
• there is a universe U of objects x which are characterized by a set of N criteria denoted by G = {g₁, g₂, …, g_j, …, g_N}, where N ≥ 3;
• there is a set of reference objects T (also called reference set or training set), which is formed by objects b_kh $\in$U which are assigned to a category C_k, (k = 1, …, M);
• there is an outranking relation σ(x,y) defined in U × U which models the degree of credibility of the statement “x is at least as good as y” from the DM’s perspective.

The Hybrid Multi-Criteria Sorting Genetic Algorithm (H-MCSGA) algorithm presented in [14] uses the THESEUS method to assign solutions to two ordered categories (satisfactory and unsatisfactory). THESEUS is combined with the non-dominated sorting of an evolutionary algorithm to increase the selective pressure towards the RoI.

3. Description of P-HMCSGA

P-HMCSGA is an algorithm designed to solve MOPs, which allows the DM to specify his/her preferences by a realistic profile. Fernandez and Navarro [30] propose an outranking preference model that supports incorporating these preferences, which are regularly obtained by assignment examples. In outranking models, approaches like preference-disaggregation analysis [31,32] reflect preferences into these models’ parameters. In this paper, the terms direct and indirect concern the way to determine the outranking model parameters.

P-HMCSGA consists of three phases to perform the multi-objective optimization process. In the first phase, the DM specifies preferences in a profile that characterized her/his, which permits categorize the solutions as good and bad. The second phase transforms the categorized solutions into preference model parameters. Both phases correspond, respectively, with the indirect and direct elicitation of preferences mentioned in [33,34]. Finally, the third phase incorporates preferences in the solution process as the parameters of the preference model, supporting a multi-criteria classifier. Figure 1 illustrates these steps and the next sections explain each one.

The profiles are proposed to characterize a DM’s preferences expressed in understandable terms, avoiding the cognitive effort involved in selecting, from a solutions sample, the ones as close as possible to his/her preferences. This difficulty increases with the number of objectives.

An example of this characterization would be the profile of a DM who wishes to favor portfolios in which the number of supported projects is maximized. Another DM could be more interested in reducing the consumption of the available budget.

Depending on the selected profile, through profile generators, reference sets are formed to use in different parts of the optimization process. In this algorithm, the following generators are proposed.

• Profile-generator-α: Here, a reference set is formed with solutions selected according to the specified preference profile. It appears in phase 1 (indirect preference obtaining).
• Profile-generator-β: Here, a reference set is formed from solutions with implicit preferences that are inferred using the PDA strategy [35]. It appears in phase 3 (direct obtaining of preferences).

3.1. Phase 1: Indirect Preference Elicitation

In this phase, we start from the idea of presenting solutions to a decision-maker; these solutions can be obtained through a solution generator, a repository, etc. Commonly, it is intended that from these solutions, the DM selects those that are representative for him to be part of the good category and others to consider them in the category of bad solutions. Instead, to reduce the DM’s cognitive load, the generator-α method in Figure 2 allows the DM to provide a simple preference profile to emulates him/her in the reference set’s construction through this profile. This is a set of classified solutions that serve as training, reflecting the DM’s preferences in a categorized way. Similarly, only two categories are considered at this time: good and bad solutions.

Step 1. In this first part of the optimization process, the optimization instance is introduced to a solution generator without preferential support to generate feasible solutions.

Step 2. The DM selects a profile and, together with the generated solutions, is the input of a categorizer, which separates the good and bad solutions according to the preference profile.

Step 3. For the categorizer, the input is a set of solutions and the selected profile-α. Depending on the profile, the selection of solutions could require additional information. In this step, a coincidence count is made for each solution according to the α profile and, once the coincidence count has been complete, descending ordering is made according to this count’s value.

Step 4. The n solutions with the greatest coincidence are selected to form the category of good solutions. In the same way, the n solutions with the lowest coincidences form the category of bad solutions.

Step 5. These two sets form the reference set or categorized examples to use in the next phase.

3.2. Phase 2: Direct Preference Elicitation

For the DM, it is easier to indicate their preferences in profiles (converted a posteriori in categorized solutions) than to perform it directly by assigning weights to objectives, establishing acceptance ranges for each criterion, or giving preferential model parameters. For the Phase 2, the use of a PDA method [31] is proposed to transform the categorized preference information into parameters of a preferential model [30] that is part of the search process; this phase is shown in Figure 3.

Step 1. For this Phase 2, an instance generator method was developed so that PDA transforms the DM’s preferences into parameters of a preferential model. This generator receives as the first input the categorized examples obtained in Phase 1.

Step 2. The second input for the instance generator is the parameter ranges. The estimator of the feasibility region method obtains these approximate reference parameters from the initial optimization instance’s objectives. These values are adjusted according to the set of references (categorized examples) also introduced to PDA.

Step 3. Once the approximate reference parameters have been calculated, they are joined with the set of references obtained in Phase 1 to generate an input instance for the PDA.

Step 4. In the PDA procedure, the preferences, expressed in categorized examples, are transformed into preferential model parameters. At the end of Phase 2, a set of preferential model parameters are obtained for its incorporation into the search process of Phase 3.

3.3. Phase 3: Incorporation of Preferences in the Solution Process

Initially, in Phase 1, the preferences are introduced as a profile and converted to a reference set. After, in Phase 2, they are reflected in preference model parameters. Figure 4 shows the process of Phase 3, in which the preferences are incorporated in the optimization process.

Step 1. Once the parameters for the preferential model have been generated using PDA, the optimization instance incorporating these parameters is generated so that the preferences are included in the search process.

Step 2. With the instance with preferences, an initial search is conducted with a strategy that approximates the region of interest. For this, an alternatives generator with preferences method, like Non-Outranked Ant Colony Optimization (NO-ACO) proposed in [36] and modified in [14], finds a sample of satisfactory and unsatisfactory solutions, considering net flow, strict-preference and Pareto dominance (see Section 2). In [37], the NO-ACO algorithm uses the three objective Equation (11) as a subrogate model to solve PPP instances.

Step 3. The obtained solutions sample is introduced to the profile-generator-β to form a reference set, considering that the solutions satisfy the DM requested profile and his/her tolerance. The reference set includes good solutions from the satisfactory set and bad solutions from the unsatisfactory ones.

Step 4. After this, the parameterized optimization instance and the reference set obtained with the profile-generator-β are introduced to the H-MCSGA optimizer [14], which uses outranking classification to adds more solutions discrimination capability to the sorting process of NSGA-II. Based on the preference model, this strategy makes a better approximation towards the DM’s region of interest.

Step 5. The architecture of the proposed algorithm facilitates the interactive incorporation of preferences to allow the DM to refine them. Every certain number of iterations, the DM can give feedback with a sample of the best solutions obtained for the profile specified, with the possibility of choosing the ones most preferred. This set of solutions can enrich the initial reference set to direct the search more intensively toward the refined region of interest. The evaluation of interactive preference incorporation remains as future work.

Figure 5 shows the proposed P-HMCSGA, in which the intervention of the three phases that have been previously exposed can be observed.

4. Experimental Design and Results

This section describes the experimental process that evaluates P-HMCSGA. The process analyzes the algorithm in two experiments. The first experiment analyzes the effect of the profile of a decision maker in the search process. The second experiment studies the error variability of initial reference solutions and their impact on final solutions.

The experimental design tested the approach, in each experiment, on three different profiles, one configuration for the involved algorithms and six instances of the project portfolio problem (PPP). The performance of P-HMCSGA was measured using five different indicators that reflect how well it approximates the Pareto front with and without preferences and how well it adjusts the portfolios to the specified profiles.

A summary of the steps followed during the experiment are depicted in Figure 6. The remainder of the section details the elements utilized and the results obtained.

4.1. DM Profiles

A profile refers to the method used by a DM to make a decision. The evaluation of P-HMCSGA uses the following three preferential profiles:

Established projects: A predefined projects set in the portfolio is considered to be formed and they are defined according to the DM’s preferences; one possible reason for this profile is that these projects have been beneficial in the past.

Preference in the area and/or region: For the DMs, a portfolio has more preference with a higher number of supported projects on a pre-specified area or region.

Cardinality: The DM favors portfolios that maximize the number of supported projects.

4.2. Algorithm Configuration

Table 1. Algorithms used in the proposed P-HMCSGA.

Process	Algorithm	Iterations	Crossover	Mutation	Executions
Generation of alternatives without preferences	A2-NSGA-III [38]	100	1	0.01	30
PDA	NSGA-II [22,28]	1000	0.9	1/(5 ∗ N)	2
Generation of alternatives based on preferences	NO-ACO [37]	10			30
Optimizer	H-MCSGA [17]	500	1	0.05	30

shows the algorithms and their parameters’ values used for each process involved in the P-HMCSGA. The process is shown in Column 1. Column 2 indicates which strategy was used in each process. Columns 3 to show the configuration of the parameters’ values used in each strategy. The used genetic operators were the same as reported in [8,10,17] for each approach.

4.3. Instances of the Project Portfolio Problem

The instances of the PPP proposed in [39] served as a benchmark for the evaluation of P-HMCSGA.

Table 2. Description of the instances used in the experimentation.

Instance	Description
	Objectives	Projects
1	9	100
2	9	100
3	9	100
4	9	150
5	9	150
6	16	500

summarizes the details about the instances. The medium-scale instances have nine objectives and the large-scale instances has 16 objectives.

4.4. Quality Indicators to Evaluate Solutions

This work uses five different indicators to evaluate the performance of the proposed P-HMCSGA algorithm. These metrics are detailed in the remainder of this section.

Indicator ND_A measures the non-dominance proportion achieved over an approximated Pareto front (PF) A. Equation (13) computes this indicator as to the quotient of the size of the set of non-dominated solutions F₀ produced by P-HMCSGA and the size of set A.

$$N{D}_A=\frac{\left|F_0\right|}{\left|A\right|}\times 100$$

(13)

Indicator PSO_A measures the proportion between non-strictly outranked solutions (i.e., solutions that are hard to distinguish by preference according to a specific DM (see Section 2) and an approximated PF A. Equation (14) computes this indicator as the quotient of the size of the approximated non-strict-outranked frontier F_NSO produced by P-HMCSGA and the size of the set A.

$$PS{O}_A=\frac{\left|F_{NSO}\right|}{\left|A\right|}\times 100$$

(14)

Indicator PC measures the percentage of maximum cardinality achieved by the solutions reported by P-HMCSGA. Equation (15) computes it as the quotient between the number of supported projects in a portfolio, sp, and the estimated maximum projects that could ever be supported, ems.

$$PC=\frac{sp}{ems}\times 100$$

(15)

Indicator PES (previously established projects) measures the proportion of the DM’s previously established projects that are found in a portfolio generated by P-HMCSGA. Equation (16) computed as the quotient between ep, i.e., the number of projects in a portfolio that are wanted by the DM, and EP (established projects), the maximum number of wanted projects.

$$PES=\frac{ep}{EP}\times 100$$

(16)

Finally, indicator PAR (project in area/region) is the proportion of supported projects that goes in agreement with the area/region desired in the portfolio and established by the DM. Equation (17) measures this proportion as the quotient between EAR, the number of projects in the portfolio constructed by P-HMCSGA that satisfied the area and region conditions of the DM and q, the number of projects in the instance that satisfy the area and region conditions established by the DM.

$$PAR=\frac{EAR}{q}\times 100$$

(17)

The NDA and PSOA are referred to as general quality indicators because they measure the quality of a strategy based on their closeness to the PF or the RoI, the general metric evaluations for multi-criteria algorithms. The indicators PC, PES and PAR are indicators of specific quality because they measure how well the portfolios constructed have respected the preferences established by a particular preference profile.

4.5. Experiment 1: Effect of the Profile of a Decision Maker in the Search Process

This experiment was carried out based on the idea that if the solutions are presented to two decision makers with different profiles, these may be good for one decision maker and they may not be good for another, or perhaps only some. An example is shown in Figure 7, where, for a DM that seeks to maximize the number of projects included in the portfolio, both solutions satisfy that requirement, but if these same solutions are presented to a DM whose profile establishes that project number 3 must be supported, the first solution is definitely not acceptable because it does not include this.

From the above, an experiment was designed, the process of which is shown in Figure 8. There, it illustrates that P-HMCSGA solves each instance using each of the n profiles (the configurations of the approaches are according to those defined in Section 4.2). With the results, a matrix of size n × n is formed. The set of solutions produced using each profile i is compared against the other profiles j in order to estimate how well the satisfaction of a profile i by P-HMCSGA behaves in comparison with other profiles j not considered at the moment. Hence, a cell (i,j) contains the number of portfolios that satisfies profiles i and j. Appendix A and Appendix B show the complete set of results derived from experimenting with the considered set of instances; the remainder of the sections presents a summary based on selected cases.

Table 3. DM’s profile characterization and maximum found values.

Profile	Expected	Minimum Accepted	Maximum Found
Cardinality	41	38	40
Established projects	15	11	11
Area-Region	22	16	21

shows the different DM profiles considered in the experiment for all the instances. Each profile defines two values: the expected value, which is the desired amount of elements required to satisfy a DM completely, and the minimum accepted, which is the minimum number of elements necessary to consider a solution as satisfactory. The maximum found shows the best match obtained from a portfolio constructed by P-HMCSGA.

Table 4. Matrix of results of satisfactory solutions evaluated in other preferential profiles using instance o9p100_1.

Parameter Setting	Evaluation in the Profile
	Cardinality	Established Projects	Area-Region
Cardinality	91 (40)	8 (10)	4 (17)
Established projects	8 (38)	2 (11), 12 (10)	2 (15)
Area-Region	3 (40)	16 (10)	1 (21)

shows the matrix obtained for the concentration of the results of the evaluations in the profiles. The row leads the profile used by P-HMCSGA to approximate the RoI. The column shows how the best value obtained by fixing the profile behaves in other profiles. The value in parenthesis indicates the best value in the compared profile; the value outside is the number of solutions that obtained that value.

The results from Table 4 show that the highest number of solutions coincide with the main diagonal; this demonstrates that the use of profiles in the search process of P-HMCSGA indeed pursues the construction of portfolios that satisfy such preference conditions.

Table 5. Specific quality indicators for each profile as established by the DM using instance o9p100_1.

Indicator	Evaluation in the Profile
	Cardinality	Established Projects	Area-Region
PC	97.56%	66.66%	77.27%
PES	92.68%	73.33%	68.18%
PAR	97.56%	66.66%	95.45%

shows the results from the measurements established by the indicators defined in Section 4.4. Again, the highest scores are in the main diagonal and are achieved when the indicator matches the profile used during the search process. These results corroborate the fact that the use of profiles favors the construction of solutions that satisfy a DM’s preferences.

Figure 9 illustrates the process used to identify the approximate Pareto front and non-strict outranked sets from P-HMCSGA on each profile. There, all the solutions considered satisfactory for each profile were concentrated in bags of satisfactory solutions, sets of non-repeated solutions that satisfy non-dominance or non-strictly outrank conditions.

Table 6. Dominance and strictly-outranked in cardinality profile using instance o9p100_1.

Bag		Cardinality		Established Projects		Area-Region
		#Solutions	Percentage	#Solutions	Percentage	#Solutions	Percentage
#Solutions	99	91		8		3
ND	90	82	90.11	8	100	3	100
NSO	90	90	98.90	0	0	0	0

summarizes the measurements on the ND and NSO indicators obtained from the cardinality profile. Using P-HMCSGA to approximate the PF and the RoI on instance o9p100_1, under the cardinality profile, the set A of reported portfolios was of size 99. The numbers of portfolios that satisfy the cardinality, established projects and area-region profiles are shown in row one and columns 3, 5 and 7, respectively.

The proportion of non-dominated solutions on each profile is shown in row 2 and columns 4, 6 and 8. The proportion of non-strictly outranked solution on each profile is shown in row 3 and columns 4, 6 and 8. The results show that if we use cardinality in the profile, the best measures for indicators ND and NSO are obtained when comparing against the same cardinality.

Table 7. Dominance and strictly-outranked in established profile.

Bag		Cardinality		Established Projects		Area-Region
		#Solutions	Percentage	#Solutions	Percentage	#Solutions	Percentage
#Solutions	38	8		14		16
ND	37	8	100	14	100	15	93.75
NSO	37	8	100	14	100	15	93.75

summarizes the measurements on the ND and NSO indicators obtained from the established projects profile. Using P-HMCSGA to approximate the PF and the RoI on instance o9p100_1, under the established projects profile, the set A of reported portfolios was of size 38. The numbers of portfolios that satisfy the cardinality, established projects and area-region profiles are shown in row one and columns 3, 5 and 7, respectively. The proportion of non-dominated solutions on each profile is shown in row 2 and columns 4, 6 and 8. The proportion of non-strictly outranked solution on each profile is shown in row 3 and columns 4, 6 and 8. The results show that if we use established projects in the profile, the best measures for indicators ND and NSO are obtained when comparing against the same established projects.

Table 8. Dominance and strictly-outranked in area-region profile.

Bag		Cardinality		Established Projects		Area-Region
		#Solutions	Percentage	#Solutions	Percentage	#Solutions	Percentage
#Solutions	56	4		2		50
ND	50	4	100	2	100	44	88
NSO	50	4	100	2	100	44	88

summarizes the measurements on the ND and NSO indicators obtained from the area-region profile. Using P-HMCSGA to approximate the PF and the RoI on instance o9p100_1, under the area-region profile, the set A of reported portfolios was of size 56. The numbers of portfolios that satisfy the cardinality, established projects and area-region profiles are shown in row one and columns 3, 5 and 7, respectively. The proportion of non-dominated solutions on each profile is shown in row 2 and columns 4, 6 and 8. The proportion of non-strictly outranked solution on each profile is shown in row 3 and columns 4, 6 and 8. The results show that if we use established projects in the profile, the best measures for indicators ND and NSO are obtained when comparing against the same area-region.

Table 6, Table 7 and Table 8 show that the percentage of solutions remaining satisfactory (non-dominated and non-strictly outranked) is very high in the solutions obtained from the parameter configuration corresponding to the specified profile. When the search was not configurated according to the interesting profile, it obtains few solutions (which were not repeated). Both complementary results show that the search direction depends on the preference profile established by the DM. The solutions obtained from the configuration of specific parameters for the profile are good in dominance and outranking. Besides, using these parameters, it is possible to find a greater number of satisfactory solutions for the profile.

4.6. Experiment 2: Error Variability of Initial Reference Solutions and Its Impact on Final Solutions

The objective of this experiment is to analyze how the quality of an initial reference set affects the performance of P-HMCSGA. For this purpose, the implementation of the algorithm considers the use of two types of reference sets. The low-quality reference set (denoted “Low”) has solutions around the minimum value in a profile that is considered satisfactory for a DM. The high-quality reference set (denoted “Good”) has solutions close to the maximum value possible of satisfaction for the chosen profile. The experiment compares the final set of solutions produced by P-HMCSGA using each of the reference sets in terms of the level of satisfaction of the profile and the number of solutions produced. The results show that using a robust reference set formed by solutions of high quality improves the performance of P-HMCSGA and allows it to find solutions that better satisfy the preferential profile.

For this experiment, the configuration of P-HMCSGA was in accordance with the values in Table 1, except for the number of executions of the generation of alternatives without preferences that were set to 1 for simplicity. The instance considered for the experiment was o9p100_1. The profile used was established projects and it fixes 15 projects as the desire by the DM (expected column in

Table 9. Values that satisfy the DM with the established projects profile on instance o9p100_1.

	Expected	Minimum Accepted	Maximum Found
Established projects	15	11	14

); Also, in addition, it considers as satisfactory any solution having a subset of at least 11 of such projects (minimum accepted column in Table 9). The low-quality reference has 20 portfolios or solutions; from them, two contain 12 of the desired 15 projects and the remaining ones contain only 11 projects. The high-quality reference set (or robust reference set) also has 20 portfolios; however, three of them have all the desired projects and 17 of them have 14. Table 9 also shows the maximum number of desired projects that could be found in a solution constructed by P-HMCSGA in the experiment; those solutions could only be found using a reference set of high quality.

Table 10. Error variability of initial reference solutions and its impact on final solutions.

	Quality of Reference Set
Profile	Low		Good
	Maximum in RS	Finals	Maximum in RS	Finals
Established projects	2 (12), 18 (11)	6 (13), 1 (12), 3 (11)	3 (15), 17 (14)	14 (14), 206 (13), 686 (12)
PES	80%	86.6%	100%	93%

shows the results of this experiment. In row 1, the column “Maximum in RS” shows the composition of the reference sets Low and Good; the column “Finals” shows the composition of the satisfactory solutions found by P-HMCSGA. In both columns, the notation X(Y) indicates that there are X solutions having Y desire projects from the 15 considered in the profile. In row 2, the best value achieved according to the PES indicator is shown, considering the composition of the portfolios reported and 15 as the maximum number of desired projects, EP. It is important to note the contrast of the solutions obtained using reference sets with different qualities. The significant variations in the quality of solutions obtained are evident, favoring the results of the robust reference set; this situation is due to the fact that there are far more solutions with a greater number of desired projects involved in the portfolios and also because those solutions present the highest value in PES, indicating that they are closer to the DM’s profile than the others.

Finally,

Table 11. Dominance comparison of solutions with good quality RS and low quality RS.

		Low Quality RS		Good Quality RS
		#Solutions	Percentage	#Solutions	Percentage
#Solutions	226	6		220
ND	220	5	83.33%	215	97.73%

shows the summary of the dominance comparison of the solutions found using the different referent sets. In the case of the final solutions obtained using the low-quality reference set, of the six of the acceptable solutions according to the preference profile, five remained non-dominated. On the other hand, the use of the high-quality reference set presents a larger number of non-dominated solutions (97.73% of all those reported) all also being satisfactory to the DM.

5. Conclusions

We present P-HMCSGA, a hybrid evolutionary algorithm for solving multi-objective optimization problems. The algorithm incorporates the DM’s preferences to guide the search towards the region of interest that the DM desires the algorithm to approach. The DM gives a preferential profile containing their preferences expressed in understandable terms, which demand less cognitive effort than when he/she selects solutions from a generated sample, which is a common way to elicit preferences. P-HMCSGA reflects this preference profile in the outranking relational parameters of an ordinal multi-criteria ordinal classification method. These strategies add more solutions discriminationcapability to the well-known non-dominated sorting process incorporated in P-HMCSGA, achieving a better approximation towards the DM’s region of interest.

The proposed algorithm satisfies some desirable features of a preferences incorporation method: (a) the DM interacts easily with the solutions sample generator method, decreasing the cognitive effort from the DM when the DM gives a simple preferential profile to automatically separate solutions as “good” and “bad” and to the forms reference set for a classifier method; (b) the multi-criteria preferences outranking model is compatible with relevant characteristics of real DMs expressed in preference profiles and preferences are rarely associated with realistic DM’s characteristics; (c) it is possible to estimate the preference model parameters from the profile provided by the DM during the interactive process; (d) to a certain extent, the profile generator and the ordinal classification replace the DM during the optimization process, bringing valuable aid to the DM, especially in the presence of a high number of objectives.

Our algorithm obtains, as output, a set of non-dominated solutions which belong to the DM best class. The experiments were carried out to solve a project portfolio optimization problem with instances of nine and sixteen objectives. From these experiments, we can observe that P-HMCSGA has performed as expected and make the following conclusions:

(i)

Allowing the DM to express their preferences through a DM characterization profile positively impacts the quality of the solution obtained in the optimization; a reasonable number of the solutions found correspond with the specified profile, being non-dominated and satisfactory for the DM.

(ii)

The proposed algorithm is sensible is to different profiles. Our algorithm obtains the greatest number of satisfactory solutions when the preference model parameters correspond to the desired profile. This result confirms that the search direction depends on the preferences profile established by the DM.

(iii)

The level of robustness of a profile impacts the quality of final solutions. The result shows that using a robust reference set allows one to find better solutions, satisfying the preferential profile. Therefore, the interactive intervention of the DM is necessary to enrich the reference set, learn from their preferences and learn about the problem itself. Our results were obtained with a single run of the preference elicitation step; we hope that even better results can be obtained through several preference elicitation executions.

The P-HMCSGA running time only doubles the time spent by the slower inner strategy. The latter can be observed from the results when analyzing instances with nine and 16 objectives, separately. In nine objective instances, A2-NSGA-III was the most time-consuming strategy, requiring at least four times the amount of time of any other. In sixteen objective strategies, NO-ACO was the slowest and needed at least five times longer than any other. Hence, the accumulated consumed time would be, at most, twice the slower strategy.

We have not included a comparison with other algorithms because our preference representation requires conversion methods to make a fair and comparable evaluation. Another possible analysis is to implement our preference incorporation method into several state-of-the-art multi-objective optimization metaheuristics to determine the advantages and limits of our proposal. However, this is beyond the scope of this paper.

Future work is proposed to verify the algorithm’s interactive capacity, which can enrich the initial reference set with new solutions to intensity the search toward the region of interest. In addition to interactivity, a DM might be interested in specifying their profile with more than one preference. For example, in the project portfolio problem, a DM has particular ideal preferences on portfolios with a small number of projects and their cost is at a most certain quantity. Some voting strategies could be useful to deal with profiles that include several preferences. Pareto Explorer is a recent tool that incorporates user’s preferences, articulated either in decision variables, objectives, weight space, or toward knee solutions, in the computation of the “ideal” solution of a given MaOP is the Pareto Explorer [40].