mixle.evolve.structure module¶
Structural genotype for evolutionary structure search — a model’s compositional tree + a distance on it.
Grammar/structure induction is not open research: it is genetic programming over structures (Koza 1992) with a
tree-edit genotype distance (Zhang & Shasha 1989) and selection by fitness. This module supplies the genotype
(model_signature) and the distance (structural_distance); the Mutate
operator supplies the mutations and the Population + verify gate supply selection.
A signature is a nested (type_label, [child_signatures]) tree — a mixture recurses into its .components,
a leaf is childless. The distance is an (unordered) tree-edit distance: exact relabel cost plus a minimum-cost
assignment between the two nodes’ children, with unmatched subtrees fully inserted/deleted, normalized to
[0, 1].
Child matching used to be greedy — take each of a’s children in order and pair it with whichever of b’s
remaining children is currently closest. That is order-dependent, and therefore not symmetric: A(A) vs
A(B,A) measured 1, and the same pair with the operands swapped measured 2, because the greedy walk over
[B, A] spent its only partner on B before reaching A. Normalization cannot repair that. A “distance”
that changes when you swap its arguments is not one, and Population’s diversity
selection consumes it as if it were: two members’ dissimilarity depended on which came first in the list.
- model_signature(model)[source]
The compositional structure of
modelas a(type_label, [child signatures])tree.
- tree_edit_distance(a, b)[source]
Unordered tree-edit distance: relabel cost (0/1) + minimum-cost matching of children, with unmatched subtrees fully inserted/deleted. Symmetric, zero exactly on identical trees, and non-negative.