I want to start by pointing out that most real optimization problems I run into are not free — they come with constraints. I cannot design a bridge with unlimited material cost, or schedule a factory without respecting machine capacity, or tune a portfolio without keeping risk under some threshold. Constrained Evolutionary Optimization is the branch of evolutionary computation I use specifically to handle these bounded problems: it extends the basic evolutionary algorithm framework with mechanisms that guide the search toward solutions that are not just high-fitness but also feasible, meaning they satisfy all the problem’s constraints. Its importance lies in bridging the gap between elegant unconstrained optimization theory and the messy, constraint-laden problems that show up in engineering, finance, logistics, and beyond.
History and Background
I see constrained evolutionary optimization emerging naturally alongside the broader evolutionary computation field from the 1960s onward, but it matured as its own subfield through the 1990s and 2000s as researchers realized that naive evolutionary algorithms struggled badly with constraints. Early attempts simply rejected infeasible individuals (“death penalty”), which wasted enormous amounts of computation, especially in problems where feasible regions were small. Researchers like Zbigniew Michalewicz did foundational work cataloguing and comparing constraint-handling techniques in the 1990s, and his 1996 book “Genetic Algorithms + Data Structures = Evolution Programs” was influential in formalizing many of the ideas I still use today, such as penalty functions. Later, more sophisticated methods like stochastic ranking (Runarsson and Yao, 2000) and epsilon-constrained methods (Takahama and Sakai, 2006) refined how evolutionary algorithms balance feasibility and objective quality, and these remain widely used building blocks in modern constrained evolutionary optimizers.
Problem Statement
I define the general constrained optimization problem I am solving as: minimize (or maximize) an objective function $f(x)$ subject to a set of inequality constraints $g_i(x) \le 0$ and equality constraints $h_j(x) = 0$, where $x$ lies in some bounded search space. The challenge is that standard evolutionary operators — mutation and crossover — have no inherent awareness of these constraints, so they will happily generate infeasible individuals. The problem constrained evolutionary optimization solves is: how do I guide an evolutionary search so that it spends its effort finding good, feasible solutions, rather than wasting effort exploring or getting trapped in infeasible regions?
Core Concepts
- Feasible region: The subset of the search space where all constraints are satisfied.
- Constraint violation: A measure of how much an individual breaks the problem’s constraints, often summed across all violated constraints.
- Penalty function: A method that reduces (penalizes) the fitness of infeasible individuals in proportion to their constraint violation.
- Repair mechanism: A method that modifies an infeasible individual to make it feasible, rather than penalizing it.
- Feasibility rule: A comparison rule (like Deb’s rule) that prefers feasible individuals over infeasible ones, and among infeasible individuals prefers those with lower constraint violation.
- Multi-objective reformulation: Treating constraint violation as an additional objective to be minimized alongside the original objective.
How It Works
I approach constrained evolutionary optimization as the standard evolutionary loop, but with constraint handling woven into evaluation and selection:
- I initialize a population of candidate solutions, typically at random within the variable bounds.
- For each individual, I evaluate both the objective function $f(x)$ and every constraint function, computing a total constraint violation measure.
- I combine objective and constraint information using a chosen strategy — penalty function, feasibility rules, repair, or a multi-objective approach.
- I perform selection based on this combined criterion, favoring feasible individuals with good objective values over infeasible ones.
- I apply crossover and mutation to generate offspring, same as in standard evolutionary algorithms.
- I re-evaluate offspring for objective value and constraint violation.
- I form the new generation, often applying elitism to retain the best feasible solution found.
- I repeat until a stopping criterion is met, and I return the best feasible solution found.
Working Principle
The internal logic is about reshaping the selection pressure so that it accounts for two competing goals: minimizing the objective and satisfying constraints. I find Deb’s feasibility rule particularly elegant because it avoids the difficulty of tuning penalty coefficients: it says that between two individuals, a feasible one always beats an infeasible one; between two feasible individuals, the one with better objective value wins; and between two infeasible individuals, the one with lower total constraint violation wins. This rule effectively creates a lexicographic priority — feasibility first, objective quality second — which naturally steers the population toward the feasible region without me needing to hand-tune how “expensive” a constraint violation should be relative to the objective.
Mathematical Foundation
The general constrained optimization problem is:
$$ \text{minimize } f(x), \quad x \in \mathbb{R}^n $$
$$ \text{subject to } g_i(x) \le 0, \ i = 1, \dots, m \quad \text{and} \quad h_j(x) = 0, \ j = 1, \dots, p $$
For the penalty function approach, I transform this into an unconstrained problem by defining an augmented fitness:
$$ F(x) = f(x) + \sum_{i=1}^{m} r_i \cdot \max(0, g_i(x))^2 + \sum_{j=1}^{p} r_j \cdot |h_j(x)|^2 $$
where $r_i$ and $r_j$ are penalty coefficients controlling how harshly violations are punished.
The total constraint violation used in feasibility rules is typically defined as:
$$ V(x) = \sum_{i=1}^{m} \max(0, g_i(x)) + \sum_{j=1}^{p} |h_j(x)| $$
Deb’s feasibility comparison rule between two individuals $x_1$ and $x_2$ can be expressed as: $x_1$ is preferred over $x_2$ if any of the following hold:
$$ V(x_1) = 0 \text{ and } V(x_2) = 0 \text{ and } f(x_1) < f(x_2) $$
$$ V(x_1) = 0 \text{ and } V(x_2) > 0 $$
$$ V(x_1) > 0 \text{ and } V(x_2) > 0 \text{ and } V(x_1) < V(x_2) $$
Diagrams
flowchart TD
A["Initialize population"] --> B["Evaluate objective"]
B --> C["Evaluate constraint violation"]
C --> D["Apply constraint handling"]
D --> E["Selection, crossover, and mutation"]
E --> F["Evaluate offspring"]
F --> G{"Stop?"}
G -- No --> C
G -- Yes --> H["Return best feasible solution"]Pseudocode
function ConstrainedEA(f, constraints, pop_size, max_generations):
population = generate_random_population(pop_size)
for generation in 1 to max_generations:
for each individual x in population:
x.objective = f(x)
x.violation = compute_total_violation(x, constraints)
parents = select_parents_using_feasibility_rule(population)
offspring = []
for each pair (p1, p2) in parents:
c1, c2 = crossover(p1, p2)
c1 = mutate(c1)
c2 = mutate(c2)
c1.objective = f(c1); c1.violation = compute_total_violation(c1, constraints)
c2.objective = f(c2); c2.violation = compute_total_violation(c2, constraints)
offspring.append(c1, c2)
population = form_new_population_with_elitism(population, offspring)
if stopping_condition(population):
break
return best_feasible_individual(population)
Step-by-Step Example
I’ll use a simple example: minimize $f(x) = x^2$ subject to the constraint $x \ge 3$ (rewritten as $g(x) = 3 – x \le 0$), over real-valued $x$ in $[-10, 10]$.
Suppose my initial population includes: $x_1 = 1$ ($f=1$, $g=2$, violated), $x_2 = 4$ ($f=16$, $g=-1$, feasible), $x_3 = -2$ ($f=4$, $g=5$, violated), $x_4 = 5$ ($f=25$, $g=-2$, feasible).
- Applying Deb’s rule: $x_2$ beats $x_1$ and $x_3$ because it’s feasible and they’re not.
- Between $x_2$ and $x_4$, both feasible, $x_2$ wins because $f(4)=16 < f(5)=25$.
- Between $x_1$ and $x_3$, both infeasible, I compare violation: $g(x_1)=2$ vs $g(x_3)=5$, so $x_1$ wins for having lower violation.
- So the ranking, best to worst, is: $x_2, x_4, x_1, x_3$.
- Selection favors $x_2$ and $x_4$ as parents. Crossover and mutation might produce a child near $x=3.2$, which is feasible and closer to the true constrained optimum at $x=3$ (where $f(3)=9$).
- Over generations, the population converges toward $x=3$, the boundary of the feasible region, which is exactly where the true constrained minimum lies for this problem.
Time Complexity
Just like a standard evolutionary algorithm, evaluating the population each generation costs $O(N \cdot C)$ where $N$ is population size and $C$ is the cost of evaluating the objective. Constraint handling adds the cost of evaluating each constraint function, so if there are $m$ constraints each costing roughly $C_g$, the per-generation cost becomes $O(N \cdot (C + m \cdot C_g))$. Across $G$ generations, total time is $O(G \cdot N \cdot (C + m \cdot C_g))$. Repair-based methods add extra cost per infeasible individual for the repair procedure itself, which varies depending on how the repair is implemented.
Space Complexity
Space requirements mirror the standard evolutionary algorithm: $O(N \cdot L)$ for storing the population, where $L$ is the encoding length of each individual. I additionally store, per individual, the objective value and total constraint violation, which adds only $O(N)$ overhead, and is negligible compared to the population storage itself.
Correctness Analysis
I look at correctness in terms of whether the search is guaranteed to eventually find feasible, near-optimal solutions. With feasibility-rule-based selection and elitism preserving the best feasible individual found so far, the algorithm is monotonically non-decreasing in solution quality among feasible individuals, meaning it never “forgets” a good feasible solution once found. As with unconstrained evolutionary algorithms, a formal global-optimality guarantee requires assumptions like nonzero mutation probability across the entire space and infinite generations — under those idealized conditions, every feasible point remains reachable, so the algorithm converges to the global constrained optimum in the limit. In finite, practical runs, correctness is empirical: I validate performance on benchmark constrained optimization problems (like the CEC constrained benchmark suites) rather than relying on a formal proof for a specific instance.
Advantages
- It handles constraints without requiring the objective or constraint functions to be differentiable or even continuous.
- Feasibility rules like Deb’s avoid the need to hand-tune penalty coefficients, which is a common pain point with penalty methods.
- It can handle both equality and inequality constraints, as well as highly nonlinear or disjoint feasible regions.
- It integrates naturally with the rest of the evolutionary algorithm framework, requiring only changes to selection and evaluation.
- It works even when the feasible region is small or oddly shaped, which is where many classical constrained optimizers struggle.
Disadvantages
- Poorly tuned penalty coefficients can cause the search to either ignore constraints or become overly conservative.
- Feasibility-rule methods can struggle when the feasible region is extremely small, since early generations may contain no feasible individuals at all to guide the search.
- It generally requires more fitness/constraint evaluations than problem-specific constrained solvers when those are available (e.g., linear or convex problems).
- Performance is sensitive to the choice of constraint-handling technique, and no single technique dominates across all problem types.
- It offers no formal optimality certificate the way convex optimization methods do.
Applications
- Structural engineering design, such as minimizing weight subject to stress and safety constraints.
- Portfolio optimization under risk, budget, and regulatory constraints.
- Power system dispatch problems, respecting generator capacity and transmission constraints.
- Supply chain and logistics optimization with capacity, budget, and time-window constraints.
- Water resource management, respecting reservoir capacity and environmental flow constraints.
- Robot trajectory planning subject to obstacle-avoidance and kinematic constraints.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define POP_SIZE 30
#define GENERATIONS 100
#define MUTATION_STD 0.5
// Problem: minimize f(x) = x^2 subject to g(x) = 3 - x <= 0 (i.e., x >= 3)
// Search space: x in [-10, 10]
typedef struct {
double x;
double objective;
double violation;
} Individual;
double objective_function(double x) {
return x * x;
}
double constraint_violation(double x) {
double g = 3.0 - x; // g(x) <= 0 required
return (g > 0) ? g : 0.0; // violation amount (0 if satisfied)
}
void evaluate(Individual *ind) {
ind->objective = objective_function(ind->x);
ind->violation = constraint_violation(ind->x);
}
double random_uniform(double lo, double hi) {
return lo + (hi - lo) * ((double) rand() / RAND_MAX);
}
// Deb's feasibility rule: returns 1 if a is better than b
int is_better(Individual a, Individual b) {
if (a.violation == 0 && b.violation == 0)
return a.objective < b.objective;
if (a.violation == 0 && b.violation > 0)
return 1;
if (a.violation > 0 && b.violation == 0)
return 0;
return a.violation < b.violation;
}
Individual tournament_select(Individual pop[]) {
Individual best = pop[rand() % POP_SIZE];
for (int i = 0; i < 2; i++) {
Individual challenger = pop[rand() % POP_SIZE];
if (is_better(challenger, best))
best = challenger;
}
return best;
}
double gaussian_noise(double std) {
// Box-Muller transform for approximate Gaussian mutation
double u1 = (double) rand() / RAND_MAX;
double u2 = (double) rand() / RAND_MAX;
return std * sqrt(-2.0 * log(u1)) * cos(2.0 * M_PI * u2);
}
int main() {
srand((unsigned) time(NULL));
Individual population[POP_SIZE], new_population[POP_SIZE];
// Step 1: initialize population randomly in [-10, 10]
for (int i = 0; i < POP_SIZE; i++) {
population[i].x = random_uniform(-10.0, 10.0);
evaluate(&population[i]);
}
for (int gen = 0; gen < GENERATIONS; gen++) {
// Step 2: elitism, keep the best individual per feasibility rule
int best_idx = 0;
for (int i = 1; i < POP_SIZE; i++)
if (is_better(population[i], population[best_idx]))
best_idx = i;
new_population[0] = population[best_idx];
// Step 3: generate rest of population via selection + mutation
for (int i = 1; i < POP_SIZE; i++) {
Individual parent = tournament_select(population);
Individual child = parent;
child.x += gaussian_noise(MUTATION_STD);
if (child.x < -10) child.x = -10;
if (child.x > 10) child.x = 10;
evaluate(&child);
new_population[i] = child;
}
for (int i = 0; i < POP_SIZE; i++)
population[i] = new_population[i];
printf("Generation %d: best x = %.4f, f(x) = %.4f, violation = %.4f\n",
gen, population[0].x, population[0].objective, population[0].violation);
}
return 0;
}
Sample Input and Output
For the problem of minimizing $f(x) = x^2$ subject to $x \ge 3$, over $[-10,10]$, a typical run outputs something like:
Generation 0: best x = 3.7421, f(x) = 14.0033, violation = 0.0000
Generation 20: best x = 3.0891, f(x) = 9.5423, violation = 0.0000
Generation 60: best x = 3.0021, f(x) = 9.0126, violation = 0.0000
Generation 99: best x = 3.0000, f(x) = 9.0000, violation = 0.0000
The population converges to $x = 3$, exactly at the constraint boundary, which is the true constrained minimum since the unconstrained minimum at $x=0$ is infeasible.
Optimization Techniques
- Adaptive penalty coefficients: I adjust penalty weights dynamically based on how many individuals are currently feasible, increasing pressure if too many individuals remain infeasible.
- Stochastic ranking: I probabilistically decide, when comparing individuals, whether to rank by objective or by constraint violation, which balances exploration of the boundary region with pure feasibility pressure.
- Epsilon-constrained method: I relax the feasibility requirement slightly at first (allowing some violation) and shrink this tolerance over generations, helping the search approach constraint boundaries more smoothly.
- Repair operators: For problems where I can cheaply “fix” an infeasible solution (e.g., clipping values back into range or projecting onto a constraint), repairing is often more efficient than penalizing.
- Boundary-focused mutation: Since many constrained optima lie exactly on constraint boundaries, biasing mutation to explore near known active constraints speeds up convergence.
Common Mistakes
- Using a fixed, poorly chosen penalty coefficient that either makes constraints irrelevant (too small) or makes the search overly conservative (too large).
- Forgetting to track and preserve the best feasible solution across generations, especially when the algorithm briefly loses feasibility.
- Applying feasibility rules without any mechanism to handle the case where the entire initial population is infeasible, which can stall the search.
- Not normalizing constraint violation across constraints of very different scales, which biases the search toward satisfying only the constraints with large numeric magnitude.
- Ignoring equality constraints’ inherent difficulty — treating them the same as inequality constraints without relaxing them into a small tolerance band often prevents any individual from ever reaching exact feasibility.
Further Reading
- Michalewicz, Z. “Genetic Algorithms + Data Structures = Evolution Programs.” Springer, 1996: https://link.springer.com/book/10.1007/978-3-662-03315-9
- Deb, K. “An Efficient Constraint Handling Method for Genetic Algorithms.” Computer Methods in Applied Mechanics and Engineering, 2000: https://www.sciencedirect.com/science/article/pii/S0045782599003898
- Runarsson, T. P., Yao, X. “Stochastic Ranking for Constrained Evolutionary Optimization.” IEEE Transactions on Evolutionary Computation, 2000: https://ieeexplore.ieee.org/document/873238
- Coello Coello, C. A. “Theoretical and Numerical Constraint-Handling Techniques used with Evolutionary Algorithms: A Survey of the State of the Art.” Computer Methods in Applied Mechanics and Engineering, 2002: https://www.sciencedirect.com/science/article/pii/S0045782501003231
- Wikipedia overview of constrained optimization: https://en.wikipedia.org/wiki/Constrained_optimization
