Genetic Algorithms: Evolutionary Optimization

The Problem With the Sweetest Mango

Every mango season, orchard growers in places like Ratnagiri face a quiet optimization problem. A tree does not produce mangoes of identical sweetness, size, and disease-resistance — every fruit, and every seedling grown from its seed, is slightly different. A grower who wants sweeter mangoes next season does not redesign a tree from scratch using chemistry. Instead, they pick the sweetest fruits from this year's harvest, plant their seeds, and let those trees cross-pollinate with other good trees. Some of the resulting seedlings will be sweeter than either parent, some will be worse, and a few — because plant genetics recombines in unpredictable ways — will be a happy surprise. Repeat this selecting-and-replanting process for a few generations and the orchard's average sweetness climbs, even though no single grower ever calculated the "optimal" mango tree directly.

This is not a metaphor for what you are about to learn — it is a working description of it. A genetic algorithm (GA) is a method for solving optimization problems in computer science by directly copying this process: keep a population of candidate solutions, let the better ones combine and reproduce, add a little random variation, and repeat over many generations until the population's best solution is good enough. It was formalized by John Holland in the 1970s specifically as a search technique for problems too large to check by brute force, and it belongs to a family of methods called evolutionary computation. In this chapter you will build one by hand, bit by bit, on a problem small enough to verify every number yourself.

From Orchards to Bit Strings

To turn "breeding better mangoes" into an algorithm a computer can run, every biological idea needs a precise computational twin. Here is the dictionary you will use for the rest of this chapter:

• Chromosome (individual): one candidate solution to your problem, written as a fixed-length string — usually a string of bits (0s and 1s), though it could be numbers or symbols depending on the problem.
• Gene: one position in that string. Each gene encodes one small decision about the solution.
• Population: a collection of chromosomes that exist "at the same time" — the current set of candidate solutions the algorithm is considering.
• Fitness function: a function that scores how good a chromosome is at solving the actual problem. Higher fitness means a better candidate solution — this is the only place the real-world problem enters the algorithm.
• Selection: the rule for choosing which chromosomes get to "reproduce" — chromosomes with higher fitness are more likely to be picked, but it is not guaranteed, exactly like a sweeter mango tree is more likely, not certain, to be replanted.
• Crossover (recombination): combining parts of two parent chromosomes to produce a child chromosome, mixing traits from both.
• Mutation: a small random change to a gene in a chromosome, applied with low probability, to introduce variation that crossover alone cannot create.
• Generation: one full cycle of selection, crossover, and mutation that produces a new population from the old one.

These six ingredients are the entire algorithm. Everything else in this chapter is watching them work on one concrete, fully traceable example.

A Real Problem: Packing the Trek Bag

Your school is organizing a one-day trek, and your bag has a strict weight limit of 10 kg set by the trip coordinator. You have five items you could bring, each with a weight and a "usefulness value" you have rated from 1 to 10:

• Tent — weight 4 kg, value 10
• Sleeping bag — weight 3 kg, value 8
• Water — weight 2 kg, value 7
• Snacks — weight 3 kg, value 5
• First-aid kit — weight 1 kg, value 6

Your goal: choose a subset of these five items that fits under 10 kg while maximizing total value. This is a classic problem called the 0/1 knapsack problem — "0/1" because each item is either fully included or fully excluded, no fractional items allowed.

With only 5 items, you could check every possibility by hand: each item is either in the bag or not, giving 2 × 2 × 2 × 2 × 2 = 2⁵ = 32 possible bags. Let's actually find the best one by reasoning it out, because you will need this correct answer later to check whether the genetic algorithm actually found it.

All five items together weigh 4+3+2+3+1 = 13 kg — over the limit, so something must be dropped. Drop the snacks (weight 3, value 5): the remaining four items weigh 4+3+2+1 = 10 kg exactly, and are worth 10+8+7+6 = 31. Try dropping something else instead — say the sleeping bag: weight becomes 4+2+3+1 = 10 kg, value 10+7+5+6 = 28, which is worse. Drop the tent instead: weight 3+2+3+1 = 9 kg (1 kg of capacity wasted), value 8+7+5+6 = 26 — also worse. You can check every other 3- and 4-item combination the same way, and none beats 31. So the mathematically best trek bag is Tent + Sleeping bag + Water + First-aid kit, weighing exactly 10 kg and worth 31 — leave the snacks behind.

