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