Алгоритм удаления сиротских нейронов из нейронной сети

Question

Я пытаюсь реализовать NEAT (Neuro Evolution of Augmenting Топология).

У меня есть список сетевых подключений, называемых «гены». Связь между нейроном1 и нейроном2 будет геном.от = нейрон1, ген.to = нейрон2.

Моя задача - генерировать нейронную сеть из этих генов (нейронная сеть - это просто карта от индекса к нейрону, ген.из и ген.to являются ключами к нейронам на карте).

У меня есть numPossibleInputs входных узлов, поэтому мы добавляем их первым (0-numPossibleInputs-1 являются входными нейронами).

У меня есть numOutputs выходных узлов, поэтому мы добавляем их также.

Затем мы сортируем наши гены на основе их индексов связи «до».

Наконец, мы создаем скрытые нейронные уровни на основе генов ... Поскольку нейронная сеть представляет собой карту, мы просто проверяем, является ли соединение или из соединения уже нейроном, иначе создайте новый. Этот алгоритм создает сети просто отлично.

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 ... всего один выход. Можно представить это следующим образом: [вход входа входа скрыт * 10 выхода * 1] 3 входов, 10 скрытых и 1 выход

Это изображение этой сети наивности генерироваться: Simple Network

Как мы можем видеть, что приведенная сеть не должна иметь 4 или 5 вообще, так как они не влияют ни на какие выходы (в этом случае только один выход, 13). Уменьшенная нейронная сеть будет только 0-> 13 и 1-> 13.

У меня были некоторые первоначальные мысли о том, как решить эту:

А. 1. Цикл по каждому соединению и хэширования gene.from идентификаторами. Это идентификаторы нейронов, которые являются вкладом в что-то еще. 2. После заполнения хэша снова запустите цикл и удалите любые гены с геном. Не находясь в хеше (ген.to не является чем-то другим, если он не находится в хеше). 3. Повторяйте, пока мы ничего не удалим

B. Создайте наивную сеть ... затем, сканируйте назад в сети, с каждого выхода, пока мы не сможем двигаться дальше (позаботьтесь о повторяющихся циклах) , Хешируйте каждый найденный узел. Как только наш график будет выполнен, сравните наш хэш узлов, найденных с полными узлами, выраженными в нашем списке генов. Используйте только гены с нейронами в хеше найденных узлов и переделывайте сеть.

Я надеялся получить некоторые отзывы о том, что может быть лучшим алгоритмом для этого, основанный на моем сетевом представлении. Я думаю, что мой B лучше, чем A, но я надеялся, что было более элегантное решение, которое не было 't привлечь меня разбора топологии графа. Возможно, что-то умное, что я могу сделать, сортируя соединения (By to by by from)?

Спасибо!

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 
} 

По моему профайлеру, подавляющее большинство времени проводили в этом аккуратном алгоритме в самой симуляции. То есть генерация правильной сети тривиальна по сравнению с тестированием сети против жесткой задачи.

Answer 2

Существует гораздо более эффективный способ добавления нейронов. Вместо того, чтобы просто добавлять новый нейрон и надеяться, что он будет подключен в один прекрасный день, вы также можете воспользоваться случайным соединением, разделить его на два соединения и добавить между ними нейрон.