Evolutionary Algorithms 2 Flashcards
What are the 3 types of EA?
Genetic Algorithms -> Based on natural selection.
Evolution Strategies -> Used for continuous optimisation.
Genetic Programming -> Optimisation of algorithms and programs through iteratively improving GP trees.
Define EA…
A class of optimisation algorithms that take inspiration from theory of evolution. They are used for infeasible search spaces to obtain a ‘good enough’ solution. They iteratively optimise candidate solutions until a termination criteria is met.
What are the 3 core principles that make EA work?
- Exploration vs exploitation
- Population based
- Iterative
What are the 4 core operations of an EA?
Selection
Mutation or Recombination
Fitness evaluation
Population update
What types of mutation can occur?
Single point
Swap
What types of Recombination can occur?
1 point
2 point
uniform crossover using a binary mask
What are hillclimbing and local search?
2 simpler but less effective optimisation algorithms.
Explain Hillclimbing
An optimisation algorithm of finding a more optimal solution from the current solution. It can iteratively move up from the current solution, but can’t move down.
It’s prone to getting stuck at local optima.
Explain Local search
An optimisation algorithm that searches the neighbourhood of a solution for a more optimal solution. It does this via mutating the solution rather than moving to a new solution.
What is a Generational algorithm? What are the 2 types?
An algorithm where each population update is based around introducing new candidate solutions.
Basic -> Completely new population update.
Elitist -> Retains solutions with highest fitness, but replaces all others with a newly generated candidate solution.
What is a Steady State algorithm? What are the types?
An algorithm where candidate solutions are mutated as opposed to new ones being introduced.
Replace weakest -> Find and replace the weakest first
Replace first weakest -> From K, replace first weaker solution you encounter.
