4

Python で単純な遺伝的プログラミング ユーティリティをコーディングしようとしています。しかし今、私は自分のツリーのクロスオーバー/メイト機能で立ち往生しています。ツリーはネストされたリストによって構築され、次のようになります。

# f = internal node (a function), c = leaf node (a constant)
tree1 = [f, [f, [f, c, c], [f, c, c]], [f, [f, c, c], [f, c, c]]]
tree2 = [f, [f, [f, c, c], c], [f, [f, c, c], c]]

各ツリーのポイントをランダムに選択して分割し、各ツリーの一部を新しいツリーに結合したいと考えています。また、超えてはならない最大深度もあるため、ツリーが大きすぎる可能性があるため、ツリー内のどこでも選択を行うことはできません。以下は、それがどのように機能するかの例です。

# f:n, where n is the number of arguments the function take
#               + split here  
tree1 = [f:2, [f:3, a, a, a], a]
#                            + split here
tree2 = [f:2, [f:2, a, a], [f:1, a]

tree_child1 = [f:2, [f:1, a], a]
tree_child2 = [f:2, [f:2, a, a], [f:3, a, a, a]]

これを解決する方法について（現時点では）わかりません。ヒントや解決策は大歓迎です！

(誰かが構造をよりよく理解するのに役立つかもしれないので、解析関数を追加しました。)

# My recursive code to parse the tree.
def parse(self, node=None):
    if not node:
        node = self.root

    if isinstance(node, list):
        function = node[0]
        res = []
        for child in node[1:function.arity+1]:
            res.append(self.parse(child))
        value = function.parse(*res) # function
    else:
        value = node.parse() # constant
    return value
4

2 に答える 2

2

私は最終的にこれのほとんどを演習として実装しました。

まず、分割可能な場所の数、つまり非機能ノードの数を見つけます。

def count(obj):
    total = 0
    for o in obj[1:]:
        # Add the node itself.
        total += 1

        if isinstance(o, list):
            total += count(o)
    return total

次に、ヘルパー: 上記の範囲のインデックスが与えられると、それがどこにあるかを把握します。

def find_idx(tree, idx):
    """
    Return the node containing the idx'th function parameter, and the index of that
    parameter.  If the tree contains fewer than idx parameters, return (None, None).
    """
    if not isinstance(idx, list):
        # Stash this in a list, so recursive calls share the same value.
        idx = [idx]

    for i, o in enumerate(tree):
        # Skip the function itself.
        if i == 0:
            continue

        if idx[0] == 0:
            return tree, i

        idx[0] -= 1
        if isinstance(o, list):
            container, result_index = find_idx(o, idx)
            if container is not None:
                return container, result_index

    return None, None

スワップを行うのは非常に簡単です。

def random_swap(tree1, tree2):
    from random import randrange
    pos_in_1 = randrange(0, count(tree1))
    pos_in_2 = randrange(0, count(tree2))

    parent1, idx1 = find_idx(tree1, pos_in_1)
    parent2, idx2 = find_idx(tree2, pos_in_2)

    # Swap:
    parent1[idx1], parent2[idx2] = parent2[idx2], parent1[idx1]

c = 1
tree1 = ["f:2", c, ["f:1", c]]
tree2 = ["f:2", ["f:2", ["f:2", c, c], ["f:2", c, c]], ["f:3", ["f:4", c, c, c, c], ["f:2", c, c], c]]

while True:
    random_swap(tree1, tree2)
    print tree1
    print tree2

これは最大深度を実装していませんが、それが始まりです。

これにより、ルート ノードが置き換えられることもありません。つまり、tree1 のノードが新しい tree2 になり、tree2 のすべてが tree1 のノードになります。回避策は、たとえば全体をラップすることです。[lambda a: a, tree] であるため、編集可能なノードには常に親ノードがあります。

これはあまり効率的ではありません。ノード数を維持すると高速になる可能性がありますが、数を効率的に更新するには、親への参照も保存する必要があります。そのルートに行く場合は、実際のツリー クラスを見つけたり、実装したりする必要があります。

于 2009-07-15T05:02:11.583 に答える
0

各内部ノードに各ブランチの子の数を格納する場合、0から1+合計の子までの乱数を生成することで分割点を選択できます。答えが1の場合は、そのノードで分割します。それ以外の場合は、番号を使用して、どのサブツリーに降りるかを判断し、プロセスを繰り返します。

于 2009-07-15T01:37:05.363 に答える