Двоичное дерево Генетическое программирование

Question

Я только что начал с Генетическое программирование, и у меня возникают проблемы с инициализацией моего населения.

Мне нужно дерево для представления каждого решения кандидата. Проблема заключается в том, что я незнаком с деревьями.

Есть два способа инициализации, что мне нужно, а именно Grow (дерево переменного размера) и Полный (сбалансированный одинаковой формы и размера дерева).

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

Я инициализируется мой класс Tree, однако, я не знаю, как поступить здесь и далее заполнить дерево (либо полное или Grow).

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


} 

Может ли кто-нибудь любезно рассказать мне, как это можно сделать, или даже просто подтолкнуть в правильном направлении.

Я пытаюсь случайно заполнить деревья до предопределенной глубины.

• Операторы (+ -/*) вставляются повсюду, кроме листовых узлов.
• Операнды (1-100) вставляются только на листовых узлах

Благодарности.

Answer 1

Непонятно, что вы хотите. Вы спрашиваете, как представить приведенные вами примеры или как реализовать методы генерации случайных деревьев в соответствии с одной из двух стратегий?

Ваши примеры могут быть представлены с классом дерева таким образом:

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]

Вы можете случайным образом деревья с помощью методов, описанных в следующем классе:

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

} 

Тогда вы можете просто сделать:

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

Answer 2

Вам нужно создать две функции, которые добавляют элементы к дереву. Для функции GROW вы можете сделать что-то вроде ниже ...

В принципе, вы должны начать настройку листовых узлов на основе критериев, которые вы решите. Это не прекрасный пример, но может помочь вам двигаться в правильном направлении.

Я не запускал это, но это должно продемонстрировать, как вырастить дерево. Возможно, вам придется добавить функции, чтобы они работали так, как вы хотите.

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

Дерево:

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

Значение:

общественного класса Value { Строка Опер; Integer val

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

вы можете посмотреть на реализацию Крошечный GP http://cswww.essex.ac.uk/staff/rpoli/TinyGP/ (сделано Рикардо Poli). Однако эта реализация требует глубокого знания языка программирования C.

В качестве альтернативы вы можете использовать варианты GP с линейным представлением хромосом (таких как линейный GP, декартовый GP, программирование экспрессии генов, программирование с несколькими выражениями и т. Д.). У них есть более простая и понятная реализация. Например, посмотрите на исходный код программирования с несколькими выражениями: http://www.mepx.org/source_code.html