- What are the genetic algorithms (GAs)?
February 12, 2024
Overview: Genetic algorithms (GAs) are optimization methods inspired by natural selection and genetics. They are used to solve optimization problems by evolving a population of candidate solutions.
Key concepts:
Objective: We aim to optimize the quadratic function \(f(x) = x^2 - 4x + 4\), minimizing the value of \(f(x)\).
Function: \[ f(x) = x^2 - 4x + 4 \]
We begin by creating an initial population of three individuals: \(x_1 = 1\), \(x_2 = 3\), and \(x_3 = 0\).
population <- c(1, 3, 0) population
## [1] 1 3 0
Fitness function: The fitness of an individual is how well it minimizes the function \(f(x)\).
For each individual, calculate \(f(x)\): \[ f(x) = x^2 - 4x + 4 \]
f <- function(x) { x^2 - 4*x + 4 } # we calculate fitness fitness <- f(population) fitness
## [1] 1 1 4
Let’s plot the quadratic function \(f(x)\) to visualize the optimization landscape.
We select individuals for crossover based on fitness. Lower fitness values are better in this case, so we select \(x_1 = 1\) and \(x_2 = 3\).
# w select the parents with the best fitness (lowest values) selected_parents <- population[order(fitness)][1:2] selected_parents
## [1] 1 3
Crossover: Combines the genes (values) of two parents to create offspring.
Mutation: Introduces random changes to avoid local minima.
# perform crossover (simple example: no change in this step) offspring <- selected_parents # introduce mutation with a small probability (no mutation for this example) mutated_offspring <- offspring mutated_offspring
## [1] 1 3
We replace one of the individuals in the population with the offspring to form a new population.
# replace the least fit individual in the population with one of the offspring new_population <- c(selected_parents, population[which.min(fitness)]) new_population
## [1] 1 3 1
The process is repeated over multiple generations. The population evolves over time, approaching the optimal solution, to eventually reach it.
Theoretical optimal point:
The minimum of the quadratic function occurs at: \[ x = \frac{-b}{2a} = 2 \] The corresponding function value is \(f(2) = 0\).
# calculate the optimal point optimal_x <- -(-4) / (2 * 1) optimal_y <- f(optimal_x) c(optimal_x, optimal_y)
## [1] 2 0
Key Takeaways:
Further Applications:
Any questions?