PaperlayerView exact revision on arXiv

Source-linked AI summary

Dynamic Multi-Objectives Optimization with a Changing Number of Objectives

Renzhi Chen, Ke Li, Xin Yao

arXiv:1608.06514v2cs.NE

TL;DR

The paper addresses the limited study of dynamic multi-objective problems whose objective count changes, causing Pareto-front/set manifolds to expand or contract. It proposes DTAEA, which co-evolves complementary convergence and diversity archives with adaptive reconstruction, and reports strong benchmark performance in tracking these changes. The study also identifies unconstrained, regularly varying environments as boundaries for future work.

  • Problem

    Dynamic multi-objective research rarely considers changing objective counts, which expand or contract Pareto-front/set manifold dimensions and challenge existing handling techniques.

  • Method

    DTAEA co-evolves convergence and diversity archives, reconstructing both adaptively when the environment changes and coupling them through mating selection.

  • Results

    Comprehensive benchmark experiments demonstrate DTAEA’s effectiveness in tracking Pareto-front/set manifold expansion or contraction under dynamically changing objective counts.

  • Takeaways & Limitations

    The results support two-archive evolutionary handling as an effective approach for dynamic multi-objective problems with changing objective counts.

  • Takeaways & Limitations

    The study does not consider constrained optimization and focuses on environments where changes are detectable and regular.

Abstract

from arXiv · show

Existing studies on dynamic multi-objective optimization focus on problems with time-dependent objective functions, while the ones with a changing number of objectives have rarely been considered in the literature. Instead of changing the shape or position of the Pareto-optimal front/set when having time-dependent objective functions, increasing or decreasing the number of objectives usually leads to the expansion or contraction of the dimension of the Pareto-optimal front/set manifold. Unfortunately, most existing dynamic handling techniques can hardly be adapted to this type of dynamics. In this paper, we report our attempt toward tackling the dynamic multi-objective optimization problems with a changing number of objectives. We implement a new two-archive evolutionary algorithm which maintains two co-evolving populations simultaneously. In particular, these two populations are complementary to each other: one concerns more about the convergence while the other concerns more about the diversity. The compositions of these two populations are adaptively reconstructed once the environment changes. In addition, these two populations interact with each other via a mating selection mechanism. Comprehensive experiments are conducted on various benchmark problems with a time-dependent number of objectives. Empirical results fully demonstrate the effectiveness of our proposed algorithm.

1 Introduction

Dynamic multi-objective optimization with a changing number of objectives is underexplored because objective-count changes expand or contract the Pareto-front/set manifold, challenging existing dynamic handling methods. The paper proposes DTAEA, which co-evolves complementary convergence and diversity archives that are reconstructed after environmental changes.

  • Existing dynamic multi-objective studies mainly address time-dependent objective functions, while changing objective counts have received limited attention.
  • Software development phases exemplify real-life settings in which different phases involve different numbers of objectives.
  • Changing the objective count generally expands or contracts the Pareto-front/set manifold dimension rather than merely changing its position or shape.
  • DTAEA simultaneously maintains a convergence archive for selection pressure toward the Pareto front and a diversity archive for diversified solutions.
  • The two archives co-evolve, interact through mating selection, and are adaptively reconstructed when the environment changes.

2 Preliminaries

The paper formalizes continuous dynamic multi-objective problems with a time-varying objective count and examines how increasing or decreasing that count changes Pareto-optimal populations. These changes create convergence and diversity challenges that existing dynamic techniques do not adequately address.

  • 2.1 Basic Definitions: At time t, the problem has m(t) real-valued objectives over a decision space, with Pareto dominance and optimality defined using the objectives active at t.
  • 2.1 Basic Definitions: Theorem 1 states that increasing objectives makes the current Pareto front and set subsets of those after the increase, with the reverse relation under decreases.
  • 2.1 Basic Definitions: Under the regularity property, the Pareto front and set form (m(t) −1)-dimensional piecewise continuous manifolds in objective and decision spaces.
  • 2.2 Challenges: After increasing objectives on DTLZ2, convergence remains good but diversity becomes insufficient because solutions crowd on a lower-dimensional curve.
  • 2.2 Challenges: After decreasing objectives, some solutions leave the Pareto front and duplicate or similar solutions reduce diversity, requiring both recovery and dispersion.
  • 2.3 Weaknesses of Existing Dynamic Handling Techniques: Existing diversity, memory, and prediction strategies are poorly matched to objective-count changes, particularly because prediction models manifold movement rather than dimensional expansion or contraction.

3 Proposed Algorithm

