In a genetic algorithm, the fitness function is:

The only problem-specific part, letting the same generic GA machinery be reused across different problems

Always identical across every problem

Unrelated to how good a chromosome's solution is

Only used once, at the very start

Crossover, compared to mutation, is best described as the operator that mainly provides:

Exploitation — recombining genetic material already present in the population

Exploration — introducing entirely new genetic material not present anywhere

Only removal of chromosomes, never combination

If no chromosome anywhere in the population has a particular useful bit pattern, that pattern can be introduced by:

Mutation, but not crossover alone

Crossover alone, no matter how many generations run

It can never be introduced by any means

In the standard GA cycle, the correct order of steps in one generation is:

Evaluate fitness, select parents, crossover, mutate, replace population

Replace population, then initialise it for the first time

Mutate before evaluating fitness at all

Crossover before the population is even created

A genetic algorithm is best described as:

A heuristic search, not guaranteed to find the global optimum

An exact algorithm guaranteed to find the global optimum

Only usable on already-sorted data

Which of the following are standard chromosome encodings used in genetic algorithms? (More than one option may be correct.)

A permutation encoding (an ordering of items)

No encoding is ever used at all

Single-point crossover on two parent chromosomes works by:

Cutting both parents at the same random position and swapping the tails to form offspring

Deleting both parents entirely with no offspring produced

Only ever operating on a single parent, never two

Randomly altering individual bits with no regard for either parent

Genetic Algorithms

Genetic algorithms are a search/optimisation technique inspired by biological evolution, named as their own sub-item in Unit 10 with no GATE CS equivalent. This chapter grounds the operators and the overall cycle correctly — 'survival of the fitter' by simulated selection, crossover and mutation — rather than a superficial biology metaphor.

Encoding Strategies and the Fitness Function

A genetic algorithm represents each candidate solution to a problem as a CHROMOSOME — most classically a fixed-length BINARY string, though real-valued or permutation encodings are used when they fit the problem more naturally (e.g. a permutation encoding for the travelling salesman problem, where a candidate tour is an ordering of cities rather than a bit string). A POPULATION is a set of many such chromosomes evaluated in parallel each generation. The fitness function scores each chromosome by how good a solution it represents for the actual problem being solved — it is the ONLY problem-specific part of the whole algorithm, which is exactly what makes the same generic GA machinery (selection, crossover, mutation) reusable across very different problems just by swapping in a different fitness function and encoding.

The Genetic Operators: Selection, Crossover and Mutation

The three named genetic operators
Operator	What it does
Selection	Chooses which chromosomes become PARENTS for the next generation, biased toward higher fitness (but not exclusively the single best, to preserve diversity) — roulette-wheel selection (probability of selection proportional to fitness) and tournament selection (pick k at random, keep the fittest of those k) are the two standard mechanisms.
Crossover	Combines genetic material from TWO parent chromosomes into one or two offspring — single-point crossover cuts both parents at the same random position and swaps the tails, so an offspring inherits a prefix from one parent and a suffix from the other; this is the primary EXPLOITATION operator, recombining already-promising partial solutions.
Mutation	Randomly flips/alters a small number of positions in a SINGLE offspring's chromosome (e.g. a bit-flip mutation), applied at a LOW probability — this is the primary EXPLORATION operator, introducing genetic material that crossover alone (which only recombines what already exists in the population) could never produce, and guarding against the population converging prematurely on a merely locally-good solution.

🎯 Why crossover and mutation together, and neither alone

Crossover alone can only ever recombine genetic material already present somewhere in the population — if no chromosome anywhere has a particular useful bit pattern, crossover can never introduce it, no matter how many generations run. Mutation alone (with no crossover) reduces the search to something closer to independent random hill-climbing on each chromosome, discarding the main benefit of a POPULATION-based search — combining partial solutions that are each good in a different respect. The two operators trade exploitation (crossover, refining what is already promising) against exploration (mutation, injecting genuinely new material), and a GA needs both in the right balance to avoid both premature convergence and aimless random search.

The GA Cycle

INITIALISE a population of chromosomes, typically at random.
EVALUATE every chromosome's fitness using the problem-specific fitness function.
SELECT parents biased toward higher fitness.
Apply CROSSOVER to selected parent pairs to produce offspring.
Apply MUTATION to the offspring at a low probability.
REPLACE (all or part of) the old population with the new offspring, forming the next generation, and repeat from step 2 until a stopping criterion (a fitness threshold, or a fixed number of generations) is reached.

⚠️ A GA finds a good solution; it does not guarantee THE best solution

A genetic algorithm is a HEURISTIC/metaheuristic search, not an exact algorithm — it is not guaranteed to find the global optimum, and can (like any local-improvement-based search) get stuck making progress toward a merely locally-good solution, though mutation and a diverse population reduce this risk compared to naive hill-climbing. This is exactly the same 'approximation, not exactness' character seen in this course's own approximation algorithms and randomized algorithms material — GAs are best understood as a general-purpose heuristic for hard search/optimisation problems where an exact algorithm is impractical, not as a method that proves optimality the way branch-and-bound does.

Problem Solving Using GAs

