Evolutionary Programming + Genetic Programming

evolutionary programs used to represents problems with real value numbers. genetic algorithms used for genes that are binary or a fixed number of permutations

what is evolutionary computation?

family of algorithms/ techniques that are inspired by evolution theory and aimed to solve optimisation problems and generate AI in games

what methods are under the field of evolutionary computation

* evolutionary programming
* evolutionary strategies
* genetic algorithms
* genetic programming
* learning classifier systems
* estimation of distribution algorithms

what is the basic concept of evolutionary computation?

what is evolutionary programming?

multi-population algorithm similar to GAs that aim to find a solution.

unlike GAs, every parent mutates to create a single ‘child’ → this means that the population doubles (instead of using crossover to create a child based on 2 parents)

how does evolutionary programming differ from genetic algrotihms?

mutation operator is more complex and adaptive

does not involve crossover operator

selection operator is in the form of Tournament selection and not a roulette wheel

what is tournament selection?

each member of the population is compared with a fixed number of other individuals

* for each comparison the individual gains a point if its fitness is better than the opponent

after @@comparisons,@@ the population is reduced to its original size (remove 50%) by keeping the individuals with the highest score

what is the pseudocode for the evolutionary programming algorithm?

check in-between tournament selection and mutation to check for invalid individuals

what is genetic programming?

an evolutionary approach that extends genetic algorithms where we evolve @@computer programs@@ by natural selection

what is one type of genetic programming?

symbolic regression

what is symbolic regression?

a @@mathematical expression@@ is represented as a tree and we are trying to breed the best mathematical function

how does symbolic regression work?

1. initially determine the set of terminals and non-terminals/functions
2. fitness = the observed data vs. the calculated data that comes from evaluating the expression the tree represents
3. crossover and mutation are adapted to handle tree structures
4. a genetic programming algorithm is virtually the same as the genetic algorithm

what type of operators can genetic programming do compared to genetic algorithms?

as an extension of genetic algorithms, genetic programming can do all of the operators in GAs plus more specialised versions that work on the mathematical tree rather than on a chromosome (string of digits)

what are the specialised genetic programming operators?

sub-tree exchange crossover

self crossover

\
point mutation

permutation mutation

prune mutation

hoist mutation

expansion mutation

sub-tree mutation

what is the sub-tree exchange crossover operator?

two sub trees are swapped between parents

what is the self crossover operator?

sub trees are exchanged within an individual parent

what is the point mutation operator?

a node in the tree is changed to a different symbol

what is the permutation mutation operator?

two terminal (num/variable) nodes from the same sub tree are swapped

what is the hoist mutation operator?

a sub tree creates a new individual

what is the expansion mutation operator?

a sub tree is added to the base of the tree

what is the prune mutation operator?

a sub tree is removed

what is the sub tree mutation operator?

a sub tree is replaced with a random sub tree