Genetische Programmierung Stackoverflow Fehler

Question

Mein Code scheint unendliche Rekursion zu tun, wenn ich es mit Bäumen einer größeren Tiefe aufrufen. Ich habe versucht, es ohne Rekursion zu tun, und gut das ist irgendwie schwierig zu tun, da ich den Baum selbst manipulieren muss, sowieso hier ist m Code. Dank

Problem ist mit dem printPostOrder Verfahren, um es zu einem Blattknoten und das geht hin und her Druck, dass Blattknoten und deren Mutter bis der Stapel überläuft

Ich würde eher poste ich meinen vollen Code so wird, dass Sie können bekommen, was ich versuche.

Node Insertion ist wie dieser

import java.util.*; 

public class IPG { 

    class Node { 

     private int arity; 
     private String label; 
     private int value; 
     private Node[] children; 
     protected int visit = 0; 
     protected boolean isVisited = false; 

     public Node(int arity, String label) { 
      this.arity = arity; 
      this.label = label; 
      this.children = new Node[3]; 
     } 

     public Node(Node another) { 
      this.label = another.label; 
      this.arity = another.arity; 
     } 

     @Override 
     public String toString() { 
      return label; 
     } 

     String getLabel() { 
      return label; 
     } 

     void insertChild(int pos, Node n) { 
      if (pos < arity) { 
       children[pos] = n; 
      } 
     } 

     Node getChildAt(int i) { 
      return children[i]; 
     } 

     void setValue(int value) { 
      this.value = value; 
     } 

     int getArity() { 
      return arity; 
     } 

     void replace(Node another) { 
      this.arity = another.arity; 
      this.children = another.children; 
      this.label = another.label; 
     } 

    } 

    private Node[] functions = { new Node(2, "AND"), new Node(2, "OR"), 
      new Node(1, "NOT"), new Node(3, "IF") }; 

    private Node[] terminals = { new Node(0, "A0"), new Node(0, "D1"), 
      new Node(0, "D0"), new Node(0, "A1"), new Node(0, "D2"), 
      new Node(0, "D3"), new Node(0, "A2"), new Node(0, "D4"), 
      new Node(0, "D5"), new Node(0, "D6"), new Node(0, "D7") }; 

    private Random random = new Random(); 

    private int multiplexerType = 3; 

    public Node getTerminal() { 
     return terminals[random.nextInt(multiplexerType)]; 
    } 

    public Node getFunction() { 

     return functions[random.nextInt(3)]; 
    } 

    public Node getAnyNode() { 
     return random.nextInt(2) == 1 ? getFunction() : getTerminal(); 
    } 

    public Node generateGrow(int depth) { 
     Node root; 

     if (depth > 1) 
      root = getAnyNode(); 

     else 
      root = getTerminal(); 

     for (int i = 0; i < root.getArity(); i++) 
      root.insertChild(i, generateGrow(depth - 1)); 

     return root; 
    } 

    public Node generateFull(int depth) { 
     Node root; 

     if (depth > 1) 
      root = getFunction(); 

     else 
      root = getTerminal(); 

     for (int i = 0; i < root.getArity(); i++) 
      root.insertChild(i, generateFull(depth - 1)); 

     return root; 
    } 

    public void printPostOrder() { 
     Node root = generateFull(3); 
     printPostOrder(root); 
    } 

    private void printPostOrder(Node n) { 
     if (n == null) { 
      return; 
     } else { 
      System.out.println(n + " "); 

      printPostOrder(n.children[0]); 
      printPostOrder(n.children[1]); 
      printPostOrder(n.children[2]); 
     } 
    } 

    public static void main(String[] args) { 
     new IPG().printPostOrder(); 
    } 
} 

Answer 1

Das Problem ist, dass wenn Sie Ihre functions Array generieren, Sie nur einen Knoten jedes Typs erstellen, und dann getFunction() wiederverwendet diese gleichen Knoten. Wenn Sie beispielsweise einen "AND" -Knoten einfügen und dessen Kind auch ein "AND" -Knoten ist, wird ein Zyklus erstellt, da sie tatsächlich das gleiche Objekt sind.

Es ist eine einfache Lösung, brauchen Sie nur, um sicherzustellen, wie so einen neuen Knoten mit jedem Aufruf von getFunction(), zum Beispiel zu erstellen:

private String [] functionNames = {"AND", "OR", "NOT", "IF"}; 
private int [] functionArities = {2,2,1,3}; 

public Node getFunction() { 
    int index = random.nextInt(3); // If you want to use "IF" nodes too this 
            // needs to be nextInt(4) 
    return new Node(functionArities[index],functionNodes[index]); 
} 

Answer 2

Es besteht die Möglichkeit, dass der Graph zyklisch ist. Nur weil Sie vordefinierte Knoten verwenden und diese zufällig auswählen. Je tiefer der Knoten ist, desto höher ist die Wahrscheinlichkeit, dass ein Knoten mehr als einmal eingefügt wird. Und in diesem Fall haben Sie Ihren Zyklus und die JVM beschwert sich mit einem SSO.

Die Wurzel Ihres Problems ist das functions Array (terminals ist OK, weil ein Terminal-Knoten keine Kinder hat).

Entfernen Sie das Array und erstellen Sie ein neues Funktionsobjekt für jeden Knoten.