Package net.bmahe.genetics4j.neat.combination

Class NeatChromosomeCombinator<T extends Comparable<T>>

java.lang.Object
net.bmahe.genetics4j.neat.combination.NeatChromosomeCombinator<T>
Type Parameters:
T - the fitness value type (typically Double)
All Implemented Interfaces:
ChromosomeCombinator<T>
public class NeatChromosomeCombinator<T extends Comparable<T>> extends Object implements ChromosomeCombinator<T>
Implements genetic crossover for NEAT (NeuroEvolution of Augmenting Topologies) neural network chromosomes.

NeatChromosomeCombinator performs innovation-number-based genetic recombination between two neural network chromosomes, creating offspring that inherit network topology and connection weights from both parents while preserving the historical tracking essential to the NEAT algorithm.

NEAT crossover algorithm:

  1. Parent comparison: Determine which parent is "fitter" using comparison policy
  2. Gene alignment: Match connections by innovation number between parents
  3. Matching genes: Randomly inherit from either parent (biased by inheritance threshold)
  4. Disjoint genes: Inherit from fitter parent when innovation ranges overlap
  5. Excess genes: Inherit from fitter parent beyond other parent's range
  6. Gene re-enabling: Potentially re-enable disabled genes based on threshold

Key genetic operations:

  • Innovation alignment: Uses innovation numbers to match corresponding genes
  • Fitness-biased inheritance: Favors genes from fitter parent based on inheritance threshold
  • Gene state management: Handles enabled/disabled connection states during crossover
  • Topology preservation: Ensures offspring have valid network topology

Gene classification:

  • Matching genes: Same innovation number in both parents, inherit randomly
  • Disjoint genes: Innovation number exists in one parent within other's range
  • Excess genes: Innovation number beyond other parent's highest innovation
  • Disabled genes: May be re-enabled if other parent has enabled version

Common usage patterns: 


 // Create NEAT chromosome combinator
 RandomGenerator randomGen = RandomGenerator.getDefault();
 NeatCombination policy = NeatCombination.builder()
     .inheritanceThresold(0.7)  // 70% bias toward fitter parent
     .reenableGeneInheritanceThresold(0.25)  // 25% gene re-enabling chance
     .parentComparisonPolicy(FitnessComparison.build())
     .build();
 
 ParentComparisonHandler comparisonHandler = new FitnessComparisonHandler();
 NeatChromosomeCombinator<Double> combinator = new NeatChromosomeCombinator<>(
     randomGen, policy, comparisonHandler
 );
 
 // Perform crossover
 NeatChromosome parent1 = // ... first parent
 NeatChromosome parent2 = // ... second parent
 Double fitness1 = 0.85;
 Double fitness2 = 0.72;
 
 List<Chromosome> offspring = combinator.combine(
     eaConfiguration, parent1, fitness1, parent2, fitness2
 );
 NeatChromosome child = (NeatChromosome) offspring.get(0);

Inheritance threshold effects:

  • 0.5: Unbiased inheritance, equal probability from both parents
  • > 0.5: Bias toward fitter parent, promotes convergence
  • < 0.5: Bias toward less fit parent, increases diversity
  • 1.0: Always inherit from fitter parent (when fitness differs)

Gene re-enabling mechanism:

  • Preservation: Disabled genes maintain connection topology information
  • Re-activation: Chance to re-enable genes that are enabled in other parent
  • Exploration: Allows rediscovery of previously disabled connection patterns
  • Genetic diversity: Prevents permanent loss of structural information

Duplicate connection prevention:

  • Links cache: Tracks already included connections to prevent duplicates
  • Topology validation: Ensures each connection appears at most once
  • Cache efficiency: O(1) lookup for connection existence checking
  • Memory management: Cache cleared after each crossover operation

Performance considerations:

  • Linear time complexity: O(n + m) where n, m are parent connection counts
  • Innovation sorting: Leverages pre-sorted connection lists for efficiency
  • Memory efficiency: Minimal allocation during crossover
  • Cache optimization: Efficient duplicate detection and prevention
