Evolutionary algorithms
An evolutionary algorithm (EA) is a population-based metaheuristic optimization algorithm inspired by biological evolution. It makes use of mechanisms such as reproduction, mutation, recombination, and selection to evolve a population of candidate solutions to the problem. A fitness function is used to evaluate the quality of the solutions by incorporating a number of factors that are likely to be present in an optimal solution. (Note: reproduction and recombination are generally considered the same thing, achieved through the method of crossover)
The power of EAs is their generality and ability to approximate solutions to a wide variety of problems well, not making assumptions about the underlying fitness landscape.
General Process
- Generate an initial population of random individuals
- Score each individual in the population according to the fitness function
- Repeat the following steps until termination
- Select best individuals according the fitness function. Can be selected in a deterministic or stochastic fashion (the latter to introduce diversity)
- Create new individuals through crossover between selected parents, along with random mutations
- Evaluate the fitness of the newly created individuals (children)
- Replace least fit members of the population with the newly created children
Genetic Algorithms
Genetic algorithms (GA) are one of the most common forms of EAs, inspired by natural selection. The GA process follows closely to the general EA process above. One of their defining characteristics is the requirement of a genetic representation of the candidate solutions, from which the individuals, or phenotypes, of the population can be fully realized through the process of epigenisis. The genotype is traditionally represented as a string of bits, and the evolution process (i.e. crossover, mutation, etc) takes place on the genotype level.
When designing a genetic algorithm, one mainly has concern themselves with the (1) the fitness function, and (2) the genetic representation. The difficulty in designing the fitness function is nothing new; one must properly incorporate and weight factors that are believed to evoke the desired behavior. As for the genetic representation, the primary concern is using an effective, compact code that lends itself well to crossover and mutation operations.
Genetic Programming
Genetic programming (GP) is a method for evolving computer programs to solve or approximate algorithmic solutions to a problem.
The fitness function is typically based on how well a program can solve the given task. The crossover operation involves the swapping of components across programs to produce mixed functionality in children. The mutation process can be as simple as random substitution of program components for other components.
Evolutionary Programming
Evolutionary programming (EP) is completely similar to genetic programming, but the program to be optimized is fixed and instead the parameters of that program are evolved for optimality.
Evolution Strategy
Evolution strategy (ES)
Differential evolution
Differential evolution is a evolutionary metaheuristic that is typically used for numerical optimization of multivariable real-valued functions. It can used to optimize for problems that have an objective function that’s non-differentiable, non-continuous, stochastic, etc.
https://www.maths.uq.edu.au/MASCOS/Multi-Agent04/Fleetwood.pdf