IB COMPUTER SCIENCE | A4.3.7 Genetic Algorithms (HL)

Lesson objective

Describe genetic-algorithm populations, fitness, selection, crossover, mutation, evaluation and termination in route planning and other real-world applications.

Learn

A4.3.7 | GENETIC ALGORITHMS (HL ONLY)

01 | SEARCH FOR A GOOD SOLUTION WHEN THERE ARE MANY POSSIBILITIES

A delivery van must visit several locations and return to its depot. Changing the visit order changes the total distance. With many stops, trying every order becomes expensive. How can a program search for a useful route within a limited time?

A genetic algorithm is a population-based optimisation technique inspired by selection and variation in biological evolution. It evaluates candidate solutions, selects parents and generates new candidates through crossover and mutation.

The analogy describes the search process, not actual living organisms or an algorithm that understands delivery work. The designer must define valid solutions, a way to score them and when to stop. A genetic algorithm can find good candidates without guaranteeing the best possible one.

02 | OPTIMISATION IS THE TASK

Optimisation means seeking a solution that improves a defined objective while meeting relevant constraints. The objective might be shorter routes, less energy use or fewer timetable conflicts.

A candidate solution is one possible complete answer, such as an entire visit order. The algorithm compares many candidates rather than learning a correct route label for every input.

A genetic algorithm is a general search technique and does not require a labelled training dataset. It can also optimise a machine-learning model’s configuration, but that is one application rather than its definition.

03 | THE TRAVELLING SALESPERSON PROBLEM

In the travelling salesperson problem, seek a shortest tour that visits each specified location once and returns to the start. In our teaching version, the depot H is fixed and there are six delivery stops, A through F.

The encoded route stores just the stop order. The sequence A B C D E F means H → A → B → C → D → E → F → H. H is added at the start and end when the route is evaluated.

The activity uses straight-line Euclidean distances in a fictional plane. Real vehicle routing may require road travel times, capacities, time windows and other constraints. Solving this small tour does not establish a deployable delivery plan.

04 | WHY EXHAUSTIVE SEARCH GROWS QUICKLY

Stops after a fixed depot Possible ordered visits
3 3! = 6
6 6! = 720
10 10! = 3,628,800
15 15! = 1,307,674,368,000

The symbol ! means factorial: multiply the positive integers up to that number. These counts include reversed tours as separate orders, even when symmetric distances give them equal length.

A small instance can be checked exhaustively. For many stops, the number of orders grows rapidly, motivating heuristics or other optimisation methods. The best method depends on the problem; a genetic algorithm is not the only option and may be unnecessary for a tiny instance.

05 | CHROMOSOMES AND GENES ENCODE A SOLUTION

A chromosome is the representation of one candidate solution. A gene is one component of that representation. For the tour, the chromosome is a permutation of A through F, with a stop ID in each position.

A valid chromosome contains every required stop exactly once. A B B D E F is invalid because B repeats and C is missing. An ordinary bit-string operator cannot be applied blindly to this route representation.

Other tasks can use different encodings: numbers for design dimensions, task orders for scheduling or assignments of lessons to timetable slots. The representation and operators must suit the actual constraints.

06 | A POPULATION CONTAINS SEVERAL COMPLETE CANDIDATES

The population is the current collection of candidate chromosomes. Our demonstration keeps eight route candidates. Each row in its population table is a complete tour, not one segment of a single shared route.

The initial population is generated by shuffling the six stops using a seeded pseudorandom process. Population members can share parts of their route or even be identical. A population is not automatically eight distinct answers.

Variety matters because different candidates provide material for the search. Too little diversity can focus the algorithm prematurely on a limited part of the solution space. More candidates can add variety but also require more evaluations.

07 | EVALUATION MEASURES EACH CANDIDATE

For every route, add all leg distances, including the return to H. If H = (1,1) and A = (2,8), the H-to-A distance is √((2−1)² + (8−1)²) = √50 ≈ 7.071 units.

Evaluate every candidate under the same objective and constraints. A route with a shorter total is better for this task. The evaluation function determines what the search is encouraged to preserve.

A fast program cannot compensate for a wrong objective. Ignoring a required return journey, an omitted delivery or a vehicle limit can make an apparently excellent score describe an unusable solution.

08 | FITNESS MUST HAVE A CLEAR DIRECTION

A fitness function expresses candidate quality for selection. Terminology varies: some software minimises a cost called fitness; other explanations maximise a quality score. Always state which direction is better.

