PaperlayerView exact revision on arXiv

Source-linked AI summary

A Review of Evolutionary Multi-modal Multi-objective Optimization

Ryoji Tanabe, Hisao Ishibuchi

arXiv:2009.13347v1cs.NE

TL;DR

Existing MMOP studies are difficult to survey because many were conducted independently under different names and lacked explicit MMOP terminology. This paper reviews that literature, defines the problem framework, and discusses algorithms, test problems, indicators, and open issues. It concludes that MMOP research remains practically important but requires clearer definitions, broader analysis, and improved performance assessment.

  • Problem

    The MMOP literature is fragmented because many studies did not explicitly use the term MMOP, while the field's definition remains controversial.

  • Method

    The paper reviews evolutionary MMOP studies across definitions, algorithms, test problems, and performance indicators, including work published under different names.

  • Results

    The review identifies open issues, including limited performance analysis, uncertain algorithm behavior under different resource settings, and guidelines for designing MMOP test problems.

  • Takeaways & Limitations

    MMOP studies can draw useful clues from multi-modal single-objective optimization, while performance indicators must account for solution-space diversity as well as objective-space quality.

Abstract

from arXiv · show

Multi-modal multi-objective optimization aims to find all Pareto optimal solutions including overlapping solutions in the objective space. Multi-modal multi-objective optimization has been investigated in the evolutionary computation community since 2005. However, it is difficult to survey existing studies in this field because they have been independently conducted and do not explicitly use the term "multi-modal multi-objective optimization". To address this issue, this paper reviews existing studies of evolutionary multi-modal multi-objective optimization, including studies published under names that are different from "multi-modal multi-objective optimization". Our review also clarifies open issues in this research area.

I. INTRODUCTION

Evolutionary multi-objective optimization usually evaluates solution sets in objective space, but decision makers may need diverse, nearly equivalent solutions in solution space. This review addresses the fragmented literature on evolutionary multi-modal multi-objective optimization and identifies open issues.

  • MOEAs seek non-dominated solution sets approximating the Pareto front for later preference-based selection.
  • Solutions can be far apart in solution space while having identical or similar objective vectors, creating meaningful alternatives for decision makers.
  • If a preferred solution becomes unavailable, another solution with similar objectives can serve as a substitute.
  • In a space mission example, x1 dominates x2, but their objective vectors differ only slightly while departure times differ by 440 days.
  • MMOPs seek all solutions equivalent to Pareto optimal solutions, including multiple equivalent Pareto-optimal subsets such as Two-On-One's symmetrical O1 and O2.
  • The review covers definitions, algorithms, test problems, and performance indicators, including previously untagged studies, and clarifies open issues.

II. DEFINITIONS OF MMOPS

The paper defines MMOPs around finding all solutions equivalent to Pareto-optimal solutions, addressing a still-controversial definition. Equivalence is controlled by a decision-maker-selected objective-space threshold, allowing the target solution set to vary.

  • An MMOP involves finding all solutions that are equivalent to Pareto optimal solutions.
  • Two solutions are equivalent when the norm of their objective-vector difference is at most the non-negative threshold δ.
  • With δ = 0, the target is all equivalent Pareto-optimal solutions; with δ > 0, acceptable dominated solutions may also be included.
  • Changing δ lets the decision maker adjust the MMOP goal and potentially obtain more practical options.
  • The paper uses MMOP regardless of the chosen δ value, while noting that the definition remains open to discussion.

III. MMEAS

MMEAs extend evolutionary multi-objective optimization by seeking high-quality solutions that are diverse in both objective and solution spaces. The reviewed methods include dominance-based variants and approaches using clustering, archives, niching, or immune-system operations.

  • III. MMEAS: MMEAs require high solution quality, objective-space diversity, and solution-space diversity.MOEAs emphasize the first two abilities, while multi-modal single-objective optimizers emphasize the first and third.
  • 1) Pareto dominance-based MMEAs: Omni-optimizer combines objective- and solution-space crowding distances within an NSGA-II-based optimizer.Its solution-space crowding distance is calculated variable-wise and then aggregated for each individual.
  • 1) Pareto dominance-based MMEAs: Omni-optimizer’s alternative crowding distance produced more diverse solutions than NSGA-II in the reported results.The comparison is attributed to the alternative crowding-distance design.
  • 1) Pareto dominance-based MMEAs: Other dominance-based MMEAs use sharing functions, solution-distance mating, clustering, reference-vector selection, or separate objective- and solution-space archives.Examples include DNEA, DN-NSGA-II, DBSCAN-based methods, rake selection, and SPEA2+.
  • 1) Pareto dominance-based MMEAs: PQ,ϵ-MOEA, 4D-Miner, and MNCA can handle MMOPs with δ > 0, including acceptable-quality dominated solutions.PQ,ϵ-MOEA uses ϵ-dominance and an unbounded archive, whereas 4D-Miner maintains dissimilar individuals in an external archive.
  • 1) Pareto dominance-based MMEAs: Niching-CMA and immune-system-based methods broaden MMEA designs beyond standard genetic variation operators.Niching-CMA adaptively adjusts niches, while omni-aiNet and cob-aiNet use suppression, insertion, or population-size controls.

