Friday, 27 February 2015

Review 1.2: Understanding mutation


Mutation and Crossover are main technologies used in genetic programming. In genetic programming, we usually generate a set of programs which are represented in the format of program trees. But we do not hope these random programs can give correct solutions for problems we want to solve. Hence, we use mutation and crossover technics to make those programs to evolve.

Firstly, let us take a look at mutation. Mutation means something changes from itself. The following code show a method to mutate a program tree:
def mutate(tree:N, paramCount:Int, prob:Double = 0.1 ):N = {
    if ( seed.nextDouble < prob )
        makeRandomTree(paramCount)
    else {
        mutateChildren(tree,paramCount)
    }
}

def mutateChildren(parent:N,paramCount:Int) = {
    var result = parent
    if (parent.isInstanceOf[Node])
        result.asInstanceOf[Node].children = parent.asInstanceOf[Node].children.map(mutate(_,paramCount)) 
    result
}

The code use a recusive way to mutate the program tree by changing its nodes one by one with a top-down direction. It firstly address to the parent node. If the randomly generated float is less than given probility which is default 0.1, then the parent node mutate by calling makeRandomTree(a method to generate random program tree, mainly use random and probility ways) method. Otherwise, it change its target to the parent's child nodes and apply the mutate method to them.
The following picture shows a kind of mutation.
From the picture we can see the whole tree was changed. This is just one condition. The parent node may not change and just has it child node changed. Or, nothing changed at all.

No comments:

Post a Comment