PaperlayerView exact revision on arXiv

Source-linked AI summary

Two-Archive Evolutionary Algorithm for Constrained Multi-Objective Optimization

Ke Li, Renzhi Chen, Guangtao Fu, Xin Yao

arXiv:1711.07907v1cs.NE

TL;DR

Constrained multi-objective optimization requires balancing convergence, diversity, and feasibility, while existing approaches can overemphasize feasibility on complex constraints. The paper proposes C-TAEA, a parameter-free two-archive algorithm with restricted mating selection. Across benchmark problems, C-TAEA reports competitive performance, including substantially better C1-DTLZ3 results than peer algorithms.

  • Problem

    Existing constraint-handling techniques often overemphasize feasibility instead of balancing convergence, diversity, and feasibility, which can make search ineffective on complex constraints.

  • Method

    C-TAEA co-evolves convergence and diversity archives, with the latter exploring under-exploited regions including infeasible areas, and uses restricted mating selection.

  • Results

    Around 50 times smaller IGD values on average and effective HV values were obtained by C-TAEA on C1-DTLZ3, whereas peer algorithms’ HV values were all 0.

  • Takeaways & Limitations

    The two archives provide complementary convergence, feasibility, and diversity behavior for constrained multi-objective optimization.

  • Takeaways & Limitations

    The authors identify future work on broader problem classes, including unconstrained, dynamic, and additional real-world optimization problems.

Abstract

from arXiv · show

When solving constrained multi-objective optimization problems, an important issue is how to balance convergence, diversity and feasibility simultaneously. To address this issue, this paper proposes a parameter-free constraint handling technique, two-archive evolutionary algorithm, for constrained multi-objective optimization. It maintains two co-evolving populations simultaneously: one, denoted as convergence archive, is the driving force to push the population toward the Pareto front; the other one, denoted as diversity archive, mainly tends to maintain the population diversity. In particular, to complement the behavior of the convergence archive and provide as much diversified information as possible, the diversity archive aims at exploring areas under-exploited by the convergence archive including the infeasible regions. To leverage the complementary effects of both archives, we develop a restricted mating selection mechanism that adaptively chooses appropriate mating parents from them according to their evolution status. Comprehensive experiments on a series of benchmark problems and a real-world case study fully demonstrate the competitiveness of our proposed algorithm, comparing to five state-of-the-art constrained evolutionary multi-objective optimizers.

1 Introduction

Constrained multi-objective optimization must balance convergence, diversity, and feasibility, but feasibility-first methods can become trapped in narrow or scattered feasible regions. C-TAEA addresses this with two complementary co-evolving archives and restricted mating selection.

  • Convergence, diversity, and feasibility are simultaneous challenges in constrained multi-objective optimization.
  • Feasibility-first constraint handling can trap populations in local optima or local feasible regions when feasible regions are narrow or disparately distributed.
  • C-TAEA maintains co-evolving convergence and diversity archives to address constrained multi-objective optimization.
  • The convergence archive provides selection pressure toward the Pareto front while maintaining convergence and feasibility.
  • The diversity archive explores areas under-exploited by the convergence archive, including infeasible regions, to improve diversity and help bypass local optima or feasible regions.
  • Restricted mating selection separately chooses parents from the two archives according to their evolution status, leveraging their complementary information.

2 Preliminaries

Existing constrained evolutionary approaches commonly emphasize feasibility, which can weaken the balance among convergence, diversity, and feasibility on complex constraints. The paper motivates a two-archive strategy using examples where feasibility-driven search becomes trapped or misses feasible Pareto-front regions.

  • 2.1 Literature Review: Constraint-handling methods are grouped into feasibility-driven, convergence–feasibility balancing, and infeasible-solution repair approaches.
  • 2.2 Challenges to Existing Constraint Handling Techniques: Most existing techniques emphasize feasibility more than the simultaneous balance of convergence, diversity, and feasibility, risking ineffective search under complex constraints.
  • 2.2 Challenges to Existing Constraint Handling Techniques: In C1-DTLZ3, an infeasible ribbon intersects the feasible region, making feasibility-driven strategies prone to becoming trapped at the outermost feasible boundary.
  • 2.2 Challenges to Existing Constraint Handling Techniques: In C2-DTLZ2, sparsely located feasible regions can trap feasibility-driven methods in only some regions, while decomposition-based methods may fail to find feasible solutions.
  • 2.2 Challenges to Existing Constraint Handling Techniques: The paper proposes using a two-archive strategy to balance convergence, diversity, and feasibility across the search space, including appropriate use of infeasibility information.

3 Proposed Algorithm

