alogos.systems.whge._cached_calculations

Cached calculations of Weighted Hierarchical Grammatical Evolution (WHGE).

Functions

shortest_distances(grammar)	Calculate for each nonterminal the minimum distance to reach only terminals.
expressive_powers(grammar, max_depth)	Pre-calculate the expressive power of each non-terminal symbol in the grammar.

---

Detailed object descriptions

alogos.systems.whge._cached_calculations.shortest_distances(grammar)

Calculate for each nonterminal the minimum distance to reach only terminals.

Distance is not clear, because it could mean number of expansions but actually means tree depth.

References

• Bartoli, Castelli, Medvet in 2018: Weighted Hierarchical Grammatical Evolution

  • p. 4: “set i equal to the index of the production rule in R s which leads to a sequence of terminals in the lowest number of derivations from s [ShortestRuleIndex()]”

• Software implementation

  • HierarchicalMapper.java

    • data structure: optionJumpsToTerminalMap = new LinkedHashMap<>();

    • algorithm: two loops, the first to set a default, the second to actually compute it

    • final value: shortestOptionIndexesMap stores the indices of the shortest rules of each nonterminal

alogos.systems.whge._cached_calculations.expressive_powers(grammar, max_depth)

Pre-calculate the expressive power of each non-terminal symbol in the grammar.

What is actually calculated and stored is not expressive_power itself but ceil(log2(expressive_power)) in order to further decrease the amount of repetitive computations later.

References

• Bartoli, Castelli, Medvet in 2018: Weighted Hierarchical Grammatical Evolution

  • p. 4: “We quantify the expressive power e_s of a symbol s with the number of different (partial) derivation trees with which can be generated from s (e_s = 1 for terminal symbols). […] if a derivation tree still contains nonterminals at depth n_d, we do not further derive them and count the resulting partial derivation trees without further deriving them.”

  • 16. 4: Pseudocode - Algorithm 2:

    • There seem to be two small errors

      1. The floor function ⌊ ⌋ should actually be the ceiling function ⌈ ⌉ and the length l should be outside of it and multiplied after rounding. This has the effect that if log2 of an expressive power is between 0 and 1, it is rounded up to 1 and therefore the nonterminal has some weight instead of none. The reference code correctly uses the ceiling function to calculate the weights. See also https://en.wikipedia.org/wiki/Floor_and_ceiling_functions

      2. The index in the while loop needs to start with 1 instead of 0. If code starts counting from 0, then j = 1 + (c mod n) becomes j = c mod n or otherwise j may become too large and cause an IndexError.

• Software implementation

  • `WeightedHierarchicalMapper.java <https://github.com/ericmedvet/evolved-ge/blob/master/src/main/java/it/units/malelab/ege/ge/mapper/WeightedHierarchicalMapper.java`__

    • For each nonterminal, the expressive power is calculated and stored in a HashMap as ceil(log2(expressive_power)):

      • data structure: weightsMap = new HashMap<>();

      • algorithm: a method called for each nonterminal with the name countOptions(T symbol, int level, int maxLevel)

      • final value: int bits = (int) Math.ceil(Math.log10(options) / Math.log10(2d));