从神经网络中移除孤儿神经元的算法

Question

我正在尝试实现 NEAT(增强拓扑的神经进化)。

我有一个网络连接列表，称为“基因”。 neuron1 和 neuron2 之间的连接是 gene.from = neuron1, gene.to = neuron2。

我的任务是从这些基因生成一个神经网络(神经网络只是一个从索引到神经元的映射，gene.from 和 gene.to 是映射中神经元的键)。

我有 numPossibleInputs 个输入节点，因此我们首先添加这些节点(0-numPossibleInputs-1 是输入神经元)。

我有 numOutputs 个输出节点，所以我们也添加它们。

然后，我们根据“到”连接索引对基因进行排序。

最后，我们根据基因创建隐藏层神经元...由于神经网络是一张 map ，我们只需检查连接的起点或起点是否已经是一个神经元，否则就创建一个新的神经元。该算法可以很好地创建网络。

 public void generateNetwork()
{
    neuralNetwork.clear();

    for(int i = 0; i < numPossibleInputs; i++)
    {
        neuralNetwork.put(i, new Neuron());
    }

    for(int i = 0; i < numOutputs; i++)
    {
        neuralNetwork.put(i+numPossibleInputs+numPossibleHidden, new Neuron());
    }

    genes.sort((ConnectionGene g1, ConnectionGene g2)-> Integer.compare(g1.toNeuronIndex, g2.toNeuronIndex));

    for(ConnectionGene gene : getCleanGenes(genes))
    {
        if(gene.enabled)
        {
            if(!neuralNetwork.containsKey(gene.toNeuronIndex))
            {
                neuralNetwork.put(gene.toNeuronIndex, new Neuron());
            }
            neuralNetwork.get(gene.toNeuronIndex).incomingConnections.add(gene); // Add this gene to the incoming of the above neuron

            if(!neuralNetwork.containsKey(gene.fromNeuronIndex))
            {
                neuralNetwork.put(gene.fromNeuronIndex, new Neuron());
            }
        }
    }

}

当进化算法“关闭”某些基因(注意 gene.enabled)时，问题就来了。例如，考虑以下基因(还有其他基因，但它们被禁用):

2->4

4->4

13->4

0->13

1->13

5->13

我们也有禁用基因，2->5 和 4->13。这些不能在网络中使用，因为它们没有被表达。 (这就是为什么我必须每一代都生成一个新网络，可以添加、启用、禁用等基因)。

这适用于 numPossibleInputs ==3，因此 0 1 和 2 是输入(2 是偏差)。 5 是一个隐藏层节点，因为 5 > 3，但小于 10 + 3 = 13。13 是一个输出节点，我有 numPossibleHidden == 10 所以 10 + 3 = 13...只有一个输出。可以这样画:[input input input hidden*10 output*1] for 3 inputs, 10 hidden, and 1 output

这是该网络天真生成的图片: Simple Network

正如我们所见，简化后的网络根本不应该有 4 或 5 个，因为它们对任何输出都没有影响(在本例中只有一个输出，13)。简化的神经网络只是 0->13 和 1->13。

我对如何解决这个问题有一些初步想法:

一个。 1. 遍历每个连接并对 gene.from ids 进行哈希处理。这些是神经元 ID，它们是其他东西的输入 2. 填充散列后，再次循环并删除任何具有 gene.to 的基因不在散列中(如果 gene.to 不在散列中，则它不是任何其他内容的输入)。 3. 重复直到我们不删除任何东西

B.生成原始网络...然后，在网络中向后爬行，从每个输出开始，直到我们不能再继续(注意循环)。散列我们找到的每个节点。一旦我们的图形搜索完成，将我们找到的节点散列与我们基因列表中表达的总节点进行比较。仅在找到的节点的散列中使用带有神经元的基因并重新构建网络。

我希望就什么可能是基于我的网络表示来执行此操作的最佳算法获得一些反馈——我认为我的 B 比 A 更好，但我希望有一个更优雅的解决方案不涉及我解析图拓扑。也许我可以通过对连接进行排序(按到、按从)来做一些聪明的事情？

谢谢!

Answer 1

我使用了上面的 B 解决方案，使用各种不同的网络类型对其进行了测试，它工作正常 - 也就是说，网络将摆脱所有没有从输入到输出的正确路径的节点。我会在这里发布代码以防有人想使用它:

   private List<ConnectionGene> cleanGenes(Map<Integer,Neuron> network)
{
    // For each output, go backwards
    Set<Integer> visited = new HashSet();
    for(int i = 0; i < numOutputs; i++)
    {
        visited.add(i+numPossibleInputs+numPossibleHidden);
        cleanGenes(i+numPossibleInputs+numPossibleHidden, network, visited);
    }

    List<ConnectionGene> slimGenes = new ArrayList();
    for(ConnectionGene gene : genes)
    {
        // Only keep gene if from/to are nodes we visited
        if(visited.contains(gene.fromNeuronIndex) && visited.contains(gene.toNeuronIndex))
        {
            slimGenes.add(gene);
        }
    }
    return slimGenes;
}

private boolean cleanGenes(int neuronIndex, Map<Integer, Neuron> network, Set<Integer> visited)
{
    int numGoodConnections = 0;
    for(ConnectionGene gene : network.get(neuronIndex).incomingConnections)
    {
        numGoodConnections++;
        if(gene.enabled && !visited.contains(gene.fromNeuronIndex))
        {
            visited.add(gene.fromNeuronIndex);
            if(!cleanGenes(gene.fromNeuronIndex, network, visited))
            {
                numGoodConnections--;
                visited.remove(gene.fromNeuronIndex); // We don't want this node in visited, it has no incoming connections and isn't an input.
            }
        }
    }

    if(numGoodConnections == 0)
    {
        return neuronIndex < numPossibleInputs; // True if an input neuron, false if no incoming connections and not input
    }
    return true; // Success
}

根据我的分析器，花在这个 NEAT 算法上的绝大部分时间都花在了模拟本身上。也就是说，与针对艰巨任务测试网络相比，生成适当的网络是微不足道的。