Genetic algorithm vocabulary is easy to memorise, but numericals become confusing when you must decode a chromosome and apply every operator in order. The broader Genetic Algorithms in AI: A Worked One-Generation Example connects the method to AI concepts and exam preparation. This five-bit trace fixes the representation, fitness function, random draws, cut point, mutation and replacement rule so every intermediate value can be recomputed. It shows one possible stochastic run, not a guarantee of improvement or a global optimum.
Genetic algorithm fundamentals begin with representation and fitness
A genetic algorithm is a population-based optimisation method inspired by selection and variation. Keep the analogy precise:
A chromosome is one encoded candidate solution.
A gene is one position in that encoding.
An allele is the value stored at a gene position.
A population is the current set of candidate solutions.
Fitness measures how suitable a candidate is for reproduction or survival.
Our five-bit chromosome b4b3b2b1b0 represents an unsigned integer x from 0 to 31. Thus, 10101 decodes to 16 + 4 + 1 = 21. The objective and fitness are both f(x) = x^2, giving f(21) = 441.
Term | Value | Meaning |
|---|---|---|
Genotype |
| Encoded five-bit candidate |
Phenotype |
| Decoded solution value |
Fitness |
| Score used by the algorithm |
The GATE CS Exam Preparation route places this topic within broader CS preparation.
The genetic algorithm cycle has six ordered decisions
The generation proceeds through six ordered decisions:
Initialise a population.
Decode each chromosome.
Evaluate fitness.
Select parents.
Create offspring through crossover and mutation.
Apply replacement and test a stopping condition.
Selection biases reproduction towards useful candidates. Crossover recombines building blocks, mutation adds variation, and replacement forms the next population. Termination applies a budget, target or stagnation rule. Implementations vary, but changing the order would change this run.
This differs from Greedy Algorithms: Strategy and Problems. A greedy method follows a problem-specific local choice, while this method stochastically samples and modifies a population. Neither dominates every problem.
Genetic algorithm worked example: one complete generation
Start with four candidates:
Candidate | Chromosome | Decoded | Fitness |
|---|---|---|---|
A |
| 5 | 25 |
B |
| 10 | 100 |
C |
| 18 | 324 |
D |
| 21 | 441 |
Total fitness is 25 + 100 + 324 + 441 = 890; the average is 890 / 4 = 222.5.
Roulette selection gives candidate i probability f_i / sum(f):
Candidate | Selection probability | Cumulative upper bound |
|---|---|---|
A |
|
|
B |
|
|
C |
|
|
D |
|
|
Draw r1 = 0.30 falls in C's interval, selecting C = 10010. Draw r2 = 0.80 selects D = 10101.
Apply one-point crossover after the third bit:
100|10 + 101|01 -> 10001, 10110
The offspring decode to 17 and 22, with fitness 17^2 = 289 and 22^2 = 484. Flip the first offspring's second bit from the left: 10001 -> 11001. It decodes to 25 with fitness 25^2 = 625. The other offspring stays at 484.
Use elitist steady-state replacement: keep the best originals, C and D, and replace A and B with the offspring. The next fitness values are 324, 441, 625, 484. Their total is 324 + 441 + 625 + 484 = 1874, average 1874 / 4 = 468.5, and best 625. Originally these were 890, 222.5 and 441. This favourable run does not guarantee monotonic improvement.
Selection, crossover and mutation control different parts of the search
Operator | Purpose | Exam-level distinction |
|---|---|---|
Roulette selection | Bias selection by relative fitness |
|
Tournament selection | Choose the best from a random subset | Subset size controls selection pressure |
Rank selection | Select using fitness ordering | Uses rank rather than the raw score |
Crossover | Recombine selected parents | One-point uses one cut; two-point swaps between two cuts; uniform uses a mask |
Bit-flip mutation | Change a binary allele | Flips one bit from 0 to 1 or from 1 to 0 |
One-point crossover gives 100|10 and 101|01 one cut. Two-point swaps between two cuts; uniform chooses each gene through a mask.
Representation determines valid mutation. A permutation needs an operator that preserves a valid permutation; real values need numeric perturbation. Mutation maintains diversity, but too much makes the search nearly random.
Fitness design, constraints and stopping rules decide whether the search is meaningful
Objective and fitness are identical in this maximisation example. Minimisation or constraints may require transformation or a penalty. If x <= 20 and the penalty is 100(x - 20), candidate x = 25 scores 25^2 - 100(25 - 20) = 625 - 500 = 125, not 625.
Roulette selection and elitism exploit high fitness. Crossover explores combinations; mutation adds changes selection alone cannot create. High selection pressure with low diversity can cause premature convergence.
Stop after a fixed generation budget, a declared target fitness, or no improvement for a fixed number of generations. In Dynamic Programming Explained: 0/1 Knapsack, exact subproblem values follow when the recurrence applies. A genetic algorithm usually returns the best candidate found under its run conditions.
Genetic algorithm exam questions test arithmetic and operator order
Practise operator order and arithmetic with four checks:
Decode
10110. Answer:16 + 4 + 2 = 22.Find C's selection probability. Answer:
324/890 = 0.3640.Cross
100|10and101|01. Answer:10001and10110.Identify
10001 -> 11001. Answer: bit-flip mutation.
Under elitist steady-state replacement, the original survivors are 10010 and 10101, not the chromosomes unselected as parents. The next population is {10010, 10101, 11001, 10110}.
Crossover only recombines alleles present at each locus in the selected binary parents. Mutation can introduce an absent bit value. This distinction is representation-specific.
Genetic algorithm traps and their corrections
The fittest chromosome must be selected. Roulette gives D the highest probability,
0.4955, but not certainty. Elitism guarantees survival under this policy; roulette does not.Crossover and mutation are interchangeable. Keep the trace ordered:
100|10 + 101|01 -> 10001, 10110, then mutate10001 -> 11001, then decode and re-evaluate.A higher average proves global convergence. It only shows this population scores better under
f(x) = x^2. Search can stagnate, lose diversity or worsen without elitism.Raw fitness is already a probability. Roulette probabilities must be normalised and sum to approximately 1, allowing only for rounding error.
Genetic algorithms fundamentals in the short version
Remember: encode, evaluate, select, cross, mutate, replace. In this elitist steady-state run, average moved 222.5 -> 468.5 and best fitness 441 -> 625.
Final self-test: cross 011|01 and 110|00 after bit 3 without mutation. The offspring 01100 and 11001 decode to 12 and 25.
If you want Artificial Intelligence and other CS topics arranged in a structured preparation sequence, use GATE Guidance by Sanchit Sir as the next step.
