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.