Evolutionary Algorithms: Population-Based Optimization

When one fitness number stops being enough

A team building an on-device image classifier for a budget Android phone (the kind that ships to first-time internet users across UP and Bihar on a 2 GB RAM, sub-₹8,000 device) is not optimizing one thing. A model that is 40 MB and 99% accurate is useless if the phone has 3 GB of storage split across WhatsApp, YouTube, and family photos. A model that is 2 MB and 60% accurate is useless because it misclassifies half its inputs. The team needs a model that is small and accurate and, if it runs on-device rather than calling a server, fast enough not to drain the battery. These three goals actively fight each other: shrinking a network usually raises its error rate, and pruning layers for speed usually costs both size headroom and accuracy.

The genetic algorithm from the sibling chapter on evolutionary optimization, and the evolution strategies (CMA-ES, OpenAI-ES) used to train RL policy weights, both share an assumption worth naming explicitly: there is exactly one scalar fitness value to maximize or minimize per candidate. Every selection step in a standard GA or ES ranks candidates by a single number. That assumption breaks the moment a real engineering problem has two or more objectives that do not reduce to one number without someone first deciding how much accuracy is "worth" in megabytes, which is a business decision, not a mathematical one. This chapter covers the branch of the evolutionary-algorithms family built specifically for that situation: multi-objective evolutionary algorithms, worked through the algorithm that made them practical at scale, NSGA-II.

Pareto dominance: comparing candidates without collapsing them into one number

Suppose every candidate model is scored on two objectives to be minimized: size in megabytes and error rate in percent. Candidate A dominates candidate B, written A ≺ B, exactly when A is no worse than B on every objective and strictly better on at least one. Formally, for objective vectors a = (a₁, a₂) and b = (b₁, b₂):

A dominates B  ⇔  (a₁ ≤ b₁ AND a₂ ≤ b₂) AND (a₁ < b₁ OR a₂ < b₂)

Take A = (4 MB, 5%) and B = (4 MB, 6%). Same size, A strictly lower error — A dominates B, because "no worse in either, strictly better in at least one" only needs the tie broken somewhere. Now take A = (3 MB, 6%) and C = (5 MB, 3%). Neither dominates the other: A wins on size, C wins on error. Two candidates in this relationship are called non-dominated with respect to each other, and both represent genuinely different, defensible trade-offs. The set of solutions that no other solution dominates is the Pareto front — not one answer, but the entire menu of best trade-offs, with the actual choice among them left to whoever understands the deployment constraint (does this app ship to 2 GB-RAM phones or 6 GB ones?).

A single-objective GA cannot represent this menu at all — its selection operator needs a strict ranking, and a strict ranking would force a premature choice about how much accuracy one megabyte is worth. Pareto dominance is a partial order: some pairs compare, some don't. That's the entire reason a specialized evolutionary machinery is needed on top of ordinary GA variation operators (crossover and mutation, covered in the sibling chapter and unchanged here) — something has to convert "many solutions, partially ordered" back into "which N survive to the next generation."

NSGA-II: fast non-dominated sorting plus the crowding operator

The Non-dominated Sorting Genetic Algorithm II, published by Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and T. Meyarivan in IEEE Transactions on Evolutionary Computation in 2002 ("A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II"), is the algorithm that made multi-objective evolutionary search tractable enough for routine engineering use. It runs the same crossover-and-mutation loop as a standard GA, but replaces "sort by fitness, keep the top N" with two new pieces of machinery for choosing survivors: fast non-dominated sorting, which layers the whole population into fronts, and the crowding distance, which measures how densely packed a solution's neighborhood on its front is.

Fast non-dominated sorting. For every candidate p, track two things: n_p, the number of population members that dominate p, and S_p, the set of members p itself dominates. Every candidate with n_p = 0 is dominated by nobody — that's Front 1, the current Pareto front. Peel Front 1 out, and for every member q that any Front-1 solution used to dominate, decrement n_q by one; whichever q's drop to zero form Front 2. Repeat until every candidate is assigned a front. This runs in O(MN²) for M objectives and N candidates, versus the O(MN³) of the original NSGA — the "fast" in the name is literal, not marketing.

