A4.3.7 Application of Genetic Algorithms (HL only) Notes

Understanding Genetic Algorithms

1. Genetic Algorithms (GAs) are a type of optimization technique inspired by the principles of natural selection and evolution.
2. They are particularly effective for solving complex problems where traditional methods may struggle.

Key Components of Genetic Algorithms

1. Population: Initial set of potential solutions.
2. Fitness Function: Evaluates how good a solution is (objective function).
3. Selection: Chooses the best (fittest) solutions to reproduce.
4. Crossover (Recombination): Combines parts of two solutions to create offspring.
5. Mutation: Randomly alters parts of a solution to maintain diversity.
6. Evaluation: Tests the new solutions using the fitness function.
7. Termination: Stops when a solution is “good enough” or a condition is met (e.g., max generations).

Real-World Applications of Genetic Algorithms

Route Planning: The Travelling Salesperson Problem (TSP)

1. Problem: Find the shortest route to visit a list of cities and return to the starting point.
2. How GAs Solve It:
   1. Representation: Each route is a sequence of city indices.
   2. Fitness Function: Inverse of the total distance (shorter routes have higher fitness).
   3. Crossover: Combines parts of two routes while ensuring no city is visited twice.
   4. Mutation: Swaps two cities to explore new routes.

Wind Farm Layout Optimization

1. Problem: Maximize energy production while minimizing costs.
2. How GAs Solve It:
   1. Population: Different configurations of turbine placements.
   2. Fitness Function: Energy output minus installation costs.
   3. Crossover: Combines high-performing layouts.
   4. Mutation: Adjusts turbine positions to explore new possibilities.

Scheduling and Timetabling

1. Problem: Allocate resources (e.g., employees, machines) efficiently.
2. How GAs Solve It:
   1. Population: Different schedules or timetables.
   2. Fitness Function: Minimizes conflicts and maximizes resource utilization.
   3. Crossover: Combines parts of two schedules.
   4. Mutation: Introduces small changes to explore new solutions.

Network Design and Optimization

1. Problem: Design efficient communication networks.
2. How GAs Solve It:
   1. Population: Different network topologies.
   2. Fitness Function: Balances cost, reliability, and performance.
   3. Crossover: Combines features of high-performing networks.
   4. Mutation: Introduces new connections or removes redundant ones.

Why Genetic Algorithms Are Effective

1. Exploration and Exploitation: GAs balance exploring new solutions (mutation) and refining existing ones (crossover).
2. Adaptability: They can handle dynamic and complex problem spaces.
3. Parallelism: GAs evaluate multiple solutions simultaneously, making them efficient for large-scale problems.

Ethical Considerations

1. Bias in Fitness Functions: Ensure the fitness function aligns with ethical and societal goals.
2. Resource Allocation: In applications like scheduling, consider the impact on human workers.