2) Decomposition-based MMEAs:

Decomposition-based MMEAs modify MOEA/D-style decomposition so multiple diverse individuals can represent each subproblem or so solution-space proximity affects replacement. A key design challenge is problem-dependent neighborhood or multiplicity setting.

  • 2) Decomposition-based MMEAs: A three-phase multistart method clusters M × K best-so-far solutions before running decomposed single-objective searches.It first performs (1, λ)-ES on each objective, detects equivalent Pareto-optimal subsets, and then runs searches using Tchebycheff decomposition.
  • 2) Decomposition-based MMEAs: MOEA/D variants assign one or more individuals to each subproblem to represent equivalent solutions.This differs from standard MOEA/D, which assigns a single individual to each weight-vector-defined subproblem.
  • 2) Decomposition-based MMEAs: MOEA/D with K individuals combines PBI fitness with solution-space distances, but choosing K is problem dependent.MOEA/D-AD avoids K but requires a relative neighborhood size L.
  • 2) Decomposition-based MMEAs: MOEA/D-AD assigns offspring by objective-space weight-vector proximity and replaces nearby solution-space individuals when scalarizing fitness permits.An offspring also enters when no existing individual lies within the specified L-neighborhood in solution space.

3) Set-based MMEAs:

Set-based MMEAs optimize collections of solutions rather than only individual solutions, balancing objective quality with solution-space diversity. They differ in whether these criteria are weighted into one indicator or treated as separate meta-objectives.

  • 3) Set-based MMEAs: DIOP evolves an archive and a target population, using a weighted G indicator to balance objective performance and solution-space diversity.The archive approximates the Pareto front, while the target population seeks diverse solutions with acceptable quality.
  • 3) Set-based MMEAs: DIOP defines its objective-space and solution-space terms with hypervolume and Solow-Polasky diversity, respectively.Meta-individuals ϵ-dominated by archive meta-individuals are excluded from the G calculation.
  • 3) Set-based MMEAs: Table I records population size, evaluation budget, δ > 0 capability, and whether each of 18 MMEAs uses an unbounded population or archive.The caption also identifies methods for which initial population sizes or post-processing settings are reported.
  • 3) Set-based MMEAs: Another set-based MMEA evolves one population and treats objective performance and solution diversity as two meta-objective functions.NSGA-II is used to maximize the two criteria simultaneously rather than their weighted sum.

4) A post-processing approach:

The post-processing approach searches for alternatives to a selected final solution instead of requiring an MMEA to locate every Pareto-optimal solution during the initial optimization. It formulates this search as a constrained meta two-objective problem.

  • 4) A post-processing approach: After an MOEA obtains nondominated solutions and a decision maker selects xfinal, searching equivalent objective vectors can be sufficient.The approach targets alternatives to the selected solution rather than all Pareto-optimal solutions.
  • 4) A post-processing approach: The post-processing method formulates a constrained meta two-objective minimization problem around xfinal.Its meta-objectives represent distances from xfinal in objective and solution spaces.
  • 4) A post-processing approach: The desired alternatives are similar to xfinal in objective space but far from it in solution space.The constraint gmeta with θ > 0 prevents the solution-space distance from becoming infinitely small in unbounded problems.
  • 4) A post-processing approach: NSGA-II serves as the meta-optimizer for the post-processing search.

5) Open issues:

The review identifies unresolved questions about MMEA effectiveness, scalability, dominated-solution handling, and archive capacity. It also highlights the need for broader benchmarking and comparative evaluation.

  • Benchmarking gaps: MMEA performance remains insufficiently analyzed across population sizes, evaluation budgets, and problems with four or more objectives.Most MMEAs have been applied only to two-objective MMOPs, while real-world applications can involve four or more objectives.
  • Research infrastructure: The field would benefit from an online results repository and a large-scale benchmarking study to make optimizer comparisons and development more systematic.The review explicitly proposes a repository analogous to the CEC2013 resource for multi-modal single-objective optimization.
  • Dominated solutions: MMEAs generally do not support diverse dominated solutions with acceptable quality when δ > 0.Most methods remove dominated individuals, so mechanisms such as multiple subpopulations are needed to preserve these solutions.
  • Optimization trade-offs: MMEAs often sacrifice Pareto-front approximation quality because solution-space diversity mechanisms can interfere with objective-space optimization.Several studies report worse abilities to find high-quality and objective-space-diverse solutions than MOEAs, including worse IGD than NSGA-II for representative methods.
  • Archive management: Population or archive capacity limits the number of equivalent Pareto optimal solutions that can be maintained when their number is unknown a priori.The review suggests unbounded external archives as a general strategy, noting that only three MMEAs use such a mechanism.

