Tree crossover for SLP individuals (preserving donor structure while minimising exon disruption)

[morinim]

Summary

The current TREE crossover implementation for ultra::gp::individual copies a donor subtree from one parent (from) into the other (to) by recursively overwriting genes at the same loci used in the donor. This guarantees validity, because donor dependencies are copied together, but it also causes an important side effect:

many active genes (exons) in the destination are overwritten unnecessarily.

In practice, the current operator behaves as a location-preserving subtree transplant. What is missing is a relocation-aware graft: the donor subtree should be copied into the destination while preserving semantics, but internal donor nodes should be placed into introns of the receiver whenever possible.

The proposal described below rewrites TREE crossover so that:

• the donor subtree root still replaces an active locus in the destination;
• donor dependencies are relocated into introns of the destination as much as possible;
• addresses are rewritten consistently;
• SLP validity constraints are preserved;
• fallback behaviour remains well defined when introns are insufficient.

This should reduce disruption, preserve more of the recipient’s active structure, and make introns serve as intended: storage capacity for latent code.

Context

gp::individual uses a Straight Line Program representation:

• each gene is stored at a locus;
• arguments may reference earlier loci via D_ADDRESS;
• therefore every valid individual respects a strict acyclicity / forward-evaluation constraint: if a gene at row i uses an address, that address must refer to a row < i;
• only a subset of genes are active (cexons()), while the rest are introns.

Current TREE crossover (simple and correct):

auto crossover_ = [&](const locus &l, const auto &lambda) -> void
{
  to.genome_(l) = from[l];

  for (const auto &al : from[l].args)
    if (std::holds_alternative<D_ADDRESS>(al))
      lambda(from[l].locus_of_argument(al), lambda);
};

crossover_(random_locus(from), crossover_);

This recursively copies the donor root and all of its dependencies at their original donor loci.

Design goals

Design goals

The proposed TREE crossover aims to satisfy the following goals.

Preserve donor subtree semantics

The inserted material must remain a complete dependency-closed subgraph. No dangling addresses. No partial dependency loss.

Minimise disruption to the receiver

The graft root must affect the active program, but internal donor nodes should go into introns whenever possible, rather than overwriting arbitrary exons.

Preserve SLP validity

The resulting individual must satisfy current is_valid() checks:

• correct arity;
• category consistency;
• valid address ordering (address.index < current.index);
• valid hash/signature.

####Avoid changes to gp::individual representation
The improvement should fit the current storage model and should not require:

• genome resizing;
• new gene types;
• proxy primitives;
• special runtime support.

Keep fallback behaviour explicit

If the destination does not have enough introns, the operator must degrade in a controlled way rather than silently reverting to broad exon destruction.

Proposed solution

High-level idea

The new TREE crossover should work in four logical phases:

• extract the donor subtree rooted at a random active donor locus;
• topologically order the subtree so that dependencies come before users;
• remap donor loci to destination loci, preferring introns for internal nodes;
• rewrite and insert donor genes with corrected addresses.

This separates what is copied from where it is placed.

Example

Suppose the donor subtree is:

[3] ADD(1, 2)
[7] MUL([3], 2)

and the selected donor root is [7].

Suppose the receiver has available introns at:

[12], [15]

A suitable remapping is:

[7] -> [7]     // root overwrites its destination locus
[3] -> [12]    // dependency goes into an intron

The rewritten graft becomes:

[12] ADD(1, 2)
[7]  MUL([12], 2)

The resulting active effect is the same as in the donor subtree, but only one active receiver locus was necessarily overwritten.

[morinim]

