1 package net.bmahe.genetics4j.neat;
2
3 import java.util.HashMap;
4 import java.util.List;
5 import java.util.Map;
6 import java.util.Objects;
7 import java.util.Set;
8 import java.util.function.Function;
9
10 import org.apache.commons.collections4.CollectionUtils;
11 import org.apache.commons.lang3.Validate;
12 import org.apache.logging.log4j.LogManager;
13 import org.apache.logging.log4j.Logger;
14
15 /**
16 * Implements a feed-forward neural network for evaluating NEAT (NeuroEvolution of Augmenting Topologies) chromosomes.
17 *
18 * <p>FeedForwardNetwork provides a computational engine for executing neural networks evolved by the NEAT algorithm. It
19 * takes a network topology defined by connections and nodes, organizes them into computational layers, and provides
20 * efficient forward propagation for fitness evaluation. The network supports arbitrary topologies with variable numbers
21 * of hidden layers and connections, as long as the resulting graph remains acyclic. For chromosomes that contain
22 * recurrent connections, use {@link RecurrentNetwork}.
23 *
24 * <p>Key features:
25 * <ul>
26 * <li><strong>Dynamic topology</strong>: Supports arbitrary network structures evolved by NEAT</li>
27 * <li><strong>Layer-based evaluation</strong>: Automatically computes optimal evaluation order</li>
28 * <li><strong>Configurable activation</strong>: Supports any activation function for hidden and output nodes</li>
29 * <li><strong>Efficient propagation</strong>: Optimized forward pass through network layers</li>
30 * </ul>
31 *
32 * <p>Network evaluation process:
33 * <ol>
34 * <li><strong>Input assignment</strong>: Input values are assigned to input nodes</li>
35 * <li><strong>Layer computation</strong>: Each layer is computed in topological order</li>
36 * <li><strong>Node activation</strong>: Each node applies weighted sum followed by activation function</li>
37 * <li><strong>Output extraction</strong>: Output values are collected from designated output nodes</li>
38 * </ol>
39 *
40 * <p>Network construction workflow:
41 * <ul>
42 * <li><strong>Topology analysis</strong>: Network connections are analyzed to determine layer structure</li>
43 * <li><strong>Layer partitioning</strong>: Nodes are organized into evaluation layers using topological sorting</li>
44 * <li><strong>Connection mapping</strong>: Backward connections are precomputed for efficient evaluation</li>
45 * <li><strong>Dead node removal</strong>: Unreachable nodes are excluded from computation</li>
46 * </ul>
47 *
48 * <p>Common usage patterns:
49 *
50 * <pre>{@code
51 * // Create network from NEAT chromosome
52 * NeatChromosome chromosome = // ... obtain from evolution
53 * Set<Integer> inputNodes = Set.of(0, 1, 2);
54 * Set<Integer> outputNodes = Set.of(3, 4);
55 * Function<Float, Float> activation = Activations::sigmoid;
56 *
57 * FeedForwardNetwork network = new FeedForwardNetwork(
58 * inputNodes, outputNodes, chromosome.getConnections(), activation
59 * );
60 *
61 * // Evaluate network on input data
62 * Map<Integer, Float> inputs = Map.of(0, 1.0f, 1, 0.5f, 2, -0.3f);
63 * Map<Integer, Float> outputs = network.compute(inputs);
64 *
65 * // Extract specific outputs
66 * float output1 = outputs.get(3);
67 * float output2 = outputs.get(4);
68 * }</pre>
69 *
70 * <p>Activation function integration:
71 * <ul>
72 * <li><strong>Sigmoid activation</strong>: Standard logistic function for binary classification</li>
73 * <li><strong>Tanh activation</strong>: Hyperbolic tangent for continuous outputs</li>
74 * <li><strong>Linear activation</strong>: Identity function for regression problems</li>
75 * <li><strong>Custom functions</strong>: Any Function<Float, Float> can be used</li>
76 * </ul>
77 *
78 * <p>Performance optimizations:
79 * <ul>
80 * <li><strong>Layer precomputation</strong>: Network layers are computed once during construction</li>
81 * <li><strong>Connection mapping</strong>: Backward connections are precomputed for fast lookup</li>
82 * <li><strong>Dead node elimination</strong>: Unreachable nodes are excluded from evaluation</li>
83 * <li><strong>Efficient propagation</strong>: Only enabled connections participate in computation</li>
84 * </ul>
85 *
86 * <p>Error handling and validation:
87 * <ul>
88 * <li><strong>Input validation</strong>: Ensures all input nodes receive values</li>
89 * <li><strong>Output validation</strong>: Verifies all output nodes produce values</li>
90 * <li><strong>Topology validation</strong>: Validates network structure during construction</li>
91 * <li><strong>Connection consistency</strong>: Ensures connection endpoints reference valid nodes</li>
92 * </ul>
93 *
94 * <p>Integration with NEAT evolution:
95 * <ul>
96 * <li><strong>Chromosome evaluation</strong>: Converts NEAT chromosomes to executable networks</li>
97 * <li><strong>Fitness computation</strong>: Provides network output for fitness evaluation</li>
98 * <li><strong>Topology evolution</strong>: Supports networks with varying structure complexity</li>
99 * <li><strong>Innovation tracking</strong>: Works with networks containing historical innovations</li>
100 * </ul>
101 *
102 * @see NeatChromosome
103 * @see Connection
104 * @see Activations
105 * @see NeatUtils#partitionLayersNodes
106 */
107 public class FeedForwardNetwork {
108 public static final Logger logger = LogManager.getLogger(FeedForwardNetwork.class);
109
110 private final Set<Integer> inputNodeIndices;
111 private final Set<Integer> outputNodeIndices;
112 private final List<Connection> connections;
113
114 private final List<List<Integer>> layers;
115 private final Map<Integer, Set<Connection>> backwardConnections;
116
117 private final Function<Float, Float> activationFunction;
118
119 /**
120 * Constructs a new feed-forward network with the specified topology and activation function.
121 *
122 * <p>The constructor analyzes the network topology, computes evaluation layers using topological sorting, and
123 * precomputes connection mappings for efficient forward propagation. The network is immediately ready for evaluation
124 * after construction.
125 *
126 * @param _inputNodeIndices set of input node indices
127 * @param _outputNodeIndices set of output node indices
128 * @param _connections list of network connections defining the topology
129 * @param _activationFunction activation function to apply to hidden and output nodes
130 * @throws IllegalArgumentException if any parameter is null or empty
131 */
132 public FeedForwardNetwork(final Set<Integer> _inputNodeIndices,
133 final Set<Integer> _outputNodeIndices,
134 final List<Connection> _connections,
135 final Function<Float, Float> _activationFunction) {
136 Validate.isTrue(CollectionUtils.isNotEmpty(_inputNodeIndices));
137 Validate.isTrue(CollectionUtils.isNotEmpty(_outputNodeIndices));
138 Validate.isTrue(CollectionUtils.isNotEmpty(_connections));
139 Objects.requireNonNull(_activationFunction);
140
141 this.inputNodeIndices = _inputNodeIndices;
142 this.outputNodeIndices = _outputNodeIndices;
143 this.connections = _connections;
144 this.activationFunction = _activationFunction;
145
146 this.layers = NeatUtils.partitionLayersNodes(this.inputNodeIndices, this.outputNodeIndices, this.connections);
147 this.backwardConnections = NeatUtils.computeBackwardConnections(this.connections);
148 }
149
150 /**
151 * Computes the network output for the given input values.
152 *
153 * <p>This method performs forward propagation through the network, computing node activations layer by layer in
154 * topological order. Input values are assigned to input nodes, then each subsequent layer is computed by applying
155 * weighted sums and activation functions.
156 *
157 * <p>The computation process:
158 * <ol>
159 * <li>Input values are assigned to input nodes</li>
160 * <li>For each layer (starting from first hidden layer):</li>
161 * <li>For each node in the layer:</li>
162 * <li>Compute weighted sum of inputs from previous layers</li>
163 * <li>Apply activation function to the sum</li>
164 * <li>Store the result for use in subsequent layers</li>
165 * <li>Extract and return output values from output nodes</li>
166 * </ol>
167 *
168 * @param inputValues mapping from input node indices to their values
169 * @return mapping from output node indices to their computed values
170 * @throws IllegalArgumentException if inputValues is null, has wrong size, or missing required inputs
171 */
172 public Map<Integer, Float> compute(final Map<Integer, Float> inputValues) {
173 Objects.requireNonNull(inputValues);
174 Validate.isTrue(inputValues.size() == inputNodeIndices.size());
175
176 final Map<Integer, Float> nodeValues = new HashMap<>();
177
178 for (final Integer inputNodeIndex : inputNodeIndices) {
179 Float nodeValue = inputValues.get(inputNodeIndex);
180 if (nodeValue == null) {
181 throw new IllegalArgumentException("Input vector missing values for input node " + inputNodeIndex);
182 }
183 nodeValues.put(inputNodeIndex, nodeValue);
184 }
185
186 int layerIndex = 1;
187 while (layerIndex < layers.size()) {
188
189 final List<Integer> layer = layers.get(layerIndex);
190
191 if (CollectionUtils.isNotEmpty(layer)) {
192
193 for (Integer nodeIndex : layer) {
194 float sum = 0.0F;
195 final var incomingNodes = backwardConnections.getOrDefault(nodeIndex, Set.of());
196 for (final Connection incomingConnection : incomingNodes) {
197 if (incomingConnection.toNodeIndex() != nodeIndex) {
198 throw new IllegalStateException();
199 }
200
201 // Incoming connection may have been disabled and dangling
202 if (nodeValues.containsKey(incomingConnection.fromNodeIndex())) {
203 final float weight = incomingConnection.weight();
204 final float incomingNodeValue = nodeValues.get(incomingConnection.fromNodeIndex());
205
206 sum += weight * incomingNodeValue;
207 }
208 }
209 final Float outputValue = activationFunction.apply(sum);
210 nodeValues.put(nodeIndex, outputValue);
211 }
212 }
213
214 layerIndex++;
215 }
216
217 final Map<Integer, Float> outputValues = new HashMap<>();
218 for (final Integer outputNodeIndex : outputNodeIndices) {
219 final Float value = nodeValues.get(outputNodeIndex);
220 if (value == null) {
221 throw new IllegalArgumentException("Missing output value for node " + outputNodeIndex);
222 }
223 outputValues.put(outputNodeIndex, value);
224 }
225 return outputValues;
226 }
227 }