IV. MULTI-MODAL MULTI-OBJECTIVE TEST PROBLEMS

The paper reviews synthetic MMOP test problems designed to contain multiple equivalent Pareto optimal solution subsets. These problems vary in geometry, transformations, scalability, and the number of solution subsets.

  • Test-problem design: MMOP test problems are explicitly designed to contain multiple equivalent Pareto optimal solution subsets, unlike conventional multi-objective test suites.The reviewed suite includes ten problems, including Two-On-One, Omni-test, SYM-PART variants, Superspheres, EBN, SSUF, and Polygon.
  • SYM-PART problems: SYM-PART1 uses translated two-objective functions whose Pareto optimal subsets can lie on nine lines.Parameter a controls the Pareto-optimal region, while b and c specify subset positions; tile identifiers determine translations.
  • Problem diversity: The reviewed problems represent diverse structures, including regular subsets, rotated or distorted variants, mirrored constructions, multi-frontal landscapes, and problems where all solutions are Pareto optimal.Omni-test has regularly located subsets; SYM-PART2 and SYM-PART3 apply rotation and distortion; EBN makes every solution Pareto optimal.
  • Problem properties: Table II characterizes MMOP test problems by objectives M, design variables D, equivalent Pareto optimal subsets P, and irregularity.Irregularity indicates that the shapes of multiple equivalent Pareto optimal subsets differ from one another.

1) Open issues:

The review finds substantial gaps in the scalability and realism of existing MMOP test problems. It points toward more systematic problem-generation principles and stronger links to real-world applications.

  • Scalability: No reviewed test-problem family is scalable simultaneously in objectives M, design variables D, and equivalent subsets P.Only Polygon is scalable in M, while Omni-test and HPS are scalable in D.
  • Scalability: Omni-test’s number of equivalent Pareto optimal subsets increases exponentially with D because of its combinatorial construction.This growth creates a limitation for scalable benchmarking as the number of design variables increases.
  • Realism: The connection between synthetic MMOP test problems and actual real-world problems remains largely unexamined.Designing a Polygon problem from a real-world map does not make that problem an actual real-world problem.
  • Generator design: Problem generators could borrow established design criteria such as scalability, controllable numbers of global and local optima, and regular or irregular optimum distributions.These properties are identified as useful guidelines for constructing MMOP test-problem generators.

V. PERFORMANCE INDICATORS FOR MMEAS

MMEA performance indicators must assess objective-space convergence alongside solution-space diversity, uniformity, and spread, but existing indicators differ in reference-set requirements and size comparability. IGDX can reward solution-space coverage while overlooking objective-space distribution, so fair evaluation should combine MMEA-specific and MOEA indicators.

  • Solution- and objective-space evaluation: IGD evaluates approximation of the Pareto front, whereas IGDX evaluates approximation of Pareto optimal solutions in the solution space.Both indicators use a reference solution set and Euclidean distances.
  • Indicator properties: MMEA indicators also include coverage, subset-distribution, and solution-space-volume measures such as CS, SPS, and PSV.CS counts covered Pareto optimal solution subsets; SPS measures variation in nearby-solution counts; PSV measures occupied solution-space volume.
  • Indicator properties: MMEA indicators are designed to evaluate convergence to Pareto optimal solution subsets, diversity, uniformity, and spread, with additional properties concerning reference sets and solution-set sizes.Table III organizes these properties for the reviewed indicators.
  • Indicator limitations: A1 and A2 each contain 27 solutions, but A1 covers the Pareto front with 27 objective vectors while A2 covers all nine subsets with only 3 equivalent objective vectors.The example shows that objective-space coverage and solution-space multimodality can diverge.
  • Open issues: Most reviewed indicators require a reference solution set, although real-world problems usually lack the Pareto-optimal reference set A*; fair comparison across different solution-set sizes is also desirable.The review notes that indicators from multi-modal single-objective optimization cannot be directly transferred to MMEAs.

VI. CONCLUSION

The paper reviews evolutionary multi-modal multi-objective optimization across definitions, algorithms, test problems, and performance indicators, while clarifying open issues. It emphasizes that reliable indicators are needed because the field remains underexplored despite practical importance.

  • Review scope: The review synthesizes existing studies in terms of MMOP definitions, MMEAs, test problems, and performance indicators.It addresses studies that were difficult to survey because they used different terminology or were conducted independently.
  • Open issues: The paper clarifies open issues in multi-modal multi-objective optimization, which has received less attention than multi-modal single-objective optimization despite practical importance.The conclusion characterizes the field as not well explored.
  • Performance evaluation: The review identifies performance-indicator issues and argues that reliable indicators are necessary for advancing MMEAs.The paper specifically highlights the need for indicators suited to evaluating MMEAs.
Loading 2009.13347v1…