关于在JavaScript中原型实现NEAT的若干技术问题

Hey there! Awesome that you're digging into implementing NEAT in JavaScript—Kenneth O. Stanley's original paper is a classic, so kudos for taking on this hands-on project. Let's break down your questions about structural innovation and how to track it properly.

In NEAT, structural innovation refers to any change that alters the topology of a neural network genome—meaning it's not just tweaking weight values (that's parametric evolution), but actually adding new components to the network. There are two core types of structural innovations NEAT uses:

• Adding a new connection: Creating a directed link between two nodes that didn't have one before.
• Adding a new node: Splitting an existing connection into two links, with a new node inserted between them (the original connection's weight is transferred to one of the new links, and the other starts with a default weight like 1.0).

The key here is that these are new, previously unseen topological changes. NEAT's whole schtick is that it starts with tiny, simple networks and grows complexity over time via these innovations—so tracking them correctly is critical to avoiding redundant work and ensuring evolutionary progress.

NEAT solves this with a global innovation history paired with unique innovation IDs—this is one of the paper's core contributions. Here's how it works, and how to implement it in JavaScript:

1. Maintain a Global Innovation Registry #

You need a persistent, global store (not just per-generation) that records every unique structural innovation that's ever occurred during evolution. Each entry should capture enough info to identify a duplicate innovation later.

2. Assign Unique IDs to Each Innovation #

For each potential structural change, check if it's already in the registry:

• For new connections: When trying to add a link from node A to node B (direction matters—A→B is different from B→A), look up if this exact node pair exists in your registry. If it does, reuse the existing innovation ID. If not, create a new unique ID, add the pair to the registry, and assign this ID to the new connection gene.
• For new nodes: When splitting an existing connection between A and B, check if this specific split (same source and target nodes) has been done before. If yes, reuse the innovation ID for the new node. If not, create a new ID, log the split in the registry, and assign this ID to the new node gene.

3. JavaScript Implementation Example #

Here's a simple, practical way to set this up with Maps for fast lookups:

// Global state for innovation tracking
const innovationRegistry = new Map();
let nextInnovationId = 0;

// Check for existing connection innovation, or create a new one
function getConnectionInnovationId(sourceNodeId, targetNodeId) {
  // Use a unique key for the directed node pair
  const key = `conn-${sourceNodeId}-${targetNodeId}`;
  if (innovationRegistry.has(key)) {
    return innovationRegistry.get(key);
  }
  // New innovation: assign ID and register it
  nextInnovationId++;
  innovationRegistry.set(key, nextInnovationId);
  return nextInnovationId;
}

// Check for existing node split innovation, or create a new one
function getNodeInnovationId(sourceNodeId, targetNodeId) {
  // Key identifies splitting the edge between source and target
  const key = `node-split-${sourceNodeId}-${targetNodeId}`;
  if (innovationRegistry.has(key)) {
    return innovationRegistry.get(key);
  }
  nextInnovationId++;
  innovationRegistry.set(key, nextInnovationId);
  return nextInnovationId;
}

4. Why Not Just Track Per-Generation Innovations? #

You mentioned recording innovations per generation, but NEAT relies on a global history because the same structural change can pop up independently in different generations or different genomes. Using a global ID ensures that identical innovations get the same ID across the entire evolution. This is crucial for:

• Species formation: NEAT groups genomes into species based on compatibility, which uses innovation IDs to count how many structural differences exist between genomes.
• Crossover: When breeding genomes, innovation IDs let NEAT match up homologous genes (same structural innovation) from parent genomes, ensuring proper recombination of beneficial traits.

• Structural innovation: Any topological change (new connection or node) that modifies the network's structure (not just weights).
• Tracking: Use a global registry to log every unique innovation with a persistent ID. Check this registry before creating a new structure to avoid duplicate IDs.

内容的提问来源于stack exchange，提问作者Nigk