PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Iman Rahimi, Amir H. Gandomi, Fang Chen, Efren Mezura-Montes

arXiv:2206.13802v1math.OC

TL;DR

Constraint-handling techniques for multiobjective optimization have received less attention than those for single-objective optimization, despite the trade-offs and complexity of multiobjective problems. The paper reviews constraint-handling methods and maps the related literature, finding this attention gap in the bibliometric analysis.

  • Problem

    The paper addresses limited attention to constraint-handling techniques for multiobjective optimization, where objective trade-offs and solution complexity make solving problems challenging –.

    Source: §1 · p. 1, §7 · p. 27

  • Method

    The authors reviewed constraint-handling techniques for evolutionary and swarm-intelligence population algorithms and analyzed related publications and bibliometric statistics using Scopus and Web of Science records.

    Source: §2 · p. 3, §8 · p. 28

  • Results

    Constraint-handling techniques for multiobjective optimization have received less attention than those for single-objective optimization.

    Source: §7 · p. 27

  • Takeaways & Limitations

    The authors recommend further research on constraint-handling techniques for multiobjective and many-objective optimization.

    Source: §7 · p. 27

    The review notes that decoder-based constraint handling can incur high computational cost.

    Source: §7 · p. 27

Abstract

from arXiv · show

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, 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.

1. Introduction

The introduction motivates evolutionary methods for complex multiobjective optimization and frames a review of constraint-handling techniques (CHTs) and the literature around them. It identifies limited attention to multiobjective CHTs and sets out questions on techniques, their drawbacks, field contributors, research gaps, and future directions.

Introduction

  • MOOPs involve trade-offs rather than a single solution, and evolutionary computation can address their complexity even when the Pareto-front form is discontinuous or nonconvex.The introduction presents evolutionary computation as suitable for MOOPs across different Pareto-front forms.Source: §1 · p. 1
  • Prior CHTs rank infeasible solutions by constraint violation, prioritize constraints over objectives, or exclude constraint-violating solutions; other methods use multiple rankings but can be costly and parameter-sensitive.The cited approaches include distance-based classes, priority assignment, constraint-based tournament selection, exclusion of violating solutions, and multi-ranking.Source: §1 · pp. 1–2
  • Other approaches combine penalty and multiobjective ranking, switch or exchange objectives, separate objectives from constraints, or use repair and adaptive tradeoffs,.The min-max formulation directs feasible and infeasible individuals toward Pareto optimality and feasibility, respectively.Source: §1 · p. 2
  • The introduction notes that most cited studies focus on single-objective CHTs, with less attention to multiobjective optimization because many methods can be modified for it.The work aims to provide new insights from relevant publications and examine current gaps and future directions.Source: §1 · p. 3
  • The research questions cover what CHTs are and their disadvantages, field keywords and contributors, publication statistics, active countries and affiliations, and future research directions.The questions include journals, researchers, and researchers’ countries as well as basic statistics for multiobjective population-based algorithms.Source: §1 · p. 3

2. Research Methodology

The study followed a five-stage procedure, from literature retrieval and review to scientometric analysis and synthesis of findings, research gaps, and future directions.

2. Research Methodology

  • The five-stage procedure gathered literature from Scopus and Web of Science using targeted searches for constrained multi-objective evolutionary or swarm optimization, covering publications through May 4, 2021.The search strings used TITLE-ABS-KEY combinations of terms on constrained optimization and constraint handling; supplementary files contain the extracted database records.Source: §2 · p. 3
  • Stage 2 removed duplicate records with Mendeley and formulated research questions, while stage 3 introduced constraint-handling concepts and compared methods.Source: §2 · p. 3
  • Stage 4 used VOSviewer, and RStudio for scientometric analysis, including co-occurrence, co-authorship, citation, citation-network analyses, and article pages and authors counts.Source: §2 · p. 3
  • Stage 5 synthesized findings to answer the research questions, identify important gaps, and determine future research directions.Source: §2 · p. 3

3. Constraint Handling Methods in Evolutionary Algorithms (RQ1) · 3.1 Penalty function approach

The review organizes constraint handling into penalty functions, decoders, special operators, and separation techniques, and describes penalty functions as a simple, common approach in multiobjective evolutionary algorithms. It outlines their basic operation and several variants, whose behavior depends on how penalties are selected or adapted.

