NeatChromosomeAddConnection.java

package net.bmahe.genetics4j.neat.mutation.chromosome;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
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.mutation.chromosome.ChromosomeMutationHandler;
import net.bmahe.genetics4j.core.spec.chromosome.ChromosomeSpec;
import net.bmahe.genetics4j.core.spec.mutation.MutationPolicy;
import net.bmahe.genetics4j.neat.Connection;
import net.bmahe.genetics4j.neat.InnovationManager;
import net.bmahe.genetics4j.neat.chromosomes.NeatChromosome;
import net.bmahe.genetics4j.neat.spec.NeatChromosomeSpec;
import net.bmahe.genetics4j.neat.spec.mutation.AddConnection;

/**
 * Chromosome mutation handler that adds new connections to NEAT (NeuroEvolution of Augmenting Topologies) neural networks.
 * 
 * <p>NeatChromosomeAddConnection implements the add-connection structural mutation for NEAT chromosomes,
 * which increases network connectivity by creating new weighted links between existing nodes. This mutation
 * is essential for NEAT's ability to explore different network topologies and discover optimal connectivity patterns.
 * 
 * <p>Add-connection mutation process:
 * <ol>
 * <li><strong>Node selection</strong>: Randomly select source and target nodes from all available nodes</li>
 * <li><strong>Validity checking</strong>: Ensure the connection doesn't violate network constraints</li>
 * <li><strong>Duplicate prevention</strong>: Verify the connection doesn't already exist</li>
 * <li><strong>Innovation assignment</strong>: Assign unique innovation number via InnovationManager</li>
 * <li><strong>Weight initialization</strong>: Set random weight within chromosome bounds</li>
 * <li><strong>Connection creation</strong>: Add enabled connection to the chromosome</li>
 * </ol>
 * 
 * <p>Connection constraints:
 * <ul>
 * <li><strong>No self-connections</strong>: Source and target nodes must be different</li>
 * <li><strong>No duplicate connections</strong>: Connection between same nodes cannot already exist</li>
 * <li><strong>Feed-forward topology</strong>: Output nodes cannot be sources, input nodes cannot be targets</li>
 * <li><strong>Valid node references</strong>: Both nodes must exist in the network</li>
 * </ul>
 * 
 * <p>Node selection strategy:
 * <ul>
 * <li><strong>Available nodes</strong>: All input, output, and hidden nodes are potential connection endpoints</li>
 * <li><strong>Dynamic range</strong>: Node range adapts to include any hidden nodes created by add-node mutations</li>
 * <li><strong>Uniform selection</strong>: All valid nodes have equal probability of being selected</li>
 * <li><strong>Constraint filtering</strong>: Invalid connections are rejected and no mutation occurs</li>
 * </ul>
 * 
 * <p>Common usage patterns:
 * <pre>{@code
 * // Create add-connection mutation handler
 * RandomGenerator randomGen = RandomGenerator.getDefault();
 * InnovationManager innovationManager = new InnovationManager();
 * NeatChromosomeAddConnection handler = new NeatChromosomeAddConnection(
 *     randomGen, innovationManager
 * );
 * 
 * // Check if handler can process mutation
 * AddConnection mutationPolicy = AddConnection.of(0.1);
 * NeatChromosomeSpec chromosomeSpec = NeatChromosomeSpec.of(3, 2, -1.0f, 1.0f);
 * boolean canHandle = handler.canHandle(mutationPolicy, chromosomeSpec);
 * 
 * // Apply mutation to chromosome
 * NeatChromosome originalChromosome = // ... existing chromosome
 * NeatChromosome mutatedChromosome = handler.mutate(mutationPolicy, originalChromosome);
 * 
 * // Result: chromosome may have one additional connection (if valid connection found)
 * }</pre>
 * 
 * <p>Integration with NEAT algorithm:
 * <ul>
 * <li><strong>Innovation tracking</strong>: Uses InnovationManager for consistent innovation number assignment</li>
 * <li><strong>Population consistency</strong>: Same connection types get same innovation numbers across population</li>
 * <li><strong>Genetic alignment</strong>: Innovation numbers enable proper crossover alignment</li>
 * <li><strong>Structural diversity</strong>: Increases topological diversity in the population</li>
 * </ul>
 * 
 * <p>Weight initialization:
 * <ul>
 * <li><strong>Random weights</strong>: New connections get random weights within chromosome bounds</li>
 * <li><strong>Uniform distribution</strong>: Weights uniformly distributed between min and max values</li>
 * <li><strong>Immediate activation</strong>: New connections are enabled and immediately affect network behavior</li>
 * <li><strong>Bounded values</strong>: Weights respect chromosome's min/max weight constraints</li>
 * </ul>
 * 
 * <p>Performance considerations:
 * <ul>
 * <li><strong>Efficient validation</strong>: Fast checks for connection existence and validity</li>
 * <li><strong>Innovation caching</strong>: Leverages InnovationManager's O(1) innovation lookup</li>
 * <li><strong>Memory efficiency</strong>: Minimal allocation during mutation</li>
 * <li><strong>Failed mutation handling</strong>: Gracefully handles cases where no valid connection can be added</li>
 * </ul>
 * 
 * @see AddConnection
 * @see NeatChromosome
 * @see InnovationManager
 * @see ChromosomeMutationHandler
 */
