1 package net.bmahe.genetics4j.neat.chromosomes; 2 3 import java.util.ArrayList; 4 import java.util.Collections; 5 import java.util.Comparator; 6 import java.util.List; 7 import java.util.Objects; 8 import java.util.Set; 9 import java.util.stream.Collectors; 10 import java.util.stream.IntStream; 11 12 import org.apache.commons.lang3.Validate; 13 14 import net.bmahe.genetics4j.core.chromosomes.Chromosome; 15 import net.bmahe.genetics4j.neat.Connection; 16 17 /** 18 * Represents a neural network chromosome in the NEAT (NeuroEvolution of Augmenting Topologies) algorithm. 19 * 20 * <p>NeatChromosome is the core genetic representation in NEAT, encoding a neural network as a collection of 21 * connections between nodes. Each chromosome defines a complete neural network topology with input nodes, output nodes, 22 * optional hidden nodes, and weighted connections. The chromosome maintains essential parameters for network 23 * construction and genetic operations. 24 * 25 * <p>Key characteristics: 26 * <ul> 27 * <li><strong>Network topology</strong>: Encoded as a list of connections with innovation numbers</li> 28 * <li><strong>Node organization</strong>: Fixed input/output nodes with dynamically added hidden nodes</li> 29 * <li><strong>Weight constraints</strong>: Configurable minimum and maximum weight bounds</li> 30 * <li><strong>Innovation tracking</strong>: Connections sorted by innovation number for genetic alignment</li> 31 * </ul> 32 * 33 * <p>NEAT algorithm integration: 34 * <ul> 35 * <li><strong>Structural mutations</strong>: Add/delete nodes and connections while preserving innovation tracking</li> 36 * <li><strong>Weight mutations</strong>: Modify connection weights within specified bounds</li> 37 * <li><strong>Genetic crossover</strong>: Innovation-number-based gene alignment for topology recombination</li> 38 * <li><strong>Compatibility distance</strong>: Genetic similarity measurement for speciation</li> 39 * </ul> 40 * 41 * <p>Network structure: 42 * <ul> 43 * <li><strong>Input nodes</strong>: Indices 0 to (numInputs - 1), receive external inputs</li> 44 * <li><strong>Output nodes</strong>: Indices numInputs to (numInputs + numOutputs - 1), produce network outputs</li> 45 * <li><strong>Hidden nodes</strong>: Indices starting from (numInputs + numOutputs), created by add-node mutations</li> 46 * <li><strong>Connections</strong>: Weighted links between nodes with enable/disable states and innovation numbers</li> 47 * </ul> 48 * 49 * <p>Common usage patterns: 50 * 51 * <pre>{@code 52 * // Create a basic NEAT chromosome 53 * List<Connection> connections = List.of(Connection.of(0, 2, 0.5f, true, 0), // input 0 -> output 0 54 * Connection.of(1, 3, -0.3f, true, 1) // input 1 -> output 1 55 * ); 56 * 57 * NeatChromosome chromosome = new NeatChromosome(2, // number of inputs 58 * 2, // number of outputs 59 * -1.0f, // minimum weight 60 * 1.0f, // maximum weight 61 * connections); 62 * 63 * // Access chromosome properties 64 * int numAlleles = chromosome.getNumAlleles(); 65 * Set<Integer> inputNodes = chromosome.getInputNodeIndices(); 66 * Set<Integer> outputNodes = chromosome.getOutputNodeIndices(); 67 * List<Connection> allConnections = chromosome.getConnections(); 68 * 69 * // Create feed-forward network for evaluation 70 * FeedForwardNetwork network = new FeedForwardNetwork(chromosome.getInputNodeIndices(), 71 * chromosome.getOutputNodeIndices(), 72 * chromosome.getConnections(), 73 * Activations::sigmoid); 74 * }</pre> 75 * 76 * <p>Genetic operations compatibility: 77 * <ul> 78 * <li><strong>Mutation operations</strong>: Compatible with weight, add-node, add-connection, and state mutations</li> 79 * <li><strong>Crossover operations</strong>: Innovation numbers enable proper gene alignment between parents</li> 80 * <li><strong>Selection operations</strong>: Supports species-based selection through compatibility distance</li> 81 * <li><strong>Evaluation operations</strong>: Can be converted to executable neural networks</li> 82 * </ul> 83 * 84 * <p>Innovation number organization: 85 * <ul> 86 * <li><strong>Sorted connections</strong>: Connections automatically sorted by innovation number</li> 87 * <li><strong>Genetic alignment</strong>: Enables efficient crossover and compatibility calculations</li> 88 * <li><strong>Historical tracking</strong>: Maintains evolutionary history of structural changes</li> 89 * <li><strong>Population consistency</strong>: Same innovation numbers across population for same connection types</li> 90 * </ul> 91 * 92 * <p>Performance considerations: 93 * <ul> 94 * <li><strong>Immutable connections</strong>: Connection list is sorted once and made immutable</li> 95 * <li><strong>Efficient lookup</strong>: Node indices computed deterministically for fast access</li> 96 * <li><strong>Memory efficiency</strong>: Only stores necessary network topology information</li> 97 * <li><strong>Cache-friendly</strong>: Sorted connections improve cache locality for genetic operations</li> 98 * </ul> 99 * 100 * <p>Integration with NEAT ecosystem: 101 * <ul> 102 * <li><strong>Chromosome factories</strong>: Created by NeatConnectedChromosomeFactory and similar</li> 103 * <li><strong>Genetic operators</strong>: Processed by NEAT-specific mutation and crossover handlers</li> 104 * <li><strong>Network evaluation</strong>: Converted to FeedForwardNetwork for fitness computation</li> 105 * <li><strong>Speciation</strong>: Used in compatibility distance calculations for species formation</li> 106 * </ul> 107 * 108 * @see Connection 109 * @see FeedForwardNetwork 110 * @see InnovationManager 111 * @see net.bmahe.genetics4j.neat.spec.NeatChromosomeSpec 112 */ 113 public class NeatChromosome implements Chromosome { 114 115 private final int numInputs; 116 private final int numOutputs; 117 private final float minWeightValue; 118 private final float maxWeightValue; 119 private final List<Connection> connections; 120 121 /** 122 * Constructs a new NEAT chromosome with the specified network topology and parameters. 123 * 124 * <p>This constructor creates an immutable neural network chromosome by copying and sorting the provided connections 125 * by their innovation numbers. The sorting ensures efficient genetic operations and proper gene alignment during 126 * crossover operations. 127 * 128 * <p>Network structure validation: 129 * <ul> 130 * <li>Input and output counts must be positive</li> 131 * <li>Weight bounds must be properly ordered (min < max)</li> 132 * <li>Connections list must not be null (but can be empty)</li> 133 * <li>Connection endpoints should reference valid nodes (not enforced here)</li> 134 * </ul> 135 * 136 * @param _numInputs number of input nodes in the network (must be positive) 137 * @param _numOutputs number of output nodes in the network (must be positive) 138 * @param _minWeightValue minimum allowed connection weight value 139 * @param _maxWeightValue maximum allowed connection weight value (must be > minWeightValue) 140 * @param _connections list of network connections (will be copied and sorted by innovation number) 141 * @throws IllegalArgumentException if numInputs <= 0, numOutputs <= 0, minWeightValue >= maxWeightValue, or 142 * connections is null 143 */ 144 public NeatChromosome(final int _numInputs, final int _numOutputs, final float _minWeightValue, 145 final float _maxWeightValue, final List<Connection> _connections) { 146 Validate.isTrue(_numInputs > 0); 147 Validate.isTrue(_numOutputs > 0); 148 Validate.isTrue(_minWeightValue < _maxWeightValue); 149 Validate.notNull(_connections); 150 151 this.numInputs = _numInputs; 152 this.numOutputs = _numOutputs; 153 this.minWeightValue = _minWeightValue; 154 this.maxWeightValue = _maxWeightValue; 155 156 final List<Connection> copyOfConnections = new ArrayList<>(_connections); 157 Collections.sort(copyOfConnections, Comparator.comparing(Connection::innovation)); 158 this.connections = Collections.unmodifiableList(copyOfConnections); 159 } 160 161 /** 162 * Returns the total number of alleles (genetic components) in this chromosome. 163 * 164 * <p>For NEAT chromosomes, the allele count includes: 165 * <ul> 166 * <li>Input nodes: Each input node represents one allele</li> 167 * <li>Output nodes: Each output node represents one allele</li> 168 * <li>Connections: Each connection (with its weight and state) represents one allele</li> 169 * </ul> 170 * 171 * <p>Hidden nodes are not counted separately as they are implicit in the connection structure. This count is used by 172 * the genetic algorithm framework for population statistics and compatibility calculations. 173 * 174 * @return the total number of alleles in this chromosome 175 */ 176 @Override 177 public int getNumAlleles() { 178 return numInputs + numOutputs + connections.size(); 179 } 180 181 /** 182 * Returns the number of input nodes in this neural network. 183 * 184 * <p>Input nodes are the entry points for external data into the network. They are assigned node indices from 0 to 185 * (numInputs - 1) and do not apply activation functions to their input values. 186 * 187 * @return the number of input nodes (always positive) 188 */ 189 public int getNumInputs() { 190 return numInputs; 191 } 192 193 /** 194 * Returns the number of output nodes in this neural network. 195 * 196 * <p>Output nodes produce the final results of network computation. They are assigned node indices from numInputs to 197 * (numInputs + numOutputs - 1) and apply activation functions to their weighted input sums. 198 * 199 * @return the number of output nodes (always positive) 200 */ 201 public int getNumOutputs() { 202 return numOutputs; 203 } 204 205 /** 206 * Returns the minimum allowed connection weight value for this network. 207 * 208 * <p>This bound is used by mutation operators to constrain weight perturbations and ensure that connection weights 209 * remain within reasonable ranges. Weight mutations should respect this bound to maintain network stability. 210 * 211 * @return the minimum allowed connection weight 212 */ 213 public float getMinWeightValue() { 214 return minWeightValue; 215 } 216 217 /** 218 * Returns the maximum allowed connection weight value for this network. 219 * 220 * <p>This bound is used by mutation operators to constrain weight perturbations and ensure that connection weights 221 * remain within reasonable ranges. Weight mutations should respect this bound to maintain network stability. 222 * 223 * @return the maximum allowed connection weight 224 */ 225 public float getMaxWeightValue() { 226 return maxWeightValue; 227 } 228 229 /** 230 * Returns an immutable list of all connections in this neural network. 231 * 232 * <p>The connections are sorted by innovation number to ensure consistent ordering for genetic operations. Each 233 * connection defines a weighted link between two nodes and includes an enabled/disabled state for topology 234 * exploration. 235 * 236 * <p>Connection properties: 237 * <ul> 238 * <li><strong>Immutable ordering</strong>: Connections are sorted by innovation number</li> 239 * <li><strong>Complete topology</strong>: Includes both enabled and disabled connections</li> 240 * <li><strong>Genetic information</strong>: Each connection carries innovation tracking data</li> 241 * <li><strong>Network structure</strong>: Defines the complete computational graph</li> 242 * </ul> 243 * 244 * @return immutable list of network connections, sorted by innovation number 245 */ 246 public List<Connection> getConnections() { 247 return connections; 248 } 249 250 /** 251 * Returns the set of input node indices for this neural network. 252 * 253 * <p>Input node indices are deterministically assigned as consecutive integers starting from 0. Input nodes receive 254 * external data and do not apply activation functions to their values. These indices are used for network 255 * construction and evaluation. 256 * 257 * <p>Index assignment: 258 * <ul> 259 * <li><strong>Range</strong>: 0 to (numInputs - 1)</li> 260 * <li><strong>Fixed assignment</strong>: Input indices never change during evolution</li> 261 * <li><strong>External interface</strong>: These indices map to external input data</li> 262 * <li><strong>No activation</strong>: Input nodes pass through their values unchanged</li> 263 * </ul> 264 * 265 * @return set of input node indices (0 to numInputs-1) 266 */ 267 public Set<Integer> getInputNodeIndices() { 268 return IntStream.range(0, numInputs) 269 .boxed() 270 .collect(Collectors.toSet()); 271 } 272 273 /** 274 * Returns the set of output node indices for this neural network. 275 * 276 * <p>Output node indices are deterministically assigned as consecutive integers starting immediately after the input 277 * nodes. Output nodes apply activation functions to their weighted input sums and produce the final network results. 278 * 279 * <p>Index assignment: 280 * <ul> 281 * <li><strong>Range</strong>: numInputs to (numInputs + numOutputs - 1)</li> 282 * <li><strong>Fixed assignment</strong>: Output indices never change during evolution</li> 283 * <li><strong>Network results</strong>: These nodes produce the final computational output</li> 284 * <li><strong>Activation applied</strong>: Output nodes apply activation functions to their sums</li> 285 * </ul> 286 * 287 * @return set of output node indices (numInputs to numInputs+numOutputs-1) 288 */ 289 public Set<Integer> getOutputNodeIndices() { 290 return IntStream.range(numInputs, getNumInputs() + getNumOutputs()) 291 .boxed() 292 .collect(Collectors.toSet()); 293 } 294 295 @Override 296 public int hashCode() { 297 return Objects.hash(connections, maxWeightValue, minWeightValue, numInputs, numOutputs); 298 } 299 300 @Override 301 public boolean equals(Object obj) { 302 if (this == obj) 303 return true; 304 if (obj == null) 305 return false; 306 if (getClass() != obj.getClass()) 307 return false; 308 NeatChromosome other = (NeatChromosome) obj; 309 return Objects.equals(connections, other.connections) 310 && Float.floatToIntBits(maxWeightValue) == Float.floatToIntBits(other.maxWeightValue) 311 && Float.floatToIntBits(minWeightValue) == Float.floatToIntBits(other.minWeightValue) 312 && numInputs == other.numInputs && numOutputs == other.numOutputs; 313 } 314 315 @Override 316 public String toString() { 317 return "NeatChromosome [numInputs=" + numInputs + ", numOutputs=" + numOutputs + ", minWeightValue=" 318 + minWeightValue + ", maxWeightValue=" + maxWeightValue + ", connections=" + connections + "]"; 319 } 320 }