Here we minimise total distance d and display a corresponding higher-is-better score fitness = 1 / (1 + d). For d = 20, this is 1/21 ≈ 0.0476; for d = 30, it is 1/31 ≈ 0.0323. The shorter route has the higher fitness.

Selection in the activity compares route distance directly, which is equivalent to ranking these fitness scores. Fitness is not a probability, prediction accuracy or a count of biologically healthy individuals.

09 | SELECTION CHOOSES WHICH CANDIDATES BECOME PARENTS

Selection favours better candidates as parents, giving useful patterns more opportunities to appear in later generations. It does not mean every poor candidate is immediately deleted or every chosen child will improve.

The demonstration uses tournament selection: sample two population members with replacement, then choose the shorter route. Repeat to select a second parent. A member can be sampled or selected more than once.

Other selection procedures exist, including fitness-proportional approaches. Too much preference for a narrow set of candidates can reduce diversity; too little can make the search weakly guided by the objective.

10 | CROSSOVER COMBINES PARENTS WITHOUT BREAKING THE ROUTE

Crossover creates a child using parts of two parents. For a permutation route, the operator must avoid repeated or missing stops. This example uses an order-preserving prefix method.

Stage Route or operation
Parent 1 A B C D E F
Parent 2 D A F C B E
Copy a prefix of length 2 from Parent 1 A B
Scan Parent 2 and skip stops already copied D, F, C, E remain
Append the remaining stops in that order A B D F C E

The child inherits a prefix from one parent and relative order from the other, while still visiting all six stops exactly once. A naive splice could duplicate stops, so validity is part of the operator design.

This is one clear permutation-preserving crossover, not a requirement that every genetic algorithm use this exact method. Recombination can produce a shorter, equal or longer route.

11 | MUTATION INTRODUCES A RANDOM CHANGE

Mutation introduces variation into a candidate. In the route example, swap two different positions. Starting with A B D F C E, swapping the third and fifth positions gives A B C F D E.

A swap preserves the permutation, so every required stop is still present once. For a numerical design chromosome, a suitable mutation might instead adjust a bounded dimension.

Mutation does not know which change will be useful. The new candidate must be evaluated. It can improve the objective, worsen it or leave the score unchanged. Its role includes maintaining search diversity, not guaranteeing progress on every operation.

12 | MUTATION RATE IS A CONFIGURATION CHOICE

In the demonstration, a mutation probability of 20% means each newly generated non-elite child has a 0.2 chance of receiving one swap. If selected, exactly two distinct route positions are exchanged.

That is a per-child convention, not a probability applied independently to each gene. Other implementations define mutation differently, so state what the configured rate means.

A very low rate can limit new variation. A high rate can disrupt useful structure, although the effect depends on the operator, selection and task. The best setting is not universal, and a 100% swap rate is not the same as replacing every route with a completely random one.

13 | ELITISM RETAINS A KNOWN GOOD CANDIDATE

Elitism copies one or more of the best current candidates unchanged into the next population. Our activity retains one best route and generates seven other candidates.

Under its fixed deterministic distance objective, this ensures the best retained distance cannot get worse from one generation to the next. The mean population distance can still rise, because other children may be worse.

Without elitism, even the best current candidate could be lost during reproduction. Too much copying, however, can reduce diversity and slow exploration. Elitism is a design choice, not a property of every genetic algorithm.

14 | FORM AND EVALUATE THE NEXT GENERATION

A generation is one population stage. In the example, preserve the elite, select parents, create each remaining child by crossover, possibly mutate it, then evaluate the completed new population.

The evaluation feeds the next round of selection. This creates a repeated cycle in which better-scoring components may spread, while variation continues to generate alternatives.

Individual children and the population average do not have to improve each time. The search is stochastic and guided, not a sequence of guaranteed steps toward a known answer.

15 | WATCH A REAL POPULATION SEARCH

The simulation evolves eight valid six-stop tours. It uses two-person tournament selection, prefix-order crossover, a per-child swap mutation and one elite. Inspect the first new child’s parents and operations after each generation.

Changing mutation affects future children and keeps the current population. The seed applies only when you start a new run. Each run stops at generation 50.

The route shown is the best candidate in the current population. The trace shows only the first generated child, while the population table shows all eight candidates. A new run may start with a good tour by chance; improvement is not promised in every displayed generation.

The optional benchmark separately checks all 720 ordered tours in this tiny example. It is never fed into selection, crossover or mutation. Exhaustive checking is feasible here precisely because the demonstration is small; it is not how the genetic search generates its candidates.

16 | EVALUATE WHETHER THE SEARCH IS HELPING