A sketch of an implementation:

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

  const bool b(random::boolean());
  const auto &from(b ? rhs : lhs);
  auto          to(b ? lhs : rhs);

  const auto genes(std::ranges::distance(from));
  Expects(genes > 1);

  switch (from.active_crossover_type_)
  {
    /* ... */
  default:  // TREE crossover (relocation-aware, with safe fallback)
  {
    const locus donor_root(random_locus(from));

    // ---- 1. Collect the donor subgraph (dependency-closed) ----
    std::vector<locus> donor_nodes;
    std::set<locus> donor_seen;

    const auto collect =
      [&](const locus &l, const auto &self) -> void
      {
        if (!donor_seen.insert(l).second)
          return;

        for (const auto &a : from[l].args)
          if (std::holds_alternative<D_ADDRESS>(a))
            self(from[l].locus_of_argument(a), self);

        // Post-order: dependencies first.
        donor_nodes.push_back(l);
      };

    collect(donor_root, collect);

    // Make the order deterministic and suitable for placement:
    // lower rows first, then lower categories.
    std::sort(donor_nodes.begin(), donor_nodes.end(),
              [](const locus &a, const locus &b)
              {
                if (a.index != b.index)
                  return a.index < b.index;
                return a.category < b.category;
              });

    // ---- 2. Compute active loci in `to` ----
    std::set<locus> exon_set;
    {
      const auto exs(to.cexons());
      for (auto it(exs.begin()); it != exs.end(); ++it)
        exon_set.insert(it.locus());
    }

    // ---- 3. Candidate active roots in `to` (same category as donor_root) ----
    std::vector<locus> root_candidates;
    {
      const auto exs(to.cexons());
      for (auto it(exs.begin()); it != exs.end(); ++it)
        if (it.locus().category == donor_root.category)
          root_candidates.push_back(it.locus());
    }

    // Try root candidates in random order.
    std::map<locus, locus> remap;
    bool relocated(false);

    while (!root_candidates.empty() && !relocated)
    {
      const auto idx(random::sup(root_candidates.size()));
      const locus dest_root(root_candidates[idx]);

      std::swap(root_candidates[idx], root_candidates.back());
      root_candidates.pop_back();

      // All non-root donor nodes must be placed before dest_root.index.
      // Moreover, to guarantee validity we assign them in strictly increasing
      // row order, preserving donor dependency order.
      std::map<locus, locus> candidate_remap;
      std::set<locus> used;

      candidate_remap[donor_root] = dest_root;
      used.insert(dest_root);

      locus::index_t next_min_index(0);
      bool ok(true);

      for (const auto &dl : donor_nodes)
      {
        if (dl == donor_root)
          continue;

        locus chosen{};
        bool found(false);

        // Two passes:
        //   1. prefer introns
        //   2. then allow exons
        for (int pass(0); pass < 2 && !found; ++pass)
          for (locus::index_t i(next_min_index); i < dest_root.index && !found; ++i)
            for (symbol::category_t c(0); c < to.categories() && !found; ++c)
            {
              const locus cand(i, c);

              if (cand.category != dl.category)
                continue;
              if (used.contains(cand))
                continue;

              const bool is_intron(!exon_set.contains(cand));
              if ((pass == 0 && !is_intron) || (pass == 1 && is_intron))
                continue;

              chosen = cand;
              found = true;
            }

        if (!found)
        {
          ok = false;
          break;
        }

        candidate_remap[dl] = chosen;
        used.insert(chosen);
        next_min_index = chosen.index + 1;
      }

      if (ok)
      {
        remap = std::move(candidate_remap);
        relocated = true;
      }
    }

    if (relocated)
    {
      // ---- 4. Insert the relocated subtree with rewritten addresses ----
      for (const auto &dl : donor_nodes)
      {
        gene g(from[dl]);

        for (auto &a : g.args)
          if (std::holds_alternative<D_ADDRESS>(a))
          {
            const locus src(from[dl].locus_of_argument(a));
            a = D_ADDRESS(remap.at(src).index);
          }

        to.genome_(remap.at(dl)) = std::move(g);
      }
    }
    else
    {
      // ---- Safe fallback: original TREE crossover ----
      const auto fallback =
        [&](const locus &l, const auto &self) -> void
        {
          to.genome_(l) = from[l];

          for (const auto &a : from[l].args)
            if (std::holds_alternative<D_ADDRESS>(a))
              self(from[l].locus_of_argument(a), self);
        };

      fallback(donor_root, fallback);
    }

    break;
  }
  }

  to.active_crossover_type_ = from.active_crossover_type_;
  to.set_if_older_age(from.age());
  to.signature_ = to.hash();

  Ensures(to.is_valid());
  return to;
}

[morinim]

Refactored code.

In the anonymous namespace of individual.cc:

namespace
{

[[nodiscard]] std::vector<locus> collect_subgraph(const individual &prg,
                                                  const locus &root)
{
  std::vector<locus> nodes;
  std::set<locus> visited;

  const auto collect =
    [&](const locus &l, const auto &self) -> void
    {
      if (!visited.insert(l).second)
        return;

      for (const auto &a : prg[l].args)
        if (std::holds_alternative<D_ADDRESS>(a))
          self(prg[l].locus_of_argument(a), self);

      // Post-order: dependencies first.
      nodes.push_back(l);
    };

  collect(root, collect);

  std::sort(nodes.begin(), nodes.end(),
            [](const locus &a, const locus &b)
            {
              if (a.index != b.index)
                return a.index < b.index;
              return a.category < b.category;
            });

  return nodes;
}

[[nodiscard]] std::set<locus> exon_loci(const individual &prg)
{
  std::set<locus> ret;

  const auto exs(prg.cexons());
  for (auto it(exs.begin()); it != exs.end(); ++it)
    ret.insert(it.locus());

  return ret;
}

[[nodiscard]] std::vector<locus> active_loci_of_category(
  const individual &prg, symbol::category_t category)
{
  std::vector<locus> ret;

  const auto exs(prg.cexons());
  for (auto it(exs.begin()); it != exs.end(); ++it)
    if (it.locus().category == category)
      ret.push_back(it.locus());

  return ret;
}

[[nodiscard]] bool try_build_relocation_map(
  const individual &to,
  const std::vector<locus> &donor_nodes,
  const locus &donor_root,
  const locus &dest_root,
  const std::set<locus> &to_exons,
  std::map<locus, locus> &remap)
{
  remap.clear();

  // The root must stay active in the destination.
  remap[donor_root] = dest_root;

  std::set<locus> used;
  used.insert(dest_root);

  // Conservative placement strategy:
  // - all non-root donor nodes must be placed before dest_root.index
  // - assigned rows are strictly increasing
  // This is stronger than necessary, but guarantees backward references.
  locus::index_t next_min_index(0);

  for (const auto &dl : donor_nodes)
  {
    if (dl == donor_root)
      continue;

    locus chosen{};
    bool found(false);

    // Pass 1: prefer introns
    // Pass 2: allow exons
    for (int pass(0); pass < 2 && !found; ++pass)
      for (locus::index_t i(next_min_index); i < dest_root.index && !found; ++i)
        for (symbol::category_t c(0); c < to.categories() && !found; ++c)
        {
          const locus cand(i, c);

          if (cand.category != dl.category)
            continue;
          if (used.contains(cand))
            continue;

          const bool intron(!to_exons.contains(cand));
          if ((pass == 0 && !intron) || (pass == 1 && intron))
            continue;

          chosen = cand;
          found = true;
        }

    if (!found)
      return false;

    remap[dl] = chosen;
    used.insert(chosen);
    next_min_index = chosen.index + 1;
  }

  return true;
}

void copy_relocated_subgraph(const individual &from,
                             individual &to,
                             const std::vector<locus> &donor_nodes,
                             const std::map<locus, locus> &remap)
{
  for (const auto &dl : donor_nodes)
  {
    gene g(from[dl]);

    for (auto &a : g.args)
      if (std::holds_alternative<D_ADDRESS>(a))
      {
        const locus src(from[dl].locus_of_argument(a));
        a = D_ADDRESS(remap.at(src).index);
      }

    to.genome_(remap.at(dl)) = std::move(g);
  }
}

void copy_subgraph_in_place(const individual &from,
                            individual &to,
                            const locus &root)
{
  const auto copy =
    [&](const locus &l, const auto &self) -> void
    {
      to.genome_(l) = from[l];

      for (const auto &a : from[l].args)
        if (std::holds_alternative<D_ADDRESS>(a))
          self(from[l].locus_of_argument(a), self);
    };

  copy(root, copy);
}

void tree_crossover(const individual &from, individual &to)
{
  const locus donor_root(random_locus(from));
  const auto donor_nodes(collect_subgraph(from, donor_root));

  const auto to_exons(exon_loci(to));
  auto root_candidates(active_loci_of_category(to, donor_root.category));

  while (!root_candidates.empty())
  {
    const auto idx(random::sup(root_candidates.size()));
    const locus dest_root(root_candidates[idx]);

    std::swap(root_candidates[idx], root_candidates.back());
    root_candidates.pop_back();

    std::map<locus, locus> remap;
    if (try_build_relocation_map(to, donor_nodes, donor_root, dest_root,
                                 to_exons, remap))
    {
      copy_relocated_subgraph(from, to, donor_nodes, remap);
      return;
    }
  }

  // Safe fallback: original behaviour.
  copy_subgraph_in_place(from, to, donor_root);
}

}  // namespace

The interested portion of the main crossover() is just:

/* ... */
default:  // TREE crossover
    tree_crossover(from, to);
    break;
/* ... */