1 package net.bmahe.genetics4j.neat;
2
3 import java.util.concurrent.ConcurrentHashMap;
4 import java.util.concurrent.atomic.AtomicInteger;
5
6 import org.apache.commons.lang3.Validate;
7 import org.apache.logging.log4j.LogManager;
8 import org.apache.logging.log4j.Logger;
9
10 /**
11 * Manages innovation numbers for the NEAT (NeuroEvolution of Augmenting Topologies) algorithm.
12 *
13 * <p>The InnovationManager is a critical component of the NEAT algorithm that tracks structural innovations in neural
14 * networks through unique innovation numbers. This system enables NEAT to perform meaningful genetic crossover between
15 * neural networks with different topologies while preserving historical information about when specific connections
16 * were first added to the population.
17 *
18 * <p>Key responsibilities:
19 * <ul>
20 * <li><strong>Innovation tracking</strong>: Assigns unique numbers to each new connection type (from-to node pair)</li>
21 * <li><strong>Historical marking</strong>: Maintains consistent innovation numbers across the population</li>
22 * <li><strong>Crossover support</strong>: Enables alignment of neural network structures during recombination</li>
23 * <li><strong>Cache management</strong>: Provides efficient lookup and generation of innovation numbers</li>
24 * </ul>
25 *
26 * <p>NEAT innovation number system:
27 * <ul>
28 * <li><strong>Unique identification</strong>: Each unique connection (from-node → to-node) gets one innovation
29 * number</li>
30 * <li><strong>Population consistency</strong>: Same connection type across individuals gets same innovation number</li>
31 * <li><strong>Temporal ordering</strong>: Innovation numbers reflect the historical order of structural mutations</li>
32 * <li><strong>Crossover alignment</strong>: Enables gene alignment during genetic recombination</li>
33 * </ul>
34 *
35 * <p>Innovation number workflow:
36 * <ol>
37 * <li><strong>Mutation occurs</strong>: Add-connection mutation creates new connection type</li>
38 * <li><strong>Innovation check</strong>: Manager checks if this connection type was seen before</li>
39 * <li><strong>Number assignment</strong>: New types get new innovation numbers, existing types reuse numbers</li>
40 * <li><strong>Population tracking</strong>: All individuals with same connection type share same innovation number</li>
41 * <li><strong>Crossover alignment</strong>: Innovation numbers enable proper gene alignment during recombination</li>
42 * </ol>
43 *
44 * <p>Common usage patterns:
45 *
46 * <pre>{@code
47 * // Create innovation manager for new evolution run
48 * InnovationManager innovationManager = new InnovationManager();
49 *
50 * // During add-connection mutation
51 * int fromNode = 0, toNode = 3;
52 * int innovationNumber = innovationManager.computeNewId(fromNode, toNode);
53 * Connection newConnection = Connection.of(fromNode, toNode, weight, innovationNumber, true);
54 *
55 * // Reset cache between generations if needed
56 * innovationManager.resetCache();
57 *
58 * // Start with specific innovation number
59 * InnovationManager manager = new InnovationManager(1000);
60 * }</pre>
61 *
62 * <p>Cache management strategy:
63 * <ul>
64 * <li><strong>Per-generation caching</strong>: Cache innovation numbers within each generation</li>
65 * <li><strong>Cross-generation persistence</strong>: Innovation numbers remain consistent across generations</li>
66 * <li><strong>Memory management</strong>: Reset cache periodically to prevent memory growth</li>
67 * <li><strong>Concurrent access</strong>: Thread-safe operations for parallel genetic operations</li>
68 * </ul>
69 *
70 * <p>Performance considerations:
71 * <ul>
72 * <li><strong>O(1) lookup</strong>: Fast innovation number retrieval through hash map caching</li>
73 * <li><strong>Memory efficiency</strong>: Cache only unique connection types seen in current generation</li>
74 * <li><strong>Thread safety</strong>: Concurrent operations supported for parallel evolution</li>
75 * <li><strong>Cache lifecycle</strong>: Reset cache between evolution runs to prevent memory leaks</li>
76 * </ul>
77 *
78 * <p>Integration with NEAT algorithm:
79 * <ul>
80 * <li><strong>Structural mutations</strong>: Add-connection mutations use innovation manager</li>
81 * <li><strong>Genetic crossover</strong>: Innovation numbers enable gene alignment</li>
82 * <li><strong>Compatibility distance</strong>: Innovation numbers used to identify matching, excess, and disjoint
83 * genes</li>
84 * <li><strong>Population management</strong>: Shared innovation manager across entire population</li>
85 * </ul>
86 *
87 * @see Connection
88 * @see ConnectionPair
89 * @see NeatChromosome
90 * @see net.bmahe.genetics4j.neat.mutation.AddConnectionPolicyHandler
91 */
92 public class InnovationManager {
93 public static final Logger logger = LogManager.getLogger(InnovationManager.class);
94
95 public static final int DEFAULT_INITIAL_ID = 0;
96
97 private final AtomicInteger currentId;
98
99 private final ConcurrentHashMap<ConnectionPair, Integer> innovationCache = new ConcurrentHashMap<>();
100
101 /**
102 * Constructs an innovation manager with the specified initial innovation number.
103 *
104 * @param initialValue the starting innovation number for new innovations
105 */
106 public InnovationManager(final int initialValue) {
107 currentId = new AtomicInteger(initialValue);
108 }
109
110 /**
111 * Constructs an innovation manager with the default initial innovation number (0).
112 */
113 public InnovationManager() {
114 this(DEFAULT_INITIAL_ID);
115 }
116
117 /**
118 * Computes or retrieves the innovation number for a connection between two nodes.
119 *
120 * <p>If this connection type (from-node → to-node) has been seen before, returns the existing innovation number from
121 * the cache. Otherwise, generates a new innovation number and caches it for future use. This ensures that the same
122 * connection type across different individuals in the population receives the same innovation number.
123 *
124 * @param from the source node index of the connection
125 * @param to the target node index of the connection
126 * @return the innovation number for this connection type
127 * @throws IllegalArgumentException if from equals to (self-connections not allowed)
128 */
129 public int computeNewId(final int from, final int to) {
130 Validate.isTrue(from != to);
131
132 final var connectionPair = new ConnectionPair(from, to);
133 return innovationCache.computeIfAbsent(connectionPair, k -> currentId.getAndIncrement());
134 }
135
136 /**
137 * Resets the innovation cache, clearing all cached connection-to-innovation-number mappings.
138 *
139 * <p>This method should be called between evolution runs or generations to prevent memory growth and ensure that
140 * innovation number assignment starts fresh. Note that this does not reset the current innovation number counter, so
141 * new innovations will continue to receive unique numbers.
142 */
143 public void resetCache() {
144 logger.trace("Resetting cache with currently {} entries", innovationCache.size());
145 innovationCache.clear();
146 }
147 }