Crowding distance. Within one front, all solutions are equally "good" in the dominance sense, so a second tie-breaker is needed that has nothing to do with dominance: diversity. For each objective, sort the front's members by that objective's value, give the two boundary (extreme) members infinite distance so they're always kept, and for every interior member add the normalized gap between its two neighbors on that objective. Summed across all objectives, a solution sitting in a sparse stretch of the front gets a large crowding distance; a solution sandwiched between near-duplicates gets a small one. NSGA-II's survivor selection then applies the crowded-comparison operator: prefer the lower (better) front rank first, and among equal ranks, prefer the larger crowding distance. Combined with elitism — parents and offspring are pooled into one set of 2N candidates before this selection runs, so a good solution can never be discarded just because that generation's offspring were worse — the population converges toward the true front while spreading itself evenly along it, instead of collapsing onto one lucky corner.

Worked example: sorting six on-device model candidates

Six trained candidate models are scored on (size in MB, error in %), both to be minimized: P1 = (1, 9), P2 = (2, 6), P3 = (3, 4), P4 = (5, 3), P5 = (4, 7), P6 = (6, 2). By hand: P5 is dominated by P2 (2≤4 and 6≤7, strictly better on size) and separately by P3 (3≤4 and 4≤7, strictly better on both) — so P5 cannot be in Front 1. Every other pair trades off (whoever is smaller in size is larger in error), so P1, P2, P3, P4, P6 form Front 1 and P5 alone forms Front 2. The code below implements exactly this and prints the fronts, then computes crowding distance across Front 1's five members.

def dominates(a, b):
    """True if solution a Pareto-dominates b (both objectives minimized)."""
    not_worse = all(x <= y for x, y in zip(a, b))
    strictly_better = any(x < y for x, y in zip(a, b))
    return not_worse and strictly_better

def fast_non_dominated_sort(pop):
    S = {p: [] for p in pop}      # solutions each p dominates
    n = {p: 0 for p in pop}       # how many solutions dominate p
    fronts = [[]]
    for p in pop:
        for q in pop:
            if p == q:
                continue
            if dominates(pop[p], pop[q]):
                S[p].append(q)
            elif dominates(pop[q], pop[p]):
                n[p] += 1
        if n[p] == 0:
            fronts[0].append(p)
    i = 0
    while fronts[i]:
        next_front = []
        for p in fronts[i]:
            for q in S[p]:
                n[q] -= 1
                if n[q] == 0:
                    next_front.append(q)
        i += 1
        fronts.append(next_front)
    fronts.pop()  # drop the trailing empty front
    return fronts

def crowding_distance(front, pop, num_obj=2):
    dist = {p: 0.0 for p in front}
    for m in range(num_obj):
        ranked = sorted(front, key=lambda p: pop[p][m])
        dist[ranked[0]] = float("inf")
        dist[ranked[-1]] = float("inf")
        lo, hi = pop[ranked[0]][m], pop[ranked[-1]][m]
        if hi == lo:
            continue
        for i in range(1, len(ranked) - 1):
            prev_val = pop[ranked[i - 1]][m]
            next_val = pop[ranked[i + 1]][m]
            dist[ranked[i]] += (next_val - prev_val) / (hi - lo)
    return dist

pop = {
    "P1": (1, 9), "P2": (2, 6), "P3": (3, 4),
    "P4": (5, 3), "P5": (4, 7), "P6": (6, 2),
}

fronts = fast_non_dominated_sort(pop)
print(fronts)
# [['P1', 'P2', 'P3', 'P4', 'P6'], ['P5']]

cd = crowding_distance(fronts[0], pop)
for name in fronts[0]:
    d = cd[name]
    print(name, "inf" if d == float("inf") else round(d, 4))
# P1 inf
# P2 1.1143
# P3 1.0286
# P4 0.8857
# P6 inf

