Definition
Genetic Algorithm
A search heuristic that mimics the process of natural selection to generate high-quality solutions to optimization and search problems.
- In other words: Genetic algorithms are a type of evolutionary algorithm inspired by the process of natural selection.
- They are used to find approximate solutions to problems where exact solutions are difficult or impossible to compute.
Note
- Genetic algorithms are a type of heuristic.
- They do not guarantee an optimal solution but often find good solutions in a reasonable amount of time.
Key Concepts
- Population
- A population is a collection of candidate solutions to the problem.
- Each solution in the population is called an individual or a chromosome.
- Chromosome
- A chromosome is a representation of a solution to the problem.
- It is typically encoded as a string of genes, which can be binary, integer, or real-valued.
- Fitness Function
- The fitness function evaluates how good a solution is.
- It assigns a fitness score to each individual in the population.
- Selection
- Selection is the process of choosing individuals from the population to create the next generation.
- Individuals with higher fitness scores are more likely to be selected.
- Crossover
- Crossover is a genetic operator that combines the genes of two parent individuals to create offspring.
- It is also known as recombination.
- Mutation
- Mutation is a genetic operator that introduces random changes to an individual's genes.
- It helps maintain genetic diversity in the population.
How Genetic Algorithms Work
- Initialization: Start with a randomly generated population of individuals.
- Evaluation: Calculate the fitness of each individual using the fitness function.
- Selection: Select individuals based on their fitness scores.
- Crossover: Combine pairs of selected individuals to create offspring.
- Mutation: Apply random changes to some individuals.
- Replacement: Replace the old population with the new generation.
- Termination: Repeat steps 2–6 until a stopping condition is met (e.g., a solution is found or a maximum number of generations is reached).
Case study
Traveling Salesman Problem (TSP)
The Traveling Salesman Problem (TSP) is a classic optimization problem where the goal is to find the shortest possible route that visits a set of cities and returns to the starting city.
Chromosome Representation
- Each chromosome represents a possible route.
- For example, a route visiting 5 cities could be represented as [A, B, C, D, E].
Fitness Function
- The fitness function calculates the total distance of the route.
- Shorter routes have higher fitness scores.
Crossover and Mutation
- Crossover: Combine two parent routes to create a new route.
- Mutation: Swap the order of two cities in the route.
Example
- Parent 1: [A, B, C, D, E]
- Parent 2: [C, D, E, A, B]
- Offspring: [A, B, E, D, C]
Example
- Example of Mutation
- Original Route: [A, B, C, D, E]
- Mutated Route: [A, D, C, B, E]
Applications of Genetic Algorithms
- Optimization Problems: Scheduling, routing, and resource allocation.
- Machine Learning: Feature selection and neural network training.
- Engineering Design: Structural optimization and control system design.
Common Mistake
- A common mistake is assuming that genetic algorithms always find the best solution .
- They are approximate methods and may only find good enough solutions.