Track best distance, average distance and diversity across generations. A shorter best route is useful evidence about the objective, but one lucky run does not demonstrate a generally reliable optimiser.

Repeat with controlled seeds or comparable budgets, compare with suitable baselines and check all constraints. Counting distinct route strings gives one rough diversity indicator; in this symmetric toy problem a tour and its reverse have equal length but count as different strings.

Compare search cost too. If evaluation requires an expensive engineering simulation, each new candidate can cost substantial time. More generations and a larger population are not free improvements.

17 | TERMINATION: DECIDE WHEN TO STOP

Stopping rule Meaning Limit
Generation or time budget Stop after a chosen amount of search May stop before finding a very good route
Sufficient objective value Stop when a justified target is reached A target need not be the global optimum
Little recent improvement Stop after a defined period of limited progress A plateau can still be a local or premature result

Our demonstration stops at generation 50. It does not automatically stop when an independently calculated benchmark is displayed, because the benchmark does not control the search.

A termination condition tells us the search has stopped. It does not by itself prove global optimality. Even population convergence can mean that diversity has been lost around a suboptimal family of candidates.

18 | A TIMETABLING APPLICATION

A school timetable can be represented by assignments of lessons to rooms and times. A population contains alternative complete timetables. A fitness or cost function can assess clashes, room suitability and preferences.

A student group or teacher cannot attend two lessons simultaneously: that is a hard constraint. A preference for avoiding a last-period lesson may be a soft constraint whose violation has a cost.

Crossover and mutation must preserve validity or be followed by repair or explicit constraint handling. Combining two acceptable timetables carelessly can create a teacher clash, so a good score must not hide an invalid candidate.

19 | ENGINEERING DESIGN AND RESOURCE SCHEDULING

Application Possible chromosome Evaluation Important constraint
Engineering design Dimensions or material choices Mass, performance, cost or energy objective Strength, operating limits and valid designs
Task scheduling Task order or resource assignments Completion time, delay or resource use Dependencies and capacity
Network configuration Valid connection or allocation choices Latency, cost or reliability Connectivity and capacity requirements
Model-configuration search Encoded model settings Development validation score and compute cost Keep final test data out of search decisions

A genetic algorithm is useful only if candidates can be represented, varied and evaluated meaningfully. It may suit complex or irregular search spaces, but a specialised exact method or simpler heuristic may perform better.

For real applications, validate the evaluation model and compare alternatives under a fair budget. An optimiser can exploit inaccuracies in a simulator or proxy objective just as it can exploit a genuine improvement.

20 | CONSTRAINTS AND MULTIPLE OBJECTIVES

Shortest distance is not the only real-world concern. A delivery plan may need to meet time windows, stay within capacity and balance distance against driver time or emissions. Some objectives conflict.

A penalty can increase a candidate’s cost when it violates specified rules, but its weighting must be justified. A finite penalty does not automatically guarantee every required constraint is satisfied. Repair methods or feasibility-preserving representations are other options.

When combining objectives with weighted scores, units and weights determine the trade-off. Do not claim one optimum solves all concerns unless the objective and constraints support that interpretation.

21 | PREMATURE CONVERGENCE AND SEARCH LIMITS

If many candidates become similar too soon, the population may lose access to useful alternatives. This is premature convergence. Strong selection and excessive elite copying can contribute, while suitable mutation and varied starting populations can help maintain diversity.

These measures do not guarantee escape from every poor region. Random variation may fail to discover an important combination within the allowed budget, and crossover may repeatedly recombine very similar routes.

Genetic algorithms can require many evaluations and need choices about representation, population size, selection and variation. Their flexibility is valuable, but it does not make them universally faster, more accurate or globally optimal.

22 | DISTINGUISH GENETIC SEARCH FROM REINFORCEMENT LEARNING

In the previous lesson, an agent learned choices through state–action experiences and rewards. Here the search evaluates complete candidate solutions and reproduces a population across generations.

Both can optimise numerical signals, but a route chromosome is not the same as an agent’s current state, and a generation is not an environment step. A genetic algorithm could optimise a policy’s parameters, but then its population-search process still needs to be distinguished from the policy’s behaviour.

For the syllabus, connect each term to the chosen application: population of route candidates, fitness from route quality, parent selection, valid crossover, variation by mutation, repeated evaluation and an explicit stopping rule.

23 | CHECK THE OPTIMISATION PROCESS

Identify the main genetic-algorithm concept in each situation. Focus on what changes or is measured rather than just the biological vocabulary.

