Skip to main content

Description

The genetic algorithm is a search heuristic that mimics the process of natural selection to find optimal solutions to problems. It operates through mechanisms inspired by biological evolution, eg. selection, crossover, and mutation. This algorithm is particularly effective for solving optimization problems with a large and complex search space.

Overview​

  1. Fitness Function: This is the function being optimized, eg. the objective function. It represents the "fitness" of each individual, with more "fit" individuals being closer to the optimal solution, leading to survival and reproductive usage in the next generation.

  2. Population: The population is a set of potential solutions. Each individual in the population represents a candidate solution to the optimization problem.

  3. Mutation: Mutation introduces random changes to an individual's parameters. This helps maintain genetic diversity within the population and allows the algorithm to explore a wider search space. Mutation is to be defined by the user, as different problems require different implementations of mutation.

  4. Crossover: This process combines the parameters of two parent solutions to produce a new offspring. We implement one-point crossover, which is done by randomly selecting a split point, and exchanging the parameters beyond that point between the parents. Crossover helps combine good solutions from different individuals and can lead to the discovery of new, potentially better solutions.

  5. Selection: The selection process determines which individuals get to reproduce based on their fitness. Individuals with higher fitness are selected before individuals with lower fitness. The amount of individuals selected is user-defined.

  6. Elitism: Elitism involves preserving the best individuals from the current generation to the next generation without any changes. This ensures that the best solutions found so far are not lost during the optimization process, and that "good" traits are preserved for future generations. Elitism can be an effective strategy, and can lead to faster convergence, as shown in examples used in Baluja & Caruana. Elitism can be implemented by the user, who may define how many individuals are preserved.

The Optimization Process​

  1. Initialization:

    • Generate an initial population using a predefined set of parameters (seed) or a random generation function.

  2. Iteration:

    • Evaluation: Assess the fitness of the populations.
    • Selection: Choose the top-performing individuals based on their fitness to act as parents.
    • Crossover: Combine pairs of parents to produce offspring, introducing new solutions.
    • Mutation: Apply random changes to some of the offspring's parameters to maintain diversity.
    • Replacement: Form the new population by selecting the best individuals from the parents and offspring.

  3. Termination:

    • Repeat the iteration process for the specified number of generations.
    • Return the parameters of the best fitness value evaluated.

Intuition​

  • Exploration vs. Exploitation: Genetic algorithms balance exploring new solutions (via mutation and crossover) and exploiting known good solutions (via selection based on fitness). This balance helps avoid local minima and improves the chances of finding a global optimum.

  • Diversity: Maintaining a diverse population through mutation and crossover helps the algorithm avoid premature convergence to suboptimal solutions. Diversity allows the algorithm to explore various regions of the search space.

  • Fitness-Based Selection: By favoring individuals with higher fitness, the algorithm ensures that better solutions are more likely to be carried forward, leading to an overall improvement in the population over generations.