Interactive Evolutionary Multiple Objective Optimization for Group Decision Incorporating Value-based Preference Disaggregation Methods

In this subsection, we review some representative MOO algorithms that learn value functions from user’s indirect preference information. Some of them select a single value function compatible with the DM’s preference information. In particular, in Phelps and Köksalan (2003) the DM is asked to provide at regular intervals some pairwise comparisons of solutions. These are used to derive the most discriminant additive linear value function, which serves to rank individuals in the evolutionary algorithm. Differently, in Deb et al. (2010) one constructs a polynomial value function based on the DM’s (partial) ranking of a small subset of solutions. Such function is employed to identify the most desirable solutions in the population and to reject a large subset of these which are non-relevant for the DM. The same type of preference information is used in Battiti and Passerini (2010) though with a highly non-linear complex function which is used to rank individuals in the same Pareto front. This algorithm has been proven to work well with few interactions with the DM, but requiring her/him to rank larger subsets of solutions than in Deb et al. (2010). Finally, in the NEMO-0 (Necessary preference enhanced Evolutionary Multi-objective Optimization-0) method (Branke et al. 2015), one generalized the approach of Phelps and Köksalan (2003) for inferring an arbitrarily monotonic value function compatible with the DM’s pairwise comparisons, and used it in the same way as in Battiti and Passerini (2010). The method has been illustrated to perform well even if the DM’s preference information is not representable with a linear model.

Instead of using a single value function, some other approaches exploit a set of functions compatible with the DM’s indirect preferences. In this regard, Greenwood et al. (1997) consider a set of linear value functions compatible with the DM’s ranking of a few solutions. This set is exploited to derive the necessary preference information confirmed by all compatible functions. Such relation—reflecting robust consequences of the DM’s exemplary statements—is used to replace the non-dominance sorting step of the evolutionary algorithms. NEMO-I (Branke et al. 2015) implements the same idea though with more general additive value functions. Recently, to reduce the computational complexity of NEMO-I, in NEMO-II (see Branke et al. 2015, 2016) the necessary relation has been replaced with the preference fronts obtained by iterative identification of potentially optimal solutions, i.e., individuals which are ranked first by at least one compatible value function. Moreover, NEMO-II adjusts the complexity of an assumed preference model to the pairwise comparisons provided by the DM, thus, starting the iterative process with a simple linear value function and switching to the Choquet integral (Choquet 1954) when the linear model is not expressive enough.

In this paper, we focus on the NEMO methods. They can be perceived as hybrids combining the evolutionary method, called Non-dominated Sorting Genetic Algorithm II (NSGA-II) (Deb et al. 2002), with some interactive ordinal regression approaches (see Jacquet-Lagrèze and Siskos 2001; Corrente et al. 2013). Our interest in NEMO comes from its favorable characteristics in terms of both preference information and preference model it employs. Indeed, NEMO requires the DM to compare some pairs of solutions from the current population, which is less demanding than specifying precise values for some preference model parameters, but also less restrictive and more general than ranking a subset of individuals or picking the best or the worst one among them. Moreover, it uses an additive value function as the preference model. Such function is often an appropriate simplification of the DM’s preference structure, it has high explainability due to its low amount of inter-criteria preference parameters, and is more transparent than some non-parametric approaches used in MOO, such as support vector machines (Battiti and Passerini 2010) or artificial neural networks (Todd and Sen 1999).

NEMO, alike other existing interactive EMO methods, has been designed to deal with preferences expressed by a single DM. However, one often faces situations when individuals collectively make a choice. Each of the group members can have her/his own priorities, perception of the decision problem to be tackled, and unique contribution to the outcomes (Matsatsinis et al. 2005). In such case, the decision is no longer attributed to a single group member, but instead the aim is to find a group consensus. When dealing with multiple DM in the context of MOO, the main challenge consists in designing the algorithms so that they are able to focus the search on the consensus solutions. The promising initial results in this regard (Kadziński and Tomczyk 2015) encourage us to extend this line of research in terms of both further methodological advancements and experimental analysis.

In this paper, when compared to Kadziński and Tomczyk (2015), we propose a few additional variants of NEMO-GROUP that incorporate indirect preference information of several DM. All these variants properly modify NSGA-II so that it promotes the solutions preferred by the group members in the optimization run. They differ, however, in how they evaluate the quality of constructed solutions. In particular, solutions may be ranked either with respect to a single compatible value function or the whole set of such functions. A representative function can be derived individually for each DM or constructed for all group members considered jointly. When working with a set of compatible models, the elitism of solutions can be preserved by referring either to the fronts of potential optimality the solution belongs to, or to the most advantageous result attained by each solution. Finally, the population of solutions can be evolved separately for each DM or in common for the entire group.