24 | DESCRIBE AN APPLICATION FROM START TO FINISH

For route planning, describe the chain: encode each valid tour as a permutation; create an initial population; evaluate full route distance; select better candidates as parents; combine order information without duplicating stops; mutate some children; evaluate the next generation; repeat until the defined termination rule.

State what improvement means and include a limitation: “Shorter valid tours are preferred, so good candidates influence later generations. However, stochastic search and a finite budget do not prove the shortest possible route.”

For another application, change the encoding, constraints and evaluation to match the task. Reusing the vocabulary without explaining what one candidate represents is not a complete description of a genetic algorithm in context.

Further reading: population, selection and reproduction and representation-specific variation operators.

MATCH THE GENETIC-ALGORITHM IDEA TO ITS ROLE

Terminology

Terminology

Genetic algorithm

A population-based optimisation method using selection and variation across generations.

Optimisation

Seeking a better objective value while meeting relevant constraints.

Candidate solution

One possible complete answer to the defined problem.

Chromosome

The encoded representation of a candidate solution.

Gene

A component or position in a candidate’s representation.

Permutation

An ordering containing each required element exactly once.

Population

The current collection of candidate solutions.

Generation

One population stage in the repeated search.

Initialisation

Creating the starting population under a defined procedure.

Fitness function

A stated evaluation of candidate quality with an explicit better direction.

Objective

The quantity or quantities being optimised.

Selection

Choosing candidates to contribute as parents, often favouring better scores.

Tournament selection

Sampling candidates and selecting the best sampled member under the rule.

Parent

A selected candidate contributing information to a child.

Child

A new candidate generated from existing candidates through variation.

Crossover

Combining information from parents to form a new candidate.

Mutation

A random variation applied under a defined representation-compatible rule.

Mutation probability

The chance of applying a mutation under a stated per-child or per-gene convention.

Elitism

Copying selected best candidates unchanged into the next population.

Evaluation

Calculating candidate quality and checking relevant constraints.

Termination

Stopping the search under a stated criterion.

Diversity

Variety among candidates in the search population.

Premature convergence

Loss of useful variety before a sufficiently good region has been explored.

Hard constraint

A requirement a valid solution must satisfy.

Soft constraint

A preference or condition whose violation can incur a cost.

Penalty

A cost adjustment for a specified violation, requiring appropriate interpretation.

Repair

A process that changes an invalid candidate to meet specified validity rules.

Travelling salesperson problem

Finding a shortest tour visiting each required location once and returning to the start.

Exact benchmark

A reference established by complete or otherwise exact optimisation for the stated instance.

Stochastic search

A search using random choices, whose result can depend on the random stream.

Questions

Questions

CHECK YOUR UNDERSTANDING

Select all correct choices. Each exact set earns one point.

1. Which describe a genetic algorithm?
2. For the toy route, which are correct?
3. Which describe the fitness convention?
4. Which describe selection?
5. Which preserve a tour permutation?
6. Which describe mutation in the activity?
7. Which follow from the activity’s one elite?
8. Which are valid termination statements?
9. Which application details matter?
10. Which are honest evaluation statements?

EXPLAIN AND COMPARE

Write your answers before revealing each sample.

1. Describe how a genetic algorithm can be applied to a travelling salesperson problem.

2. Describe chromosome, gene and population in the route example.

3. Calculate the fitness values for distances 20 and 30 using 1/(1+d), then describe the preference.

4. Describe tournament selection and one limitation.

5. Construct the child from Parent 1 A B C D E F and Parent 2 D A F C B E using a two-gene prefix.

6. Describe a suitable route mutation and why it preserves validity.

7. Describe evaluation and replacement in the demonstration.

8. Describe two termination rules and their limits.

9. Describe how a timetable application changes the representation and fitness.

10. Describe why diversity and mutation affect the search.

11. Describe how to evaluate the quality of a genetic search.

12. Describe a difference between genetic algorithms and reinforcement learning.

DESCRIBE IT | DESIGN A SEARCH FOR A REAL TASK

Choose route planning, timetabling or engineering design. Describe one candidate representation, a valid initial population, objective and constraints, parent selection, compatible crossover and mutation, evaluation, replacement and termination. Explain one reason the best retained candidate is not automatically the global optimum.

Flashcards

Flashcards

Click to flip. Select the ideas you need to revisit.

0 cards selected for revision.

Selections are kept while this page is open.

Workbook

Workbook

COMING SOON

The workbook for A4.3.7 Genetic Algorithms (HL) is coming soon. Complete the matching task and written questions in your exercise book.