Как разделить два вложенных списка и объединить части, чтобы создать два новых вложенных списка - PullRequest
Новая
       16

Как разделить два вложенных списка и объединить части, чтобы создать два новых вложенных списка

4 голосов
/ 15 июля 2009

Я пытаюсь написать простую утилиту генетического программирования на 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

Ответы [ 2 ]

2 голосов
/ 15 июля 2009

В итоге я выполнил большую часть этого упражнения.

Сначала найдите количество возможных мест для разделения: количество нефункциональных узлов. 

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. Обходной путь должен был бы обернуть все это в, например. [лямбда а: а, дерево], поэтому редактируемые узлы всегда имеют родительский узел.

Это не очень эффективно. Поддержание количества узлов может сделать это быстрее, но тогда вам также понадобится сохранить ссылку на родителя, чтобы эффективно обновлять счетчики. Если вы пойдете по этому пути, вы действительно захотите найти или реализовать настоящий класс дерева.

0 голосов
/ 15 июля 2009

Если вы храните в каждом внутреннем узле количество дочерних элементов в каждой ветви, то вы можете выбрать точку разделения, сгенерировав случайное число от 0 до 1 + общее количество дочерних элементов. Если ответ 1, разделите на этом узле, в противном случае используйте номер, чтобы выяснить, к какому поддереву спуститься, и повторите процесс.

...