GOLEM icon indicating copy to clipboard operation
GOLEM copied to clipboard

Add general crossovers for graphs with cycles

Open gkirgizov opened this issue 2 years ago • 1 comments

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

gkirgizov avatar Jul 05 '23 04:07 gkirgizov

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.

gkirgizov avatar Jul 28 '23 11:07 gkirgizov