1 package net.bmahe.genetics4j.neat.mutation.chromosome;
2
3 import java.util.ArrayList;
4 import java.util.LinkedHashSet;
5 import java.util.List;
6 import java.util.Objects;
7 import java.util.random.RandomGenerator;
8
9 import org.apache.commons.lang3.Validate;
10 import org.apache.logging.log4j.LogManager;
11 import org.apache.logging.log4j.Logger;
12
13 import net.bmahe.genetics4j.core.chromosomes.Chromosome;
14 import net.bmahe.genetics4j.core.mutation.chromosome.ChromosomeMutationHandler;
15 import net.bmahe.genetics4j.core.spec.chromosome.ChromosomeSpec;
16 import net.bmahe.genetics4j.core.spec.mutation.MutationPolicy;
17 import net.bmahe.genetics4j.neat.Connection;
18 import net.bmahe.genetics4j.neat.InnovationManager;
19 import net.bmahe.genetics4j.neat.chromosomes.NeatChromosome;
20 import net.bmahe.genetics4j.neat.spec.NeatChromosomeSpec;
21 import net.bmahe.genetics4j.neat.spec.mutation.AddConnection;
22
23 /**
24 * Chromosome mutation handler that adds new connections to NEAT (NeuroEvolution of Augmenting Topologies) neural
25 * networks.
26 *
27 * <p>NeatChromosomeAddConnection implements the add-connection structural mutation for NEAT chromosomes, which
28 * increases network connectivity by creating new weighted links between existing nodes. This mutation is essential for
29 * NEAT's ability to explore different network topologies and discover optimal connectivity patterns.
30 *
31 * <p>Add-connection mutation process:
32 * <ol>
33 * <li><strong>Node selection</strong>: Randomly select source and target nodes from all available nodes</li>
34 * <li><strong>Validity checking</strong>: Ensure the connection doesn't violate network constraints</li>
35 * <li><strong>Duplicate prevention</strong>: Verify the connection doesn't already exist</li>
36 * <li><strong>Innovation assignment</strong>: Assign unique innovation number via InnovationManager</li>
37 * <li><strong>Weight initialization</strong>: Set random weight within chromosome bounds</li>
38 * <li><strong>Connection creation</strong>: Add enabled connection to the chromosome</li>
39 * </ol>
40 *
41 * <p>Connection constraints:
42 * <ul>
43 * <li><strong>No self-connections</strong>: Source and target nodes must be different</li>
44 * <li><strong>No duplicate connections</strong>: Connection between same nodes cannot already exist</li>
45 * <li><strong>Feed-forward topology</strong>: Output nodes cannot be sources, input nodes cannot be targets</li>
46 * <li><strong>Valid node references</strong>: Both nodes must exist in the network</li>
47 * </ul>
48 *
49 * <p>Node selection strategy:
50 * <ul>
51 * <li><strong>Available nodes</strong>: All input, output, and hidden nodes are potential connection endpoints</li>
52 * <li><strong>Dynamic range</strong>: Node range adapts to include any hidden nodes created by add-node mutations</li>
53 * <li><strong>Uniform selection</strong>: All valid nodes have equal probability of being selected</li>
54 * <li><strong>Constraint filtering</strong>: Invalid connections are rejected and no mutation occurs</li>
55 * </ul>
56 *
57 * <p>Common usage patterns:
58 *
59 * <pre>{@code
60 * // Create add-connection mutation handler
61 * RandomGenerator randomGen = RandomGenerator.getDefault();
62 * InnovationManager innovationManager = new InnovationManager();
63 * NeatChromosomeAddConnection handler = new NeatChromosomeAddConnection(
64 * randomGen, innovationManager
65 * );
66 *
67 * // Check if handler can process mutation
68 * AddConnection mutationPolicy = AddConnection.of(0.1);
69 * NeatChromosomeSpec chromosomeSpec = NeatChromosomeSpec.of(3, 2, -1.0f, 1.0f);
70 * boolean canHandle = handler.canHandle(mutationPolicy, chromosomeSpec);
71 *
72 * // Apply mutation to chromosome
73 * NeatChromosome originalChromosome = // ... existing chromosome
74 * NeatChromosome mutatedChromosome = handler.mutate(mutationPolicy, originalChromosome);
75 *
76 * // Result: chromosome may have one additional connection (if valid connection found)
77 * }</pre>
78 *
79 * <p>Integration with NEAT algorithm:
80 * <ul>
81 * <li><strong>Innovation tracking</strong>: Uses InnovationManager for consistent innovation number assignment</li>
82 * <li><strong>Population consistency</strong>: Same connection types get same innovation numbers across population</li>
83 * <li><strong>Genetic alignment</strong>: Innovation numbers enable proper crossover alignment</li>
84 * <li><strong>Structural diversity</strong>: Increases topological diversity in the population</li>
85 * </ul>
86 *
87 * <p>Weight initialization:
88 * <ul>
89 * <li><strong>Random weights</strong>: New connections get random weights within chromosome bounds</li>
90 * <li><strong>Uniform distribution</strong>: Weights uniformly distributed between min and max values</li>
91 * <li><strong>Immediate activation</strong>: New connections are enabled and immediately affect network behavior</li>
92 * <li><strong>Bounded values</strong>: Weights respect chromosome's min/max weight constraints</li>
93 * </ul>
94 *
95 * <p>Performance considerations:
96 * <ul>
97 * <li><strong>Efficient validation</strong>: Fast checks for connection existence and validity</li>
98 * <li><strong>Innovation caching</strong>: Leverages InnovationManager's O(1) innovation lookup</li>
99 * <li><strong>Memory efficiency</strong>: Minimal allocation during mutation</li>
100 * <li><strong>Failed mutation handling</strong>: Gracefully handles cases where no valid connection can be added</li>
101 * </ul>
102 *
103 * @see AddConnection
104 * @see NeatChromosome
105 * @see InnovationManager
106 * @see ChromosomeMutationHandler
107 */
108 public class NeatChromosomeAddConnection implements ChromosomeMutationHandler<NeatChromosome> {
109
110 public static final Logger logger = LogManager.getLogger(NeatChromosomeAddConnection.class);
111
112 private final RandomGenerator randomGenerator;
113 private final InnovationManager innovationManager;
114
115 /**
116 * Constructs a new add-connection mutation handler with the specified components.
117 *
118 * <p>The random generator is used for node selection and weight initialization. The innovation manager provides
119 * unique innovation numbers for new connections, ensuring consistent tracking across the population.
120 *
121 * @param _randomGenerator random number generator for stochastic operations
122 * @param _innovationManager innovation manager for tracking structural changes
123 * @throws IllegalArgumentException if randomGenerator or innovationManager is null
124 */
125 public NeatChromosomeAddConnection(final RandomGenerator _randomGenerator,
126 final InnovationManager _innovationManager) {
127 Objects.requireNonNull(_randomGenerator);
128 Objects.requireNonNull(_innovationManager);
129
130 this.randomGenerator = _randomGenerator;
131 this.innovationManager = _innovationManager;
132 }
133
134 /**
135 * Determines whether this handler can process the given mutation policy and chromosome specification.
136 *
137 * <p>This handler specifically processes AddConnection mutations applied to NeatChromosomeSpec specifications,
138 * ensuring type compatibility for NEAT neural network connection addition.
139 *
140 * @param mutationPolicy the mutation policy to check
141 * @param chromosome the chromosome specification to check
142 * @return true if policy is AddConnection and chromosome is NeatChromosomeSpec, false otherwise
143 * @throws IllegalArgumentException if any parameter is null
144 */
145 @Override
146 public boolean canHandle(final MutationPolicy mutationPolicy, final ChromosomeSpec chromosome) {
147 Objects.requireNonNull(mutationPolicy);
148 Objects.requireNonNull(chromosome);
149
150 return mutationPolicy instanceof AddConnection && chromosome instanceof NeatChromosomeSpec;
151 }
152
153 /**
154 * Applies add-connection mutation to a NEAT chromosome.
155 *
156 * <p>This method attempts to add a new connection between two randomly selected nodes in the neural network. The
157 * mutation may fail if no valid connection can be found (e.g., all possible connections already exist or violate
158 * network constraints).
159 *
160 * <p>Mutation algorithm:
161 * <ol>
162 * <li>Determine the range of available nodes (inputs, outputs, and hidden nodes)</li>
163 * <li>Randomly select source and target nodes</li>
164 * <li>Validate the connection doesn't violate constraints</li>
165 * <li>If valid, create new connection with innovation number and random weight</li>
166 * <li>Add connection to chromosome and return modified chromosome</li>
167 * <li>If invalid, return chromosome unchanged</li>
168 * </ol>
169 *
170 * @param mutationPolicy the add-connection mutation policy
171 * @param chromosome the NEAT chromosome to mutate
172 * @return a new chromosome with potentially one additional connection
173 * @throws IllegalArgumentException if policy is not AddConnection or chromosome is not NeatChromosome
174 */
175 @Override
176 public NeatChromosome mutate(final MutationPolicy mutationPolicy, final Chromosome chromosome) {
177 Objects.requireNonNull(mutationPolicy);
178 Objects.requireNonNull(chromosome);
179 Validate.isInstanceOf(AddConnection.class, mutationPolicy);
180 Validate.isInstanceOf(NeatChromosome.class, chromosome);
181
182 final var addConnectionPolicy = (AddConnection) mutationPolicy;
183 final var neatChromosome = (NeatChromosome) chromosome;
184 final var nodeLayout = neatChromosome.getNodeLayout();
185 final var minValue = neatChromosome.getMinWeightValue();
186 final var maxValue = neatChromosome.getMaxWeightValue();
187
188 final var oldConnections = neatChromosome.getConnections();
189 final List<Connection> newConnections = new ArrayList<>(oldConnections);
190
191 final var nodeIds = new LinkedHashSet<Integer>();
192 nodeIds.addAll(nodeLayout.inputNodeIds());
193 nodeIds.addAll(nodeLayout.outputNodeIds());
194 for (final Connection connection : oldConnections) {
195 nodeIds.add(connection.fromNodeIndex());
196 nodeIds.add(connection.toNodeIndex());
197 }
198 final List<Integer> nodeIdList = List.copyOf(nodeIds);
199
200 final int fromNode = nodeIdList.get(randomGenerator.nextInt(nodeIdList.size()));
201 final int toNode = nodeIdList.get(randomGenerator.nextInt(nodeIdList.size()));
202
203 final boolean isConnectionExist = oldConnections.stream()
204 .anyMatch(connection -> connection.fromNodeIndex() == fromNode && connection.toNodeIndex() == toNode);
205
206 final boolean isFromNodeAnOutput = nodeLayout.isOutput(fromNode);
207 final boolean isToNodeAnInput = nodeLayout.isInput(toNode);
208 final boolean isOutputSourceAllowed = isFromNodeAnOutput == false
209 || addConnectionPolicy.allowOutputNodeAsSource() == true;
210
211 if (fromNode != toNode && isConnectionExist == false && isToNodeAnInput == false && isOutputSourceAllowed) {
212 final int innovation = innovationManager.computeNewId(fromNode, toNode);
213
214 final var newConnection = Connection.builder()
215 .fromNodeIndex(fromNode)
216 .toNodeIndex(toNode)
217 .innovation(innovation)
218 .weight(randomGenerator.nextFloat(minValue, maxValue))
219 .isEnabled(true)
220 .build();
221
222 newConnections.add(newConnection);
223 }
224
225 return new NeatChromosome(nodeLayout, minValue, maxValue, newConnections);
226 }
227 }