Lineage-aware uniform crossover for SLP individuals

[morinim]

The following crossover operator is a variant of uniform crossover designed for straight line program individuals:

individual crossover(const individual &lhs, const individual &rhs)
{
  Expects(lhs.size() == rhs.size());
  Expects(std::ranges::distance(lhs) == std::ranges::distance(rhs));

  auto ret(lhs);

  const auto rows(ret.size());
  const auto cols(ret.categories());

  matrix<int> keep(rows, cols, 0);

  const auto sign([](int n)
  {
    if (n > 0) return 1;
    if (n < 0) return -1;
    return 0;
  });

  for (std::size_t i(1); i < rows; ++i)
    for (std::size_t j(0); j < cols; ++j)
    {
      for (const gene &g(lhs.genome_(i, j)); const auto &al : g.args)
        if (std::holds_alternative<D_ADDRESS>(al))
          keep(i, j) += sign(keep(g.locus_of_argument(al)));

      for (const gene &g(rhs.genome_(i, j)); const auto &al : g.args)
        if (std::holds_alternative<D_ADDRESS>(al))
          keep(i, j) -= sign(keep(g.locus_of_argument(al)));

      if (keep(i, j) == 0)
      {
        if (random::boolean())
          ret.genome_(i, j) = rhs.genome_(i, j);
      }
      else if (keep(i, j) < 0)
      {
        ret.genome_(i, j) = rhs.genome_(i, j);
      }
    }

  ret.set_if_older_age(rhs.age());
  ret.signature_ = ret.hash();

  return ret;
}

Motivation

A standard uniform crossover treats each gene independently: for every locus, it chooses the corresponding gene from either parent with equal probability.

That works well when genes are weakly coupled, but SLPs are different. In an SLP, the meaning of an instruction depends on the instructions it references. As a consequence, blindly mixing genes may preserve syntactic validity while still breaking coherent computational chains.

The goal of this operator is to remain close to uniform crossover while introducing a small amount of memory: when choosing the gene for a given locus, it takes into account which parent is already better represented in that gene's dependencies.

[morinim]

The offspring is initially copied from lhs:

auto ret(lhs);

This makes lhs the default source. The algorithm only overwrites a locus when the local dependency balance favours rhs, or when the balance is neutral and a random tie-break chooses rhs.

This keeps the implementation simple and efficient. Conceptually, however, the operator should still be understood as a two-parent recombination scheme, not as a mutation of lhs.

[morinim]

matrix<int> keep(rows, cols, 0);

stores, for each locus, a small lineage signal telling whether the offspring built so far is leaning towards lhs, towards rhs, or remains neutral.

Importantly, the operator propagates only the sign of earlier lineage values:

sign(keep(...))

rather than their raw magnitude.

This is deliberate, it:

• preserves direction of ancestry;
• avoids runaway accumulation;
• prevents early choices from dominating the whole individual too aggressively.

So the operator remembers which parent a dependency tends to come from, but only in a bounded way.

[morinim]

The algorithm processes loci in increasing row order:

for (std::size_t i(1); i < rows; ++i)

This matches the nature of SLPs, where an instruction may only depend on previous instructions.

As a result, when the operator reaches locus (i, j), all referenced loci already have an associated lineage signal. This allows the crossover decision to be informed by the computational history already present in the offspring.