Such diversity of approaches allows us to discover the paradigms which are most beneficial in terms of consensus seeking in the interactive evolutionary MOO. The performance of the algorithms is judged in terms of the quality of solutions they construct. We employ both utilitarian and egalitarian value functions, thus, verifying the level of satisfaction of an average group member or the least satisfied DM, respectively. In this regard, we evaluate both the best solution and the most advantageous population obtained throughout the optimization run, as well as the algorithms’ convergence toward the part of Pareto front that is satisfactory for the whole group.

The proposed methods are thoroughly tested on a set of benchmark MOO problems with different numbers of objectives. In this way, we illustrate the impact that including additional relevant viewpoints may have on consensus reaching. Moreover, we demonstrate the potential of some variants of NEMO-GROUP for incorporating the DMs’ weights, thus, differentiating the importance of group members. Finally, we assess how the performance of proposed methods is influenced by the frequency of eliciting pairwise comparisons from the DMs and the generation in which the preference elicitation starts.

The paper is organized as follows. The next section provides a brief reminder on ordinal regression, basic evolutionary methods, and their interactive counterparts. Section 3 presents different variants of our method, NEMO-GROUP. The results of an extensive experimental study are discussed in Sect. 4. The last section concludes.

Preference information Each \(DM_k \in \mathcal {D}\) offers individual preference information which is a set \(B_k\) of pairwise comparisons of some reference solutions in \(A^{REF}_k\). In general, \(A^{REF}_k \ne A^{REF}_l\) for \(DM_k, DM_l \in \mathcal {D}\). The comparison of a pair \((a^*,b^*) \in B_k \subseteq A^{REF}_k \times A^{REF}_k\) provided by \(DM_k\) states the strict preference, weak preference, or indifference. These relations are denoted by, \(a^* \succ _{k} b^*\), \(a^* \succsim _{k} b^*\), and \(a^* \sim _{k} b^*\), respectively. Let each pairwise comparison from \(B_k\) be denoted by \(B_k^t\), \(t=1,\ldots ,p_k\), where \(p_k\) is the number of comparisons contained in \(B_k\).

Preference model To model the preferences provided by the DM and evaluate a set of solutions, we use an additive value function. It is defined on A as follows (Jacquet-Lagrèze and Siskos 2001):where \(u_j : F_j \rightarrow \mathbb {R}\), \(j=1,\ldots , m\), are subject to monotonicity and normalization constraints:When marginal value functions are assumed to be linear, for each \(a \in A\) and \(f_j \in G\): Ordinal regrssion The pairwise comparisons provided by each \(DM_k \in \mathcal {D}\) form the input data for the ordinal regression (Jacquet-Lagrèze and Siskos 2001) that finds the whole set of value functions \(\mathcal {U}_k\) being able to reconstruct these judgments. The set of linear constraints \(E^{k}\) given below translates a reference pre-order provided by \(DM_k\) to a value function:where \(\varepsilon \) is an arbitrarily small positive value.

Thus, \(\mathcal {U}_k\) is defined by a set of constraints \(E^{\mathcal {U}_k} = E^{\mathcal {U}} \cup E^k\). The set of value functions \(\mathcal {U}_{\mathcal {D}}\) compatible with the pairwise comparisons of all DMs is defined with \(E^{\mathcal {U}_{\mathcal {D}}} = E^{\mathcal {U}} \cup E^{k}\), \(k=1,\ldots , s\). Note that \(\mathcal {U}_{\mathcal {D}}\) corresponds to the intersection of sets of compatible value functions for all DMs in \(\mathcal {D}\).

If \(\varepsilon ^* = max \, \varepsilon \), s.t. \(E^{\mathcal {U}_k}\) \((E^{\mathcal {U}_{\mathcal {D}}})\), is greater than 0 and \(E^{\mathcal {U}_k}\;(E^{\mathcal {U}_{\mathcal {D}}})\) is feasible, the set of compatible value functions \(\mathcal {U}_k\) \((\mathcal {U}_{\mathcal {D}})\) is non-empty (Kadziński et al. 2013). Otherwise, the provided preference information is inconsistent with the assumed preference model, which means that there is no value function that would reproduce the pairwise comparisons provided by \(DM_k\) (if \(\mathcal {U}_k = \emptyset \)) or all DMs (if \(\mathcal {U}_{\mathcal {D}} = \emptyset \)).

Representative value function for a single DM The issue of selecting a representative function for a single DM has been discussed in detail in Kadziński et al. (2012). In this paper, we will use the most discriminant value function \(U^{REP}_k\), which is obtained by maximizing \(\varepsilon \), subject to \(E^{\mathcal {U}_k}\). It discriminates comprehensive values of reference solutions related by the preference in the DM’s partial ranking. When pairwise comparisons provided by the DM are inconsistent with an assumed preference model, they are removed, starting from the oldest one, until feasibility is restored. This approach has been employed in Branke et al. (2015) and Phelps and Köksalan (2003) to avoid an excessive use of Mixed Integer Linear Programming (MILP) techniques. Then, \(U^{REP}_k\) is selected analogously.

