Creazione di un albero binario in Java per scopi di programmazione genetica

Question

Sto lavorando a un progetto per una classe di ingegneria del software che sto prendendo. L'obiettivo è progettare un programma che utilizzi la programmazione genetica per generare un'espressione matematica che si adatti ai dati di addestramento forniti.

Ho appena iniziato a lavorare sul progetto, e sto cercando di capire come creare un albero binario che consenta l'altezza dell'albero definita dall'utente e mantenere ciascun nodo separato per semplificare il crossover e la mutazione quando riesco a implementare quei processi.

Ecco le classi di nodi che ho creato finora. Per favore perdoni quello che sono sicuro è la mia evidente inesperienza.

public class Node 
{ 
    Node parent; 
    Node leftchild; 
    Node rightchild; 

    public void setParent(Node p) 
    { 
     parent = p; 
    } 

    public void setLeftChild(Node lc) 
    { 
     lc.setParent(this); 
     leftchild = lc; 
    } 

    public void setRightChild(Node rc) 
    { 
     rc.setParent(this); 
     rightchild = rc; 
    } 
} 


public class OperatorNode extends Node 
{ 
    char operator; 


    public OperatorNode() 
    { 
     double probability = Math.random(); 

     if (probability <= .25) 
     { 
      operator = '+'; 
     } 
     else if (probability > .25 && probability <= .50) 
     { 
      operator = '-'; 
     } 
     else if (probability > .50 && probability <= .75) 
     { 
      operator = '*'; 
     } 
     else 
     { 
      operator = '/'; 
     } 
    } 

    public void setOperator(char op) 
    { 
     if (op == '+' || op == '-' || op == '*' || op == '/') 
     { 
      operator = op; 
     } 
    } 


/** 
* Node that holds x variables. 
*/ 
public class XNode extends Node 
{ 
    char x; 

    public XNode() 
    { 
     x = 'x'; 
    }  
} 

import java.util.Random; 


public class OperandNode extends Node 
{ 
    int operand; 

    /** 
    * Initializes random number generator, sets the value of the node from zero to 9. 
    */ 
    public OperandNode() 
    { 
     Random rand = new Random(); 
     operand = rand.nextInt(10); 
    } 

    /** 
    * Manually changes operand. 
    */ 
    public void setOperand(int o) 
    { 
     operand = o; 
    } 
} 

Questo compie tutto quello che ho bisogno fuori dei nodi stessi, ma sto correndo in problemi cercando di capire come trasformare questi in un albero più grande. Mi rendo conto che ho bisogno di usare un tipo di raccolta di qualche tipo, ma non riesco a trovarne uno nella Libreria che sembra appropriato per quello che sto cercando di fare.

Anche una spinta nella giusta direzione sarebbe molto apprezzata.

Answer 1

Quindi si desidera creare un albero casuale di OperatorNode s, OperandNode s e XNode s? E hai detto che vuoi definire la profondità dell'albero definita dall'utente?

Definire una funzione ricorsiva denominata buildRandomTree o qualcosa di simile. Dovrebbe essere necessario un singolo parametro int per la profondità dell'albero. Se il parametro depth è 1, restituisce un nodo foglia casuale (OperandNode o XNode). Se il parametro depth è maggiore di 1, generare un OperatorNode casuale e effettuare chiamate ricorsive per generare i sottoalberi sinistro e destro (con profondità 1 inferiore al livello corrente).

A seconda di cosa si desidera fare con i nodi, sarà necessario definire altre funzioni ricorsive. Ad esempio, probabilmente vorrai generare rappresentazioni testuali dei tuoi alberi di espressione. Per questo, è possibile definire toString() su ciascuna classe del nodo. (toString() sui sottotitoli sinistro e destro.)

Probabilmente si vorrà anche valutare gli alberi di espressione (con i valori dati per le variabili). Per questo, puoi definire un'altra funzione ricorsiva, chiamata forse evaluate(). Dovrà prendere un parametro, probabilmente uno Map, che fornirà i valori delle variabili (o "associazioni") con cui si desidera valutare l'espressione. (In questo momento gli alberi delle espressioni possono contenere solo una variabile "x", ma immagino che potresti voler aggiungere altro.Se sei sicuro di utilizzare sempre una singola variabile, allora evaluate può prendere un singolo argomento numerico per il valore di "x".)

L'implementazione di evaluate per le classi di 3 nodi sarà molto semplice. OperandNode e VariableNode restituiranno direttamente un valore; OperatorNode dovrà chiamare evaluate sui sottoalberi sinistro e destro, combinare i valori utilizzando l'operazione appropriata, quindi restituire il risultato.

Answer 2

Forse guardando this ti aiuterà.