Trace the crowding numbers by hand for P2, sitting between P1 and P3. Sorted by size, its neighbors are P1 (1 MB) and P3 (3 MB), and the front's size range is 6 − 1 = 5, giving a size-distance contribution of (3 − 1)/5 = 0.4. Sorted by error, P2's neighbors are P3 (4%) and P1 (9%) — note the neighbor set changes because the sort order changes per objective — and the error range is 9 − 2 = 7, giving (9 − 4)/7 ≈ 0.7143. Summed: 1.1143, matching the printed output exactly. P1 and P6 sit at the extremes of both objectives simultaneously, so they get infinite crowding distance and are protected from removal even though nothing about "infinite" reflects their fitness — it reflects that losing a boundary point shrinks the known extent of the discovered front, which NSGA-II is built to avoid.

Notice P4 has the lowest crowding distance (0.8857) among the finite ones, despite being a "good" Front-1 member. If the next generation's combined pool of 2N candidates has more than N members tied at Front 1, P4 is the first candidate this front would sacrifice — not because it's a worse trade-off, but because its neighbors P3 and P6 already cover its neighborhood in objective space reasonably well.

Why not just weighted-sum scalarization?

A tempting shortcut: turn the two objectives into one by minimizing w·size + (1 − w)·error for some chosen weight w, then run an ordinary single-objective GA or ES as in the sibling chapters. This works, sometimes, but has a specific geometric failure mode. Minimizing a weighted sum is equivalent to sliding a straight line of slope −w/(1−w) across the objective plane until it just touches the feasible region; the touching point is the optimum for that weight. A straight line can only ever touch the convex hull of the Pareto front. If the true front has a concave ("dented inward") stretch — common when objectives interact non-linearly, which is the normal case for accuracy-vs-compression curves — no choice of w, however finely swept, will ever land a solution inside that dent. Those trade-offs are mathematically invisible to scalarization no matter how many times it's rerun.

NSGA-II has no such blind spot because it never collapses the objectives into one number — dominance comparisons operate directly on the raw objective vectors. A single run also recovers the entire front in one pass, where scalarization needs a fresh optimization run per weight choice and still cannot guarantee even coverage (weights spaced evenly rarely produce evenly spaced front points). The cost is that NSGA-II's population must be large enough to spread across the whole front rather than converge to one point, and someone downstream still has to pick which front member to ship — NSGA-II hands over the full trade-off curve, not a decision.

Where this actually runs

Zhichao Lu, Ian Whalen, Vishnu Boddeti, and colleagues (including Kalyanmoy Deb himself) published NSGA-Net at GECCO 2019, applying NSGA-II directly to neural architecture search: candidate network topologies are evolved and ranked simultaneously on validation error and computational cost (FLOPs), producing a Pareto front of architectures instead of one "best" network — precisely the size-vs-accuracy problem the budget-phone example opened with, but with network topology itself as the search space rather than a fixed architecture's compression settings. Optuna, a widely used hyperparameter-optimization library, ships an NSGA-II sampler specifically for multi-objective studies (for instance, tuning a model simultaneously for validation loss and inference latency). The same machinery generalizes to engineering trade-offs entirely outside ML — chip floorplanning that must balance power, performance, and area (PPA) against each other, or portfolio construction balancing expected return against volatility — anywhere a design has several genuinely competing goals and no single stakeholder has the authority to fix the exchange rate between them in advance.

Common misconception

Having just worked through a single-objective GA converging on one best chromosome, it's natural to expect NSGA-II to converge on one best model the same way — students often read "P3 has the lowest error among the front" and assume P3 is "the answer." It isn't. Every member of Front 1 is, by construction, undominated: no other candidate beats it on every objective simultaneously. P1 (1 MB, 9% error) is not worse than P3 (3 MB, 4% error) in the Pareto sense — it wins decisively on size. NSGA-II's job ends at producing the front; picking one point off it requires information the algorithm was never given, such as "this app must fit in 2 MB" or "this app must clear 95% accuracy." That decision belongs to a human or a downstream constraint, not to the evolutionary search.

Active recall

Attempt each question before reading its answer.

