PaperlayerView exact revision on arXiv

Source-linked AI summary

An Interactive Evolutionary Multiobjective Optimization Algorithm Based on Interpretable Active Preference Learning

Thomas Quadt, Boris Čule, Roy Lindelauf, Herman Monsuur, Mark Voskuijl

arXiv:2610.35470v1cs.NEcs.AI

TL;DR

Interactive evolutionary multi-objective optimization can help decision-makers find preferred solutions, but pairwise preference elicitation must be efficient and black-box models can obscure how preferences shape decisions. This paper learns a globally interpretable tree from pairwise comparisons and integrates it with NSGA-II and NSGA-III; experiments report a favorable best-point outcome with a trade-off in average utility, and an engineering case study illustrates model interpretability.

  • Problem

    Interactive methods must learn preferences from a small number of cognitively simple judgments, while black-box models can obscure how preferences led to a solution in critical decisions.

    Source: §I · p. 1

  • Method

    The method actively learns a globally interpretable tree from pairwise comparisons and uses its preference rankings in NSGA-II or NSGA-III selection to guide search toward the region of interest.

    Source: §I · p. 2, §VI · p. 11

  • Results

    Across ZDT, DTLZ, and WFG benchmarks, DT-PBO-NSGA performs particularly well on lower-dimensional problems and has better best-point utility but slightly worse average utility than DT-EMOA and PBO-R-NSGA-III in higher dimensions.

    Source: §VI · p. 11

  • Takeaways & Limitations

    The car-crashworthiness case study shows that inspecting the learned tree can reveal which objectives drive the decision-maker’s preferences.

    Source: §I · p. 2

    The axis-aligned tree may have difficulty with preferences that do not follow objective axes, and it does not inherently enforce monotonicity.

    Source: §VI · p. 11

Abstract

from arXiv · show

Many decision-making tasks are inherently multi-objective. Interactive evolutionary multi-objective optimization algorithms (iEMOAs) are particularly well-suited to help the decision-maker find their most preferred solution. However, many of these algorithms employ black-box preference models. For high-stakes decision-making tasks, like healthcare and defense, a high level of transparency is needed, for instance to support accountability. We propose an interpretable iEMOA which uses active learning to efficiently learn a tree-based preference model directly from pairwise comparisons. The survival operator of NSGA-II and NSGA-III is extended with the learned preference model to guide the algorithm towards the region of interest. An extensive experimental study compares the proposed method to a state-of-the-art black-box model and a state-of-the-art interpretable model. Results indicate that our proposed model outperforms the alternatives in terms of finding the most preferred solution at the cost of a slightly worse average final population. Finally, a case study on a real-life engineering problem illustrates how inspecting the learned model reveals which objectives drive the decision-maker's preferences.

I. INTRODUCTION

Interactive evolutionary multi-objective optimization can use a decision-maker’s preferences to focus search, but eliciting those preferences and explaining black-box models remain challenges. The paper proposes an interpretable, actively learned preference model and evaluates it alongside related approaches.

I. INTRODUCTION

  • Interactive methods alternate optimization and preference elicitation, helping decision-makers understand trade-offs and feasibility before choosing a solution.Preference information can reduce search to a region of interest, while a decision-maker’s limited prior knowledge can make preferences inaccurate.Source: §I · p. 1
  • Pairwise comparisons are easier to provide than numerical ratings, so preference models should learn from as few cognitively simple judgments as possible.Decision-maker time is costly, and directly rating solutions can be cognitively demanding.Source: §I · p. 1
  • Black-box interactive methods can leave decision-makers unable to see how preferences led to a solution, a concern for critical decisions where trust and justification matter.Explanations may also help decision-makers articulate and refine preferences; the paper describes explainability in iEMOAs as a new research area with few existing methods.Source: §I · pp. 1–2
  • DT-PBO-NSGA learns an interpretable tree from pairwise comparisons and uses its leaf rankings in NSGA-II or NSGA-III survival to guide search toward the preferred region.The authors report strong results on lower-dimensional benchmarks and a favorable trade-off as objectives increase, alongside a real-world engineering case study.Source: §I · p. 2

A. Type of Evolutionary Algorithm

  • The related-work review describes interactive EMOAs across algorithm types and covers a representative subset of 20 studies, not a comprehensive survey.It distinguishes dominance-, decomposition-, and indicator-based algorithms; dominance-based selection pressure degrades in higher dimensions as nearly all solutions become non-dominated.Source: §II · p. 2, A. Type of Evolutionary Algorithm · p. 2