Now imagine the same problem with 50 possible items instead of 5. The number of possible bags becomes 2⁵⁰ — over one quadrillion. No computer on Earth can check every one of those before your trek is over. This is exactly the kind of situation a genetic algorithm is built for: problems where the search space is too large to explore completely, but where you can still measure, cheaply, how good any one candidate solution is.

Step 1 — Encoding: Turning a Bag Into a Chromosome

To run a genetic algorithm, first decide how a candidate solution becomes a chromosome. Here the choice is natural: a chromosome is a 5-bit string, one bit per item, in the fixed order [Tent, Sleeping bag, Water, Snacks, First-aid]. A bit of 1 means "pack it," a bit of 0 means "leave it." The proven-optimal bag from above is therefore the chromosome [1, 1, 1, 0, 1]. The genetic algorithm does not know this yet — it will have to discover it.

Next, define the fitness function. It must reward high value but must also punish bags that break the 10 kg rule — otherwise the algorithm would happily "solve" the problem by packing everything:

weights = [4, 3, 2, 3, 1]   # Tent, SleepingBag, Water, Snacks, FirstAid
values  = [10, 8, 7, 5, 6]
CAPACITY = 10

def fitness(chromosome):
    total_weight = sum(w for w, bit in zip(weights, chromosome) if bit == 1)
    total_value  = sum(v for v, bit in zip(values, chromosome) if bit == 1)
    if total_weight > CAPACITY:
        return 0          # an overweight bag is worthless
    return total_value

Notice the design choice: an overweight bag does not get an error, it simply gets fitness 0. This is important and worth naming explicitly — a genetic algorithm handles constraints by making bad chromosomes unattractive to selection, not by forbidding them outright. Over generations, low-fitness chromosomes just fail to reproduce and quietly disappear from the population, the same way an inedible mango variety is simply never replanted.

Step 2 — Generation 0: A Random Starting Population

A genetic algorithm starts from ignorance — a small population of random guesses. Suppose we use a population of 4 chromosomes (real GAs typically use 50–500; we use 4 so every number in this chapter can be checked by hand):

population = [
    [1, 0, 1, 0, 0],   # A
    [0, 1, 0, 1, 1],   # B
    [1, 1, 1, 1, 1],   # C
    [0, 0, 1, 0, 1],   # D
]

for chromo in population:
    print(chromo, fitness(chromo))

Trace each one by hand, the same way the function would:

• A = [1,0,1,0,0] → Tent + Water → weight 4+2 = 6 kg, value 10+7 = 17
• B = [0,1,0,1,1] → Sleeping bag + Snacks + First-aid → weight 3+3+1 = 7 kg, value 8+5+6 = 19
• C = [1,1,1,1,1] → everything → weight 13 kg, over the 10 kg limit → fitness 0
• D = [0,0,1,0,1] → Water + First-aid → weight 2+1 = 3 kg, value 7+6 = 13

Total population fitness = 17 + 19 + 0 + 13 = 49. Best so far: B, with fitness 19 — still far short of the true optimum of 31.

Step 3 — Selection: Who Gets to Reproduce

The standard method here is roulette-wheel selection: imagine a spinning wheel cut into slices, one per chromosome, where each slice's size is proportional to that chromosome's fitness. The probability of picking chromosome i is:

P(i) = f(i) / Σf(j)

Plugging in our numbers (total fitness 49): P(A) = 17/49 ≈ 0.35, P(B) = 19/49 ≈ 0.39, P(C) = 0/49 = 0.00, P(D) = 13/49 ≈ 0.27. Chromosome C — the overweight bag — has a zero-width slice on the wheel. It can never be picked as a parent. This is the constraint-handling from Step 1 actually taking effect: fitness 0 does not crash the program, it simply removes that individual from the gene pool, exactly as we designed.