3. Constraint Handling Methods in Evolutionary Algorithms (RQ1)

  • Constraint handling is classified as penalty functions, decoders, special operators, and separation methods; another MOEA taxonomy includes retaining infeasible solutions and hybrid methods.The review identifies penalty functions and separation methods for later discussion.Source: §3 · p. 4
  • Decoders can map feasible regions into sample spaces for population-based search, but incur high computational costs; special operators preserve feasibility, though feasible initialization is difficult for highly constrained problems –.Some infeasible solutions may also need to be retained to converge toward the feasible–infeasible boundary.Source: §3 · p. 4, §3.1 · p. 5

3.1 Penalty function approach

  • Penalty methods normalize constraints, sum each solution’s violations, and add a scaled violation total to objectives; poor penalty selection can leave infeasible solutions or poor distributions.The method first ignores infeasible solutions, then calculates normalized violations before applying the penalty parameter.Source: §3.1 · p. 5

3.1.1 Static penalty functions

  • Static penalties increase the coefficient when higher violation levels are reached, while the penalty function itself remains unchanged,.The method introduces several violation levels and changes the static penalty parameter when a higher level is reached.Source: §3.1.1 · p. 6

3.1.2 Dynamic penalty functions

  • Dynamic penalty functions change with iteration number, and the proposed penalty increases as iterations advance.The passage also notes evolutionary algorithms’ attention for dynamic multiobjective problems, where objectives, constraints, or objective-space dimensions can change over time.Source: §3.1.2 · p. 6

3.1.3 Adaptive penalty functions

  • Adaptive penalties use search feedback; one method varies its penalty and distance measure with objective values and constraint violations, while a self-adaptive method tracks feasible individuals and uses improved objective values [63], [64].Penalty factors are added to all objectives, as in single-objective penalty-based constraint handling.Source: §3.1.3 · p. 6
  • An annealing-based multiplicative penalty decreases temperature as iterations increase, thereby increasing the penalty.Source: §3.1.3 · p. 6
  • A co-evolutionary approach evolves solutions and penalty factors in separate subpopulations, using the amount and number of constraint violations.Source: §3.1.3 · p. 6

3.2 Separation of objective function and constraints

This section surveys constraint-handling methods that separate objective values from constraint handling, including a two-phase search that first finds feasible solutions and then optimizes objectives. It details constraint-dominance, epsilon-constrained, and feasibility-rule approaches and their use across population-based algorithms.

3.2 Separation of objective function and constraints

  • Separation-based methods distinguish objective values from constraint handling; the proposed two-phase search first finds feasible solutions, then optimizes the objective function,.Representative methods include stochastic ranking, constraint dominance, epsilon CHT, and feasibility rules.Source: §3.2 · pp. 7–8

3.2.1 Constraint dominance principle

  • Constraint dominance compares feasibility first, constraint violation for infeasible solutions, and objective dominance for feasible ones; NSGAII-CDP selects feasible offspring before infeasible solutions,.CDP was also adopted in the MOEA/D framework.Source: §3.2.1 · p. 8

3.2.2 -constrained (EC) Method

  • The epsilon-constrained method updates ε until control generation T_c; its MOEA/D implementation adapts ε and sets violation thresholds according to constraint type, feasible-space size, and search outcome –.In the method by, infeasible solutions whose violations fall below the threshold are identified.Source: §3.2.2 · p. 8

3.2.3 Feasibility rules

  • Feasibility rules are popular because they integrate across algorithms without adding parameters, and multiobjective variants, or superiority of feasible solution, account for the number of feasible solutions.The search is divided into three cases: no feasible solutions, at least one feasible solution, or a parent-offspring union with more feasible solutions than the next generation can contain.Source: §3.2.3 · p. 8

3.2.3.2 Feasibility rules in PSO

  • Feasibility rules for selection require no new parameters and are largely used in research; they were adopted by evolutionary algorithms including DE, PSO, and GA –.Source: §3.2.3 · p. 8

3.2.3.1 Feasibility rules in Differential Evolution (DE)

  • Feasibility rules have been used in DE, while multiobjective DE studies explored Pareto-based constraint handling and combined frameworks –.Pareto dominance in generalized DE encountered difficulties with more than three constraints and/or objective functions; CCHF combines feasibility rules and multiobjective optimization across feasible, infeasible, and semi-feasible situations.Source: §3.2.3.1 · p. 8

3.2.3.3 Feasibility rules in GA

  • GA variants using feasibility rules performed equally in constrained numerical optimization, while a two-phase GA first minimized violation and then optimized the original objective and constraint satisfaction [105],.Feasibility rules assigned individual fitness in the two-phase framework.Source: §3.2.3 · p. 8, §3.2.3.3 · p. 9

