A Review on Constraint Handling Techniques for Population-based Algorithms: from single-objective to multi-objective optimization

Iman Rahimi, Amir H. Gandomi, Fang Chen, Efrén Mezura‐MontesArchives 2022 · DOI

Abstract

This study provides a novel analysis of scholarly literature on constraint handling techniques (CHTs) for single-objective and multi-objective population-based algorithms according to the most relevant journals, keywords, authors, and articles. The paper reviews the main ideas of the most state-of-the-art constraint handling techniques in multi-objective population-based optimization, and then the study addresses the bibliometric analysis in the field. The extracted papers include research articles, reviews, book/book chapters, and conference papers published between 2000 and 2020 for the analysis. The results indicate that the constraint handling techniques for multi-objective optimization have received much less attention compared with single-objective optimization. The most promising algorithms for such optimization were determined to be genetic algorithms, differential evolutionary algorithms, and particle swarm intelligence.

Introduction

In the real world of mathematical optimization, search spaces are often hemmed in by physical, economic, and design constraints. While Evolutionary Algorithms (EAs) are excellent at exploring complex search spaces, they are naturally "blind" to these constraints. To solve constrained problems, researchers use Constraint Handling Techniques (CHTs) to guide the population toward the "feasible region" while maintaining pressure toward optimal objective values. This paper seeks to organize the fragmented landscape of these techniques and identify where the field is heading.

Methodology

The authors employ a dual approach: a technical review of CHT categories and a bibliometric analysis. Using data from Scopus and Web of Science (2000–2020), they performed social network analysis, co-authorship mapping, and keyword co-occurrence using tools like VOSviewer and RStudio.

Technical Categorization

The paper classifies CHTs into four primary families:

  1. Penalty Functions: The most common approach, which "punishes" infeasible solutions by worsening their fitness scores.
  2. Separation of Objectives and Constraints: Techniques like the Epsilon-constrained method or Feasibility Rules that treat constraint satisfaction as a priority distinct from objective optimization.
  3. Hybrid Methods: Combining multiple CHTs to balance exploration and exploitation.
  4. Repair and Special Operators: Algorithms that actively "fix" infeasible solutions or use specialized genetic operators to stay within the feasible boundary.
Taxonomy of different constraint handling methods in MOEA

Benchmarks and Datasets

Standard benchmarks used to evaluate these algorithms include:

  • Single-objective: Rosenbrock, G01-G09, and engineering problems like Welded Beam and Pressure Vessel.
  • Multi-objective: BNH, OSY, ZDT, DTLZ, and C-DTLZ for constrained many-objective optimization.

Key Insights and Results

  • The "Feasibility Rule" Dominance: Rules proposed by Deb (2000) remain popular because they require no additional parameters.
  • Diversity vs. Feasibility: Retaining some infeasible solutions in the population is beneficial, acting as "bridges" between disconnected feasible regions.
  • The Multi-Objective Gap: There is a clear lag in the development of CHTs specifically designed for multi-objective problems compared to single-objective ones.
  • Research Growth: The field saw a massive spike in interest after 2003, with publication volume growing to over 200 documents per year by 2020, led by Engineering and Computer Science.

The authors also provide a concise summary of the critiques of popular methods, noting that penalty functions are often time-consuming and problem-dependent.

Summary and critique of penalty function techniques

Limitations and Future Work

Several critical gaps remain:

  • Parameter Dependency: Many state-of-the-art CHTs still require significant manual tuning.
  • Many-Objective Optimization: As problems move to 4+ objectives, current CHTs struggle with the "curse of dimensionality."
  • Boundary Update (BU) Techniques: These show promise for integration with Multi-Objective Evolutionary Algorithms (MOEAs).
  • Sector-Specific Gaps: There is a need for more applied research in scheduling and resource optimization.

Summary updated

Abstract

Abstract Most real-world problems involve some type of optimization problems that are often constrained. Numerous researchers have investigated several techniques to deal with constrained single-objective and multi-objective evolutionary optimization in many fields, including theory and application. This presented study provides a novel analysis of scholarly literature on constraint-handling techniques for single-objective and multi-objective population-based algorithms according to the most relevant journals and articles. As a contribution to this study, the paper reviews the main ideas of the most state-of-the-art constraint handling techniques in population-based optimization, and then the study addresses the bibliometric analysis, with a focus on multi-objective, in the field. The extracted papers include research articles, reviews, book/book chapters, and conference papers published between 2000 and 2021 for analysis. The results indicate that the constraint-handling techniques for multi-objective optimization have received much less attention compared with single-objective optimization. The most promising algorithms for such optimization were determined to be genetic algorithms, differential evolutionary algorithms, and particle swarm intelligence. Additionally, “Engineering,” “Computer Science,” and “ Mathematics” were identified as the top three research fields in which future research work is anticipated to increase.
BibTeX
@inproceedings{rahimi2022review,
  author = {Iman Rahimi and Amir H. Gandomi and Fang Chen and Efrén Mezura‐Montes},
  title = {{A Review on Constraint Handling Techniques for Population-based Algorithms: from single-objective to multi-objective optimization}},
  booktitle = {Archives},
  year = {2022},
  doi = {10.1007/s11831-022-09859-9},
}
Figure