B. Preference Model

Prior interpretable preference models trade off expressiveness, global interpretability, and query selection. The proposed approach uses one globally inspectable tree, indirect judgments, and active preference elicitation within NSGA algorithms.

B. Preference Model

  • Existing preference models can gain expressiveness at the cost of interpretability, while DT-EMOA offers local explanations but not a directly evident global view of the best regions.DT-EMOA predicts pairwise preference from feature differences, implicitly assuming constant trade-offs across objective ranges; other interpretable approaches constrain solutions to two classes, while a random forest sacrifices interpretability.Source: B. Preference Model · pp. 2–3

C. Preference Information

  • Indirect preference information commonly takes the form of pairwise comparisons or selecting a preferred solution from a set; Table I summarizes interactive algorithms using indirect judgments.The review focuses on indirect preference information because direct preference statements have been shown difficult to supply.Source: C. Preference Information · p. 3, Table I · p. 3

D. Question Selection

  • Active query selection balances exploration against exploitation because repeatedly asking about the current best solution risks a local optimum.Only RF-EMOA and PBO-R-NSGA-III among the reviewed methods use active learning; others use random, diverse, or greedy query choices.Source: D. Question Selection · p. 3

III. METHOD

  • The proposed method addresses limited expressiveness or local interpretability and non-active query selection with a globally interpretable regression tree and active preference elicitation.The full learned preference structure is represented by one inspectable tree, showing how preferences vary across objective space.Source: §III · p. 3
  • The method uses NSGA-II for bi-objective problems and NSGA-III for problems with three or more objectives, incorporating preference fronts into their existing front-based selection.This alignment lets preference information steer the search without assuming a functional form for the decision-maker’s preferences.Source: §III · pp. 3–4

A. Preference Model

The preference model learns a regression tree from pairwise comparisons, estimating leaf preferences probabilistically and selecting informative comparisons actively. Its splitting procedure separates winners from non-winners while discarding comparisons already distinguished by a split.

A. Preference Model

  • A semi-Bayesian regression tree partitions objective space into leaves and estimates their values probabilistically to represent uncertainty and support active learning.The model is repeatedly updated from an initial set of pairwise comparisons as an acquisition function selects the next informative comparison, until a stopping criterion is met.Source: A. Preference Model · p. 4

1) Partitioning the Objective Space:

  • A custom split score measures how well a candidate partition separates preferred items from non-preferred items, replacing numerical-label impurity measures.The tree greedily chooses the feature and threshold maximizing its consistency score.Source: A. Preference Model · p. 4, 1) Partitioning the Objective Space · p. 4
  • After splitting, only comparisons whose pairs lie entirely on one side are passed to child nodes; straddling pairs are discarded because the split already differentiates them.Discarding those comparisons reduces internal data and tree size, yielding shallower trees without requiring pre- or post-pruning, though depth and split thresholds can be set manually.Source: 1) Partitioning the Objective Space · p. 4

2) Finding the Probabilistic Leaf Estimates:

Leaf utilities are estimated probabilistically from pairwise-comparison data using Gaussian assumptions and a Laplace approximation. A zero-sum constraint removes the unidentifiable constant-shift direction, while the noise-to-prior variance ratio primarily affects utility scale.

2) Finding the Probabilistic Leaf Estimates:

  • Each leaf is assigned an independent zero-mean Gaussian prior, and pairwise observations are modeled with homoskedastic Gaussian noise under independent preference statements.Source: 2) Finding the Probabilistic Leaf… · p. 4
  • Because the posterior is computationally intractable, a Laplace approximation represents it as a Gaussian centered at the maximum a posteriori estimate.Source: 2) Finding the Probabilistic Leaf… · p. 5
  • The likelihood is invariant to a constant shift in leaf values, so constraining their sum to zero removes that direction and fixes the model’s scale.The fitting procedure depends on σ_noise²/σ_prior² rather than the two hyperparameters separately; for non-extreme ratios, the main effect is utility scale, not relative leaf ordering.Source: 2) Finding the Probabilistic Leaf… · p. 5

3) Active learning:

The acquisition strategy adapts qEUBO for the tree’s discrete leaves by adding a structural-refinement term. Comparisons between leaves support exploration, while within-leaf comparisons target exploitation in the current best leaf.