public class NeatChromosomeAddConnection implements ChromosomeMutationHandler<NeatChromosome> {

	public static final Logger logger = LogManager.getLogger(NeatChromosomeAddConnection.class);

	private final RandomGenerator randomGenerator;
	private final InnovationManager innovationManager;

	/**
	 * Constructs a new add-connection mutation handler with the specified components.
	 * 
	 * <p>The random generator is used for node selection and weight initialization.
	 * The innovation manager provides unique innovation numbers for new connections,
	 * ensuring consistent tracking across the population.
	 * 
	 * @param _randomGenerator random number generator for stochastic operations
	 * @param _innovationManager innovation manager for tracking structural changes
	 * @throws IllegalArgumentException if randomGenerator or innovationManager is null
	 */
	public NeatChromosomeAddConnection(final RandomGenerator _randomGenerator,
			final InnovationManager _innovationManager) {
		Validate.notNull(_randomGenerator);
		Validate.notNull(_innovationManager);

		this.randomGenerator = _randomGenerator;
		this.innovationManager = _innovationManager;
	}

	/**
	 * Determines whether this handler can process the given mutation policy and chromosome specification.
	 * 
	 * <p>This handler specifically processes AddConnection mutations applied to NeatChromosomeSpec
	 * specifications, ensuring type compatibility for NEAT neural network connection addition.
	 * 
	 * @param mutationPolicy the mutation policy to check
	 * @param chromosome the chromosome specification to check
	 * @return true if policy is AddConnection and chromosome is NeatChromosomeSpec, false otherwise
	 * @throws IllegalArgumentException if any parameter is null
	 */
	@Override
	public boolean canHandle(final MutationPolicy mutationPolicy, final ChromosomeSpec chromosome) {
		Validate.notNull(mutationPolicy);
		Validate.notNull(chromosome);

		return mutationPolicy instanceof AddConnection && chromosome instanceof NeatChromosomeSpec;
	}

	/**
	 * Applies add-connection mutation to a NEAT chromosome.
	 * 
	 * <p>This method attempts to add a new connection between two randomly selected nodes
	 * in the neural network. The mutation may fail if no valid connection can be found
	 * (e.g., all possible connections already exist or violate network constraints).
	 * 
	 * <p>Mutation algorithm:
	 * <ol>
	 * <li>Determine the range of available nodes (inputs, outputs, and hidden nodes)</li>
	 * <li>Randomly select source and target nodes</li>
	 * <li>Validate the connection doesn't violate constraints</li>
	 * <li>If valid, create new connection with innovation number and random weight</li>
	 * <li>Add connection to chromosome and return modified chromosome</li>
	 * <li>If invalid, return chromosome unchanged</li>
	 * </ol>
	 * 
	 * @param mutationPolicy the add-connection mutation policy
	 * @param chromosome the NEAT chromosome to mutate
	 * @return a new chromosome with potentially one additional connection
	 * @throws IllegalArgumentException if policy is not AddConnection or chromosome is not NeatChromosome
	 */
	@Override
	public NeatChromosome mutate(final MutationPolicy mutationPolicy, final Chromosome chromosome) {
		Validate.notNull(mutationPolicy);
		Validate.notNull(chromosome);
		Validate.isInstanceOf(AddConnection.class, mutationPolicy);
		Validate.isInstanceOf(NeatChromosome.class, chromosome);

		final var neatChromosome = (NeatChromosome) chromosome;
		final var numInputs = neatChromosome.getNumInputs();
		final var numOutputs = neatChromosome.getNumOutputs();
		final var minValue = neatChromosome.getMinWeightValue();
		final var maxValue = neatChromosome.getMaxWeightValue();

		final var oldConnections = neatChromosome.getConnections();
		final List<Connection> newConnections = new ArrayList<>(oldConnections);

		final int maxNodeConnectionsValue = neatChromosome.getConnections()
				.stream()
				.map(connection -> Math.max(connection.fromNodeIndex(), connection.toNodeIndex()))
				.max(Comparator.naturalOrder())
				.orElse(0);

		final int maxNodeValue = Math.max(maxNodeConnectionsValue,
				neatChromosome.getNumInputs() + neatChromosome.getNumOutputs() - 1);

		final int fromNode = randomGenerator.nextInt(maxNodeValue + 1);
		final int toNode = randomGenerator.nextInt(maxNodeValue + 1);

		final boolean isConnectionExist = oldConnections.stream()
				.anyMatch(connection -> connection.fromNodeIndex() == fromNode && connection.toNodeIndex() == toNode);

		final boolean isFromNodeAnOutput = fromNode < numInputs + numOutputs && fromNode >= numInputs;
		final boolean isToNodeAnInput = toNode < numInputs;

		if (fromNode != toNode && isConnectionExist == false && isToNodeAnInput == false && isFromNodeAnOutput == false) {
			final int innovation = innovationManager.computeNewId(fromNode, toNode);

			final var newConnection = Connection.builder()
					.fromNodeIndex(fromNode)
					.toNodeIndex(toNode)
					.innovation(innovation)
					.weight(randomGenerator.nextFloat(minValue, maxValue))
					.isEnabled(true)
					.build();

			newConnections.add(newConnection);
		}

		return new NeatChromosome(numInputs, numOutputs, minValue, maxValue, newConnections);
	}
}