3.2.3.4 Feasibility rules in other population-based algorithms

  • Feasibility rules were also adapted to artificial immune systems, organizational evolutionary algorithms, biogeography-based optimization, and bacterial foraging optimization –.Source: §3.2.3.4 · p. 9

3.3 Retaining infeasible solutions in the population

Constraint handling can retain infeasible individuals during evolution by adding constraint handling to the objective space, while another technique selects individuals by Pareto rank and constraint violation.

3.3 Retaining infeasible solutions in the population

  • Transforming an m-objective problem into m+1 objectives can retain infeasible individuals during evolution,.Source: §3.3 · p. 9
  • A proposed technique selects individuals with low Pareto rank and low constraint violation.Source: §3.3 · p. 9

3.4 Hybrid methods

Hybrid methods combine multiple constraint-handling techniques (CHTs), while the section also surveys state-of-the-art CHTs and their development. It describes four hybrid approaches and several established methods for constrained optimization.

3.4 Hybrid methods

  • Four hybrid approaches combine or sequence CHTs to solve constrained multiobjective problems, with their disadvantages summarized in Figure 3.[117] discusses an ensemble that separates the population into three sub-populations, an adaptive trade-off model containing two CHTs, push-and-pull search, and a two-phase framework. The two-phase framework first weights objectives into a single objective, then applies a constrained MOEA to obtain Pareto-feasible solutions.Source: §3.4 · p. 9, Figure 3 · p. 10
  • The state-of-the-art taxonomy and timeline cover CHTs used since 2000, including feasibility rules, stochastic ranking, and epsilon-constraint and KS-function methods.Stochastic ranking uses a user-defined parameter to control infeasible solutions based on constraint violation and objective values; the epsilon-constraint method transforms a constrained problem into an unconstrained one.Source: §3.4 · p. 10, Figure 4 · p. 10, Figure 5 · p. 11
  • Other methods include boundary search between feasible and infeasible solutions, an added constraint-violation objective, and a four-CHT combination for numerical optimization.The four techniques combined in are feasibility rules, stochastic ranking, a self-adaptive penalty function, and the epsilon-constraint method.Source: §3.4 · p. 10

3.5 Stochastic ranking … 3.8 Repair approaches

These sections describe stochastic ranking and ensemble methods for balancing or combining constraint-handling techniques, then outline multiobjective reformulations and repair approaches. They also note that repair methods can narrow the search to feasible solutions but are problem-specific.

3.5 Stochastic ranking

  • Stochastic ranking balances objective and penalty functions probabilistically, improving benchmark search performance with a user-defined parameter and no complicated variation operators [121].It has also been combined with ant colony optimization,, differential evolution –, and evolutionary programming.Source: §3.5 · p. 11

3.6 Ensemble techniques

  • Ensemble constraint-handling techniques combine methods to improve capability over a single technique, though their competitive performance remains parameter-dependent,.One NSGAII-based MOEA combines nondominated sorting, constrained-domination, multiple constraint ranking, and a dynamic penalty function; other ensembles are reported in,,.Source: §3.6 · p. 11

3.7 Multiobjective concept

  • A constrained single-objective problem can be reformulated as an unconstrained multiobjective problem by adding the sum of constraint violations as an objective,, –.Source: §3.7 · p. 11
  • A taxonomy for constraint handling in multiobjective GAs lists penalty functions, special operators, and repair methods; penalty methods are popular but complicate fitness assignment based on nondomination rank [137].They add the penalty-parameter-weighted sum of constraint violations to each objective value [138],.Source: §3.7 · p. 11
  • OEGADO runs parallel GAs, each optimizing one objective, whereas OSGADO optimizes objectives sequentially using a common population.Source: §3.7 · p. 11

3.8 Repair approaches

  • Repair algorithms reduce the search space by considering only feasible individuals, with approaches for permutation, binary, graph, and grouping representations [140]–.Examples include ordered-list encodings, fixing the number of 1s or using Hopfield networks, spanning-tree repairs, and assigning items to groups.Source: §3.8 · p. 11
  • For highly constrained combinatorial problems, hybridizing population-based exploration with single-solution exploitation can improve both, and local search can act as a constraint handler –.Repair methods also have advantages, but must be designed for the specific problem.Source: §3.8 · p. 12

4 Other approaches

The section surveys renewed work on constrained multiobjective optimization, though research remains more abundant for constrained single-objective optimization. It also summarizes newer approaches and notes that many single-objective constraint-handling techniques can be adapted to multiobjective problems.

