How Evolutionary Algorithms Learn to Juggle Conflicting Goals and Hard Constraints

Some of the hardest problems in modern engineering do not have a single right answer. Designing an aircraft wing, scheduling a fleet of vehicles, or allocating power across a grid all involve objectives that fight against each other: improving one metric tends to worsen another. On top of that, real-world designs must obey hard rules, from material strength limits to emission caps, that no amount of clever trade-offs can break. A new comprehensive review published in the open-access journal Vicinagearth by Jing Liang, Hongyu Lin, Caitong Yue, Xuanxuan Ban, and Kunjie Yu of Zhengzhou University maps the entire landscape of algorithms built to solve these so-called constrained multi-objective optimization problems, and it arrives at a moment when the field is both maturing rapidly and facing a fresh wave of challenges.

The mathematical skeleton of such a problem is deceptively simple. There is a vector of decision variables, a set of objective functions to be minimized simultaneously, and two families of constraints: inequality constraints that must not be exceeded and equality constraints that must be met exactly. A solution is called feasible if it violates none of the constraints, and the total constraint violation is measured as the sum of the individual violations across every rule. What makes these problems treacherous is that the objectives usually conflict, so no single solution can be best at everything. Instead, the goal is to find a whole set of solutions that are mutually non-dominated, meaning no member of the set is better than another in every objective. This collection of trade-off points, projected into objective space, forms the Pareto front, and when constraints are added, the algorithm must chase the constrained Pareto front, a potentially very different target.

The review highlights a crucial subtlety that often surprises newcomers: the unconstrained Pareto front and the constrained Pareto front can relate to each other in four distinct ways. In the easiest case, the two fronts completely overlap, so every optimal trade-off point is already feasible. In harder cases, the constrained front is a subset of the unconstrained one, or the two only partially overlap, or, most brutally, they are entirely separate, with the unconstrained front lying wholly in infeasible territory. This taxonomy matters because many algorithms work by first pushing a population toward the unconstrained front and then pulling it back toward feasibility. That strategy shines when the two fronts are close, but it can fail badly when they point in different directions, a lesson the authors demonstrate with new experimental comparisons.

At the heart of every constrained multi-objective evolutionary algorithm sit two components: a multi-objective evolutionary engine, which may be dominance-based, decomposition-based, or indicator-based, and a constraint handling technique that decides how to weigh feasible against infeasible solutions during selection. The review walks through the classic techniques with unusual clarity. Penalty function methods fold constraint violation into the fitness value, and the entire art lies in choosing the penalty coefficient: too small and the population never finds feasible solutions, too large and it gets trapped in the first feasible pocket it stumbles into. Static, dynamic, and adaptive variants each try to thread this needle differently.

The constrained domination principle, introduced by Deb and colleagues in the landmark NSGA-II algorithm, takes a more direct route: any feasible solution beats any infeasible one, two infeasible solutions are compared by their degree of violation, and two feasible solutions are compared by ordinary Pareto dominance. It is simple, easy to embed, and converges fast, but its bias toward feasibility makes it hard for a population to cross large infeasible barriers that may separate it from the true constrained front. The epsilon constrained method, due to Takahama and Sakai, softens this by relaxing the constraint boundary with a tolerance parameter, treating mildly infeasible solutions as if they were feasible. As epsilon shrinks toward zero over the run, the method gradually recovers the strict rules while harvesting useful information from high-quality infeasible solutions along the way. Stochastic ranking adds a probabilistic twist, occasionally ignoring constraints entirely with a tunable probability, while multi-objective methods go further and promote constraint violation itself to the status of an extra objective, though this risks inflating the problem into a many-objective one where selection pressure evaporates.

Beyond these foundational techniques, the review organizes the modern algorithm zoo into six families, and this classification is arguably its most useful contribution. Some methods design new fitness functions that blend objectives and constraint violations with adaptive or dynamic weights, often using the proportion of feasible solutions in the population as a feedback signal. Others enhance the classical constraint handling techniques themselves, for example by folding angle information into the constrained domination principle so that high-quality infeasible solutions survive selection and help the population leap across infeasible regions. Constraint relaxation methods tune the epsilon boundary dynamically, sometimes using the maximum and minimum violation values observed among infeasible individuals, and even deploy detect-and-escape mechanisms that relax constraints when the population shows signs of evolutionary stagnation.