3) Active learning:

  • The acquisition function adds expected within-leaf consistency-score change to qEUBO because the tree cannot distinguish points assigned to the same leaf.The structural term is active only when both candidate points fall in the same leaf.Source: 3) Active learning · p. 5
  • Between-leaf comparisons support exploration, while within-leaf comparisons target exploitation and are restricted to the current best leaf.After choosing leaves, points are sampled at random from those leaves, including points in the current population or external archive.Source: 3) Active learning · p. 5

4) Working Example:

The working example shows how pairwise comparisons determine a ranked partition of objective space, while the algorithm alternates preference elicitation with evolutionary search. Its operators prioritize Pareto-optimality, preference, and diversity, supported by an archive that retains solutions across the front.

4) Working Example:

  • The example’s learned tree models the region 0.3 ≤ x < 0.6 as most preferred from three pairwise comparisons on ZDT1.The two candidate split thresholds are 0.3 and 0.6; the tree is built by selecting the split with the higher consistency score.Source: 4) Working Example · p. 5, Figure 2 · p. 6

B. Integration with Evolutionary Algorithm

  • The procedure alternates an initial NSGA estimate of the Pareto front, preference elicitation, and preference-guided optimization until the decision-maker is satisfied.After the first randomly chosen comparisons, subsequent questions follow the active-learning strategy; the archive preserves representative solutions across the front.Source: B. Integration with Evolutionary… · p. 6
  • Survival prioritizes Pareto-optimality, then preference-ranked regions, then diversity, using crowding distance for NSGA-II or reference-direction sorting for NSGA-III.Preference fronts are applied within the current domination front.Source: B. Integration with Evolutionary… · p. 6
  • Binary-tournament mating selection compares dominance first, preference second, and diversity-based score last.Source: B. Integration with Evolutionary… · p. 6
  • The external archive retains representative non-dominated solutions across the Pareto front, supporting between-leaf comparisons, detection of dominated solutions, and response to preference shifts.The archive is maintained by merging it with the current population and applying regular NSGA survival to preserve a diverse non-dominated representation.Source: B. Integration with Evolutionary… · pp. 6–7
  • After 1,000 initial generations and two preference comparisons, the example’s population converges to the best leaf within 100 further generations; across four elicitation stages, the region of interest narrows.The figure’s arrows mark queried comparisons, with the arrow endpoint indicating the preferred point.Source: B. Integration with Evolutionary… · p. 7, Figure 5 · p. 7

IV. EXPERIMENTAL EVALUATION

The evaluation uses artificial decision-makers, repeated trials, and benchmark suites covering varied Pareto-front geometries and decision-space characteristics. It compares DT-PBO-NSGA with interpretable and black-box preference-learning baselines under aligned evolutionary settings.

A. Experimental Settings

  • The study samples 50 artificial decision-makers and runs 50 trials per problem to assess robustness.The preference statements are generated from artificial decision-makers’ utility functions.Source: A. Experimental Settings · p. 7
  • The interpretable baseline DT-EMOA learns a tree over objective-vector differences, whereas PBO-R-NSGA-III uses a Gaussian-process preference model.The comparison uses DT-EMOA rather than its random-forest extension RF-EMOA to retain a highly interpretable baseline; elicitation burdens are matched through pairwise-comparison counts.Source: A. Experimental Settings · p. 7
  • The comparison aligns NSGA-II and NSGA-III base settings, uses four preference-elicitation rounds, and runs 100 optimization generations after each round.The first elicitation follows G initial generations, with M questions per round; DT-PBO-NSGA sets the exploration–exploitation parameter λ to 1.5.Source: A. Experimental Settings · pp. 7–8
  • The ZDT suite covers bi-objective cases, while DTLZ and WFG test three to five objectives; pairwise comparisons are restricted to at most five objectives.The suites span varied front geometries, and WFG adds decision-space transformations such as bias, deception, non-separability, and parameter dependencies.Source: A. Experimental Settings · p. 8
  • Artificial preferences come from Chebyshev and Stewart utility functions, with four Stewart decision-maker types representing different trade-off and threshold behaviors.The algorithms receive pairwise preference statements generated from these functions, not access to the utility functions themselves.Source: A. Experimental Settings · p. 8

B. Evaluation

