A4.3.7 Describe the application of genetic algorithms in various real-world situations. (HL only)

The Big Idea

Genetic Algorithms (GAs) are a class of evolutionary algorithms inspired by the process of natural selection and biological evolution. They are used to solve complex optimization problems—especially when traditional methods struggle due to high dimensionality, non-linearity, or large search spaces.

Rather than trying to compute the best solution directly, a genetic algorithm evolves better solutions over generations, using mechanisms analogous to genetic reproduction: selection, crossover, and mutation. Each potential solution is evaluated by a fitness function, and the best-performing candidates are more likely to be passed on to the next generation.

---

Fundamental Concepts

1. Population

• A population is a collection of possible solutions to a problem.
• Each individual in the population is called a chromosome, typically represented as a binary string, vector, or encoded object (e.g., a sequence of cities in a route).

2. Fitness Function

• The fitness function evaluates how good each solution is at solving the problem.
• The better the fitness, the higher the probability the solution will contribute to the next generation.

Example: In the Travelling Salesperson Problem (TSP), fitness could be the inverse of total route distance—shorter routes have higher fitness.

3. Selection

• The algorithm selects individuals from the population to become parents for the next generation.
• Better solutions have a higher probability of being selected, but lower-quality solutions may also be chosen to preserve genetic diversity.

Common strategies:

• Roulette wheel selection
• Tournament selection
• Rank-based selection

4. Crossover (Recombination)

• Two parent solutions are combined to produce offspring.
• The idea is to preserve beneficial traits while creating variation.

In TSP, crossover might combine parts of two good routes to produce a new route that includes promising segments from both.

5. Mutation

• Introduces random variation into offspring by flipping bits or changing elements in the chromosome.
• Mutation prevents premature convergence to local optima by exploring new areas of the search space.

In a route-planning problem, mutation could randomly swap two cities in a route.

6. Evaluation

• Offspring are evaluated using the fitness function to determine their quality.
• The new population is formed, typically by keeping the best individuals (elitism) and/or replacing the worst performers.

7. Termination

• The algorithm continues until a termination condition is met:
  • Maximum number of generations
  • No improvement in fitness
  • Reaching a satisfactory solution

---

Real-World Application: Route Planning (Travelling Salesperson Problem)

Problem:

A salesperson must visit a set of cities exactly once and return to the starting point, minimizing the total distance traveled.

• The TSP is NP-hard—traditional algorithms struggle with even moderate numbers of cities.
• Genetic algorithms provide heuristic-based, near-optimal solutions efficiently.

GA for TSP:

• Chromosomes: sequences of city indices (e.g., [A, D, C, B, E])
• Fitness function: inverse of route length
• Crossover: exchange sub-sequences of the route
• Mutation: swap two cities

Over generations, the GA evolves better routes that minimize total distance—even when the number of cities is large and the search space is vast.

---

Other Real-World Applications of Genetic Algorithms

Domain	Application Example
Engineering	Optimizing design of antennas, turbines, or aerodynamic surfaces
Finance	Portfolio optimization, algorithmic trading strategies
Machine Learning	Feature selection and neural network architecture search
Telecommunications	Frequency allocation in wireless networks
Biotechnology	Protein structure prediction, gene sequencing
Scheduling	Timetable generation for schools or airline crew assignments
Robotics	Evolving control systems for robot locomotion

---

Student-Relatable Example

Imagine a school planning committee wants to optimize the order of stops for a school bus route. They need to:

• Minimize total driving time
• Respect traffic patterns
• Ensure students are picked up and dropped off on time

A genetic algorithm could be used to evolve candidate routes, using fitness scores based on distance, lateness, and fuel usage. Over time, the algorithm would converge toward an efficient and practical schedule—something that would take hours or days to solve manually.

---

Summary

Genetic algorithms are powerful, nature-inspired optimization techniques that mimic the evolutionary process to solve complex problems. By evolving populations of solutions over time, guided by fitness, crossover, and mutation, GAs are capable of tackling problems that are otherwise computationally infeasible. From routing and scheduling to financial modeling and machine learning, genetic algorithms provide robust, flexible, and scalable approaches to real-world challenges.