Two of the six families have produced some of the field’s most striking recent successes. Two-stage optimization methods split the run into phases: the push-and-pull search framework, for instance, ignores all constraints in the first phase so the population can race to the unconstrained front unimpeded, then uses an improved epsilon method to pull it back toward the constrained front. Auxiliary population methods run a second population alongside the main one, often letting the helper ignore constraints entirely so it can scout the unconstrained front and transfer that knowledge back. The coevolutionary framework CCMO, which pairs a feasibility-focused main population with a constraint-free helper, and the multitasking approach MTCMO, which treats the helper as a separate optimization task with an improved epsilon mechanism, both exemplify this cooperative philosophy. A sixth family rewrites the reproduction operators themselves, using differential evolution mutation strategies that explicitly exploit promising infeasible solutions to generate offspring with better convergence and diversity.

The review does not stop at taxonomy; it also runs head-to-head experiments. Six representative algorithms, including DSPCMDE, MOEADDAE, PPS, CCMO, MTCMO, and CMOCSO, were tested on three benchmark suites with contrasting personalities: LIR-CMOP, whose narrow feasible regions are riddled with infeasible blocks; MW, with tiny, discontinuous feasible regions defined in objective space; and SDC, a newer suite where constraints and objectives share a chaotic, non-monotonic relationship. Each algorithm ran twenty times per problem with a population of one hundred and one hundred thousand evaluations, scored by the inverted generational distance metric on the PlatEMO platform. The results are instructive rather than triumphant for any single method. CMOCSO, with its competitive-and-cooperative swarm operators, dominated LIR-CMOP, taking best or second-best on thirteen of fourteen problems. CCMO and MTCMO led on MW, confirming that mining unconstrained-front information pays off there. But on SDC, where chasing the unconstrained front can actually move the population away from the constrained one, DSPCMDE’s redesigned fitness function proved superior. Friedman’s test ranked CMOCSO first overall and MTCMO second, yet the differences were modest, underscoring the review’s central message that no algorithm wins everywhere and that matching strategy to problem structure is the real game.

The benchmark section itself doubles as a history of the field’s growing rigor, from the pioneering SRN, TNK, and OSY problems of the 1990s through the adjustable-difficulty CTP and DAS-CMOP suites to recent constructions like ZXH_CF, DCMOP with its deceptive constraints that punish solutions precisely where they seem closest to the front, and the real-world RWCMOP collection of fifty engineering problems spanning mechanical design, chemical engineering, power electronics, and power systems. This progression reflects a deliberate effort to expose algorithms to narrow feasible regions, disconnected fronts, multimodality, and deception, features that older, gentler benchmarks simply never tested.

Looking forward, the authors identify five frontiers where current methods strain. Computationally expensive problems, such as those involving computational fluid dynamics, allow only a few thousand real evaluations, making surrogate models that mimic the fitness landscape essential. Multimodal problems hide multiple distinct sets of Pareto-optimal solutions mapping to the same front, demanding strong diversity preservation and mode recognition. Large-scale problems, with hundreds or thousands of decision variables, require dimension reduction and variable grouping to avoid drowning in the search space. Multi-task optimization, which could let experience transfer between related constrained problems, still needs principled knowledge-transfer mechanisms. And dynamic problems, where objectives or constraints shift over time as in fluid catalytic cracking or mineral beneficiation, force algorithms to detect environmental change in real time and decide whether yesterday’s population is worth keeping. With the field already logging thousands of accesses and dozens of citations for this review, its map of what works, what fails, and what remains unsolved is likely to steer the next generation of algorithms toward exactly these open problems.

Subject of Research: Evolutionary algorithms for constrained multi-objective optimization problems

Article Title: Evolutionary constrained multi-objective optimization: a review

Article References: Liang, J., Lin, H., Yue, C., Ban, X., & Yu, K. (2024). Evolutionary constrained multi-objective optimization: a review. Vicinagearth, 1(1), Article 5. https://doi.org/10.1007/s44336-024-00006-5

Image Credits: AI Generated

DOI: 10.1007/s44336-024-00006-5

Keywords: constrained multi-objective optimization, evolutionary algorithms, constraint handling, Pareto front, NSGA-II, epsilon constrained method, benchmark test problems, push and pull search, auxiliary populations, differential evolution, surrogate models, multi-task optimization