DT-PBO-NSGA’s relative performance depends on dimensionality and metric: its best-point utility remains strong as objectives increase, while average utility weakens. Its broader final populations help explain this trade-off, and results also vary with utility-function shape.

Evaluation metrics

  • Performance is evaluated by mean utility and best-point utility, with medians used across runs and dimensionalities to reduce the effect of outlier bad runs.Mean utility is the final population’s average utility; best-point utility is its minimum utility.Source: B. Evaluation · p. 8

Performance across Problem Dimensionality

  • As dimensionality rises, DT-PBO-NSGA’s average-utility performance declines relative to competitors, while its best-point utility advantage remains strong.Against DT-EMOA, best-point utility strongly favors DT-PBO-NSGA from three objectives onward; against PBO-R-NSGA-III, the advantage emerges from three objectives onward.Source: B. Evaluation · pp. 8–9, Table III · p. 9
  • For 4-objective problems, DT-PBO-NSGA reduces average utility by approximately 41% with a 7% increase in best-point utility, versus larger trade-offs for both baselines.Figure 6 compares relative performance to standard NSGA; for 5-objective problems, DT-PBO-NSGA’s corresponding values are 34% and 22%.Source: B. Evaluation · p. 9, Figure 6 · p. 9
  • DT-PBO-NSGA retains a larger final-population bounding-box diagonal as dimensionality increases, preserving a broader region of objective space.The broader population is associated with higher average utility and a greater chance of including the most preferred solution; Figure 7 encodes region size by bounding-box diagonal.Source: B. Evaluation · p. 9, Figure 7 · p. 10
  • All preference-based methods have worse best-point utility than standard NSGA, which consistently identifies at least one solution close to the most preferred solution.Restricting search to an estimated region of interest can miss that solution when the estimate differs slightly from the true region.Source: B. Evaluation · p. 9

Performance across Utility Functions

  • DT-EMOA performs particularly poorly on best-point utility for Stewart cases 3 and 4, whose broad near-optimal regions and steep extremes make pairwise differences less informative.DT-PBO-NSGA uses absolute objective values and has strong best-point ranks on these cases.Source: B. Evaluation · pp. 9–10, Table IV · p. 10

Supplementary Results

  • The supplementary results identify poor DT-PBO-NSGA performance on DTLZ5 and DTLZ6, where the Pareto front is a curved single curve that is difficult for axis-aligned splits to capture.The supplementary analysis also reports robustness of all three methods to generated Gaussian answer noise and recommends decreasing λ as noise increases.Source: B. Evaluation · p. 10

V. CASE STUDY

The RE34 case study applies DT-PBO-NSGA to vehicle crashworthiness with three minimized objectives. After 12 pairwise questions, its learned tree identifies a compact region near the artificial decision-maker’s most preferred solution and exposes preference rules.

Case-study problem

  • RE34 concerns vehicle crashworthiness, with minimized objectives for vehicle weight, crash-induced acceleration/deceleration, and passenger-compartment intrusion.Lower acceleration/deceleration reduces occupant forces, lower intrusion reduces deformation and injury risk, and lower weight supports a lightweight design.Source: §V · p. 10

Case-study setup

  • Using the main-experiment settings (4 × 3 pairwise comparisons) with a Chebyshev artificial DM, the algorithm asked 12 questions total, then yielded a final population and learned decision tree.Source: §V · p. 10

Case-study findings

  • The learned region of interest is relatively small compared with the global Pareto front and centered on the decision-maker’s most preferred point.Figure 8 shows the final population and the true Pareto front for the crashworthiness problem.Source: §V · p. 11
  • The tree ranks vehicles with cabin intrusion below 0.07 m, collision deceleration below 8.33 m/s, and weight at least 1676.34 kg among the best.Figure 9 represents leaf utility predictions with Gaussian means and standard deviations; the best leaf also displays population count and region information.Source: §V · p. 11, Figure 9 · p. 11

VI. CONCLUSION

DT-PBO-NSGA combines active pairwise preference learning with a tree-based model to guide NSGA toward a region of interest. Across benchmarks it offers a trade-off between average and best-point utility, while the RE34 case study shows how the learned rules can expose preference drivers.