GAs suit problems with a HUGE, poorly-structured search space where no efficient exact algorithm is known — function optimisation with many local optima, scheduling and timetabling with many interacting constraints, and evolving the STRUCTURE of a solution (not just its parameter values) are standard application classes. A worked sketch: to maximise f(x) = x² over integer x in [0, 31], encode x as a 5-bit binary chromosome (32 possible values exactly fill 5 bits), let fitness be f(x) itself (no transformation needed, since larger x is already better), select parents biased toward higher x², apply single-point crossover and low-probability bit-flip mutation, and iterate — a population containing, say, 11111 (x = 31, the true optimum) would dominate selection quickly once discovered, since its fitness (961) is far above the rest, which is exactly the selection pressure that drives convergence toward the optimum.

Key takeaways

A GA encodes candidate solutions as chromosomes; the fitness function is the only problem-specific part, letting the same GA machinery reuse across problems.
Selection is biased toward fitness; crossover recombines two parents (exploitation); mutation randomly alters one offspring at low probability (exploration).
Crossover alone cannot introduce genetic material absent from the whole population; mutation alone loses the benefit of combining distinct good partial solutions — both are needed.
The GA cycle is initialise, evaluate, select, crossover, mutate, replace, repeat until a stopping criterion is met.
A GA is a heuristic search — it finds a good solution, not a guaranteed global optimum, and can get stuck at a locally-good solution.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

In a genetic algorithm, the fitness function is:
1. The only problem-specific part, letting the same generic GA machinery be reused across different problems
2. Always identical across every problem
3. Unrelated to how good a chromosome's solution is
4. Only used once, at the very start
Show answer
Answer: A — The only problem-specific part, letting the same generic GA machinery be reused across different problems
The fitness function is evaluated every generation and is the sole component tailored to the specific problem being solved; the rest of the GA (selection, crossover, mutation mechanics) stays generic.
Crossover, compared to mutation, is best described as the operator that mainly provides:
1. Exploitation — recombining genetic material already present in the population
2. Exploration — introducing entirely new genetic material not present anywhere
3. Nothing at all
4. Only removal of chromosomes, never combination
Show answer
Answer: A — Exploitation — recombining genetic material already present in the population
Crossover recombines material from two existing parents, refining already-promising partial solutions; it is mutation that introduces genuinely new material absent from the whole population.
If no chromosome anywhere in the population has a particular useful bit pattern, that pattern can be introduced by:
1. Mutation, but not crossover alone
2. Crossover alone, no matter how many generations run
3. Selection alone
4. It can never be introduced by any means
Show answer
Answer: A — Mutation, but not crossover alone
Crossover only ever recombines material already present somewhere in the population; mutation is the operator capable of introducing genuinely new material that was absent everywhere.
In the standard GA cycle, the correct order of steps in one generation is:
1. Evaluate fitness, select parents, crossover, mutate, replace population
2. Replace population, then initialise it for the first time
3. Mutate before evaluating fitness at all
4. Crossover before the population is even created
Show answer
Answer: A — Evaluate fitness, select parents, crossover, mutate, replace population
Fitness must be known before selection can be biased toward it, and crossover/mutation act on the selected parents to produce the next generation's offspring before replacement.
A genetic algorithm is best described as:
1. A heuristic search, not guaranteed to find the global optimum
2. An exact algorithm guaranteed to find the global optimum
3. A sorting algorithm
4. Only usable on already-sorted data
Show answer
Answer: A — A heuristic search, not guaranteed to find the global optimum
Like any local-improvement-based metaheuristic, a GA can get stuck making progress toward a merely locally-good solution — it is a practical heuristic for hard search problems, not a method that proves optimality.
Which of the following are standard chromosome encodings used in genetic algorithms? (More than one option may be correct.)
1. A fixed-length binary string
2. A real-valued encoding
3. A permutation encoding (an ordering of items)
4. No encoding is ever used at all
Show answer
Answer: A — A fixed-length binary string; B — A real-valued encoding; C — A permutation encoding (an ordering of items)
Binary strings are the classical choice, but real-valued and permutation encodings are standard alternatives chosen when they fit the problem more naturally — the travelling salesman problem's permutation encoding is a standard example.
Name the selection mechanism in which the probability of a chromosome being selected is proportional to its fitness, commonly visualised as spinning a wheel divided into slices sized by fitness.
Numerical answer — type the value.
Show answer
Answer: roulette wheel selection
Roulette-wheel selection biases choice toward fitter chromosomes without excluding weaker ones entirely, alongside tournament selection as the two standard selection mechanisms.
Single-point crossover on two parent chromosomes works by:
1. Cutting both parents at the same random position and swapping the tails to form offspring
2. Deleting both parents entirely with no offspring produced
3. Only ever operating on a single parent, never two
4. Randomly altering individual bits with no regard for either parent
Show answer
Answer: A — Cutting both parents at the same random position and swapping the tails to form offspring
Single-point crossover picks one cut position and swaps the tails beyond it between the two parents, so each offspring inherits a prefix from one parent and a suffix from the other — a two-parent operator, unlike mutation's single-chromosome operation.