Crossover Operators

The pycnp.crossover module provides crossover operators for combining parent solutions during the memetic algorithm.

double_backbone_based_crossover(orig_graph: Graph, parents: list[set[int]], seed: int) → Graph[source]

Performs a Double Backbone Based (DBX) crossover operation.

This crossover operator identifies common nodes between parent solutions and constructs an offspring solution based on the backbone structure.

The algorithm: 1. Finds nodes present in both parent solutions (the “backbone”) 2. Preserves these backbone nodes in the offspring 3. Inherits remaining nodes from one parent

This operator is particularly effective for problems where solutions share common structural elements.

Parameters:

  • orig_graph (Graph) – The original graph containing all nodes and edges.

  • parents (list[set[int]]) – A list of two parent solutions, where each solution is a set of node IDs.

  • seed (int) – Random seed for reproducibility.

Returns:

A new graph representing the offspring solution.

Return type:

Graph

Notes

This function is typically called internally by the memetic algorithm rather than directly by users.

inherit_repair_recombination(orig_graph: Graph, parents: list[set[int]], seed: int) → Graph[source]

Performs an Inherit-Repair-Recombination (IRR) crossover operation.

This crossover operator uses three parent solutions to create an offspring.

The algorithm follows a three-phase process: 1. Inherit: Select nodes from parents based on inheritance probabilities 2. Repair: Fix any constraint violations in the inherited solution 3. Recombine: Combine repaired solutions to form the final offspring

IRR is specifically designed for the Distance-Based Critical Node Problem (DCNP) and requires exactly 3 parent solutions.

Parameters:

  • orig_graph (Graph) – The original graph containing all nodes and edges.

  • parents (list[set[int]]) – A list of three parent solutions for DCNP. Each solution is a set of node IDs. Must have exactly 3 parents.

  • seed (int) – Random seed for reproducibility.

Returns:

A new graph representing the offspring solution.

Return type:

Graph

Raises:

ValueError – If the number of parents is not exactly 3.

Notes

This function is typically called internally by the memetic algorithm rather than directly by users.

This operator requires: * Problem type: DCNP (Distance-Based Critical Node Problem) * Population size: exactly 3 individuals * Variable population: must be disabled (is_pop_variable=False)

reduce_solve_combine(orig_graph: Graph, parents: list[set[int]], search: SEARCH_STRATEGIES = 'CHNS', beta: float = 0.9, seed: int = 0) → Graph[source]

Performs a Reduce-Solve-Combine (RSC) crossover operation.

This is the primary crossover operator for the Critical Node Problem (CNP) that uses a problem reduction strategy.

The algorithm: 1. Reduce: Identify common nodes between parents and reduce the problem 2. Solve: Apply local search to the reduced subproblem 3. Combine: Merge the solution with non-common nodes from parents

RSC is used when is_problem_reduction=True in MemeticSearchParams.

Parameters:

  • orig_graph (Graph) – The original graph containing all nodes and edges.

  • parents (list[set[int]]) – A list of two parent solutions. Each solution is a set of node IDs.

  • search (str, optional) – The local search strategy to use on the reduced subproblem. Options: “CBNS”, “CHNS”, “DLAS” (for CNP), “BCLS” (for DCNP). Defaults to “CHNS”.

  • beta (float, optional) – The fraction of common nodes to preserve from parents. Must be in range [0, 1]. Higher values preserve more common nodes. Defaults to 0.9.

  • seed (int, optional) – Random seed for reproducibility. Defaults to 0.

Returns:

A new graph representing the offspring solution.

Return type:

Graph

Notes

This function is typically called internally by the memetic algorithm rather than directly by users.

For DCNP problems, the search strategy must be “BCLS”.