Offensive Security Researcher & Quantum Cryptography Analyst

Constrained Evolutionary Optimization Algorithm: Working and Applications

Abdul Wahab Junaid
Constrained Evolutionary Optimization algorithm and working of this algorithm.

Constrained Evolutionary Optimization algorithm and working of this algorithm.

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

How It Works

I approach constrained evolutionary optimization as the standard evolutionary loop, but with constraint handling woven into evaluation and selection:

  1. I initialize a population of candidate solutions, typically at random within the variable bounds.
  2. For each individual, I evaluate both the objective function $f(x)$ and every constraint function, computing a total constraint violation measure.
  3. I combine objective and constraint information using a chosen strategy — penalty function, feasibility rules, repair, or a multi-objective approach.
  4. I perform selection based on this combined criterion, favoring feasible individuals with good objective values over infeasible ones.
  5. I apply crossover and mutation to generate offspring, same as in standard evolutionary algorithms.
  6. I re-evaluate offspring for objective value and constraint violation.
  7. I form the new generation, often applying elitism to retain the best feasible solution found.
  8. 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).

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

Disadvantages

Applications

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

Common Mistakes

Further Reading

Exit mobile version