VI. CONCLUSION

  • DT-PBO-NSGA learns an interpretable tree from pairwise comparisons, ranks its leaves, and uses preference-based sorting between NSGA’s dominance- and diversity-based sorting.The learned ranking adapts survival and mating selection to guide the population toward the identified region of interest.Source: §VI · p. 11
  • Across ZDT, DTLZ, and WFG benchmarks, DT-PBO-NSGA performs particularly well at lower dimensionality and retains better best-point utility in higher dimensions despite slightly worse average utility.Its more conservative population reduction preserves a broader objective-space region, increasing the likelihood of finding the best solution.Source: §VI · p. 11
  • DT-EMOA performs poorly on Stewart utility types 3 and 4, while DT-PBO-NSGA can model their positional dependencies by learning from absolute objective vectors.Source: §VI · p. 11
  • Axis-aligned tree splits can struggle with preferences that do not follow those axes, and the learned tree does not inherently enforce monotonicity.The conclusion also calls for testing interpretability and performance with real-world decision-makers.Source: §VI · pp. 11–12

APPENDIX A ADDITIONAL EXPERIMENTS

Appendix experiments test robustness to noisy DM responses, vary the exploration–exploitation setting, and examine benchmark results and selected DTLZ cases. They show trade-offs between average utility and best-point utility, with outcomes also depending on problem geometry and DM noise.

A. Robustness against Noise

  • All three methods remain relatively robust to moderate DM noise, although performance generally decreases as noise increases.Noise was added independently to each object’s artificial-DM value before preference statements were determined.Source: A. Robustness against Noise · p. 15

B. Lambda ablation study

  • For noiseless DMs, very high λ improves average utility but worsens best-point utility versus λ = 1.5; for noisy DMs, conservative or balanced λ generally performs better.The reported noiseless trade-off is a 0.21 improvement in average utility alongside a 0.03 worsening in best-point utility.Source: Figure 11 · p. 15, B. Lambda ablation study · p. 15

D. Detailed Analysis of DTLZ1,2, and 7

  • After preference information is introduced, DT-EMOA’s selection pressure improves convergence, but it remains far behind the other methods on DTLZ1.Before preference information, NSGA-II struggles in higher dimensions because all solutions become non-dominated.Source: D. Detailed Analysis of DTLZ1,2, and 7 · p. 15
  • Average utility drops after preference rounds as the models converge toward the identified ROI, while best-point utility can rise when that ROI excludes the most preferred solution.The drops are usually smaller for DT-PBO-NSGA, indicating a larger ROI than those of DT-EMOA and PBO-R-NSGA-III.Source: D. Detailed Analysis of DTLZ1,2, and 7 · pp. 15–16

C. Synthetic Benchmark Results Aggregated per Problem

  • As dimensionality increases, PBO-R-NSGA-III and DT-EMOA have better average utility but worse best-point utility than DT-PBO-NSGA; DTLZ5 and DTLZ6 are exceptions.Both exceptions have Pareto-front geometry that largely reduces to a high-dimensional curve, which challenges DT-PBO-NSGA’s axis-aligned splits.Source: C. Synthetic Benchmark Results… · p. 15, Table V · p. 16

D. Detailed Analysis of DTLZ1,2, and 7

  • DT-PBO-NSGA’s broader ROI more often contains the best point, while DT-EMOA and PBO-R-NSGA-III can converge to smaller ROIs that miss it.This pattern also appears in the five-dimensional plots; one PBO-R-NSGA-III ROI is concentrated far from the best point.Source: D. Detailed Analysis of DTLZ1,2, and 7 · p. 16

APPENDIX B UTILITY FUNCTIONS VISUALIZED

Figure 15 compares utility values along the ZDT1 Pareto front for five randomly generated DMs per utility-function type.

APPENDIX B UTILITY FUNCTIONS VISUALIZED

  • Stewart cases 3 and 4 show long, flat valleys of near-optimal utility, bounded by steep increases toward the Pareto-front extremes.In some instances, those increases level off near the boundary.Source: Appendix B · p. 16
  • For Stewart cases 3 and 4, the utility effect of changing objective values depends strongly on a solution’s position along the front.Source: Appendix B · pp. 16–17
  • Chebyshev utility is piecewise linear with one kink at the most preferred point; Stewart cases 1 and 2 vary more gradually, though case 2 has sharp local steps near the optimum.The displayed profiles are for five randomly generated DMs per utility-function type.Source: Appendix B · p. 16, Figure 15 · p. 20
Loading 2610.35470v1…