Step 4 — Crossover: Mixing Two Good (Partial) Bags

Suppose selection picks A and B as parents — both above-average, which is more likely precisely because their fitness is higher. Single-point crossover picks one cut position and splices: everything before the cut comes from parent 1, everything from the cut onward comes from parent 2.

def crossover(parent1, parent2, point):
    return parent1[:point] + parent2[point:]

A = [1, 0, 1, 0, 0]
B = [0, 1, 0, 1, 1]

child1 = crossover(A, B, 2)   # first 2 genes from A, rest from B
child2 = crossover(B, A, 2)   # first 2 genes from B, rest from A

print(child1, fitness(child1))
print(child2, fitness(child2))

Trace it by hand. A[:2] = [1,0] (Tent, no Sleeping bag) and B[2:] = [0,1,1] (no Water, Snacks, First-aid), spliced together: child1 = [1,0,0,1,1] — Tent + Snacks + First-aid, weight 4+3+1 = 8 kg, value 10+5+6 = 21. That already beats both of its parents (17 and 19)! The reverse splice gives child2 = [0,1,1,0,0] — Sleeping bag + Water, weight 3+2 = 5 kg, value 8+7 = 15, weaker than either parent this time. Crossover does not guarantee improvement on every attempt — it only makes improvement possible by trying new combinations of traits that already proved themselves individually.

Step 5 — Mutation: A Deliberate Random Nudge

Mutation flips a random bit with small probability (in real GAs, typically 0.1%–5% per gene — low enough that it rarely disturbs a good chromosome, but present often enough across a large population that it occasionally helps). Suppose child1 gets mutated at its Water gene (position 2, currently 0):

def mutate(chromosome, position):
    child = chromosome[:]
    child[position] = 1 - child[position]   # flip 0->1 or 1->0
    return child

mutated_child1 = mutate(child1, 2)   # child1 = [1,0,0,1,1]
print(mutated_child1, fitness(mutated_child1))

Flipping index 2 from 0 to 1 turns [1,0,0,1,1] into [1,0,1,1,1] — Tent + Water + Snacks + First-aid, weight 4+2+3+1 = 10 kg exactly, value 10+7+5+6 = 28. One random flip took the population's best chromosome from 21 to 28, closing most of the gap to the true optimum of 31.

Generation 1: Measuring Progress

Using elitism (a common practical trick: always carry the best existing chromosomes into the next generation unchanged, so a good discovery can never be accidentally lost), suppose the new population keeps A and B and adds the two new children:

Generation 0 best fitness: 19 (chromosome B). Generation 1 population: A (17), B (19), child2 (15), mutated_child1 (28). Generation 1 best fitness: 28 — a jump of 9 points in a single generation, using nothing but the six ingredients from Step 1.

Generation 2: Reaching the True Optimum

The population now contains two chromosomes that each hold part of the answer: mutated_child1 = [1,0,1,1,1] has the right Tent, Water, and First-aid genes but the wrong Sleeping-bag/Snacks combination, while child2 = [0,1,1,0,0] happens to have exactly the right Sleeping-bag and Snacks genes (1 and 0). A two-point crossover — splicing in a middle segment from a second parent instead of just one cut — can combine them directly:

def two_point_crossover(parent1, parent2, a, b):
    return parent1[:a] + parent2[a:b] + parent1[b:]

mutated_child1 = [1, 0, 1, 1, 1]
child2         = [0, 1, 1, 0, 0]

final_child = two_point_crossover(mutated_child1, child2, 1, 4)
print(final_child, fitness(final_child))

Trace it: mutated_child1[:1] = [1] (Tent, kept), child2[1:4] = [1,1,0] (Sleeping bag, Water, Snacks — taken from child2), mutated_child1[4:] = [1] (First-aid, kept). Spliced together: final_child = [1,1,1,0,1]. Check the weight: 4+3+2+1 = 10 kg. Check the value: 10+8+7+6 = 31.

