Creare un albero binario in Java per scopi di programmazione genetica

Question

Sto lavorando su un progetto per una classe di ingegneria del software che sto prendendo. L'obiettivo è progettare un programma che utilizzerà la programmazione genetica per generare un'espressione matematica che si adatta ai dati di formazione forniti.

Ho appena iniziato a lavorare sul progetto, e sto cercando di avvolgere la mia testa su come creare un albero binario che consentirà l'altezza dell'albero definita dall'utente e mantenere un nodo separato per rendere il crossover e la mutazione più semplice quando Posso attuare quei processi.

Ecco le classi del nodo che ho creato finora. Per favore, perdonare ciò 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 compone tutto ciò di cui ho bisogno dai nodi stessi, ma sto correndo in problemi cercando di capire come trasformarli in un albero più grande. Mi rendo conto di dover usare un tipo di raccolta di qualche tipo, ma non riesco a trovarne uno nella biblioteca che sembra appropriato per quello che sto cercando di fare.

Anche una spinta nella giusta direzione sarebbe molto apprezzata.

Answer 1

Quindi vuoi costruire un albero casuale di generacoli OperatorNodes, OperandNodes e XNodes? E hai detto che vuoi rendere definita l'utente della profondità dell'albero?

Definisci una funzione ricorsiva chiamata buildRandomTree o qualcosa di simile. Dovrebbe prendere un singolo parametro int per la profondità dell'albero. Se il parametro di profondità è 1, restituire un nodo a foglia casuale (operandnode o xnode). Se il parametro di profondità è superiore a 1, genera un operatore casuale e effettuare chiamate ricorsive per generare sottosuolo sinistro e destro (con profondità 1 inferiore al livello corrente).

A seconda di ciò che vuoi fare con i nodi, dovrai definire altre funzioni ricorsive. Ad esempio, probabilmente vorrai generare rappresentazioni testuali dei tuoi alberi di espressione. Per questo, è possibile definire toString() su ciascuna delle classi del nodo. (OperatorNode.toString() dovrà chiamare toString() sui sottorei sinistra e destra.)

Probabilmente vorrete valutare anche gli alberi di espressione (con determinati valori per le variabili). Per questo, è possibile definire un'altra funzione ricorsiva, forse chiamata evaluate(). Dovrà scattare un parametro, probabilmente un Map, che fornirà i valori variabili (o "Bindings") che si desidera valutare l'espressione con. (In questo momento i tuoi alberi di espressione possono contenere solo una singola variabile "x", ma immagino che potresti voler aggiungere altro. Se sei sicuro che utilizzerai solo una singola variabile, allora evaluate può prendere un singolo argomento numerico per il valore di "X".)

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

Answer 2

forse guardando ti aiuterà.

.