Friday, 27 February 2015

Review 1.3: Understanding crossover

Understanding crossover

Different from mutation, which generate child trees from itself, crossover uses two parents to generate the child trees. This involves taking two successful program trees and combining them to create a new program tree, usually by replacing one branch from one with a branch from another. The following pic shows a example:

In order to make the function for performing a crossover taking two program trees as inputs to be simple, It is recommend to traverse both trees at the same level. If a randomly selected threshold is reached, we return a copy of the first tree with one of its branch replaced by a branch from the second tree. Here is a example code:

def crossover(father:N,mother:N,prob:Double = 0.2, top:Boolean = true ):N = {
 if ( seed.nextDouble < prob && !top )
  mother
 else {
  crossoverChildren(father,mother, prob);
 } 
}

def crossoverChildren(father:N,mother:N,prob:Double):N = {
 var result = father
 if( father.isInstanceOf[Node] && mother.isInstanceOf[Node] )  //replace a branch
  result.asInstanceOf[Node].children = father.asInstanceOf[Node].children.map(crossover(_,choose(mother.asInstanceOf[Node].children), prob, false ));
 result
}

//Choose a node randomly
def choose(children:List[N]):N = {
 children(seed.nextInt(children.length))
}

No comments:

Post a Comment