That is exactly the chromosome — and exactly the fitness — of the provably optimal trek bag found by full enumeration at the start of this chapter. In three generations, working from four random starting guesses and no knowledge of which items mattered, the algorithm assembled the best possible answer purely by repeatedly favoring high fitness, recombining partial solutions, and occasionally trying a random change.

The Full Loop, and When to Stop

Put the five steps together and a genetic algorithm is just this loop, run by a computer far faster and on far larger populations than we did by hand:

def genetic_algorithm(pop_size, chromosome_length, generations):
    population = random_population(pop_size, chromosome_length)
    for gen in range(generations):
        scored = [(chromo, fitness(chromo)) for chromo in population]
        parents = select(scored)              # fitness-weighted picks
        children = []
        for i in range(0, len(parents), 2):
            c1, c2 = crossover(parents[i], parents[i + 1], point)
            children += [mutate(c1), mutate(c2)]
        population = children
    return best(population)

Real implementations stop the loop under one of three conditions: a fixed number of generations has passed, the best fitness has not improved for many generations in a row (suggesting convergence), or fitness has reached a known target. Our trek-bag example used the third condition informally — we recognized fitness 31 as the proven maximum and stopped.

Why Not Just Brute Force Every Time?

With 5 items, checking all 2⁵ = 32 bags is trivial, and brute force is actually the better tool — it is guaranteed correct and fast enough. The trek-bag example was deliberately small so every fitness value in this chapter could be verified by hand. Genetic algorithms earn their keep once the search space becomes too large to enumerate: 20 items already means 2²⁰ = 1,048,576 possible bags; 50 items means over 2⁵⁰ (roughly 10¹⁵) possible bags — far more than any computer could check individually. A genetic algorithm never checks every possibility. Instead, with a population of, say, 50 chromosomes run for 100 generations, it evaluates at most 50 × 100 = 5,000 candidate solutions — a minuscule fraction of the search space — by spending its limited effort on regions of the space that fitness scores suggest are promising, guided by the same logic that guided our hand-traced example from fitness 19 to 28 to 31 in three steps rather than checking all 32 possibilities in order.

Two Misconceptions Worth Correcting

Misconception 1: "A genetic algorithm always finds the best possible answer." It does not, and it never promises to. A GA is a heuristic, stochastic search — it typically finds a very good solution quickly, but unlike brute-force enumeration it offers no mathematical guarantee of reaching the true global optimum. Our trek-bag example did reach fitness 31, the actual best answer, but that outcome depended on randomness working in our favor across three generations; with different random starting chromosomes or different crossover points, the same algorithm might have stalled at fitness 28 instead. This is precisely the trade a GA makes: it exchanges the guarantee of brute force for the speed to handle problems brute force cannot touch at all.

Misconception 2: "Mutation is what makes the algorithm smart." In our small example, one mutation (flipping the Water gene) did produce a dramatic jump, from fitness 21 to 28 — but that was because the search space was tiny; changing 1 of only 5 genes changes the outcome a great deal. In realistic problems with hundreds of genes, flipping a single random bit rarely changes fitness much on its own. The real engine of improvement across generations is crossover: it recombines large, already-proven-useful chunks of different chromosomes, the way our final crossover directly assembled the optimal bag by taking the Tent-and-First-aid "chunk" from one parent and the Sleeping-bag-and-Water "chunk" from another. Mutation's real job is to maintain diversity in the population and occasionally nudge the search out of a rut — which is exactly why it is applied with low probability (commonly well under 5% per gene); set it too high and the algorithm degenerates into undirected random guessing instead of guided evolution.

Where This Actually Gets Used

Genetic algorithms are the right tool specifically when a problem has a huge number of discrete candidate solutions, a cheap way to score any one of them, but no clean mathematical shortcut to the best one — exactly the shape of the trek-bag problem, scaled up.

