Evolutionary Algorithms Flashcards
The theory of evolution is the statement that all species on earth have arisen this way by…
Evolution via mutations over countless generations
Regional breeds arise when certain […] are favoured in certain environments.
Mutations
Given a population of organisms that can reproduce, and a way of continually generating diversity in the children, we can evolve to solve certain problems. This theory is called…
Survival of the Fittest
Trial and error is a form of evolutionary algorithm - however, this is flawed because…
It takes an exorbitant amount of time to train, with little to no benefits
Stochasticity is another term for…
Randomness
Evolution isn’t necessarily always survival of the fittest - the fitter you are, the more…
Likely you are to reproduce
Evolutionary algorithms work given two variables…
Some solution, and a function that can measure how good of a solution it is
The three stages of evolution for a population of generated solutions are…
Select the best solutions, create variations on these solutions, then update the population.
Selection, variation, population update
Evolutionary algorithms are extremely good at tasks such as… (pick one)
Optimisation, machine learning
Optimisation is the process of…
Finding the best solution for a given problem
The solution space is…
The domain of all possible solutions for a given task
The fitness of a candidate solution is…
The suitability of that solution to the given task, measured as a product of a fitness function f(s).
Problems are said to be ‘in P’ if they are [tractable/intractable], and ‘not known to be in P’ if they are [tractable/intractable].
Tractable, intractable
An approximate algorithm is an algorithm that, given a hard problem…
Will deliver a solution in a reasonable time, as close to optimal as possible
Hillclimbing is the process of…
Generating a mutant solution, then evaluating its fitness, saving it as our new solution if it is better
If we plot the solution space S against the fitness f(s) of each solution, this graph is called a…
Landscape
The set of all possible mutations of a solution is called its…
Neighbourhood
Drastic mutations can be likened to high […] in machine learning, causing solutions to shoot past local maxima.
Learning rates
If we apply genetic operators repeatedly to every new population of solutions, we call this a [generational/steady-state] algorithm.
Generational
If we apply genetic operators only a few times, then replace the bad solutions, we call this a [generational/steady-state] algorithm.
Steady-State
In steady-state algorithms, there are two strategies for replacing bad solutions…
Either replacing the n weakest solutions, or replacing the weakest solution with the best solution from that batch
‘Replace the weakest’ or ‘replace the first weakest’
Roulette wheel selection involves the selection of the best candidates by…
Giving solutions a percentage chance of being picked equal to that solution’s fitness divided by the total fitness of all candidates
If we apply roulette wheel selection to a set of solutions with fitness [100, 50, 25, 25], how likely are we to pick solution 3?
25 divided by 100 + 50 + 25 + 25 = 25/200 = 12.5%
Rank-based selection involves the selection of the best candidates by…
Giving solutions a percentage chance of being picked proportionate to the inverse of their rank in the candidate space (i.e. the worst solution will be ranked number 1).
