Erstellen eines Binärbaums in Java für Zwecke der genetischen Programmierung

Question

Ich arbeite an einem Projekt für einen Software-Engineering-Kurs, an dem ich teilnehme.Das Ziel besteht darin, ein Programm zu entwerfen, das genetische Programmierung nutzt, um einen mathematischen Ausdruck zu generieren, der zu den bereitgestellten Trainingsdaten passt.

Ich habe gerade mit der Arbeit an dem Projekt begonnen und versuche, mich damit auseinanderzusetzen, wie ich einen Binärbaum erstellen kann, der eine benutzerdefinierte Baumhöhe ermöglicht und jeden Knoten getrennt hält, um Crossover und Mutation einfacher zu machen, wenn ich dazu komme die Umsetzung dieser Prozesse.

Hier sind die Knotenklassen, die ich bisher erstellt habe.Bitte verzeihen Sie, da ich sicher bin, dass es sich um meine offensichtliche Unerfahrenheit handelt.

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;
    }
}

Dadurch wird alles erreicht, was ich aus den Knoten selbst benötige, aber ich stoße auf Probleme, herauszufinden, wie ich diese in einen größeren Baum umwandeln kann.Mir ist klar, dass ich einen Sammlungstyp verwenden muss, aber ich kann in der Bibliothek keinen finden, der für das, was ich tun möchte, geeignet erscheint.

Selbst ein kleiner Anstoß in die richtige Richtung wäre sehr dankbar.

Answer 1

Sie möchten also einen zufälligen Baum erstellen OperatorNodeS, OperandNodes, und XNodeS?Und Sie sagten, Sie möchten die Baumtiefe benutzerdefiniert machen?

Definieren Sie eine rekursive Funktion namens buildRandomTree oder etwas ähnliches.Es sollte eine einzige dauern int Parameter für die Baumtiefe.Wenn der Tiefenparameter 1 ist, wird ein zufälliger Blattknoten (OperandNode oder XNode) zurückgegeben.Wenn der Tiefenparameter größer als 1 ist, generieren Sie einen zufälligen OperatorNode und führen Sie rekursive Aufrufe durch, um den linken und rechten Teilbaum zu generieren (mit einer Tiefe von 1 kleiner als die aktuelle Ebene).

Je nachdem, was Sie mit den Knoten machen möchten, müssen Sie andere rekursive Funktionen definieren.Beispielsweise möchten Sie wahrscheinlich Textdarstellungen Ihrer Ausdrucksbäume generieren.Dafür können Sie definieren toString() auf jeder der Knotenklassen.(OperatorNode.toString() werde anrufen müssen toString() auf den linken und rechten Teilbäumen.)

Sie möchten wahrscheinlich auch die Ausdrucksbäume auswerten (mit vorgegebenen Werten für die Variablen).Zu diesem Zweck können Sie eine andere rekursive Funktion definieren, möglicherweise aufgerufen evaluate().Es muss einen Parameter annehmen, wahrscheinlich einen Map, wodurch die Variablenwerte (oder „Bindungen“) angegeben werden, mit denen Sie den Ausdruck auswerten möchten.(Im Moment können Ihre Ausdrucksbäume nur eine einzige Variable „x“ enthalten, aber ich kann mir vorstellen, dass Sie vielleicht weitere hinzufügen möchten.Wenn Sie sicher sind, dass Sie immer nur eine einzige Variable verwenden werden, dann evaluate kann ein einzelnes numerisches Argument für den Wert von „x“ annehmen.)

Die Implementierung von evaluate denn Ihre 3 Knotenklassen werden alle sehr einfach sein. OperandNode Und VariableNode gibt einfach direkt einen Wert zurück; OperatorNode werde anrufen müssen evaluate Kombinieren Sie im linken und rechten Teilbaum die Werte mit der entsprechenden Operation und geben Sie dann das Ergebnis zurück.

Answer 2

sieht vielleicht vielleicht Dieses wird Ihnen helfen.