alogos.systems._shared.init_population¶
Shared initialization functions for several systems.
Functions¶
|
Create a population from given genotypes. |
|
Create a population from given derivation trees. |
|
Create a population from given phenotypes. |
|
Create a population from random genotypes. |
|
Create a population with GP RHH. |
|
Create a population with PI RHH. |
|
Create a population with Nicolau's PTC2 method. |
Detailed object descriptions¶
- alogos.systems._shared.init_population.given_genotypes(grammar, parameters, dp, _representation, _init_individual)[source]¶
Create a population from given genotypes.
- alogos.systems._shared.init_population.given_derivation_trees(grammar, parameters, dp, _representation, _init_individual)[source]¶
Create a population from given derivation trees.
- alogos.systems._shared.init_population.given_phenotypes(grammar, parameters, dp, _representation, _init_individual)[source]¶
Create a population from given phenotypes.
- alogos.systems._shared.init_population.random_genotypes(grammar, parameters, dp, _representation, _init_individual)[source]¶
Create a population from random genotypes.
References
2017, Nicolau: Understanding grammatical evolution: initialisation
3.1 Random initialisation (RND): “The original implementations of GE
used a random (RND) initialisation procedure. This simple procedure consists of generating random genotype arrays (either binary or integer) of a specified length, in a manner similar to random initialisation in (fixed-length) genetic algorithms.”
2018, Ryan, O’Neill, Collins: Handbook of Grammatical Evolution
p. 11: “Originally, we used random initialisation for the GE population. However, as noted in [18, 26, 86], random initialisation can lead to very heavily biased initial populations. […] What is crucial though, is to put some effort into ensuring good variation in that initial population, and to avoid simple random initialisation.”
- alogos.systems._shared.init_population.gp_rhh(grammar, parameters, dp, _representation, _init_individual)[source]¶
Create a population with GP RHH.
Notes
This approach was originally developed in genetic programming (GP), where it was termed “ramped half and half” (RHH). In grammatical evolution (GE), the adapted but conceptually identical approach is known as “sensible initialization”.
Two main variants of it can be found in GE literature:
Variant 1: It does not ensure that there are no duplicate trees.
Variant 2: It removes duplicate trees by comparing their linear genotypes. First the linear encoding uses the smallest possible integers to represent the rules for each step. To increase variability within the generated genotypes, an “unmod” operator is applied to each codon, which uses a random integer from the whole possible range, which still represents the same rule as the original smallest possible integer.
References
2003, Ryan et al.: Sensible Initialisation in Chorus
“This paper employs an approach similar to ramped half and half for Chorus. The abstract syntax trees used by Koza are replaced here by derivation trees, showing the sequence of derivations leading from the start symbol to a legal sentence of the grammar (a collection of only terminal symbols).”
2016, Fagan et al.: Exploring position independent initialisation in grammatical evolution
“It can be seen from Table II that both traditional Grow and traditional Ramped Half-and-Half generate excessive numbers of duplicate individuals. This is due to the propensity of the original Grow method towards generating small trees. With Full and PI-based methods, the creation of duplicate individuals reduces markedly as the ramping depth increases.”
- alogos.systems._shared.init_population.pi_rhh(grammar, parameters, dp, _representation, _init_individual)[source]¶
Create a population with PI RHH.
- alogos.systems._shared.init_population.ptc2(grammar, parameters, dp, _representation, _init_individual)[source]¶
Create a population with Nicolau’s PTC2 method.
In 2000, Luke created a new population initialization approach called “Probabilistic tree-creation 2” (PTC2). In 2010, Harper adapted it to grammatical evolution. In 2017, Nicolau created a variant of Harper’s PTC2 method, which is implemented here.
References
2000, Luke: Two Fast Tree-Creation Algorithms for Genetic Programming
“PTC1 is a modification of GROW that allows the user to provide probabilities of appearance of functions in the tree, plus a desired expected tree size, and guarantees that, on average, trees will be of that size.”
“With PTC2, the user provides a probability distribution of requested tree sizes. PTC2 guarantees that, once it has picked a random tree size from this distribution, it will generate and return a tree of that size or slightly larger.”
2010, Harper: GE, explosive grammars and the lasting legacy of bad initialisation
“The PTC2 methodology is extended to GE and found to produce a more uniform distribution of parse trees.”
“If the algorithm is called in a ramped way (i.e. starting with a low number of expansions, say 20, and increasing until say 240) then a large number of trees of different size and shapes will be generated.”
2017, Nicolau: Understanding grammatical evolution: initialisation:
3.3 Probabilistic tree-creation 2 (PTC2)
3.6 Probabilistic tree-creation 2 with depth limit (PTC2D)
2018, Ryan, O’Neill, Collins: Handbook of Grammatical Evolution
p. 13: “More recent work on initialisation includes that of Nicolau, who demonstrated that across the problems examined in their study, a variant of Harper’s PTC2 consistently outperforms other initialisations”