4

二分木に遺伝的演算子を適用することに頭を悩ませようとして問題が発生しています。

まず、 Grow (可変サイズのツリー) とFull (バランスの取れた同じ形状とサイズのツリー)という 2 種類のツリーを生成するメソッドがあります。

    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
}

ここで、遺伝的演算子、つまりミューテーションとクロスオーバーを実装する方法を理解するのに苦労しています

初期集団から木をランダムに選択しますが、これらの遺伝的演算子を適用するにはどうすればよいですか? 変異の場合:

  • 親ツリーのポイントをランダムに選択する必要があります。
  • 選択したポイントの下にあるサブツリー全体を削除します。
  • 削除されたサブツリーと同様の深さの新しいサブツリーを生成します。
  • 元の親ツリーと選択したポイントに戻します。

これが今の子孫です。

グラフィック描写:

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

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

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

クロスオーバーについても同様のことを行う必要があります。

理論的には簡単に思えますが、これをコーディングする方法がわかりません（Java）。どんな助けでも大歓迎です。

編集:完全なツリーを生成するために使用した方法は次のようになります。

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

2 に答える 2

2

いくつかの手順を簡単に説明しようと思います。

親ツリーのポイントをランダムに選択します

kこれを行う 1 つの方法は、0 とツリー内の非リーフ要素の数の間の乱数、たとえば を選択することです。ランダムなポイントは、ツリーを順番にトラバースする際kのth 要素になります。

選択したポイントの下のサブツリー全体を置き換えます。

サブツリーを新しく生成されたツリーに設定するだけです。このようなもの：

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()メソッドは、直接の親ノードを返します。

返されるランダムなサブツリーがルート自体である場合も確認する必要があることに注意してください。

于 2015-08-14T12:10:37.250 に答える