DTAEA addresses changing-objective DMOPs with two fixed-size, co-evolving archives that assign complementary priority to convergence and diversity.

  • DTAEA maintains equal-sized convergence and diversity archives throughout evolution.
  • The convergence archive supplies competitive selection pressure toward the optima, while the diversity archive seeks diversified solutions.
  • The algorithm’s flow includes archive-based evolutionary processing for dynamic multi-objective optimization with a changing objective count.

3.1 Reconstruction Mechanisms

When the environment changes, DTAEA reconstructs its two archives using mechanisms tailored separately to objective-count increases and decreases.

  • Archive reconstruction is the main response to environmental change, with different mechanisms for increasing and decreasing objective counts.
  • After Increasing the Number of Objectives: After an objective increase, the last convergence archive preserves optimal solutions while Latin hypercube sampling supplies diversified decision-space solutions.
  • After Decreasing the Number of Objectives: After an objective decrease, all non-dominated solutions from the previous convergence archive form the new convergence archive.
  • After Decreasing the Number of Objectives: If the reconstructed convergence archive is undersized after a decrease, additional solutions are selected before Latin hypercube sampling fills the diversity archive.

3.2 Update Mechanisms

The update mechanisms reconstruct the convergence archive (CA) and diversity archive (DA) using density-based subspace associations. The CA emphasizes competitive convergence, whereas the DA preserves diversified solutions in under-exploited regions.

  • Update Mechanisms: The CA and DA use different update mechanisms because the CA emphasizes convergence while the DA emphasizes diversity.Their mechanisms are described separately after introducing the shared density-estimation method.
  • Density Estimation Method: The density estimator divides the normalized objective space into subspaces using uniformly distributed weight vectors and associates each solution with one subspace.Subspace density equals the number of associated solutions.
  • Update Mechanism of the CA: The CA combines its population with offspring, ranks solutions by non-domination, and trims crowded subspaces by eliminating their worst solutions.The archive is filled level by level until its threshold, then density-based elimination completes the trimming.
  • Update Mechanism of the CA: The CA’s worst solution in a subspace is selected according to the g_tch criterion relative to that subspace’s weight vector and the ideal point.The cited equation defines the worst-solution selection used during density-based trimming.
  • Update Mechanism of the DA: The DA combines its population with offspring and iteratively selects the best non-dominated solution from subspaces insufficiently represented by the CA.The process continues until the DA reaches its predefined threshold.

3.3 Offspring Reproduction

Offspring reproduction exploits interaction between the co-evolving archives through restricted mating selection. Parents are selected from the CA and DA according to population distribution, followed by simulated binary crossover and polynomial mutation.

  • Restricted Mating Selection: Restricted mating selection chooses mating parents from the CA and DA to exploit their complementary convergence and diversity effects.The DA supplies diversified information and supports adaptation to changing environments.
  • Restricted Mating Selection: The first mating parent is randomly selected from the CA, while the second parent’s archive is chosen using the CA’s diversity indicator I_o^CA.A higher I_o^CA indicates a well-diversified CA and gives greater selection probability to the CA for the second parent.
  • Variation Operators: Offspring are generated from the selected parents using simulated binary crossover and polynomial mutation.These are the variation operators used in the paper.

3.4 Time Complexity Analysis

DTAEA reconstructs its archives when the number of objectives changes, with reconstruction costs depending on whether objectives are increased or decreased. Its overall per-generation complexity is O(N^2).

  • Archive Reconstruction: The CA and DA are reconstructed when the environment changes through an increase or decrease in the number of objectives.The reconstruction is part of the algorithm’s dynamic response.
  • Objective Increase: When objectives increase, CA reconstruction adds no computation, whereas DA reconstruction costs O(N) function evaluations.These costs are reported specifically for the objective-increment case.
  • Overall Complexity: The total complexity of DTAEA in one generation is O(N^2) comparisons.The cited analysis attributes this cost to the subspace-related loop.

3.5 Further Discussions

DTAEA uses decomposition-based subspaces for a different purpose than several related algorithms. It balances convergence and diversity by assigning elite non-dominated solutions to the CA and well-spread remaining solutions to the DA.

  • Connections with Decomposition-Based Algorithms: DTAEA divides objective space into subspaces with weight vectors, but unlike MOEA/D-M2M, it does not primarily allocate equal computational resources to each subspace.Its two archives instead support a balance between convergence and diversity after environmental changes.

4 Experimental Settings

