Генетические операторы на бинарном дереве

У меня проблемы с попыткой разобраться с применением генетических операторов к бинарным деревьям.

Во-первых, у меня есть методы, которые генерируют два типа деревьев для начальной популяции, а именно Grow (дерево переменного размера) и Full (сбалансированное дерево одинаковой формы и размера).

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

Класс для каждого дерева выглядит так:

public class Tree<E>{

   E element;
   Tree<E> left, right;
   double rawFit;
   int hitRat;

   public Tree(E element)
   {
      this.element=element;
   }   

   public Tree (E element, Tree left, Tree right) 
   {
      this.element = element;
      this.left = left;
      this.right = right;
       }

        //MORE
        //CODE
}

Теперь у меня возникли проблемы с пониманием того, как реализовать генетические операторы, а именно Mutation и Crossover.

Случайно выбирая дерево из моей начальной популяции, как мне применить эти генетические операторы? Для мутации:

  • Мне нужно случайным образом выбрать точку в родительском дереве.
  • Удалить все поддерево ниже выбранной точки.
  • Создайте новое поддерево той же глубины, что и удаленное поддерево.
  • Замените его обратно на исходное родительское дерево и выбранную точку.

Теперь это потомство.

Графическое изображение:

                             PARENT
                              (*)            
randomly chosen point -->  (+)   (-)  
                         (1)(2) (3)(4)

       OFFSPRING         RANDOM SUBTREE
         (*)            
    (NULL)  (-)     +        (*) 
          (3) (4)          (5) (6)

     NEW OFFSPRING
          (*)            
      (*)    (-) 
    (5)(6) (3) (4)

Мне также нужно сделать что-то подобное для кроссовера.

Теоретически это кажется простым, но я понятия не имею, как это кодировать (Java). Любая помощь будет оценена по достоинству.

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

private static final String[] OPERATORS = {"+", "-", "/", "*"};
private static final int MAX_OPERAND = 100;
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);
        }
    }

java mutation tree genetic-algorithm binary-tree
person Leo    schedule 14.08.2015    source источник
comment
Что вы сделали до сих пор? Кроме того, как вы хотите создать новое поддерево с такой же глубиной, что и удаленное поддерево. ?   -  person Stefan Sprenger    schedule 14.08.2015
comment
@StefanSprenger Я отредактировал свой вопрос, чтобы показать, как я создал дерево. Тот же метод можно использовать для создания поддерева.   -  person Leo    schedule 14.08.2015

Ответы (2)


arrow_upward
1
arrow_downward

Я постараюсь кратко объяснить некоторые шаги.

Произвольный выбор точки в родительском дереве

Один из способов сделать это — выбрать случайное число, скажем, k, между 0 и количеством неконечных элементов в дереве. Случайной точкой будет k-й элемент при обходе дерева по порядку.

Замените все поддерево ниже выбранной точки.

Просто установите поддерево в новое сгенерированное дерево. Что-то вроде этого:

public class Tree<E> {

    public void mutate() {
        Tree tree = this.getRandomSubtree();
        tree.replace(NEW_RANDOM_TREE);
    }

    public void replace(Tree<E> newTree) {
        if(this.isLeftChild()) this.getParent().setLeft(newTree);
        else                   this.getParent().setRight(newTree);
    }
    ...
}

Метод getRandomSubtree() возвращает случайную точку в дереве.
Метод getParent() дерева возвращает непосредственный родительский узел.

Обратите внимание, что вам также придется проверить некоторые случаи, когда возвращаемое случайное поддерево является корнем.

person John Bupit    schedule 14.08.2015

arrow_upward
0
arrow_downward

  1. Произвольно выберите точку: Выберите случайный узел из несбалансированного двоичного дерева

  2. Удалять поддерево из выбранного узла не нужно, просто получите глубину выбранного поддерева и сохраните ссылку на него. http://www.geeksforgeeks.org/get-level-of-a-node-in-a-binary-tree/

  3. Используйте свой «полный» метод для создания нового случайного поддерева с сохраненной глубиной старого поддерева и назначьте это поддерево сохраненной ссылке старого поддерева, чтобы старое поддерево было уничтожено сборщиком мусора.

person Stefan Sprenger    schedule 14.08.2015