• Antenna design at NASA: for the 2006 Space Technology 5 (ST5) mission, NASA's Evolvable Systems research group used a genetic algorithm to evolve the shape of an X-band antenna. The algorithm's final design was an oddly bent, asymmetric wire shape that no human engineer would have sketched by hand — but it met the mission's radiation-pattern requirements, and it flew on all three ST5 spacecraft.
• Timetabling: assigning exam slots, classrooms, and invigilators for hundreds of students and courses without clashes is, structurally, a knapsack-like combinatorial problem with an astronomically large number of possible timetables. Many institutions use genetic-algorithm-based schedulers because brute-force checking of every timetable is impossible, but a fitness function counting "number of clashes" (lower is better) is easy to compute for any one candidate timetable.
• Evolving neural network structure: the NEAT algorithm (NeuroEvolution of Augmenting Topologies, introduced by Kenneth Stanley and Risto Miikkulainen in 2002) uses a genetic algorithm to evolve not just the weights but the actual connection structure of small neural networks, historically used to evolve agents that learn to play games or control simple simulated creatures without being explicitly programmed with rules.

In every one of these cases, the pattern from the trek bag repeats exactly: encode a candidate as a chromosome, score it with a fitness function, and let selection, crossover, and mutation search a space too large to check by hand or by brute force.

Check Your Understanding

1. A new trek variant has a 12 kg limit and one extra item, a camera: weight 2 kg, value 9 (in addition to the original five items). Compute the fitness of the chromosome [1, 1, 0, 0, 1, 1] (order: Tent, Sleeping bag, Water, Snacks, First-aid, Camera).

Answer: included items are Tent(4,10), Sleeping bag(3,8), First-aid(1,6), Camera(2,9). Weight = 4+3+1+2 = 10 kg ≤ 12, so it is valid. Value = 10+8+6+9 = 33.

2. Why does the fitness function return 0 for an overweight bag instead of simply skipping that chromosome or raising an error?

Answer: Returning 0 lets the chromosome remain in the population but gives it essentially no chance under fitness-weighted selection, so the algorithm "learns" to avoid overweight combinations through the normal selection process rather than needing a special-case rule bolted onto the algorithm.

3. A chromosome has 20 genes, each 0 or 1. How many distinct candidate solutions exist in total? If a GA uses a population of 40 and runs for 60 generations, roughly how many candidate solutions will it evaluate in total, and what fraction of the full search space is that?

Answer: 2²⁰ = 1,048,576 possible solutions. The GA evaluates about 40 × 60 = 2,400 candidates — about 0.23% of the full space — yet can still converge on a near-optimal answer because it searches guided by fitness rather than exhaustively.

4. In the single-point crossover crossover(A, B, 2) where A = [1,1,0,1,0] and B = [0,0,1,0,1], what is the resulting child chromosome?

Answer: A[:2] = [1,1], B[2:] = [1,0,1], so the child is [1,1,1,0,1].

5. True or false: increasing the mutation rate from 2% to 60% per gene will make a genetic algorithm find better solutions faster. Justify your answer.

Answer: False. At 60% per gene, most genes in every child would flip essentially at random each generation, destroying the useful gene combinations that crossover and selection had already assembled. The algorithm would behave like undirected random search rather than guided evolution, and would very likely perform worse, not better.

Summary

• A genetic algorithm solves optimization problems by evolving a population of candidate solutions (chromosomes) across generations, using a fitness function to score them and favor better ones for reproduction.
• The core cycle is: evaluate fitness → select parents in proportion to fitness → crossover (recombine) parents into children → mutate children with low probability → repeat.
• Constraints (like the 10 kg trek-bag limit) are typically handled by assigning very low or zero fitness to invalid chromosomes, so selection naturally filters them out rather than needing explicit rules.
• Crossover recombines proven partial solutions and is the main engine of improvement across generations; mutation maintains diversity and helps escape stagnation, and is kept at low probability for that reason.
• A GA offers no guarantee of finding the true global optimum the way brute-force enumeration does — but it can search vast solution spaces (thousands of items rather than five) that brute force could never finish checking, by evaluating only a tiny, fitness-guided fraction of all possible solutions.

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 genetic algorithms: evolutionary 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 genetic algorithms: evolutionary optimization to at least 3 other topics you have studied.