Genetic programming: Difference between revisions

Revision as of 10:20, 7 August 2023

Revision as of 06:44, 8 August 2023

Line 41:

===Selection===

Selection is a process whereby certain individuals are selected from the current generation that would serve as parents for the next generation. The individuals are selected probabilistically such that the better performing individuals have a higher chance of getting selected.<ref name="field guide" /> The most commonly used selection method in GP is [[tournament selection]], although other methods such as [[fitness proportionate selection]], lexicase selection,<ref>{{Cite book|last=Spector|first=Lee|title=Proceedings of the 14th annual conference companion on Genetic and evolutionary computation |chapter=Assessment of problem modality by differential performance of lexicase selection in genetic programming |url=https://dl.acm.org/citation.cfm?id=2330846|pages=401–408|language=en-US|publisher=ACM|doi=10.1145/2330784.2330846|year=2012|isbn=9781450311786|series=Gecco '12|date=2012 |s2cid=3258264}}</ref> and others have been demonstrated to perform better for many GP problems.

Elitism, which involves seeding the next generation with the best individual (or best ''n'' individuals) from the current generation, is a technique sometimes employed to avoid regression.

===Crossover===

In Genetic Programming two fit individuals are chosen from the population to be parents for one or two children. In tree genetic programming, these parents are represented as inverted lisp like trees, with their root nodes at the top. In subtree crossover in each parent a subtree is randomly chosen. (Highlighted with yellow in the animation.) In the root donating parent (in the animation on the left) the chosen subtree is removed and replaced with a copy of the randomly chosen subtree from the other parent, to give a new child tree.

Sometimes two child crossover is used, in which case the removed subtree (in the animation on the left) is not simply deleted but is copied to a copy of the second parent (here on the right) replacing (in the copy) its randomly chosen subtree. Thus this type of subtree crossover takes two fit trees and generates two child trees.

[[File:Genetic_programming_subtree_crossover.gif|Genetic programming subtree crossover]]

===Replication===

Some individuals selected according to fitness criteria do not participate in crossover, but are copied into the next generation, akin to asexual reproduction in the natural world. They may be further subject to mutation.

===Mutation===

There are many types of mutation in genetic programming. They start from a fit syntactically correct parent and aim to randomly create a syntactically correct child. In the animation