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
TL;DR
The paper addresses the limited understanding of constraint handling techniques across single-objective and multiobjective population-based optimization. It reviews these techniques and analyzes the scholarly literature through bibliometric and scientometric measures. The study concludes that multiobjective constraint handling has received less attention than single-objective work and highlights genetic algorithms, differential evolutionary algorithms, and particle swarm intelligence as promising approaches.
Problem
The study addresses limited understanding and comparatively limited attention to constraint handling techniques for multiobjective population-based optimization.
Method
The paper reviews constraint handling techniques and analyzes relevant research articles, reviews, books, book chapters, and conference papers using literature and scientometric analysis.
Results
Multiobjective constraint handling has received much less attention than single-objective optimization, with genetic algorithms, differential evolutionary algorithms, and particle swarm intelligence identified as promising algorithms.
Takeaways & Limitations
Future work should focus on multiobjective and many-objective constraint handling, including coupling boundary update techniques with multiobjective evolutionary algorithms.
Takeaways & Limitations
Constraint handling techniques have scope-specific trade-offs: retaining many infeasible solutions may reduce convergence speed, while special operators have limited applicability and decoders can be computationally costly.
Abstract
from arXiv · showhide
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 study introduces constraint handling techniques for population-based evolutionary and swarm algorithms, motivated by the difficulty of constrained multiobjective optimization. It frames a literature-analysis agenda around technique characteristics, disadvantages, publication patterns, research communities, and future gaps.
- Motivation: Multiobjective optimization involves trade-offs among objectives, so no single solution satisfies all objectives simultaneously.The paper presents evolutionary computation as suitable for such problems because Pareto-front form is not decisive for these methods.
- Constraint handling: Constraint evolutionary algorithm optimization combines an evolutionary algorithm with a constraint handling technique to solve constrained problems.The introduction describes constraint handling as part of the algorithmic framework for constrained optimization.
- Constraint handling: Prior techniques include infeasibility ranking, constraint and objective prioritization, controlled mutation, and multiple non-dominated rankings.These approaches differ in how they classify infeasible individuals, preserve feasible-solution diversity, or rank solutions.
- Constraint handling: Adaptive trade-off models address populations containing only infeasible solutions, mixed feasible and infeasible solutions, or only feasible solutions.The cited model targets evaluation and selection decisions across these three population states.
- Research gap: Most reviewed studies focus on single-objective constraint handling, while multiobjective applications receive comparatively little attention.The paper attributes this partly to the expectation that single-objective methods can be modified for multiobjective optimization.
- Study scope: The research questions cover technique importance and disadvantages, keywords, journals, researchers, countries, affiliations, statistics, gaps, and future directions.The study also outlines sections covering methodology, constraint handling techniques, multiobjective genetic algorithms, scientometric analysis, and recommendations.
2. Research Methodology
The research procedure begins by collecting relevant documents from Scopus and Web of Science using targeted constraint-handling and multiobjective optimization search terms.
- Document collection: Documents were gathered from Scopus and Web of Science in the first stage of the research procedure.The procedure used database searches as its initial document-collection stage.
- Search strategy: The database search used combinations of terms for constrained or constraint handling, multiobjective, evolutionary, and swarm optimization.These terms were applied through TITLE-ABS-KEY queries.
3. Constraint Handling Methods in Evolutionary Algorithms (RQ1)
Constraint-handling methods in evolutionary algorithms are organized into penalty, decoder, special-operator, separation, infeasible-retention, and hybrid approaches. Penalty functions are common but depend on suitable penalty design and can cause computational or convergence problems.
- Method taxonomy: Constraint-handling methods include penalty functions, decoders, special operators, separation methods, retaining infeasible solutions, and hybrid methods.Decoders map search domains to feasible spaces, while special operators preserve feasibility or move solutions within specified regions.
- Penalty functions: Penalty variants include death, dynamic, static, adaptive, stochastic-ranking, annealing-based, and co-evolutionary penalty functions.Dynamic penalties change with iteration number, adaptive penalties use search feedback, and co-evolutionary methods evolve solutions and penalty factors separately.
- Penalty functions: Penalty functions modify objective values using constraint violations, with interior and exterior forms distinguished by whether an initial feasible solution is required.Exterior penalties do not require an initial feasible solution, whereas interior methods do.
- Penalty functions: Penalty methods require normalized constraint violations, which are aggregated and added to objective values through a penalty parameter.The penalty parameter must be selected appropriately for MOEAs to work well.
- Limitations: Penalty approaches can consume many evaluations, cause premature convergence or infeasible solutions, and produce weak algorithm performance or poor solution distributions.Reported disadvantages also include time-consuming evolution and penalties that become too weak or too strong.
3.2 Separation of objective function and constraints
Separation methods treat objective values and constraint handling as distinct components, often prioritizing feasibility before objective optimization. Feasibility rules compare solutions by feasibility, violation, and dominance, and have been adapted across several population-based algorithms.
- Separation principle: Separation methods divide the search into feasibility and objective-optimization phases rather than combining objective and constraint values directly.Representative approaches include stochastic ranking, constraint dominance, epsilon constraint handling, and feasibility rules.
- Constraint dominance principle: Constraint dominance ranks a feasible solution above an infeasible one, compares infeasible solutions by violation, and compares feasible solutions by dominance.NSGAII-CDP divides the population into feasible and infeasible subpopulations.
- Epsilon constraint handling: The epsilon-constrained method updates an epsilon threshold until a control-generation parameter is reached, with adaptive variants embedded in MOEA/D.The threshold depends on constraint type, feasible-space size, and search outcome.
- Feasibility rules: Feasibility rules require no additional parameters and can be integrated into algorithms including differential evolution, particle swarm optimization, and genetic algorithms.The search space is described in three phases based on whether feasible solutions exist and how many are present.
- Algorithm applications: Feasibility rules have been adapted to differential evolution, particle swarm optimization, genetic algorithms, artificial immune systems, organizational evolutionary algorithms, biogeography-based optimization, and bacterial foraging optimization.They have been widely used in differential evolution but rarely in multiobjective differential evolution.
3.3 Retaining infeasible solutions in the population
An alternative constraint-handling strategy retains infeasible individuals during evolution by transforming an m-objective constrained problem into an (m+1)-objective problem. This preserves information from infeasible solutions while enabling selection based on Pareto rank and constraint violation.
- Infeasible-solution retention: Retaining infeasible solutions transforms a constrained problem with m objectives into one with m+1 objectives.The added objective represents constraint handling and allows infeasible solutions to remain in the evolutionary population.
- Selection: One proposed technique selects individuals with both low Pareto rank and low constraint violation.
3.4 Hybrid methods
Hybrid constraint-handling methods combine multiple techniques to address constrained multiobjective optimization, while the review also organizes state-of-the-art approaches and their disadvantages.
- Hybrid methods: Hybrid methods combine several constraint-handling techniques for constrained multiobjective optimization.Examples include ensemble methods, adaptive trade-off models, push-and-pull search, and two-phase frameworks.
- Disadvantages: Penalty-function methods require choosing appropriate penalty parameters.The review lists parameter selection as a principal disadvantage of the penalty-function method.
- State-of-the-art overview: The review presents a taxonomy and timeline of state-of-the-art constraint-handling techniques used since 2000.The taxonomy is attributed to, while the timeline covers techniques introduced from 2000 onward.
- Hybrid methods: The review discusses feasibility rules, stochastic ranking, self-adaptive penalty functions, and epsilon-constraint methods as combined approaches.These techniques are described as a combination used for constrained numerical optimization problems.
3.5 Stochastic ranking
Stochastic ranking balances objective and penalty functions probabilistically, while the broader review describes penalty, repair, and hybrid constraint-handling strategies and their trade-offs.
- Stochastic ranking: Stochastic ranking balances objective and penalty functions using a user-defined parameter.It was reported to improve search performance without introducing complicated variation operators.
- Penalty methods: Penalty-function methods are widely used in constrained multiobjective optimization but are not straightforward when fitness assignment relies on nondomination rank.Constraint violations are incorporated alongside multiobjective function assessments.
- Repair methods: Repair algorithms reduce the search space by retaining feasible individuals and can be adapted to permutations, binary representations, graphs, and grouping problems.The review lists several representation-specific repair procedures.
- Hybrid search: Pure evolutionary algorithms may perform poorly on complex combinatorial problems with many constraints, motivating hybridization with single-solution methods.Population-based methods emphasize exploration, whereas local search and simulated annealing emphasize exploitation.
- Limitations: Repair algorithms are problem-specific and must be designed for the particular problem.The review identifies this specificity as a disadvantage of repair approaches.
4 Other approaches
The review identifies renewed interest in constrained multiobjective optimization and catalogs newer approaches spanning surrogate, decomposition, repair, indicator-based, and multi-stage methods.
- Recent developments: Recent work shows renewed interest in constrained multiobjective optimization despite substantially more research on constrained single-objective optimization.This conclusion is based on approaches summarized for 2020–2021.
- Recent developments: Other listed approaches include indicator-based constraint handling, gradient-based repair, decomposition-based algorithms, and push-and-pull search.The review also identifies detect-and-escape, reference-point, and multi-stage evolutionary methods.
- Taxonomy: The review summarizes constraint-handling techniques in multiobjective evolutionary algorithms through a general taxonomy.It notes that many techniques developed for single-objective optimization can also be applied to multiobjective optimization.
5 Benchmark test problems
The review situates constrained multiobjective optimization within a broader set of evolutionary and mathematical approaches and emphasizes benchmark problems for evaluating algorithm performance.
- Applications: Genetic algorithms are identified among the methods used for multiobjective wireless network optimization.This application appears in the listed approaches for constrained multiobjective optimization.
- Benchmark test problems: Benchmark and test problems help researchers understand the strengths and weaknesses of evolutionary algorithms.The review describes benchmark problems as tools for performance measurement and algorithm comparison.
- Approach categories: The review distinguishes constrained multiobjective optimization from other methods, including surrogate models and mathematical algorithms.These categories appear in the overview of approaches to constrained multiobjective optimization.
Collaborative problems
The scientometric analysis maps publication growth, document types, categories, journals, countries, authors, and keywords in constrained multiobjective population-based optimization. The field expanded substantially through 2020, with articles, China, and artificial-intelligence categories prominent across the reported indicators.
- Publication and citation growth: In 2020, the field reached 216 documents and 7544 citations, while publication counts had increased significantly since 2003.Across 735 WOS documents, 45824 citations were identified, with 62.35 citations per item.
- Document types: 735 publications were identified, including 522 articles and 220 proceedings papers; articles represented 71.02% of the indexed documents.Articles also had the highest CPP2020 at 84.10, compared with 7.01 for proceedings papers.
- Categories: Computer Science Artificial Intelligence was the leading category, containing 271 articles, while Computer Science Theory Methods had the highest CPP2020 at 190.011 among the top categories.Computer Science Artificial Intelligence accounted for 36.87% of the 735 articles.
- Journals: Lecture Notes In Computer Science, Applied Soft Computing Journal, and Swarm and Evolutionary Computation published the most papers, with 117, 57, and 30 contributions, respectively.These journals predominate in optimization and evolutionary computation.
- Countries: China, India, and the USA were the top three countries by Scopus publications, whereas China, the USA, and India ranked first through third in WOS.The country rankings differed between the two databases, particularly for India and the USA.
- Keywords: The keyword analysis identifies multiobjective optimization, Pareto optimal solution, and evolutionary algorithms among the field’s prominent themes.Keyword networks encode co-occurrence, while node size represents usage frequency and color indicates earlier or more recent use.
7 Summary and Future Research (RQ7)
The paper summarizes constraint-handling techniques for multiobjective population-based algorithms and identifies their practical disadvantages and research gaps. It reports that multiobjective constraint handling remains less studied than the single-objective case.
- Scope: The study reviews constraint-handling techniques applied to multiobjective population-based algorithms and combines this overview with a scientometric analysis.Its technical discussion defines the main constraint-handling ideas before analyzing the literature.
- Penalty methods: Penalty methods involve distinct trade-offs: static penalties are problem-dependent, dynamic penalties may miss the global optimum, and adaptive methods require difficult parameter settings.The cited summary also notes sensitivity in annealing penalties and added parameters in self-adaptive penalties.
- Other techniques: Repair methods and special genetic operators focus on feasible space, while constraint dominance can discard information from infeasible individuals and many infeasible solutions can reduce convergence speed.Decoder methods carry high computational cost, ensemble methods are parameter-dependent, and epsilon constraints can exhibit premature convergence in some cases.
- Research gap: Constraint-handling techniques for multiobjective optimization have received much less attention than techniques for single-objective optimization.The paper identifies multiobjective optimization, constraint optimization, and evolutionary algorithms as prominent recent keywords and research fields.
8 Discussion and Conclusion
The study analyzes constraint handling in population-based optimization through literature coverage and bibliometric indicators. It reports broad publication patterns, leading research categories and contributors, and the study’s funding and conflict disclosures.
- The study evaluates constraint handling techniques for multiobjective population-based algorithms and analyzes relevant journals, keywords, authors, articles, and other publication types.The analyzed corpus includes research articles, reviews, book chapters, and conference papers.
- 45,824 citations were received by related papers in WOS, averaging 1,992.35 citations per year and 62.35 citations per item.
- 522 articles represented 71.02% of WOS documents, with 2.60 authors per publication.
- Computer Science Artificial Intelligence contributed 271 articles, or 36.87% of the total, while the first three WOS categories accounted for 83.39%.The first three categories were Computer Science Artificial Intelligence, Engineering Electrical Electronic, and Computer Science Theory Methods.
- China, the USA, and India were the three most active countries, while computer science, engineering, and mathematics had the most Scopus contributions.Their contribution counts were 936, 619, and 580 published articles, respectively.
- The research received no external funding, and the authors declared no conflict of interest.