MOSES Deep Dive

Two Nested Search Loops

MOSES organizes search at two levels:

• Outer loop (structural): Explores program topologies — the shapes of candidate programs. Each topology defines a representation: a parameterized template where specific positions (knobs) can be varied without changing the overall structure.
• Inner loop (numeric): Within a fixed topology, tunes knob settings using optimization algorithms to maximize fitness. Multiple strategies are available: hill climbing, simulated annealing, probabilistic grammar evolution (PGE), structured grammatical evolution (SGE), structured graph genetic programming (SGGP), and univariate optimization.

Knob-Based Representation

The key abstraction enabling MOSES's efficiency. Each program template has knobs — discrete or continuous parameters attached to program nodes that define the local variation space. Turning a knob produces a syntactically valid variant of the template. The representation builder analyzes a program's abstract syntax tree (AST) and identifies which positions admit variation. This converts the combinatorial search over program space into a structured optimization over knob settings within each deme.

Deme Structure

Search is partitioned into demes — subpopulations exploring neighborhoods of a particular program template. A metapopulation manager controls deme lifecycle: spawning new demes from promising templates, allocating compute budget, merging results, and retiring exhausted demes.

Fitness Evaluation Pipeline

• Behavioral score (bscore): A vector \(\mathbf{b}(p) \in \mathbb{R}^n\) measuring program \(p\)'s performance on each of \(n\) data points
• Composite score (cscore): Aggregates the behavioral vector into a scalar \(c(p) = f(\mathbf{b}(p))\), incorporating precision-based scoring, penalty terms, and domain-specific objectives
• Fitness: Final ranking that balances composite score against program complexity — implementing an Occam's razor preference for simpler programs

Imbalanced Category Handling

For classification with skewed class distributions, MOSES provides three mechanisms: --balance=1 (automatic rebalancing), --score-weight (inverse-frequency weighting, mathematically equivalent to scoring by informedness = 0.5×(sensitivity + specificity)), and multi-objective deme strategies where different demes balance two objective functions differently. (mailing-list-backed: MOSES-for-classification-with-imbalanced-categories, 2014)

Elegant Normal Form (ENF)

Boolean programs are reduced toward a canonical form using algebraic simplification rules: distributive law, complement law, idempotent law, absorption-idempotent law, and annulment-identity law. ENF reduction eliminates redundant structure, making programs more readable and enabling MOSES to recognize when syntactically different programs are semantically equivalent.

Feature Selection

Before evolutionary search, MOSES can reduce the input dimensionality. Available methods: hill climbing, incremental selection, simple filtering, and stochastic mutual dependency (SMD) with similarity scorers.