OnePointCrossover.java

package progen.kernel.evolution.operators;

import java.util.ArrayList;
import java.util.List;

import progen.kernel.tree.Node;
import progen.kernel.tree.Tree;

/**
 * Implementación del operador de cruce de un punto. Este operador trabaja de
 * tal forma que selecciona un nodo compatible de la parte similar de dos
 * árboles. Estos árboles pertenecen a dos individuos distintos, pero tienen el
 * mismo identificador, es decir, son RBP0 ambos, o ADF0 ambos, etc.
 * 
 * La parte común de dos árboles se entenderá como el conjunto de nodos de ambos
 * árboles que contienen la misma función, de tal forma que si se superpusieran
 * ambos árboles, esta parte común sería exactamente igual.
 * 
 * @author jirsis
 * @since 2.0
 */
public class OnePointCrossover extends StandardCrossover {

  /**
   * En este caso, la selección de nodos se realiza de acuerdo al comportamiento
   * que se espera para este operador, es decir, devuelve dos nodos, uno de cada
   * árbol, de todos aquellos que pertenecen a la parte común de esos árboles.
   * 
   * @see StandardCrossover#selectNodes(Tree treeA, Tree treeB)
   */
  @Override
  protected List<Node> selectNodes(Tree treeA, Tree treeB) {
    final List<Node> nodes = new ArrayList<Node>();
    final List<Node> stackA = new ArrayList<Node>();
    final List<Node> stackB = new ArrayList<Node>();
    final List<Node> comunA = new ArrayList<Node>();
    final List<Node> comunB = new ArrayList<Node>();

    selectComun(treeA.getRoot(), treeB.getRoot(), stackA, stackB, comunA, comunB);

    // se eliminan las raices dado que es el único nodo que aún siendo
    // común, no se puede utilizar para cruzar.
    comunA.remove(treeA.getRoot());
    comunB.remove(treeB.getRoot());

    if (comunA.size() > 0 && comunB.size() > 0) {
      final int randomNode = (int) (Math.random() * comunA.size());
      nodes.add(comunA.get(randomNode));
      nodes.add(comunB.get(randomNode));
    }
    return nodes;
  }

  /**
   * Selecciona a partir de dos nodos, todos los nodos comunes que comparten
   * dichos nodos. Un nodo es compartido por varios nodos, si ambos nodos tienen
   * una función con el mismo símbolo y con el mismo valor de retorno.
   * 
   * @param nodeA
   *          Un de los nodos.
   * @param nodeB
   *          El otro nodo.
   * @param stackA
   *          Una pila en la que se almacenan los nodos hijo que faltan por
   *          procesar del nodo A.
   * @param stackB
   *          Una pila en la que se almacenan los nodos hijo que faltan por
   *          procesar del nodo B.
   * @param comunA
   *          Conjunto de nodos que forman la parte común al árbol A.
   * @param comunB
   *          Conjunto de nodos que forman la parte común al árbol B.
   */
  private void selectComun(Node nodeA, Node nodeB, List<Node> stackA, List<Node> stackB, List<Node> comunA, List<Node> comunB) {
    if (nodeA.getFunction().getFunction().getReturnType().equals(nodeB.getFunction().getFunction().getReturnType()) && nodeA.getFunction().getFunction().getSymbol().equals(nodeB.getFunction().getFunction().getSymbol())) {
      stackA.addAll(nodeA.getBranches());
      stackB.addAll(nodeB.getBranches());
      comunA.add(nodeA);
      comunB.add(nodeB);
    } else {
      stackA.removeAll(nodeA.getBranches());
      stackB.removeAll(nodeB.getBranches());
    }

    if (stackA.size() > 0 && stackB.size() > 0) {
      selectComun(stackA.remove(0), stackB.remove(0), stackA, stackB, comunA, comunB);
    }
  }
}