Genetic Algorithms in AI: Complete Guide with a Worked One-Generation Example

The biology metaphor takes you as far as "survival of the fittest" and no further. What UGC NET CS, teaching-recruitment papers, AI electives and GATE-style interviews actually ask for is arithmetic: given a population and a fitness function, compute each chromosome's selection probability, apply crossover at a stated cut point, and report the new best fitness. On a four-member population maximising f(x) = x^2, one generation lifts total fitness from 1170 to 1754.

What a genetic algorithm actually is

A genetic algorithm (GA) is a population-based, randomised search and optimisation heuristic inspired by natural selection. It does not need gradients or a complete mathematical model of the problem. It needs an encoding for candidate solutions and a fitness function that scores them.

Exhaustive search checks the whole search space. Hill climbing follows one candidate and can get stuck at a local optimum. A GA keeps several candidates and mixes their useful parts, so it explores many hills at once.

Almost every calculation question tests whether you can execute one loop: select, crossover, mutate, evaluate, and repeat.

In AI, GAs sit under search and optimisation, alongside hill climbing and simulated annealing. Simulated annealing also tracks a single candidate, but unlike hill climbing it will accept a worse move, with a probability that shrinks as its temperature falls. That buys it an escape from a local optimum. What it still cannot do, and a GA can, is build a new candidate out of two existing ones.

Encoding and fitness: set up the example

Suppose the task is to maximise f(x) = x^2 for an integer x from 0 to 31. A 5-bit binary chromosome can represent every allowed value. For example, 01101 represents 13, so its fitness is 13^2 = 169.

Use this initial population:

The total fitness is 169 + 576 + 64 + 361 = 1170. The average is 1170 / 4 = 292.5, and the best fitness is 576.

Binary is not the only encoding. A travelling salesperson problem can use a permutation of cities, while continuous parameters can use real values. The operators must fit the encoding. Ordinary crossover on permutations can create invalid tours, so a permutation GA uses an operator such as order crossover.

Roulette-wheel selection with actual numbers

Fitness-proportionate selection assigns chromosome i the probability p_i = f_i / 1170. Multiplying each probability by the population size gives its expected copies in a four-member mating pool.

Thus 11000 is expected to appear about twice, while 01000 may disappear. Expected copies are not guaranteed copies because the draw is random.

Tournament selection samples k candidates and keeps the best, making it less sensitive to fitness scaling. Rank selection uses fitness order and prevents one extremely fit chromosome from dominating too quickly. Elitism copies the best chromosome unchanged, so the best-so-far value cannot regress.

Crossover and mutation: one complete generation

Assume roulette selection produces the mating pool {01101, 11000, 11000, 10011}. Pair the first two chromosomes and cut after bit 4:

• 0110|1 and 1100|0 exchange tails.

• The children are 01100, where x = 12 and f = 144, and 11001, where x = 25 and f = 625.

Pair the other two and cut after bit 2:

• 11|000 and 10|011 exchange tails.

• The children are 11011, where x = 27 and f = 729, and 10000, where x = 16 and f = 256.

The new population is {01100, 11001, 11011, 10000}. Its total fitness is 144 + 625 + 729 + 256 = 1754, its average is 1754 / 4 = 438.5, and its best is 729, so in one generation total fitness rose from 1170, average fitness from 292.5, and best fitness from 576.

Mutation protects diversity by changing a gene with a small probability. If bit 2 of 10000 is flipped, counting positions from the left, it becomes 11000, giving x = 24 and f = 576. The global optimum is 11111, with x = 31 and f = 961. Crossover can rearrange alleles already present, but it cannot restore an allele after every chromosome has lost it at a position. Mutation can.

Parameters, convergence, and why GAs work

Three settings strongly affect a GA:

• Population size: A tiny population, such as this four-member teaching example, can converge prematurely. Practical runs often start around 50 to 200 candidates, then tune for the problem.

• Crossover probability: A common range is 0.6 to 0.9. Too little crossover limits useful mixing.

• Mutation probability: A common binary-GA range is 0.001 to 0.01 per bit. Near 0.5, mutation destroys inherited structure and the GA approaches random search.

Premature convergence means the population becomes copies of one mediocre chromosome, leaving selection with little diversity to exploit. Remedies include a larger population, higher mutation, rank or tournament selection, and restarting the run.

Holland's schema theorem says that short, low-order schemata with above-average fitness receive exponentially increasing trials over successive generations. A schema is a wildcard pattern such as 1*0** that matches a set of chromosomes. Its order is the count of fixed positions, so 1*0** has order 2, and its defining length is the gap between its first and last fixed position, so 1*0** has defining length 3 - 1 = 2. A single-point cut breaks a schema only inside that span, so just 2 of the 4 cut positions can destroy this one. That survival advantage for short, low-order, above-average blocks is the building-block hypothesis.

Genetic algorithm traps students fall into

• "A GA guarantees the global optimum." False. It is a stochastic heuristic that tends to find good solutions but provides no general optimality guarantee.

• Normalising the wrong values. Selection probability uses fitness, not the decoded x. Here the first probability is 169 / 1170, not 13 / 64.

• Counting crossover points incorrectly. A length-5 chromosome has L - 1 = 4 single-point cut positions, not five.

• Mixing up operator rates. Mutation is usually applied per gene at a small probability. Crossover is usually applied per parent pair at a much higher probability.

• Assuming every child is fitter. 01100 has fitness 144, below its parent 01101 at 169. Selection supplies pressure across generations; crossover alone promises no improvement.

How exams and interviews test genetic algorithms

Calculation questions usually ask you to apply one operator, produce offspring at a stated crossover point, or compute roulette probabilities and expected copies. Conceptual questions test the role of mutation, the lack of an optimality guarantee, schema-theorem wording, or matches between operators and their purposes. Paper structure and the exact unit this topic sits in change by cycle, so read both off the current GATE information brochure and the UGC NET Computer Science and Applications syllabus at ugcnet.nta.nic.in.

In placement interviews, a common design prompt is to optimise a non-differentiable objective. A complete answer states the encoding, fitness function, selection method, crossover, mutation, stopping condition, and one limitation such as computational cost or no guarantee. If systematic search is still unclear, revise Graph Algorithms: BFS, DFS and Dijkstra Traced Step by Step. To compare optimisation styles, read Dynamic Programming Explained with a Worked 0/1 Knapsack: DP is exact for its defined recurrence, while a GA is approximate.

The short version and your next step

Remember the loop: encode, evaluate, select by fitness, crossover to mix, mutate to restore diversity, and repeat until the stopping rule fires. Know the 1170 -> 1754 improvement story and the L - 1 crossover-point rule. Also remember that a GA searches effectively without promising the global optimum.

For structured AI-unit and full-syllabus preparation, use GATE Guidance by Sanchit Sir. UGC NET CS aspirants can follow the NTA-UGC-NET Paper 2 course, while the GATE CS exam category collects the broader exam pathway.