Representative value function for a group of DMs To select a representative value function \(U_{\mathcal {D}}^{REP-EPS}\) for a group of DMs, we discriminate the comprehensive values of reference solutions compared by all DMs in the following way:When there is no value function compatible with the preference information provided by all DMs, \(\varepsilon \) is interpreted as a non-statistical misranking error which indicates the distance between the DM’s preferences and the recommendation which can be obtained for the assumed model (Corrente et al. 2013). Obviously, in case of incompatibility, some pairwise comparisons are not reproduced by \(U_{\mathcal {D}}^{REP-EPS}\).

Alternatively, to deal with incompatibility of preference information at the group level, we may identify a set of consistent pairwise comparisons of all DMs. For this purpose, we maximize a minimal number of pairwise comparisons of any DM which are consistent, being representable by a single additive value function (Kadziński et al. 2013). It can be achieved by solving the following MILP problem: Apart from providing the minimal number of non-contradictory pairwise comparisons of all DMs (\(v^*\)), the solution of the above problem indicates which pairwise comparisons can be reproduced together by an additive value function (they are distinguished with \(v^{k,*}_t = 1\)). If for all DMs the numbers thereof are imbalanced, we arbitrarily choose the last \(v^*\) non-contradictory pairwise comparisons provided by each DM, so that none of them is favored. Then, we determine a representative (most discriminant) value function \(U_{\mathcal {D}}^{REP-MAX}\) compatible with thus selected subset of holistic judgments.