Other approaches

  • Table 3 reports renewed interest in constrained multiobjective optimization, despite the greater volume of constrained single-objective research.The table summarizes novel approaches proposed between 2020 and 2021.Source: Table 3 · p. 12, §4 · p. 12
  • Recent proposals include surrogate-assisted evolution [159], KKT-point methods [160],, two-phase differential evolution [162], IoT and cloud computing [163], and partition selection [174].Source: §4 · pp. 12–13
  • Other approaches include an indicator-based handling technique [165], gradient-based repair [166], and decomposition-based algorithms [117],.Source: §4 · p. 13
  • Further proposals include detect-and-escape [168], push-and-pull search, reference-point methods [170], and multi-stage evolutionary algorithms [171],.Source: §4 · p. 13
  • The taxonomy notes that many single-objective constraint-handling methods transfer to multiobjective optimization, sometimes with modification.Methods addressed include stochastic ranking [176], penalty functions [63], multi-objective methods, epsilon-constrained methods, transforming methods, modified feasibility rules [204], hybrid methods, and repair operators.Source: §4 · p. 13

5 Benchmark test problems

Benchmark problems are used to measure evolutionary-algorithm performance and help researchers understand algorithm strengths and weaknesses. The review groups examples into single-objective, multi-objective, and many-objective problems, noting that some are unconstrained.

5 Benchmark test problems

  • Some cited benchmark problems remain unconstrained, so the listed test sets do not all evaluate constraint handling.The review points to for further details on benchmark problems.Source: §5 · p. 13
  • Single-objective examples include Rosenbrock, G01-G09, Himmelblau’s problem, and Pressure Vessel.Other examples include Welded Beam, Tension–Compression Spring, Speed Reducer, and Car side design.Source: §5 · p. 13
  • Multi-objective examples include BNH, OSY, ZDT, BT, and Truss2D.Source: §5 · p. 13
  • Many-objective examples include C-DTLZ, WFG, and DTLZ.Source: §5 · p. 13

Collaborative problems

The scientometric analysis uses bibliometric measures to characterize research on constraint handling in multiobjective population-based optimization. VOSviewer and RStudio were used for the analysis.

6.1 Citation statistics

  • In 2020, the field reached 216 documents and 7,544 citations; WOS indexed 735 related documents with 45,824 citations and 62.35 citations per item.The three most-cited WOS articles were,, and, with 20,013, 2,609, and 1,591 citations, respectively; publication counts rose from 2003 through 2020.Source: §6.1 · p. 15, Figure 7 · p. 15, Figure 8 · p. 16

6.2 Statistics based on document types

  • Articles dominated WOS outputs with 522 publications (71.02%) and 84.10 citations per paper, compared with 220 proceedings papers (29.93%) and 7.01 citations per paper.Conference papers led contributions before 2010, but articles led from 2010 onward.Source: §6.2 · p. 16, Figure 9 · p. 17

6.3 Publication statistics based on journal

  • Lecture Notes in Computer Science, Applied Soft Computing Journal, and Swarm and Evolutionary Computation led Scopus sources with 117, 57, and 30 papers, respectively.Computer Science Artificial Intelligence accounted for 271 articles (36.87%); Computer Science Theory Methods had the highest reported category CPP2020, 190.011.Source: §6.3 · p. 17, Table 6 · p. 18

6.4 Publication statistics by countries

  • China, India, and the USA ranked first through third in Scopus, while WOS ranked China, the USA, and India first through third.China and the USA showed smooth publication trends from 2000–2020, whereas India, the UK, and Australia fluctuated; Australia’s output rose markedly from 2015 to 2016.Source: §6.4 · pp. 19–20, Figure 11 · p. 19, Figure 13 · p. 21

6.5 Statistics based on the subject area

  • Computer science, Engineering, and Mathematics had the most subject-area contributions, with 936, 619, and 580 documents, while Pharmacology had the fewest at 1.Medicine and Economics had 4 and 6 documents, respectively.Source: §6.5 · p. 21, Figure 14 · p. 22

6.6 Statistics based on authors

  • Scopus’s leading authors were Kalyanmoy Deb, Ray T., and Carlos A. Coello Coello with 38, 32, and 28 publications; WOS’s leaders were WANG Y, Coello Coello, and Ray T.Their WOS publication counts were 21, 20, and 17, respectively; 81.5377% of authors had one document. Scopus’s leading multiword keywords included genetic algorithm, constraint handling, and constrained optimization.Source: §6.6 · p. 22, Figure 15 · p. 23, Figure 16 · p. 23

