Programmazione genetica ad albero binario

Question

Ho appena iniziato con la programmazione genetica e sto riscontrando problemi di inizializzazione della mia popolazione.

Ho bisogno di un albero per rappresentare ogni soluzione candidata - Il problema è che non conosco gli alberi.

Ci sono due modi di inizializzazione di cui ho bisogno, vale a dire Grow (albero di dimensioni variabili) e completa (albero stessa forma e dimensione equilibrato).

FULL      GROW 
    (*)       (*) 
    (+) (-)     (5) (-) 
(1)(2) (3)(4)      (6) (7) 

ho inizializzato mia classe Albero, tuttavia, non so come procedere da qui in poi per popolare l'albero (sia completa o crescere).

public class Tree{ 
    Object value; 
    Tree left, right; 

    public Tree(Object value) 
    { 
     this.value=value; 
    } 

    public Tree (Object value, Tree left, Tree right) 
    { 
     this.value = value; 
     this.left = left; 
     this.right = right; 
    } 

    // Getter & setter for the value. 
    public Object getValue(){ 
     return value;} 
    public void setValue(Object value){ 
     this.value = value;} 

    // Getters & setters for left & right nodes. 
    public Tree getLeft(){ 
     return left;} 
    public Tree getRight(){ 
     return right;} 
    public void setLeft(Tree ln){ 
     left = ln;} 
    public void setRight(Tree rn){ 
     right = rn;} 


} 

Qualcuno potrebbe gentilmente dirmi come questo può essere fatto, o anche solo una piccola spinta nella giusta direzione.

Sto provando a popolare a caso gli alberi fino a una profondità predefinita.

• Gli operatori (+ -/*) sono inseriti ovunque a prescindere dai nodi foglia.
• Operandi (1-100) sono inseriti solo sui nodi foglia

Grazie.

Answer 1

Non è molto chiaro quello che vuoi. Stai chiedendo come rappresentare gli esempi che hai dato o come implementare i metodi per generare alberi casuali in base a una delle due strategie?

I suoi esempi possono essere rappresentati con la classe Tree in questo modo:

Tree full = new Tree("*", 
     new Tree("+", new Tree(1), new Tree(2)), 
     new Tree("-", new Tree(3), new Tree(4))); 

Tree grow = new Tree("*", 
     new Tree(5), 
     new Tree("-", new Tree(6), new Tree(7))); 

---

[EDIT]

È casuale possibile generare alberi utilizzando i metodi nella seguente classe:

class TreeGenerator { 
    private static final String[] OPERATORS = {"+", "-", "/", "*"}; 
    private static final int MAX_OPERAND = 100; 

    private static Random random = new Random(); 

    public static Tree full(int depth) { 
     if (depth > 1) { 
      String operator = OPERATORS[random.nextInt(OPERATORS.length)]; 
      return new Tree(operator, full(depth - 1), full(depth - 1)); 
     } else { 
      return new Tree(random.nextInt(MAX_OPERAND) + 1); 
     } 
    } 

    public static Tree grow(int depth) { 
     if (depth > 1 && random.nextBoolean()) { 
      String operator = OPERATORS[random.nextInt(OPERATORS.length)]; 
      return new Tree(operator, grow(depth - 1), grow(depth - 1)); 
     } else { 
      return new Tree(random.nextInt(MAX_OPERAND) + 1); 
     } 
    } 

} 

Quindi, è sufficiente fare:

Tree full3 = TreeGenerator.full(3); 
Tree grow4 = TreeGenerator.grow(4); 

Answer 2

Avrete bisogno di creare due funzioni che aggiungono elementi ad un albero. Per la funzione GROW potresti fare qualcosa di simile in basso ...

Fondamentalmente, devi iniziare a impostare i nodi foglia in base ai criteri che decidi. Questo non è un esempio perfetto ma può aiutarti a muoverti nella giusta direzione.

Non ho eseguito questo, ma questo dovrebbe dimostrare come far crescere un albero. Potrebbe essere necessario aggiungere funzioni per farlo funzionare come si desidera.

Tree head = new Tree(new Value("*")); 
for (int x = 0; x < 5; x++){ 
    head.grow(new Tree(x)); 
} 

Albero:

public class Tree{ 
    Value value; 
    Tree left, right; 

    public Tree(Value value) 
    { 
     this.value=value; 
    } 

    public Tree (Value value, Tree left, Tree right) 
    { 
     this.value = value; 
     this.left = left; 
     this.right = right; 
    } 

    // Getter & setter for the value. 
    public Value getValue(){ 
     return value;} 
    public void setValue(Value value){ 
     this.value = value;} 

    // Getters & setters for left & right nodes. 
    public Tree getLeft(){ 
     return left;} 
    public Tree getRight(){ 
     return right;} 
    public void setLeft(Tree ln){ 
     left = ln;} 
    public void setRight(Tree rn){ 
     right = rn;} 

     public void grow(Tree t){ 

    if(value.compareTo(t) < 0){ 
     if(right == null){ 
      setRight(t); 
     } else{ 
      getRight().grow(t); 
     } 
    else{ 
     if(left == null){ 
      setLeft(t); 
     } else{ 
      getLeft().grow(t); 
     } 

    } 

    public toString(){ 
     if(left == null && right == null) 
      return value.oper; 
     else{ 
      return value.val; 
    } 
} 

Valore:

public class Valore { String oper; Numero intero

public value(String str){ 
     oper = str; 
     val = Integer.MIN_VALUE; 
    } 

    public value(Integer x){ 
     oper = "non"; 
     val = x; 
    } 

    public int compareTo(Value o){ 
     if(o.val < val) return -1; 
     if(o.val > val) return 1; 
     return 0; 
    } 

} 

Answer 3

potete dare un'occhiata all'implementazione di Tiny GP http://cswww.essex.ac.uk/staff/rpoli/TinyGP/ (fatto da Ricardo Poli). Tuttavia, tale implementazione richiede una profonda conoscenza del linguaggio di programmazione C.

in alternativa è possibile utilizzare le varianti GP con rappresentazione lineare dei cromosomi (come GP lineare, GP cartesiano, programmazione Gene Expression, programmazione multipressione ecc.). Quelli hanno un'implementazione più semplice e più facile da capire. Per esempio, date un'occhiata al codice sorgente della programmazione multipressione: http://www.mepx.org/source_code.html