C-TAEA uses two co-evolving archives with complementary roles: the convergence archive drives feasibility and Pareto-front approximation, while the diversity archive explores under-exploited areas without using feasibility information. Density-based updates and restricted mating selection coordinate both archives.

  • 3 Proposed Algorithm: C-TAEA maintains fixed-size convergence and diversity archives that co-evolve as complementary populations.The convergence archive approximates the Pareto front, while the diversity archive explores areas under-exploited by it.
  • 3.1 Density Estimation Method: Objective-space density estimation partitions solutions into N subregions represented by uniformly distributed weight vectors.Each solution is associated with a unique subregion, whose density equals its number of associated solutions.
  • 3.2 Update Mechanism of the CA: The convergence archive first prioritizes feasible solutions, then uses nondominated sorting and crowding-based trimming to balance convergence and diversity.When feasible solutions are insufficient, infeasible candidates are ranked and trimmed using constraint violations.
  • 3.3 Update Mechanism of the DA: The diversity archive ignores constraint violation and uses the current convergence archive as a reference to explore complementary regions.This update combines the diversity archive with offspring and continues investigating under-exploited areas until the archive is filled.
  • 3.4 Offspring Reproduction: Restricted mating selection chooses parents from the archive with the higher proportion of nondominated solutions, adapting parent selection to archive status.The two archives are combined before their nondominated proportions determine mating-pool selection probabilities.

4 Experimental Setup

The empirical study evaluates constrained EMO algorithms on scalable benchmark problems using IGD and HV, repeated runs, distribution summaries, and Wilcoxon tests. C-TAEA is compared with five state-of-the-art constrained EMO algorithms under shared offspring-generation and termination settings.

  • 4 Experimental Setup: The benchmark suite combines five constrained test problems with six newly proposed problems, evaluated for 3, 5, 8, 10, and 15 objectives.The selected instances include C-DTLZ and DC-DTLZ problem families and are scalable to any number of objectives.
  • 4 Experimental Setup: Performance is assessed using Inverted Generational Distance and Hypervolume, which jointly evaluate convergence and diversity.Lower IGD and higher HV indicate better approximation to the Pareto front.
  • 4 Experimental Setup: Each algorithm is independently run 51 times, with medians and interquartile ranges reported for IGD and HV.The reported distributions summarize repeated performance across the benchmark experiments.
  • 4 Experimental Setup: Wilcoxon’s rank sum test at a 5% significance level evaluates whether C-TAEA’s better performance over peer algorithms is statistically significant.The test is applied to support conclusions from the IGD and HV comparisons.
  • 4 Experimental Setup: C-TAEA is compared against C-MOEA/D, C-NSGA-III, C-MOEA/DD, I-DBEA, and CMOEA.All algorithms use simulated binary crossover and polynomial mutation, with termination based on a predefined number of function evaluations.

5 Empirical Studies

Across the C-DTLZ and DC-DTLZ benchmark suites, C-TAEA generally achieves stronger IGD and HV performance than peer algorithms, especially on problems with separated or obstructed feasible regions. Its two archives complement one another by combining feasibility-oriented convergence with exploration that can cross infeasible barriers.

  • C-DTLZ Benchmark Suite: C-TAEA produces superior IGD and HV values on most C-DTLZ test instances.The comparison uses median and interquartile range values, with Wilcoxon rank-sum testing at the 5% significance level.
  • C-DTLZ Benchmark Suite: On C1-DTLZ3, C-TAEA performs best across 3- to 15-objective instances, with around 50 times smaller IGD values on average.Only C-TAEA obtains effective HV values; the other peers obtain HV values of 0.
  • C-DTLZ Benchmark Suite: On C2-DTLZ2, only C-TAEA finds all disparately distributed small feasible Pareto-front segments.The diversity archive complements convergence-archive coverage and helps the algorithm explore new feasible regions.
  • C-DTLZ Benchmark Suite: On Type-3 C-DTLZ problems, all algorithms obtain comparable IGD and HV values, with C-MOEA/D outperforming C-TAEA on 5-objective C3-DTLZ1.These problems are described as relatively less difficult for constraint handling because the feasible Pareto front is formed by feasible boundaries.
  • DC-DTLZ Benchmark Suite: On the DC-DTLZ suite, C-TAEA obtains the best IGD and HV values in all reported comparisons, with statistically significant advantages over peers.For DC1-DTLZ1 and DC1-DTLZ3, some peers find multiple feasible segments, but C-TAEA consistently outperforms them in IGD and HV.
  • DC-DTLZ Benchmark Suite: For harder DC-DTLZ cases, only C-TAEA finds all feasible Pareto-front segments while other algorithms remain trapped in local feasible regions or constraint-violation optima.The reported explanation attributes this behavior to the collaborative and complementary effects of the two co-evolving archives.

6 Conclusions and Future Directions

C-TAEA is a parameter-free, two-archive constraint-handling algorithm whose complementary archives balance convergence and diversity through restricted mating selection. Its competitiveness is supported across varied constrained benchmarks and a real-world water distribution network design case, while broader applications remain future work.

  • Conclusions: C-TAEA maintains co-evolving convergence and diversity archives with complementary evolutionary roles.The convergence archive drives solutions toward the Pareto front, while the diversity archive explores areas under-exploited by the convergence archive, including infeasible regions.
  • Conclusions: Restricted mating selection complements the archives by selecting appropriate parents for offspring reproduction.
  • Conclusions: C-TAEA remains competitive across constrained benchmarks with varied constraint types and up to 15 objectives.The comparison included five state-of-the-art constrained evolutionary multi-objective algorithms.
  • Conclusions: A real-world water distribution network design case further validated C-TAEA's effectiveness.
  • Future Directions: Future work will examine the two-archive framework on unconstrained, dynamic, and additional real-world optimization problems.The paper also identifies a need for deeper investigation of the framework's mechanisms and theoretical foundation.
Loading 1711.07907v1…