Uniform crossover selection for GP (DEAP)

gistfile1.py

def getChildrenIndices(ind, pos):
    listChildPos = []
    pos += 1
    for i in range(ind[pos-1].arity):
        # We get the root of the child subtree
        listChildPos.append(pos)
        # We look for the size of this subtree
        pos = ind.searchSubtree(pos).stop
    return listChildPos

def findCommonRegion(ind1, ind2):
    # The root is always common
    listNodesInd1, listNodesInd2 = [0], [0]
    indicesToTest = 0

    while True: 
        newList1, newList2 = [], []
        for i1,i2 in zip(listNodesInd1[indicesToTest:], listNodesInd2[indicesToTest:]):
            # If the two primitives have the same arity -> they produce a similar shaped subtree
            # and if this arity is not 0 (meaning a terminal)
            if ind1[i1].arity == ind2[i2].arity and ind1[i1].arity != 0:
                # We add the children indices to our list
                newList1.extend(getChildrenIndices(ind1, i1))
                newList2.extend(getChildrenIndices(ind2, i2))

        if len(newList1) == 0:
            # No more similar elements
            break
        else:     
            # We do not want to test each node more than once
            indicesToTest = len(listNodesInd1)

            # Append the similar children to the list of nodes
            listNodesInd1.extend(newList1)
            listNodesInd2.extend(newList2)

    # Return a list of indices for each tree; each element of the
    # list is "similar" with the element in the other list at the same index
    return listNodesInd1, listNodesInd2