search

aimclub / GOLEM

Graph Optimiser for Learning and Evolution of Models
https://thegolem.readthedocs.io
BSD 3-Clause "New" or "Revised" License
60 stars 7 forks source link

Add general crossovers for graphs with cycles #140

Open gkirgizov opened 1 year ago

gkirgizov commented 1 year ago

Now we have Crossovers for multi-root graphs thanks to #84 . But we still have no alternative for cycled graphs.

gkirgizov commented 1 year ago

I have an idea on how to apply crossovers that work for DAGs to generic connected graphs with cycles:

Crossover that preserves cycles:

  1. Find all cycling components in the graph
  2. Represent cycling components as a kind of "meta"-nodes -- we get "virtual" DAG from cycled graph
  3. Perform usual crossover on this virtual DAG
  4. Return usual cycles back from "meta"-nodes The implementation of that can be somewhat involved. I'm not sure if it worth it.

Another idea is to iteratively build 3rd graph by taking random subgraphs in alternating manner from parent graphs.