InnovationManager.java

package net.bmahe.genetics4j.neat;

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;

import org.apache.commons.lang3.Validate;
import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;

/**
 * Manages innovation numbers for the NEAT (NeuroEvolution of Augmenting Topologies) algorithm.
 * 
 * <p>The InnovationManager is a critical component of the NEAT algorithm that tracks structural innovations
 * in neural networks through unique innovation numbers. This system enables NEAT to perform meaningful
 * genetic crossover between neural networks with different topologies while preserving historical information
 * about when specific connections were first added to the population.
 * 
 * <p>Key responsibilities:
 * <ul>
 * <li><strong>Innovation tracking</strong>: Assigns unique numbers to each new connection type (from-to node pair)</li>
 * <li><strong>Historical marking</strong>: Maintains consistent innovation numbers across the population</li>
 * <li><strong>Crossover support</strong>: Enables alignment of neural network structures during recombination</li>
 * <li><strong>Cache management</strong>: Provides efficient lookup and generation of innovation numbers</li>
 * </ul>
 * 
 * <p>NEAT innovation number system:
 * <ul>
 * <li><strong>Unique identification</strong>: Each unique connection (from-node → to-node) gets one innovation number</li>
 * <li><strong>Population consistency</strong>: Same connection type across individuals gets same innovation number</li>
 * <li><strong>Temporal ordering</strong>: Innovation numbers reflect the historical order of structural mutations</li>
 * <li><strong>Crossover alignment</strong>: Enables gene alignment during genetic recombination</li>
 * </ul>
 * 
 * <p>Innovation number workflow:
 * <ol>
 * <li><strong>Mutation occurs</strong>: Add-connection mutation creates new connection type</li>
 * <li><strong>Innovation check</strong>: Manager checks if this connection type was seen before</li>
 * <li><strong>Number assignment</strong>: New types get new innovation numbers, existing types reuse numbers</li>
 * <li><strong>Population tracking</strong>: All individuals with same connection type share same innovation number</li>
 * <li><strong>Crossover alignment</strong>: Innovation numbers enable proper gene alignment during recombination</li>
 * </ol>
 * 
 * <p>Common usage patterns:
 * <pre>{@code
 * // Create innovation manager for new evolution run
 * InnovationManager innovationManager = new InnovationManager();
 * 
 * // During add-connection mutation
 * int fromNode = 0, toNode = 3;
 * int innovationNumber = innovationManager.computeNewId(fromNode, toNode);
 * Connection newConnection = Connection.of(fromNode, toNode, weight, innovationNumber, true);
 * 
 * // Reset cache between generations if needed
 * innovationManager.resetCache();
 * 
 * // Start with specific innovation number
 * InnovationManager manager = new InnovationManager(1000);
 * }</pre>
 * 
 * <p>Cache management strategy:
 * <ul>
 * <li><strong>Per-generation caching</strong>: Cache innovation numbers within each generation</li>
 * <li><strong>Cross-generation persistence</strong>: Innovation numbers remain consistent across generations</li>
 * <li><strong>Memory management</strong>: Reset cache periodically to prevent memory growth</li>
 * <li><strong>Concurrent access</strong>: Thread-safe operations for parallel genetic operations</li>
 * </ul>
 * 
 * <p>Performance considerations:
 * <ul>
 * <li><strong>O(1) lookup</strong>: Fast innovation number retrieval through hash map caching</li>
 * <li><strong>Memory efficiency</strong>: Cache only unique connection types seen in current generation</li>
 * <li><strong>Thread safety</strong>: Concurrent operations supported for parallel evolution</li>
 * <li><strong>Cache lifecycle</strong>: Reset cache between evolution runs to prevent memory leaks</li>
 * </ul>
 * 
 * <p>Integration with NEAT algorithm:
 * <ul>
 * <li><strong>Structural mutations</strong>: Add-connection mutations use innovation manager</li>
 * <li><strong>Genetic crossover</strong>: Innovation numbers enable gene alignment</li>
 * <li><strong>Compatibility distance</strong>: Innovation numbers used to identify matching, excess, and disjoint genes</li>
 * <li><strong>Population management</strong>: Shared innovation manager across entire population</li>
 * </ul>
 * 
 * @see Connection
 * @see ConnectionPair
 * @see NeatChromosome
 * @see net.bmahe.genetics4j.neat.mutation.AddConnectionPolicyHandler
 */
public class InnovationManager {
	public static final Logger logger = LogManager.getLogger(InnovationManager.class);

	public static final int DEFAULT_INITIAL_ID = 0;

	private final AtomicInteger currentId;

	private final ConcurrentHashMap<ConnectionPair, Integer> innovationCache = new ConcurrentHashMap<>();

	/**
	 * Constructs an innovation manager with the specified initial innovation number.
	 * 
	 * @param initialValue the starting innovation number for new innovations
	 */
	public InnovationManager(final int initialValue) {
		currentId = new AtomicInteger(initialValue);
	}

	/**
	 * Constructs an innovation manager with the default initial innovation number (0).
	 */
	public InnovationManager() {
		this(DEFAULT_INITIAL_ID);
	}

	/**
	 * Computes or retrieves the innovation number for a connection between two nodes.
	 * 
	 * <p>If this connection type (from-node → to-node) has been seen before, returns the existing
	 * innovation number from the cache. Otherwise, generates a new innovation number and caches it
	 * for future use. This ensures that the same connection type across different individuals in
	 * the population receives the same innovation number.
	 * 
	 * @param from the source node index of the connection
	 * @param to the target node index of the connection
	 * @return the innovation number for this connection type
	 * @throws IllegalArgumentException if from equals to (self-connections not allowed)
	 */
	public int computeNewId(final int from, final int to) {
		Validate.isTrue(from != to);

		final var connectionPair = new ConnectionPair(from, to);
		return innovationCache.computeIfAbsent(connectionPair, k -> currentId.getAndIncrement());
	}

	/**
	 * Resets the innovation cache, clearing all cached connection-to-innovation-number mappings.
	 * 
	 * <p>This method should be called between evolution runs or generations to prevent memory
	 * growth and ensure that innovation number assignment starts fresh. Note that this does
	 * not reset the current innovation number counter, so new innovations will continue to
	 * receive unique numbers.
	 */
	public void resetCache() {
		logger.trace("Resetting cache with currently {} entries", innovationCache.size());
		innovationCache.clear();
	}
}