The experiments use dynamic benchmark problems, two adapted performance metrics, and comparisons against dynamic and stationary state-of-the-art EMO algorithms. Each algorithm is independently evaluated across repeated runs with statistical testing.

  • Benchmark Problems: The study evaluates algorithms on dynamic multi-objective benchmark problems, including a problem type with a changing number of objectives.Most existing benchmarks change only the shape or position of the Pareto-optimal front or set.
  • Performance Metrics: Performance is assessed with Mean Inverted Generational Distance and hypervolume, adapted from popular metrics used in the literature.The paper notes that no standard metric exists for quantitatively evaluating dynamic multi-objective optimization algorithms.
  • Performance Metrics: MIGD averages distances between obtained solution sets and uniformly sampled points on the time-varying Pareto-optimal fronts across discrete time steps.The IGD calculation uses 10,000 uniformly distributed points sampled on each corresponding Pareto-optimal front.
  • Performance Metrics: Hypervolume measures the objective-space volume dominated by the obtained solutions and bounded by a worst point, with normalized values in [0, 1].Solutions dominated by the worst point are discarded before calculation.
  • EMO Algorithms Used in the Experimental Studies: Comparisons include DNSGA-II, MOEA/D-KF, NSGA-II, and MOEA/D, covering dynamic methods alongside their corresponding stationary baselines.MOEA/D-KF predicts Pareto-set movement with a linear discrete-time Kalman Filter, while DNSGA-II introduces random solutions after changes.
  • Experimental Procedure: Each algorithm is run independently 31 times per instance, receives 300 generations before the first change, and is compared using a Wilcoxon rank sum test at the 5% significance level.The first environmental change therefore occurs after the first 300 generations.

5 Experimental Results

Across benchmark studies, DTAEA generally outperformed the comparison algorithms under changing objective counts, while its performance depended on change frequency and problem difficulty. Component analyses further attribute this behavior to adaptive archive reconstruction and complementary convergence–diversity management.

  • Results on F1 to F4: DTAEA achieved the best MIGD and MHV values under all four change frequencies on F1, while IGD was best at every time step.At τt = 25, performance fluctuated because solutions could not fully converge before environmental changes; increasing τt stabilized performance.
  • Results on F1 to F4: DTAEA consistently showed the best performance across all time steps on F2, although all algorithms produced MIGD and MHV values on the same scale.F2 is relatively simple, allowing all algorithms to adapt within a reasonable number of function evaluations.
  • Results on F1 to F4: On F3, multimodality hindered NSGA-II and DNSGA-II from improving as objectives decreased, while dynamic handling in DNGSA-II and MOEA/D-KF did not aid adaptation.Injected solutions could provide false information about the newly changed Pareto front or set, harming evolution.
  • Results on F1 to F4: On F4, DTAEA’s superior performance was attributed to its two co-evolving populations balancing convergence and diversity throughout evolution.F4 combines changing objectives with biased Pareto-optimal solution density, requiring both convergence and diversity control.
  • Results on F5 and F6: On F5 and F6, DTAEA was best in 30 of 32 MIGD and 28 of 32 MHV comparisons, but fluctuated under high-frequency changes.F5 and F6 combine changing objective counts with time-varying Pareto-optimal sets; DTAEA lacks specific handling for the latter dynamics.
  • Effects of the Update Mechanisms: Ablation results showed the complete DTAEA outperformed its three variants, with reconstruction especially improving performance at high change frequencies.Restricted mating selection still guided search without environmental response, whereas omitting both mechanisms produced the worst variant performance.

6 Conclusions

The paper addresses dynamic multi-objective optimization with a changing number of objectives using a dynamic two-archive evolutionary algorithm. Experiments show that DTAEA tracks expansion or contraction of the Pareto-front or Pareto-set manifold while maintaining convergence and diversity, although some dynamic algorithms underperform stationary counterparts.

  • DTAEA targets objective-count changes that expand or contract the dimensionality of the Pareto-front or Pareto-set manifold.
  • The algorithm maintains complementary archives to preserve convergence and diversity throughout environmental changes.
  • Comprehensive benchmark experiments demonstrate DTAEA’s superiority for dynamic problems with a changing number of objectives.
  • Some state-of-the-art dynamic evolutionary multi-objective algorithms performed worse than stationary counterparts in the experiments.
  • The paper identifies changing-objective-count optimization as requiring further systematic investigation, including irregular changes and constrained problems.

7 Appendix: Proof of Theorem 1

Theorem 1 establishes how Pareto fronts and sets relate across objective-count changes. Increasing objectives makes the earlier front and set subsets of the later ones, whereas decreasing objectives reverses this relation.

  • When objectives increase, the Pareto front and set at time t are subsets of those at time t+1.
  • The increasing-objective case is proved by contradiction using dominance across all retained and newly added objectives.
  • When objectives decrease, the Pareto front at time t is a superset of the front at time t+1.
Loading 1608.06514v2…