1. Candidate A = (4 MB, 5%) and candidate B = (4 MB, 6%). Does A dominate B? Justify using the formal definition.
2. In the worked example, P5 = (4 MB, 7%) has a lower error rate than P1 = (1 MB, 9%). Why doesn't that put P5 on Front 1?
3. A seventh candidate P7 = (2 MB, 5%) is added to the population. Recompute the fronts fully — which candidates move, and by how many fronts?
4. Explain geometrically why weighted-sum scalarization run at w = 0, 0.1, 0.2, ..., 1.0 could still miss real points on the Pareto front that NSGA-II would find in a single run.
5. A new candidate is scored (4.0 MB, 5.0%) — identical to an existing Front-1 member in both objectives. Do the two dominate each other? What does this do to their crowding distances?
6. In fast non-dominated sorting, what does n_p track, and what breaks if the algorithm forgets to decrement n_q for q in S_p while peeling off a front?

Worked answers

1. Yes. Check both conditions: not-worse-in-any (4 ≤ 4 and 5 ≤ 6, both true) and strictly-better-in-at-least-one (5 < 6, true). Equal size is allowed under "no worse"; the strict win on error alone is enough to establish dominance.

2. P5 is dominated regardless of how it compares to P1, because dominance only requires one dominator, not universal agreement. P5 = (4, 7) is dominated by P2 = (2, 6): 2 ≤ 4 and 6 ≤ 7, with a strict win on size. It's also independently dominated by P3 = (3, 4). Whether P1 happens to also fail to dominate P5 (it does — P1 wins on size but loses on error, so P1 and P5 are mutually non-dominated) is irrelevant once any single dominator exists.

3. This has a real ripple. First, P7 = (2, 5) versus the existing population: P7 dominates P2 = (2, 6) (equal size, strictly lower error) and also dominates P5 = (4, 7) (strictly better on both). Nothing dominates P7 itself. So P7 enters Front 1 with n = 0. But P2, previously undominated, now has n = 1 (dominated by P7) and drops out of Front 1 — down to Front 2. P5's domination count, previously 2 (from P2 and P3), gains a third dominator (P7), and after P2 is peeled off in the next round P5 still isn't free, so it lands in Front 3, not Front 2. Final result: Front 1 = {P1, P7, P3, P4, P6} (five members, same count as before, with P7 replacing P2), Front 2 = {P2} alone, Front 3 = {P5} alone. One new candidate cascaded two existing members down by one front each — the obvious effect (P7 joins Front 1) is only half the story; P2's demotion and P5's further demotion are the ripple a shallow reading would miss.

4. Minimizing w·size + (1−w)·error finds the point where a straight line of slope −w/(1−w) is tangent to the feasible region from the outside; sweeping w sweeps that line's slope. A straight line can only touch the convex hull of the front. Any front point that sits in a concave indentation — locally "worse" in the sense that the line passes outside it — is never optimal for any slope, so no value of w, however finely sampled, ever selects it. NSGA-II compares objective vectors directly via dominance, with no line or hull involved, so concave regions are exactly as reachable as convex ones.

5. Two candidates with identical objective values do not dominate each other — dominance requires a strict improvement in at least one objective, and equal-everywhere fails that test on both sides. They are mutually non-dominated and sit on the same front. For crowding distance, if this pair is adjacent when the front is sorted by an objective, the gap between the tied pair itself is zero, but each point's own crowding-distance contribution on that objective is computed from its two flanking neighbors in the sorted order — not from the tied twin's value alone — so the contribution is typically reduced, not literally zero, unless the point's other-side neighbor also happens to share the same value. Near-duplicates still suppress each other's diversity score relative to a more spread-out front, making at least one of the pair a likelier casualty if the population needs to shrink (unless one happens to be a boundary point and gets protected by infinite distance regardless).

6. n_p is the count of population members currently known to dominate p; a front is exactly the set of members with n_p = 0. If the algorithm skips decrementing n_q for q ∈ S_p when p's front is peeled off, every q that was dominated only by members of that now-removed front keeps a nonzero count forever — it never reaches zero, so it's never assigned to any front. The sort would either loop forever waiting for an empty next-front check that never triggers, or (with a naive termination) silently drop valid solutions from the output, both of which corrupt every downstream selection step.

Think About It

Think about this: How would you explain evolutionary algorithms: population-based optimization to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where evolutionary algorithms: population-based optimization is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting evolutionary algorithms: population-based optimization to at least 3 other topics you have studied.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind evolutionary algorithms: population-based optimization, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.