NeatChromosomeCombinator.java
package net.bmahe.genetics4j.neat.combination;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.random.RandomGenerator;
import org.apache.commons.lang3.Validate;
import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;
import net.bmahe.genetics4j.core.chromosomes.Chromosome;
import net.bmahe.genetics4j.core.combination.ChromosomeCombinator;
import net.bmahe.genetics4j.core.spec.AbstractEAConfiguration;
import net.bmahe.genetics4j.neat.Connection;
import net.bmahe.genetics4j.neat.chromosomes.NeatChromosome;
import net.bmahe.genetics4j.neat.combination.parentcompare.ChosenOtherChromosome;
import net.bmahe.genetics4j.neat.combination.parentcompare.ParentComparisonHandler;
import net.bmahe.genetics4j.neat.spec.combination.NeatCombination;
import net.bmahe.genetics4j.neat.spec.combination.parentcompare.ParentComparisonPolicy;
/**
* Implements genetic crossover for NEAT (NeuroEvolution of Augmenting Topologies) neural network chromosomes.
*
* <p>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.
*
* <p>NEAT crossover algorithm:
* <ol>
* <li><strong>Parent comparison</strong>: Determine which parent is "fitter" using comparison policy</li>
* <li><strong>Gene alignment</strong>: Match connections by innovation number between parents</li>
* <li><strong>Matching genes</strong>: Randomly inherit from either parent (biased by inheritance threshold)</li>
* <li><strong>Disjoint genes</strong>: Inherit from fitter parent when innovation ranges overlap</li>
* <li><strong>Excess genes</strong>: Inherit from fitter parent beyond other parent's range</li>
* <li><strong>Gene re-enabling</strong>: Potentially re-enable disabled genes based on threshold</li>
* </ol>
*
* <p>Key genetic operations:
* <ul>
* <li><strong>Innovation alignment</strong>: Uses innovation numbers to match corresponding genes</li>
* <li><strong>Fitness-biased inheritance</strong>: Favors genes from fitter parent based on inheritance threshold</li>
* <li><strong>Gene state management</strong>: Handles enabled/disabled connection states during crossover</li>
* <li><strong>Topology preservation</strong>: Ensures offspring have valid network topology</li>
* </ul>
*
* <p>Gene classification:
* <ul>
* <li><strong>Matching genes</strong>: Same innovation number in both parents, inherit randomly</li>
* <li><strong>Disjoint genes</strong>: Innovation number exists in one parent within other's range</li>
* <li><strong>Excess genes</strong>: Innovation number beyond other parent's highest innovation</li>
* <li><strong>Disabled genes</strong>: May be re-enabled if other parent has enabled version</li>
* </ul>
*
* <p>Common usage patterns:
* <pre>{@code
* // 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);
* }</pre>
*
* <p>Inheritance threshold effects:
* <ul>
* <li><strong>0.5</strong>: Unbiased inheritance, equal probability from both parents</li>
* <li><strong>> 0.5</strong>: Bias toward fitter parent, promotes convergence</li>
* <li><strong>< 0.5</strong>: Bias toward less fit parent, increases diversity</li>
* <li><strong>1.0</strong>: Always inherit from fitter parent (when fitness differs)</li>
* </ul>
*
* <p>Gene re-enabling mechanism:
* <ul>
* <li><strong>Preservation</strong>: Disabled genes maintain connection topology information</li>
* <li><strong>Re-activation</strong>: Chance to re-enable genes that are enabled in other parent</li>
* <li><strong>Exploration</strong>: Allows rediscovery of previously disabled connection patterns</li>
* <li><strong>Genetic diversity</strong>: Prevents permanent loss of structural information</li>
* </ul>
*
* <p>Duplicate connection prevention:
* <ul>
* <li><strong>Links cache</strong>: Tracks already included connections to prevent duplicates</li>
* <li><strong>Topology validation</strong>: Ensures each connection appears at most once</li>
* <li><strong>Cache efficiency</strong>: O(1) lookup for connection existence checking</li>
* <li><strong>Memory management</strong>: Cache cleared after each crossover operation</li>
* </ul>
*
* <p>Performance considerations:
* <ul>
* <li><strong>Linear time complexity</strong>: O(n + m) where n, m are parent connection counts</li>
* <li><strong>Innovation sorting</strong>: Leverages pre-sorted connection lists for efficiency</li>
* <li><strong>Memory efficiency</strong>: Minimal allocation during crossover</li>
* <li><strong>Cache optimization</strong>: Efficient duplicate detection and prevention</li>
* </ul>
*
* @param <T> the fitness value type (typically Double)
* @see NeatCombination
* @see ParentComparisonHandler
* @see NeatChromosome
* @see ChromosomeCombinator
*/
public class NeatChromosomeCombinator<T extends Comparable<T>> implements ChromosomeCombinator<T> {
public static final Logger logger = LogManager.getLogger(NeatChromosomeCombinator.class);
private final RandomGenerator randomGenerator;
private final NeatCombination neatCombination;
private final ParentComparisonHandler parentComparisonHandler;
/**
* Checks whether a connection already exists in the links cache.
*
* <p>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.
*
* @param linksCache cache mapping from-node indices to sets of to-node indices
* @param connection connection to check for existence
* @return true if connection already exists in cache, false otherwise
* @throws IllegalArgumentException if linksCache or connection is null
*/
private boolean linksCacheContainsConnection(final Map<Integer, Set<Integer>> linksCache,
final Connection connection) {
Validate.notNull(linksCache);
Validate.notNull(connection);
final int fromNodeIndex = connection.fromNodeIndex();
final int toNodeIndex = connection.toNodeIndex();
return linksCache.containsKey(fromNodeIndex) == true && linksCache.get(fromNodeIndex)
.contains(toNodeIndex) == true;
}
/**
* Adds a connection to the links cache to prevent future duplicates.
*
* <p>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.
*
* @param linksCache cache mapping from-node indices to sets of to-node indices
* @param connection connection to add to the cache
* @throws IllegalArgumentException if linksCache or connection is null
*/
private void insertInlinksCache(final Map<Integer, Set<Integer>> linksCache, final Connection connection) {
Validate.notNull(linksCache);
Validate.notNull(connection);
final int fromNodeIndex = connection.fromNodeIndex();
final int toNodeIndex = connection.toNodeIndex();
linksCache.computeIfAbsent(fromNodeIndex, k -> new HashSet<>())
.add(toNodeIndex);
}
/**
* Determines whether a disabled gene should be re-enabled during crossover.
*
* <p>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.
*
* @param chosenParent the connection selected for inheritance
* @param otherParent the corresponding connection from the other parent
* @return true if the disabled connection should be re-enabled, false otherwise
* @throws IllegalArgumentException if either connection is null
*/
protected boolean shouldReEnable(final Connection chosenParent, final Connection otherParent) {
Validate.notNull(chosenParent);
Validate.notNull(otherParent);
boolean shouldReEnable = false;
if (chosenParent.isEnabled() == false && otherParent.isEnabled() == true) {
if (randomGenerator.nextDouble() < neatCombination.reenableGeneInheritanceThresold()) {
shouldReEnable = true;
}
}
return shouldReEnable;
}
/**
* Constructs a new NEAT chromosome combinator with the specified components.
*
* <p>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.
*
* @param _randomGenerator random number generator for stochastic crossover decisions
* @param _neatCombination crossover policy defining inheritance parameters
* @param _parentComparisonHandler handler for comparing parent fitness and determining inheritance bias
* @throws IllegalArgumentException if any parameter is null
*/
public NeatChromosomeCombinator(final RandomGenerator _randomGenerator, final NeatCombination _neatCombination,
final ParentComparisonHandler _parentComparisonHandler) {
Validate.notNull(_randomGenerator);
Validate.notNull(_neatCombination);
Validate.notNull(_parentComparisonHandler);
this.randomGenerator = _randomGenerator;
this.neatCombination = _neatCombination;
this.parentComparisonHandler = _parentComparisonHandler;
}
/**
* Performs genetic crossover between two NEAT chromosomes to produce offspring.
*
* <p>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.
*
* <p>Crossover process:
* <ol>
* <li>Compare parent fitness to determine inheritance bias</li>
* <li>Align genes by innovation number between parents</li>
* <li>Process matching genes with random inheritance (biased)</li>
* <li>Process disjoint genes based on fitness comparison</li>
* <li>Process excess genes from fitter parent</li>
* <li>Apply gene re-enabling rules for disabled connections</li>
* </ol>
*
* @param eaConfiguration evolutionary algorithm configuration containing fitness comparator
* @param firstChromosome first parent chromosome (must be NeatChromosome)
* @param firstParentFitness fitness value of first parent
* @param secondChromosome second parent chromosome (must be NeatChromosome)
* @param secondParentFitness fitness value of second parent
* @return list containing single offspring chromosome
* @throws IllegalArgumentException if chromosomes are not NeatChromosome instances or any parameter is null
*/
@Override
public List<Chromosome> combine(final AbstractEAConfiguration<T> eaConfiguration, final Chromosome firstChromosome,
final T firstParentFitness, final Chromosome secondChromosome, final T secondParentFitness) {
Validate.notNull(eaConfiguration);
Validate.notNull(firstChromosome);
Validate.notNull(firstParentFitness);
Validate.isInstanceOf(NeatChromosome.class, firstChromosome);
Validate.notNull(secondChromosome);
Validate.notNull(secondParentFitness);
Validate.isInstanceOf(NeatChromosome.class, secondChromosome);
final NeatChromosome firstNeatChromosome = (NeatChromosome) firstChromosome;
final NeatChromosome secondNeatChromosome = (NeatChromosome) secondChromosome;
final Comparator<T> fitnessComparator = eaConfiguration.fitnessComparator();
final double inheritanceThresold = neatCombination.inheritanceThresold();
final ParentComparisonPolicy parentComparisonPolicy = neatCombination.parentComparisonPolicy();
final int fitnessComparison = fitnessComparator.compare(firstParentFitness, secondParentFitness);
final ChosenOtherChromosome comparedChromosomes = parentComparisonHandler
.compare(parentComparisonPolicy, firstNeatChromosome, secondNeatChromosome, fitnessComparison);
final NeatChromosome bestChromosome = comparedChromosomes.chosen();
final NeatChromosome worstChromosome = comparedChromosomes.other();
final List<Connection> combinedConnections = new ArrayList<>();
final Map<Integer, Set<Integer>> linksCache = new HashMap<>();
final var bestConnections = bestChromosome.getConnections();
final var worstConnections = worstChromosome.getConnections();
int indexBest = 0;
int indexWorst = 0;
while (indexBest < bestConnections.size() && indexWorst < worstConnections.size()) {
final var bestConnection = bestConnections.get(indexBest);
final var worstConnection = worstConnections.get(indexWorst);
if (bestConnection.innovation() == worstConnection.innovation()) {
/**
* If innovation is the same, we pick the connection randomly
*/
var original = bestConnection;
var other = worstConnection;
if (randomGenerator.nextDouble() < 1 - inheritanceThresold) {
original = worstConnection;
other = bestConnection;
}
if (linksCacheContainsConnection(linksCache, original) == false) {
/**
* If the chosen gene is disabled but the other one is enabled, then there is a
* chance we will re-enable it
*/
final boolean isEnabled = shouldReEnable(original, other) ? true : original.isEnabled();
final var childConnection = Connection.builder()
.from(original)
.isEnabled(isEnabled)
.build();
combinedConnections.add(childConnection);
insertInlinksCache(linksCache, original);
}
indexBest++;
indexWorst++;
} else if (bestConnection.innovation() > worstConnection.innovation()) {
/**
* If the fitnesses are equal, then we randomly inherit from the parent
* Otherwise, we do not inherit from the lesser gene
*/
if (fitnessComparison == 0 && randomGenerator.nextDouble() < 1.0 - inheritanceThresold) {
final var original = worstConnection;
if (linksCacheContainsConnection(linksCache, original) == false) {
combinedConnections.add(Connection.copyOf(original));
insertInlinksCache(linksCache, original);
}
}
indexWorst++;
} else {
/**
* If the fitnesses are equal, then we randomly inherit from the parent
* Otherwise, we always inherit from the better gene
*/
if (fitnessComparison != 0 || randomGenerator.nextDouble() < inheritanceThresold) {
if (linksCacheContainsConnection(linksCache, bestConnection) == false) {
combinedConnections.add(Connection.copyOf(bestConnection));
insertInlinksCache(linksCache, bestConnection);
}
}
indexBest++;
}
}
/*
* Case where the best connection has more genes. It's called excess genes
*/
while (indexBest < bestConnections.size()) {
/**
* If the fitnesses are equal, then we randomly inherit from the parent
* Otherwise, we always inherit from the better gene
*/
if (fitnessComparison != 0 || randomGenerator.nextDouble() < inheritanceThresold) {
final var bestConnection = bestConnections.get(indexBest);
if (linksCacheContainsConnection(linksCache, bestConnection) == false) {
combinedConnections.add(Connection.copyOf(bestConnection));
insertInlinksCache(linksCache, bestConnection);
}
}
indexBest++;
}
/*
* Case where the worst connection has more genes. It's called excess genes.
* Since we don't inherit when their fitness aren't equal, it means we can skip
* the excess genes from the weaker connections. However we will randomly
* inherit if their fitnesses are equal
*/
while (fitnessComparison == 0 && indexWorst < worstConnections.size()) {
if (randomGenerator.nextDouble() < 1.0 - inheritanceThresold) {
final var worstConnection = worstConnections.get(indexWorst);
if (linksCacheContainsConnection(linksCache, worstConnection) == false) {
combinedConnections.add(Connection.copyOf(worstConnection));
insertInlinksCache(linksCache, worstConnection);
}
}
indexWorst++;
}
return List.of(new NeatChromosome(bestChromosome.getNumInputs(),
bestChromosome.getNumOutputs(),
bestChromosome.getMinWeightValue(),
bestChromosome.getMaxWeightValue(),
combinedConnections));
}
}