6.7 Statistics on keywords

  • Scopus keyword analysis highlighted multiobjective optimization, Pareto optimal solution, evolutionary algorithm, and artificial intelligence; optimization was the most frequent one-word keyword, at 680 occurrences.39.07979% of manuscripts were 5–10 pages, and 67.09377% were 5–20 pages.Source: §6.7 · pp. 24–25, Table 7 · p. 25, Figure 18 · p. 25

6.8 Publication statistics by number of pages (pages count)

7 Summary and Future Research (RQ7)

The paper reviews constraint-handling techniques (CHTs) for multiobjective population-based algorithms alongside a scientometric analysis. It summarizes methodological limitations and identifies research directions based on recent trends.

7 Summary and Future Research (RQ7)

  • Penalty approaches trade off information and parameter risks: death penalty ignores infeasible points, while static, dynamic, annealing, adaptive, self-adaptive, and SGA variants have problem, convergence, or tuning difficulties.Static penalties are problem-dependent and may need several parameters; dynamic penalties may converge to an infeasible solution or a feasible one far from the global optimum, and annealing penalties are sensitive to their factors. Adaptive parameter setting is difficult, self-adaptive parameters may affect fitness evaluations, and SGA requires selecting penalty factors for each subpopulation.Source: §7 · p. 26
  • Feasible-focused selection can discard useful infeasible information or cause premature convergence, whereas retaining too many infeasible solutions slows convergence despite potential diversity gains.When the population is completely infeasible, the paper recommends choosing solutions with smaller overall constraint violation.Source: §7 · pp. 26–27
  • Other CHTs also trade usability for performance: repair and special operators restrict search, decoders are costly, ensembles are parameter-dependent, and ranking, epsilon, multiobjective, and feasibility-rule methods face adoption or convergence caveats.Stochastic ranking is not often used for multiobjective algorithms; epsilon constraints may converge prematurely or rely on gradient-based mutation, multiobjective concepts may require gradient calculation, and feasibility rules are simple and flexible but can cause premature convergence by favoring feasible solutions.Source: §7 · p. 27
  • Because multiobjective CHTs have received less attention than single-objective methods, the authors recommend further work on BU coupled with MOEAs and constraint handling for many-objective problems with more than three objectives.BU is described as able to handle constraints directly.Source: §7 · p. 27
  • Scopus trends identify multiobjective optimization, constraint optimization, and evolutionary algorithms as leading keywords; GA, DE, PSO and Engineering, Computer Science, and Mathematics are projected to remain prominent.The keywords are reported for 2019–2021; the three research fields are identified as the top fields in the last two years.Source: §7 · p. 27, Table 8 · p. 27, Table 9 · p. 28
  • The authors recommend reviewing constrained MOEA applications in engineering design problems [249][250], scheduling optimization [253][254], and resource optimization.Source: §7 · p. 27

8 Discussion and Conclusion

The paper analyzes constraint-handling techniques in multiobjective evolutionary and swarm-intelligence algorithms and presents a bibliometric analysis of the field. Its results profile citations, publication types and trends, subject areas, countries, authors, and publication patterns.

8 Discussion and Conclusion

  • The study analyzes constraint-handling techniques for multiobjective evolutionary and swarm-intelligence algorithms and presents its claimed first analysis of relevant journals, keywords, authors, and articles.It extracted and analyzed related research articles, reviews, books and book chapters, and conference papers available when the study was written.Source: §8 · p. 28
  • WOS-indexed papers received 45,824 citations (62.35 per item); articles were the most common document type, with 522 (71.02%) and 2.60 authors per publication.The reported average was 1,992.35 citations per year.Source: §8 · p. 28
  • Conference papers contributed most before 2010, but articles led thereafter; Computer Science Artificial Intelligence accounted for 271 articles (36.87%), and the top three categories covered 83.39%.The other two leading categories were Engineering Electrical Electronic and Computer Science Theory Methods, each reported at 23.26%.Source: §8 · p. 28
  • Computer Science Artificial Intelligence, Engineering, and Mathematics led by publication volume; China, the USA, and India were the most active countries.Scopus counts for the three leading subject areas were 936, 619, and 580, respectively.Source: §8 · p. 29
  • Scopus publication counts were led by Kalyanmoy Deb (38), Ray T. (32), and Carlos A. Coello Coello (28); WOS counts were led by WANG Y (21), Coello Coello (20), and Ray T. (17).The Scopus and WOS rankings are reported separately in the paper.Source: §8 · p. 29
  • Most authors had one document (81.5377%), while 67.09377% of manuscripts were 5–20 pages long.Only 0.5241% of authors had more than 10 documents.Source: §8 · p. 29
Loading 2206.13802v1…