Selection and Reproduction

Overview


The seleciton process is an algorithm designed to compute the error of each item in the population and then to select the best. Af

Selection


The selection process typically requires defining a loss function which just sums the errors between the expected output and the output of the selected function from the population.

The following function evaluates a given AST. If the inputted item does not have a function attached to it, then it just returns the item. (that is, this is just a number)

Next, we need to evaluate each of the items in the arguments array. Lastly, we evaluate the function itself on the resulting arguments. 

function evaluate(tree) {
  if(tree.function === undefined) return tree;
  let args = [];
  if(tree.arguments !== undefined){
    for(let arg of tree.arguments){
      let nargs = [...arguments];
        nargs.shift();
        args.push(evaluate(arg,...nargs));
      }
  }
  let args2 = [...arguments];
  args2.shift();
  return tree.function(...args, ...args2)
}
Try it


NOTE, we include any arguments to the evaluate function itself when evaluated each function. That is, we will want to be able to call the evaluation function like this 

let test = evaluate(tree, 10);
That is, in this case, the number 10 is an input to the tree.

Mutation


Mutation is the process of making small random changes to an offspring of two parents. In the case of AST, we only mutate elements that represent constant values, by adding a small random number to the value.

Reproduction


Once a set of "best" functions have been found, the next step is create new individuals from the best set by the process of crossover. That is, given two parents, create a new individual that represents a merging of the two parents.

Top implement the crossover, we create three functions.

  • allArguments - recursively seraches through an AST tree and returns all the nodes in the tree
  • Crossover - takes two trees, randomly selects a node from the first tree and replaces it with a random node from the second tree
  • Replace - the replace functions executes the replacement used by the crossover function. 

function allArguments(tree){
  let results = [tree];
  if(tree.arguments !== undefined){
    for(let arg of tree.arguments){
      let nresults = allArguments(arg);
      for(let arg2 of nresults) results.push(arg2);
    }
  }
  return results;
}


function crossover(tree1, tree2){
  let args1 = allArguments(tree1);
  let rand1 = randomInteger(args1.length)
  let args2 = allArguments(tree2);
  let rand2 = randomInteger(args2.length)
  replace(tree1, args2[rand2], rand1);
  return tree1;
}

function replace(tree, node, number, count = 0){
  if(number === 0) return node;
  count += 1
  for(let i=0;i<tree.arguments.length;i++){
    if(count === number){
      tree.arguments[i] = copy(node);
    }
    count += 1;
    if(tree.arguments[i].arguments !== undefined){
      count = replace(tree.arguments[i], node, number, count);
    }
  }
  return count;
}
Try it

Contents