See Also:

  • Field Details

    • logger

      public static final org.apache.logging.log4j.Logger logger

    • randomGenerator

      private final RandomGenerator randomGenerator

    • neatCombination

      private final NeatCombination neatCombination

    • parentComparisonHandler

      private final ParentComparisonHandler parentComparisonHandler

  • Constructor Details

    • NeatChromosomeCombinator

      public NeatChromosomeCombinator(RandomGenerator _randomGenerator, NeatCombination _neatCombination, ParentComparisonHandler _parentComparisonHandler)
      Constructs a new NEAT chromosome combinator with the specified components.

      The combinator uses the random generator for stochastic decisions during crossover, the combination policy for inheritance parameters, and the comparison handler for determining parent fitness relationships.

      Parameters:
      _randomGenerator - random number generator for stochastic crossover decisions
      _neatCombination - crossover policy defining inheritance parameters
      _parentComparisonHandler - handler for comparing parent fitness and determining inheritance bias
      Throws:
      IllegalArgumentException - if any parameter is null

  • Method Details

    • linksCacheContainsConnection

      private boolean linksCacheContainsConnection(Map<Integer,Set<Integer>> linksCache, Connection connection)
      Checks whether a connection already exists in the links cache.

      The links cache prevents duplicate connections in the offspring by tracking all connections that have already been added. This ensures each connection appears at most once in the resulting chromosome.

      Parameters:
      linksCache - cache mapping from-node indices to sets of to-node indices
      connection - connection to check for existence
      Returns:
      true if connection already exists in cache, false otherwise
      Throws:
      IllegalArgumentException - if linksCache or connection is null

    • insertInlinksCache

      private void insertInlinksCache(Map<Integer,Set<Integer>> linksCache, Connection connection)
      Adds a connection to the links cache to prevent future duplicates.

      This method records that a connection from the specified source to target node has been added to the offspring, preventing the same connection from being added again during the crossover process.

      Parameters:
      linksCache - cache mapping from-node indices to sets of to-node indices
      connection - connection to add to the cache
      Throws:
      IllegalArgumentException - if linksCache or connection is null

    • shouldReEnable

      protected boolean shouldReEnable(Connection chosenParent, Connection otherParent)
      Determines whether a disabled gene should be re-enabled during crossover.

      If the chosen parent has a disabled connection but the other parent has the same connection enabled, there is a configurable chance to re-enable the connection in the offspring. This mechanism prevents permanent loss of potentially useful connections.

      Parameters:
      chosenParent - the connection selected for inheritance
      otherParent - the corresponding connection from the other parent
      Returns:
      true if the disabled connection should be re-enabled, false otherwise
      Throws:
      IllegalArgumentException - if either connection is null

    • combine

      public List<Chromosome> combine(AbstractEAConfiguration<T> eaConfiguration, Chromosome firstChromosome, T firstParentFitness, Chromosome secondChromosome, T secondParentFitness)
      Performs genetic crossover between two NEAT chromosomes to produce offspring.

      This method implements the NEAT crossover algorithm, aligning genes by innovation number and applying inheritance rules based on parent fitness and configuration parameters. The result is a single offspring chromosome that inherits network topology and connection weights from both parents.

      Crossover process:

      1. Compare parent fitness to determine inheritance bias
      2. Align genes by innovation number between parents
      3. Process matching genes with random inheritance (biased)
      4. Process disjoint genes based on fitness comparison
      5. Process excess genes from fitter parent
      6. Apply gene re-enabling rules for disabled connections
      Specified by:
      combine in interface ChromosomeCombinator<T extends Comparable<T>>
      Parameters:
      eaConfiguration - evolutionary algorithm configuration containing fitness comparator
      firstChromosome - first parent chromosome (must be NeatChromosome)
      firstParentFitness - fitness value of first parent
      secondChromosome - second parent chromosome (must be NeatChromosome)
      secondParentFitness - fitness value of second parent
      Returns:
      list containing single offspring chromosome
      Throws:
      IllegalArgumentException - if chromosomes are not NeatChromosome instances or any parameter is null