Evolutional algorithms
In artificial intelligence, an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based meta-heuristic optimization algorithm. An EA uses mechanisms inspired by biological evolution, such as reproduction, mutation, recombination, and selection. Candidate solutions to the optimization problem play the role of individuals in a population, and the fitness function determines the quality of the solutions (see also loss function). Evolution of the population then takes place after the repeated application of the above operators.
Evolutionary algorithms often perform well approximating solutions to all types of problems because they ideally do not make any assumption about the underlying fitness landscape. Techniques from evolutionary algorithms applied to the modeling of biological evolution are generally limited to explorations of micro-evolutionary processes and planning models based upon cellular processes.
For this exercise we will implement local maxima search with a EA, where we will use function from previous example, and we evolve our best gene to fit the requirement of local maxima.
Function to find local maxima
EA is based on a “Fitness” function, which rates the actual value (entity – phenotype), based on the input genes. In general evolution theory genotype is a set of genes, and phenotype is a combination of genotype and environment.
Since we are about to find maximum in y=f(x) 1 dimensiona space, we can use a genotype created from only 1 gene. This gene will indicate the x value, and our fitness function is then determinate by y value for the certain x.
Implementation of EA:
- Select initial parents for generation
- Breed new generation – crossovers and mutations
- Evaluate new generation, and pick best entities for next generation as parents
- Repeat until converge
As was mentioned in implementation of EA, we can perform two operations, crossover and mutation. Crossover is general operation, that makes crosses from 2 genes, but since our entity is created with only one gene, and we assume that its is created with one parent, we do not implement crossover into the local maxima search. (However this is really useful if solving N-Dimensional spaces where N !=1) .
Mutation is a second GA operation, that takes a certain gene, and modifies the value of the gene. Modification can be mathematically interpreted as adding a random value from a certain range to the gene.
In the end our function contains local maxima, and therefore to find global maximum, we will need to use bigger step size, and switch it as soon as some genes reach the global maxima. (This can be done by keypress)
| Data | Value |
|---|---|
| Source | https://en.wikipedia.org/wiki/Evolutionary_algorithm |
| Code | Evolve_alg_code.zip |
| Solution code | Evolve_alg_solution_code.zip |