Potential optimality To verify if solution \(a \in A\) is potentially optimal for \(DM_k \in \mathcal {D}\), we need to check if it is at least as good as all remaining solutions for at least one value function compatible with her/his preferences (Lee et al. 2002). This can be achieved by solving the following problem:where \(E^{'\mathcal {U}_k}\) differs from \(E^{\mathcal {U}_k}\) in that it involves only consistent pairwise comparisons (the feasibility is restoterd by removing the oldest pairwise comparisons) and assumes \(\varepsilon \) to be equal to an arbitrarily selected small positive value.

If \(\varepsilon ^{ADV}_{1,k}(a) = max \ \varepsilon ^{ADV}_k\), s.t. \(E^{\mathcal {U}_k}_{PO}(a)\) is greater or equal to zero, a is potentially optimal. The set of all such potentially optimal solutions for \(DM_k\) is denoted by \({\mathcal {PO}}_{1,k}\). Moreover, \(\varepsilon ^{ADV}_{1,k}(a)\) indicates the advantage that a has over the remaining solutions for the most advantageous value function. If \(\varepsilon ^{ADV}_{1,k}(a) < 0\), it reveals the minimal loss of a to the best solution in A for some compatible value function. Different values of \(\varepsilon ^{ADV}_{1,k}(a)\) are comparable, because being defined on the conjoint interval scale of the marginal value function (Wakker 1989), they have the meaning of intensity.

The above procedure can be repeated to assign all solutions to their respective levels of potential optimality. That is, the solutions which become potentially optimal once solutions in \({\mathcal {PO}}_{1,k}\) are removed from the explored set are denoted by \({\mathcal {PO}}_{2,k}\) and their maximal advantage over the solutions in \(A\setminus {\mathcal {PO}}_{1,k}\) by \(\varepsilon ^{ADV}_{2,k}(a)\), etc. The level of potential optimality for \(a \in A\) and \(DM_k \in \mathcal {D}\) is denoted by \(PO_k(a)\) and the respective advantage by \(\varepsilon ^{ADV}_{PO_k(a),k}(a)\). Obviously, the less \(PO_k(a)\), the better. Let us call a procedure which sorts the solutions into a set of potential optimality levels \({\mathcal {PO}}_k = \{{\mathcal {PO}}_{1,k}, {\mathcal {PO}}_{2,k},\ldots \}\) by \(\mathtt{pot}\text {-}{} \mathtt{opt}\text {-}{} \mathtt{sort}_\mathtt{k}(\mathtt{A})\). From the group decision perspective, this procedure can be generalized to:Finally, we denote a procedure which imposes a complete order on set \(A' \subseteq A\) according to some measure M (e.g., comprehensive value \(U^{REP}_k(a)\) of solution \(a \in A'\) for the representative value function or the maximal advantage \(\varepsilon ^{ADV}_{1,k}(a)\) of \(a \in A'\) over the remaining solutions) by \(\mathtt{sort}(\mathtt{A',M}(\mathtt{a}))\). Clearly, the greater M(a) for \(a\in A'\), the better its rank.

The role of genetic algorithms is to estimate meta-heuristically the Pareto fronts in MOO problems. In particular, NSGA-II (Deb et al. 2002) incorporates a fast non-dominated sorting algorithm to identify Pareto optimal solutions, and a diversity preservation mechanism for maintaining a well-spread Pareto front. It starts with the initialization of a random parent population \(P_0\) of size N. Then, the offspring \(Q_0\) of the same size is created using the usual selection, recombination and mutation operators. Further, the parents and their offspring (\(R_t = P_t \cup Q_t\)) are combined to obtain a population of size 2N. This population is sorted into a set of Pareto fronts \(\mathcal {F}\) using \(\mathtt{non}\text {-}{} \mathtt{dominated}\text {-}{} \mathtt{sort}(\mathtt{R}_\mathtt{t})\) procedure. Thus, \(\mathcal {F}_1\) is composed of non-dominated solutions, \(\mathcal {F}_2\) contains solutions dominated only by some solutions from \(\mathcal {F}_1\), etc.

The new population (\(P_{t+1}\)) is filled with the best Pareto fronts from \(R_t\) (first \(\mathcal {F}_1\), then \(\mathcal {F}_2\), etc.), until the size of the next front (\(\mathcal {F}_l\)) is larger than the number of free slots in \(P_{t+1}\). To have exactly N members in the new population and to maintain diversity, the front \(\mathcal {F}_l\) is ordered using the crowded distance CD measure. The total crowding distance of a solution is the sum of its individual objectives’ distances which are computed as the absolute normalized differences between the solution and its closest neighbors. Then, the solutions with the greatest crowding distance are added to \(P_{t+1}\). This ensures a uniform spread-out of the front throughout the various stages of the algorithm. Overall, in order for a solution to be preferred to another one it has to belong to a better non-domination front or to have a larger crowding distance in case the two belong to the same front. Algorithm 1 describes a single NSGA-II iteration for the t-th generation. Such process is iterated until a stopping criterion is met.

NEMO (Branke et al. 2015) is an interactive evolutionary hybrid which combines NSGA-II with IMO approaches based on the principle of ordinal regression. The major innovation of NEMO when compared to NSGA-II consists in asking a (single) DM at regular intervals to compare a pair of solutions (note that set A is composed of solutions from the current population). The accumulated preference information is used to constrain the space of compatible value functions.

In what follows, we focus on NEMO-0 and NEMO-II (see Branke et al. 2015, 2016) that will be extended in our proposal. We neglect NEMO-I (Branke et al. 2015), because it needs to solve a prohibitively large number of Linear Programming (LP) problems, which makes it infeasible for dealing with real-world optimization problems.

Alike NSGA-II, NEMO-0 uses the Pareto fronts as a primary criterion to rank individuals. Then, the algorithm selects a representative additive general value function \(U^{{\textit{REP}}}\) (Kadziński et al. 2012), and the solutions within each Pareto front \({\mathcal {F}}_i\) are ranked using \(\mathtt{sort}({\mathcal {F}}_\mathtt{i}, \mathtt{U}^{\mathtt{REP}}(\mathtt{a}))\) (i.e., the greater \(U^{{\textit{REP}}}(a)\), the better the solution a). Differently, NEMO-II uses the levels of potential optimality and crowding distance as the two criteria to judge individuals in terms of their suitability for inclusion in the next population.

In this subsection, we use a convex version of DTLZ2-2D to illustrate how the proposed approaches bias the search towards a sample of all Pareto-optimal solutions which is relevant for the DMs. We assume that the true linear value functions of three DMs are parameterized with the following weights \((w_1^k, w_2^k)\) for \(k=1,2,3\): \(DM_1 - (0.7,0.3)\), \(DM_2 - (0.6,0.4)\), and \(DM_3 - (0.2,0.8)\). Intuitively, the greater the weight, the more important it is to minimize the respective objective.

Figure 1 shows the results for five variants of NEMO-GROUP after 500 generations. As can be seen, NSGA-II approximates the whole Pareto front, whereas all variants of NEMO-GROUP are focused on the solutions preferred to the DMs. Since IND evolves a separate sub-population for each DM, the final population it delivers is composed of three clearly disjoint sets of solutions, each containing individuals which are most preferred to a particular DM. For algorithms evolving a joint population for the whole group, the final set of solutions is narrowed to a single small part of the Pareto front which can be seen as the best compromise for all DMs. However, these approaches differ in terms of both the region of the Pareto front to which they converge as well as the dispersion of a final population. This confirms the flexibility of the interactive evolutionary hybrids in a group decision context. In particular, REP-UT, ADV-UT, and ADV-EG converged to a part of the front which is more favorable for \(DM_1\) and \(DM_2\) whose preferences are consistent to a great extent. On the contrary, the population constructed with REP-EG is located in the central part of the objective space, because the preference information of \(DM_3\) significantly affects the convergence of this algorithm. Moreover, the population obtained with REP-UT is more stretched due to the utilitarian aggregation of the DMs’ individual representative value functions.

To demonstrate the convergence to the Pareto front over time, for REP-EG and ADV-UT, we additionally depict the populations obtained after 50 and 300 generations (see top-right corner of Fig. 1). These clearly demonstrate the improvement of solutions during the evolutionary search as well as constraining the population due to incorporation of DMs’ preference information into the evolutionary search.

In this subsection, we study the evolution of utilitarian values of the best-of-population and average-in-population solutions in successive generations. These convergence factors permit to assess the performance of different variants of NEMO-GROUP from the point of view of a whole group of DMs. On the one hand, the best solution in the returned population may be perceived as a default outcome of the method that is most likely to be accepted by the DMs. On the other hand, an average quality of the individuals contained in the population reveals if the search has been appropriately focused on the group consensus solutions (Branke et al. 2015). The algorithms are compared for the DTLZ2-3D and DTLZ4-3D problems with the number of DMs ranging between 2 and 7. Let us emphasize that DLTZ4 is considered more challenging than DTLZ2.

Figures 2 and 3 present the convergence plots for, respectively, value of the best solution and average value of all solutions in the population for DTLZ2-3D with three DMs. These plots demonstrate when different approaches start to converge towards the Pareto front, what is their convergence speed measured in terms of a change of a utilitarian value, and what is value of the solution(s) at which their performance stabilizes. Nonetheless, to compare the performance of proposed approaches for various benchmark problems and different numbers of DMs, we focus on the precise measures derived from the convergence plots.

First, we refer to the minimal values obtained throughout the 500 generations (see Table 2). When it comes to the best utilitarian solution obtained during the optimization run (i.e., the minimal best-of-population value), the variants of NEMO-GROUP which evolve a joint population for all DMs significantly outperform NSGA-II and NEMO-GROUP-IND which, respectively, approximate an entire Pareto front or evolve a sub-population individually for each DM. Thus, it is beneficial to integrate user preferences and to seek for the group consensus solution already during the evolutionary search. The greater the number of DMs, the more evident these conclusions are.

The best performing variants of NEMO-GROUP are ADV-UT, REP-UT, and PO-UT. The slight differences between these methods are statistically insignificant for most considered settings. These approaches aggregate the evaluations of each solution conducted individually for each DM with, respectively, the per-solution most advantageous value function, the representative value function approximating the DM’s true preference model, or the front of potential optimality the solution belongs to. Thus, to discover a solution which is on average perceived well by the group members, when judging the individuals in terms of their suitability for inclusion in the next population, one should apply the utilitarian measures. Indeed, REP-UT, ADV-UT, and PO-UT outperform their egalitarian counterparts: REP-EG, ADV-EG, and PO-EG, respectively. Finally, the worst performing variants of NEMO-GROUP in terms of the best-of-population value are REP-EPS and REP-MAX. This indicates that construction of a joint single representative value functions for all group members may bias the search to the less relevant regions of the Pareto front. Overall, our results confirm that it is more advantageous to aggregate the potentially conflicting viewpoints of different DMs within the sorting procedures of the evolutionary algorithm rather than when inferring the DMs’ preference model.

When comprehensively judging the returned population of solutions being most favorable from the point of view of the whole group (i.e., the best average-in-population value), again REP-UT, ADV-UT, and PO-UT perform the best in view of the majority of considered problem settings. Obviously, for all methods a single best solution is clearly better than a complete best population. For example, the comprehensive utilitarian values of the best solution and population for REP-UT, DTLZ4-3D and 3 DMs are equal to, respectively, 0.3748 and 0.3814. When this difference is relatively small (see, e.g., ADV-EG), the constructed population is well focused, whereas higher differences (see, e.g., REP-EPS) suggest greater dispersion of the constructed solutions in the objective space.

Overall, when comprehensively evaluating the whole population rather than a single solution, the differences in the performance of various methods become more evident. The benefits of integrating the DMs’ preference information into the evolutionary search are best confirmed with the average-in-population value of different NEMO-GROUP variants being significantly better than the best-of-population value for NSGA-II. For example, for DTLZ2-3D and 5 DMs the value of the best NSGA-II solution is 0.4502, while the average value of all solutions in the population of ADV-UT is 0.3941.

Intuitively, the comparison of results for different numbers of DMs indicates that the more DMs are involved in the optimization process, the worse are the utilitarian values of the best returned individual and population (i.e., the worse is their average perception by the group members). For example, when ranging the number of DMs from 2 to 7 for DTLZ2-3D, the value of the best solution constructed with REP-UT is, respectively, 0.3547, 0.3703, 0.3830, 0.3917, 0.3995, and 0.4054.

However, this is mainly due to the lower value of the optimal utilitarian solution that can be constructed when preferences of more DMs are accounted. It is clearly visible in Fig. 4 which compares the values of such optimal solutions and the best individuals constructed with a few variants of NEMO-GROUP for different numbers of DMs for DTLZ2-3D. For example, when 2, 4 or 6 DMs are involved, the utilitarian value of the optimal solution is equal to, respectively, 0.3506, 0.3798, and 0.3971. Clearly, NEMO-GROUP cannot do any better. However, the analysis of Fig. 4 indicates that for the best performing approaches (REP-UT, ADV-UT, and PO-UT) the absolute value difference of the best returned individual from the optimal solution decreases with the increase in the number of DMs. For example, for REP-UT for 2, 4 or 6 DMs, it is equal to, respectively, 0.0040, 0.0035, and 0.0024. This suggests that the proposed algorithms scale up well to greater numbers of DMs.

As the other set of measures derived from the convergence plots we consider the average group utilitarian values observed throughout 500 generations (see Table 3). They quantify the overall performance of the algorithms from the point of view of either the best solution or a complete population returned after each generation. Since the value to which the algorithms converge highly affects the overall performance, the conclusions about the best and worst performing algorithms are analogous to the case of considering only the best results. The important differences are the following:

In this subsection, we study the performance of NEMO-GROUP in terms of egalitarian values of the best-of-population and average-in-population solutions. Thus, instead of measuring the quality of solutions as the average (or sum) of individual judgments, we compute the quality that each solution represents to the whole group with respect to the least satisfied DM. Otherwise, we use the same experimental setting as in Sect. 4.2.

The best egalitarian values of a single solution and an entire population obtained by different algorithms throughout 500 generations are provided in Table 4. Obviously, they are higher (less advantageous) than the respective utilitarian values presented in Table 2.

For all considered problems and numbers of DMs, REP-EG significantly outperforms the remaining algorithms. Let us remind that when judging individuals in terms of their suitability for inclusion in the next population, REP-EG accounts for the representative value function of the least satisfied DM. Since this function aims at approximating the DM’s true preference model, when constructing the population REP-EG optimizes a quality measure which is consistent with the egalitarian group value function. This characteristic is central to its competitive advantage for the considered three-dimensional benchmark problems.

Interestingly, although accounting for the least satisfied DM during the evolutionary search, PO-EG and ADV-EG perform worse than their utilitarian counterparts PO-UT and ADV-UT, respectively. This suggests that evaluation of solutions in terms of the worst fronts they belong to or the least advantage they have over the remaining solutions, is not sufficient for discovering individuals with competitive egalitarian values. Overall, these measures are less discriminant for the comparison of different solutions than their utilitarian counterparts, and, thus, they fail to introduce a sufficiently strong selection pressure into the search. Conversely, with the focus on constructing the solutions which are acceptable for all DMs, REP-UT, ADV-UT, and PO-UT perform reasonably well also in terms of an egalitarian value.

Figure 5 demonstrates the egalitarian values of optimal solution and the best individuals constructed with different variants of NEMO-GROUP for DTLZ2-3D for the number of DMs ranging from 2 to 7. Analogously to the case of using a utilitarian value function, the more DMs are involved, the worse are the egalitarian values of the best possible solutions as well as the ones returned by the algorithms. Interestingly, whatever the number of DMs, REP-EG is able to construct a solution which is very close to the optimal one. For the remaining approaches, the gap from the optimal solution, in general, slightly increases when more DMs are involved.

In this subsection, we demonstrate the impact that including additional objectives and considering different types of true DMs’ value functions (i.e., linear or Chebycheff ones) has on the convergence of proposed algorithms. To save space, we compare NSGA-II with a representative subset of NEMO-GROUP variants (REP-UT, REP-EG, ADV-UT, ADV-EG, and IND) which use dominance relation as the first sorting procedure. Their performance is verified on DTLZ2 with 3, 5, and 7 objectives in view of utilitarian and egalitarian comprehensive value functions for 3 DMs. We focus on the average best-in-population solution throughout 500 generations.

First, we refer to the values obtained when simulating the DMs with linear value functions (see Table 5). For all considered algorithms, both utilitarian and egalitarian best-of-population values become worse with the increase in the number of considered objectives. Intuitively, the more dimensions are involved, the more challenging it is to construct the solutions which are relevant from the point of view of the whole group.

As the number of objectives increases, it becomes more difficult to identify the complete Pareto front. Since an increasing proportion of all feasible solution becomes non-dominated, the dominance relation fails to sufficiently discriminate the solutions within the evolutionary algorithms. As a result, the decrease in performance of NSGA-II is significant, and the constructed solutions are far from the true Pareto front. On the contrary, integrating DMs’ preferences into evolutionary search allows to re-introduce the necessary selection pressure. Indeed, the advantage of the interactive evolutionary hybrids over NSGA-II becomes more evident in more dimensional problems.

When it comes to the utilitarian best-of-population value, ADV-UT is the best performer whatever the number of objectives. Interestingly, when more objectives are considered ADV-EG is gaining a competitive advantage over the methods which employ the representative value functions. Thus, when the number of objectives increases, it is more beneficial to exploit a set of compatible value functions. This seems to ensure greater robustness when indicating more promising directions for optimization.

The latter conclusion is strengthened by the analysis of egalitarian best-of-population values. As indicated in Sect. 4.3, REP-EG was the best performer for a three-dimensional DTLZ2. While still performing better than REP-UT for all considered numbers of objectives, already with 5 dimensions REP-EG is outperformed by ADV-UT and for DTLZ2-7D its convergence is even worse than that of ADV-EG.

The status of ADV-UT as an overall best performer among the considered variants of NEMO-GROUP is confirmed by the results obtained when simulating the DMs with true Chebycheff functions (see Table 6). ADV-UT outperforms other methods for all considered settings. The relative comparison of the remaining approaches is the same as for the linear value functions. In particular, REP-UT is slightly better than REP-EG for the utilitarian function, whereas for the egalitarian one this order is inverse.

Apparently, the average best-in-population values presented in Table 6 decrease with the increase in the number of objectives. However, this is due to the internal definition of the Chebycheff function. That is, when more dimensions are involved, the maximal value this function can take decreases. In our experiments, for 3, 5, and 7 objectives, these maximal values were equal to, respectively, 0.6278, 0.4538, and 0.3447 for the utilitarian group value function, and 0.7977, 0.5585, and 0.4329 for the egalitarian one. Thus, the ability of algorithms to construct group consensus solutions should be judged while referring to these maximal values. For all considered variants of NEMO-GROUP the value of the best solution they construct becomes closer to the maximal possible value when more objectives are involved. For example, for the utilitarian value function for ADV-UT the respective differences are equal to 0.4046 (\({=}0.6278-0.2232\)) for 3D, 0.2475 (\({=}0.4538-0.2063\)) for 5D, and 0.1676 (\({=}0.3447-0.1771\)) for 7D. Thus, again, our results confirm that with more objectives, it is more challenging to find a group consensus solution.

In this subsection, we study the potential of some proposed approaches—REP-UT and ADV-UT—for incorporating the DMs’ weights, thus, differentiating the importance of group members. Such investigation makes sense in the context of utilitarian group value function.

Let us first illustrate how REP-UT and ADV-UT are able to bias the search depending on the weights assigned to the DMs. We consider three DMs whose linear value functions are parameterized with the following weights \((w_1^k, w_2^k)\) for \(k=1,2,3\): \(DM_1 - (0.7,0.3)\), \(DM_2 - (0.4,0.6)\), and \(DM_3 - (0.2,0.8)\). Moreover, we account for the following three vectors of weights \((W_{DM_1}, W_{DM_2}, W_{DM_3})\) assigned to the DMs: \(W_{Set~I} = (1/3, 1/3, 1/3)\), \(W_{Set~\textit{II}} = (0.1, 0.45, 0.45)\), and \(W_{Set~\textit{III}} = (0.7, 0.2, 0.1)\). Thus, in the first considered scenario all DMs play the same role in the committee, for the second set of weights – the role of \(DM_1\) is rather neglected, while for the third set – \(DM_1\) can be considered as a dictator.

Figure 6 shows the results of NSGA-II, NEMO-0 for the three DMs as well as REP-UT and ADV-UT with different sets of DMs’ weights on DTLZ2-2D after 500 generations. Whatever the vector of DMs’ weights, REP-UT and ADV-UT are able to focus the search on a single small part of the Pareto front reflecting the relative importance of the DMs. Thus, with the same weights of DMs, the population for \(W_{Set~I}\) is rather central in the objective space. For \(W_{Set~\textit{II}}\)—the returned solutions are situated between the regions that are relevant for \(DM_2\) and \(DM_3\) (though closer to the part which is most preferred by \(DM_2\) due to the marginal impact of partial preferences of \(DM_1\)). Finally, the population returned for \(W_{Set~\textit{III}}\) is very close to the solutions constructed individually for \(DM_1\) whose weight (0.7) is much greater that the weight of the remaining two DMs considered jointly. Note, however, that there are slight differences between REP-UT and ADV-UT with respect to the parts of the Pareto front to which they converge.

To experimentally evaluate the impact of incorporating DMs’ weight into the interactive evolutionary hybrids, we consider DTLZ2-3D with three DMs whose Chebycheff value functions are parameterized with the following weights \((w_1^k, w_2^k, w_3^k)\) for \(k=1,2,3\): \(DM_1 - (0.1,0.1,0.8)\), \(DM_2 - (0.3,0.4,0.3)\), and \(DM_3 - (0.4,0.3, 0.3)\). We also consider two sets of DMs’ weights: \(W_{Set~II}\) and \(W_{Set~\textit{III}}\).

We evaluate the algorithms in terms of the minimal utilitarian best-in-population and average-of-population values they obtain throughout 500 generations (see Table 7). Obviously, when evaluating the returned individuals with a utilitarian group value function, we account for the weights assigned to the DMs. In this perspective, the variants of REP-UT and AVG-UT which incorporate the DMs’ weights already during the evolutionary search (called W-REP-UT and W-AVG-UT) attain significantly better results than their counterparts assuming that all DMs play the same role in the committee. This proves both the flexibility of proposed algorithms and the benefits of accounting for the DMs’ weights when judging the individuals in the evolutionary algorithms.

Overall, W-ADV-UT attains the best results for all considered problem settings in terms of both a single solution and a complete population. The advantage of NEMO-GROUP variants incorporating the DMs’ weights is more evident for \(W_{Set~\textit{III}}\) where \(DM_1\) can be considered as a dictator. Nonetheless, to prove that the preferences of the remaining (less important) DMs do influence the search, one can refer to the best-in-population value for IND. Evolving a sub-population for each DM individually, this method is able to discover solutions which are considered reasonably good by the whole group (assuming the prevailing role of \(DM_1\)). Indeed, for \(W_{Set~\textit{III}}\), IND is considered better than REP-UT and ADV-UT. However, it is still significantly worse than W-REP-UT and W-ADV-UT, which confirms that the impact of \(DM_2\) and \(DM_3\) in these algorithms is non-negligible. Obviously, when taking into account a complete population, NSGA-II and IND are significantly outperformed by all considered variants of NEMO-GROUP.

In this subsection, we evaluate the performance of REP-UT and ADV-UT for different elicitation intervals in \(\{10, 20, 30\}\) and starting generations for preference elicitation in \(\{0, 100, 200, 300\}\). In Table 8, we provide mean utilitarian value differences of the best-in-population solutions constructed by these methods with respect to the true utilitarian solution for DTLZ2-3D discovered with LP techniques. The results indicate that NEMO-GROUP is not always able to find the true utilitarian solution, but the observed value differences are very small.

As a general rule, the more often the DMs are questioned, the more advantageous is the best solution (with the exception of REP-UT for SGE \(=\) 100 or 200). Moreover, delaying the elicitation by 100 or 200 generation does not significantly influence the best-in-population value. In fact, for both algorithms, our results indicate that better solutions can be found when delaying the preference elicitation process to SGE \(=\) 100. Nevertheless, with SGE \(=\) 300 and too rare questioning of the DMs, the convergence of algorithms is affected negatively.

For all EIs \(>0\) and SGEs \(>0\), the convergence of algorithms over time to the most preferred region is affected significantly. To support this claim, in Fig. 7, we provide the convergence plots for REP-UT concerning the value difference between the true utilitarian solution and the best-in-population solution, for different EIs and SGEs.

Firstly, the lower the EI, the faster the convergence, i.e., the sooner the best solution becomes competitive with the true utilitarian solution. However, the plots indicate that in the initial generations when the evolutionary search is still chaotic, it is more beneficial to question the DMs rarely (see the main part of Fig. 7). Only once the population is well distributed (for our problem, this happens after 100 generations), the preference elicitation should be performed more often. Secondly, when the preference elicitation is delayed (SGE \(> 0\)), one could observe a visible difference in the convergence before and after the SGE (see the top-right corner of Fig. 7).

To compare the convergence of algorithms for different EIs and SGEs, Table 9 indicates the number of generations for which the average best-in-population value reaches two arbitrarily selected value distances, 0.015 and 0.01, from the true utilitarian solution. For example, when the preference elicitation is performed every 10 generations with \({\textit{SGE}}=0\), the convergence indicator is 0.015 already before 175 generations for both REP-UT and ADV-UT, whereas with EI \(=\) 30 or SGE \(=\) 200, this happens only after 300 generations. This confirms the benefit that preference information can have in speeding up the optimization.

However, when preference elicitation is delayed (SGE \(> 0\)), one may question the DMs less often without deteriorating the algorithm’ convergence (see, e.g., the value difference of 0.01 for REP-UT with SGE \(=\) 200 and EI \(=\) 10 or 20 or for ADV-UT with SGE \(=\) 100 and EI \(=\) 20 or 30). These results confirm that in some scenarios, a satisfactory solution can be discovered faster even if the preference elicitation is started later. Nonetheless, with high SGEs the elicitation cannot be performed too rarely as the algorithms fail to discover a competitive solution.

In addition to considering the number of generations for which an average convergence indicator reaches the relative difference of 0.01 or 0.015, we analyzed the number of pairs that would have been compared by each DM until this stage. These numbers are provided in Table 9. They indicate that the cognitive effort of the DMs may be reduced when suitably adjusting EI and SGE. Most importantly, the questioning of the DMs should be delayed until the population is well distributed. For example, with \(\hbox {(SGE, EI)}=(200,30)\) the number of pairs to be compared by the DMs can be reduced about 3 or 4 times for, respectively, REP-UT and ADV-UT when referring to the basic scenario with \(\hbox {(SGE, EI)}=(0,10)\). Nonetheless, delaying the preference elicitation too much or performing it too rarely may not reduce the number of pairs that need to be compared by the DMs, while deteriorating the convergence (see, e.g., ADV-UT for \(\hbox {(SGE, EI)}=(200,10)\) and (300, 10) or (0, 20) and (0, 30)).