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]]

我不知道（目前）如何解决这个问题。任何提示或解决方案都非常受欢迎！

（添加了我的 parse 函数，因为它可以帮助人们更好地理解结构。）

# 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 回答