2009-07-15 6 views
4

Ich versuche, ein einfaches Programm für genetische Programmierung in Python zu programmieren. Aber jetzt bin ich bei der Crossover/Mate-Funktion für meine Bäume festgefahren. Die Bäume werden durch verschachtelte Listen erstellt und in etwa so aussehen:Wie man zwei verschachtelte Listen teilt und die Teile kombiniert, um zwei neue verschachtelte Listen zu erstellen

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

Ich möchte zufällig einen Punkt in jedem Baum wählen Sie aufzuspalten und dann möchte ich ein Teil von jedem Baum in einen neuen Baum zu kombinieren. Es gibt auch eine maximale Tiefe, die nicht überschritten werden sollte, so dass die Auswahl nicht wirklich irgendwo im Baum stattfinden kann, da dies einen zu großen Baum erzeugen könnte. Unten ist ein Beispiel dafür, wie es funktionieren soll:

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

ich keine Ahnung (im Moment) auf, wie diese zu lösen. Irgendwelche Tipps oder Lösungen sind mehr als willkommen!

(meine Parse-Funktion hinzugefügt, wie es jemand die Struktur besser zu verstehen, könnte helfen.)

# 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 
+1

Ich würde vorschlagen, einfache Datenstruktur des Baumes mit Knoten-Objekten statt mit verschachtelten Liste, die es lesbarer wird und Sie in der Lage, mehr Buchführung Daten und Methoden in jedem Knoten zu setzen machen. –

Antwort

2

Ich beendete die meisten davon als Übung.

Zuerst finden Sie die Anzahl der möglichen Standorte zu teilen: die Anzahl der Nicht-Funktions-Knoten.

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 

Dann ein Helfer: gegeben einen Index im oben genannten Bereich, herauszufinden, wo es ist.

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 

den Swap zu tun, ist ziemlich einfach jetzt:

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 

Diese implementieren keine maximale Tiefe, aber es ist ein Anfang.

Dies ersetzt auch nie den Wurzelknoten, wobei ein Knoten in tree1 zum neuen tree2 wird und alle von tree2 zu einem Knoten in tree1 werden. Ein Workaround wäre, das Ganze in zB zu verpacken. [Lambda a: a, Baum], editierbare Knoten haben also immer einen Elternknoten.

Dies ist nicht sehr effizient. Durch die Verwaltung von Knotenzählungen könnte es schneller werden, aber Sie müssen auch einen Verweis auf das übergeordnete Element speichern, um die Zählungen effizient zu aktualisieren. Wenn Sie diesen Weg gehen, wollen Sie wirklich eine echte Baumklasse finden oder implementieren.

0

Wenn Sie in jedem Zweig eine Zählung der Kinder in jedem internen Knoten speichern, dann könnte man eine gespaltene holen Zeigen Sie durch Generieren einer Zufallszahl von 0 bis 1 + insgesamt Kinder. Wenn die Antwort 1 ist, teilen Sie sie an diesem Knoten. Verwenden Sie andernfalls die Nummer, um herauszufinden, auf welchen Teilbaum heruntergefahren werden soll, und wiederholen Sie den Vorgang.

Verwandte Themen