programchromosome.java

一个开源的用java开发的遗传算法的封装好的工程

  }

  /**
   * Randomly chooses a valid node from the functions set.
   *
   * @param a_chromIndex index of the chromosome in the individual (0..n-1)
   * @param a_returnType the return type of node to choose
   * @param a_subReturnType the sub return type to look for
   * @param a_functionSet the functions to use
   * @param a_function true to choose a function, false to choose a terminal
   * @param a_growing true to ignore the function parameter, false otherwise
   * @return the node chosen
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  protected CommandGene selectNode(int a_chromIndex, Class a_returnType,
                                   int a_subReturnType,
                                   CommandGene[] a_functionSet,
                                   boolean a_function, boolean a_growing) {
    if (!isPossible(a_returnType, a_subReturnType, a_functionSet, a_function,
                    a_growing)) {
      if (a_growing && (a_returnType == CommandGene.VoidClass
                        || a_returnType == Void.class)) {
        // We simply return a NOP, it does nothing :-)
        // -------------------------------------------
        try {
          return new NOP(getGPConfiguration(), a_subReturnType);
        }
        catch (InvalidConfigurationException iex) {
          // Should never happen.
          // --------------------
          throw new RuntimeException(iex);
        }
      }
      final String errormsg = "Chromosome (index " + a_chromIndex
          + ") requires a " +
          (a_function ?
           ("function" + (a_growing ? " or terminal" : ""))
           : "terminal") + " of return type " +
          a_returnType
          + " (sub return type " + a_subReturnType + ")"
          + " but there is no such node available";
      if (!getGPConfiguration().isStrictProgramCreation()) {
        // Allow another try in case it is allowed.
        // ----------------------------------------
        throw new IllegalStateException(errormsg);
      }
      else {
        // Interrupt the whole evolution process.
        // --------------------------------------
        throw new RuntimeException(errormsg);
      }
    }
    CommandGene n = null;
    int lindex;
    // Following is analog to isPossible except with the random generator.
    // -------------------------------------------------------------------
    IGPProgram ind = getIndividual();
    UniqueRandomGenerator randGen = new UniqueRandomGenerator(a_functionSet.
        length, getGPConfiguration().getRandomGenerator());
    do {
      lindex = randGen.nextInt();
      // Consider return type AND sub return type (latter only if != 0).
      // ---------------------------------------------------------------
      if (a_functionSet[lindex].getReturnType() == a_returnType
          && (a_subReturnType == 0
              || a_functionSet[lindex].getSubReturnType() == a_subReturnType)) {
        if (a_functionSet[lindex].getArity(ind) == 0 &&
            (!a_function || a_growing)) {
          n = a_functionSet[lindex];
        }
        if (a_functionSet[lindex].getArity(ind) != 0 && a_function) {
          n = a_functionSet[lindex];
        }
      }
    }
    while (n == null);
    return n;
  }

  /**
   * Create a tree of nodes using the grow or the full method.
   *
   * @param a_num the chromosome's index in the individual of this chromosome
   * @param a_depth the maximum depth of the tree to create
   * @param a_returnType the return type the lastly evaluated node must have
   * @param a_subReturnType the sub return type to look for
   * @param a_functionSet the set of function valid to pick from
   * @param a_rootNode null, or parent node of the node to develop
   * @param a_recurseLevel 0 for first call
   * @param a_grow true: use grow method; false: use full method
   * @param a_childNum index of the child in the parent node to which it belongs
   * (-1 if node is root node)
   * @param a_validateNode true: check if node selected is valid
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  protected void growOrFullNode(int a_num, int a_depth,
                                Class a_returnType, int a_subReturnType,
                                CommandGene[] a_functionSet,
                                CommandGene a_rootNode, int a_recurseLevel,
                                boolean a_grow, int a_childNum,
                                boolean a_validateNode) {
    if (a_rootNode == null || a_validateNode) {
      int tries = 0;
      CommandGene[] localFunctionSet = (CommandGene[]) a_functionSet.clone();
      do {
        CommandGene node = selectNode(a_num, a_returnType, a_subReturnType,
                                      localFunctionSet, a_depth >= 1, a_grow);
        if (!getGPConfiguration().validateNode(this, node, a_rootNode, tries++,
                                               a_num, a_recurseLevel,
                                               a_returnType, localFunctionSet,
                                               a_depth,
                                               a_grow, a_childNum, false)) {
          // Remove invalid node from local function set.
          // --------------------------------------------
          localFunctionSet = remove(localFunctionSet, node);
          if (localFunctionSet.length == 0) {
            throw new IllegalStateException("No appropriate function found"
                                            + " during program creation!");
          }
          continue;
        }
        a_rootNode = node;
        break;
      }
      while (true);
    }
    // Generate the node.
    // ------------------
    m_depth[m_index] = m_maxDepth - a_depth;
    if (a_rootNode instanceof ICloneable) {
      m_genes[m_index++] = (CommandGene) ( (ICloneable) a_rootNode).clone();
    }
    else {
      m_genes[m_index++] = a_rootNode;
    }
    if (a_depth >= 1) {
      IGPProgram ind = getIndividual();
      for (int i = 0; i < a_rootNode.getArity(ind); i++) {
        /**@todo ensure required depth is cared about*/
        if (m_index < m_depth.length) {
          growOrFullNode(a_num, a_depth - 1,
                         a_rootNode.getChildType(getIndividual(), i),
                         a_rootNode.getSubChildType(i),
                         a_functionSet, a_rootNode, a_recurseLevel + 1, a_grow,
                         i, true);
        }
        else {
          // No valid program could be generated. Abort.
          // -------------------------------------------
          throw new IllegalStateException("Randomly created program violates"
                                          +
              " configuration constraints (symptom 1). It may be that you"
                                          +
              " specified a too small number of maxNodes to use!");
        }
      }
    }
    else {
      if (a_rootNode.getArity(getIndividual()) > 0) {
        // No valid program could be generated. Abort.
        // -------------------------------------------
        throw new IllegalStateException("Randomly created program violates"
                                        + " configuration constraints"
                                        + " (symptom 2)");
      }
    }
  }

  /**
   * Recalculate the depth of each node.
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public void redepth() {
    m_depth[0] = 0;
    redepth(0);
  }

  /**
   * Calculate the depth of the next node and the indices of the children
   * of the current node.
   * The depth of the next node is just one plus the depth of the current node.
   * The index of the first child is always the next node. The index of the
   * second child is found by recursively calling this method on the tree
   * starting with the first child.
   *
   * @param a_index the index of the reference depth
   * @return the index of the next node of the same depth as the
   * current node (i.e. the next sibling node)
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  protected int redepth(int a_index) {
    int num = a_index + 1;
    CommandGene command = getNode(a_index);
    if (command == null) {
      throw new IllegalStateException("ProgramChromosome invalid at index "
                                      + a_index);
    }
    IGPProgram ind = getIndividual();
    int arity = command.getArity(ind);
    for (int i = 0; i < arity; i++) {
      if (num < m_depth.length) {
        m_depth[num] = m_depth[a_index] + 1;
        // children[i][n] = num;
        num = redepth(num);
        if (num < 0) {
          break;
        }
      }
      else {
        return -1;
      }
    }
    return num;
  }

  /**
   * Gets the a_child'th child of the a_index'th node in this chromosome. This
   * is the same as the a_child'th node whose depth is one more than the depth
   * of the a_index'th node.
   *
   * @param a_index the node number of the parent
   * @param a_child the child number (starting from 0) of the parent
   * @return the node number of the child, or -1 if not found
   *
   * @author Klaus Meffert
   * @since 3.01 (since 3.0 in ProgramChromosome)
   */
  public int getChild(int a_index, int a_child) {
    /**@todo speedup*/
    int len = getFunctions().length;
    for (int i = a_index + 1; i < len; i++) {
      if (m_depth[i] <= m_depth[a_index]) {
        return -1;
      }
      if (m_depth[i] == m_depth[a_index] + 1) {
        if (--a_child < 0) {
          return i;
        }
      }
    }
    throw new RuntimeException("Bad child "
                               + a_child
                               + " of node with index = "
                               + a_index);
  }

  public CommandGene[] getFunctionSet() {
    return m_functionSet;
  }

  public void setFunctionSet(CommandGene[] a_functionSet) {
    m_functionSet = a_functionSet;
  }

  public CommandGene[] getFunctions() {
    return m_genes;
  }

  public void setFunctions(CommandGene[] a_functions)
      throws InvalidConfigurationException {
    m_genes = a_functions;
  }

  /**
   * Gets the number of nodes in the branch starting at the a_index'th node.
   *
   * @param a_index the index of the node at which to start counting
   * @return the number of nodes in the branch starting at the a_index'th node
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public int getSize(int a_index) {
    int i;
    // Get the node at which the depth is <= depth[n].
    for (i = a_index + 1; i < m_genes.length && m_genes[i] != null;
         i++) {
      if (m_depth[i] <= m_depth[a_index]) {
        break;
      }
    }
    return i - a_index;
  }

  /**
   * Gets the depth of the branch starting at the a_index'th node.
   *
   * @param a_index the index of the node at which to check the depth
   * @return the depth of the branch starting at the a_index'th node
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public int getDepth(int a_index) {
    int i, maxdepth = m_depth[a_index];
    for (i = a_index + 1; i < m_genes.length && m_genes[i] != null;
         i++) {
      if (m_depth[i] <= m_depth[a_index]) {
        break;
      }
      if (m_depth[i] > maxdepth) {
        maxdepth = m_depth[i];
      }
    }
    return maxdepth - m_depth[a_index];
  }

  /**
   * Gets the node which is the parent of the given node in this chromosome. If
   * the child is at depth d then the parent is the first function at depth d-1
   * when iterating backwards through the function list starting from the child.
   *
   * @param a_child the child node
   * @return the parent node, or null if the child is the root node
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public int getParentNode(int a_child) {
    if (a_child >= m_genes.length || m_genes[a_child] == null) {
      return -1;
    }
    for (int i = a_child - 1; i >= 0; i--) {
      if (m_depth[i] == m_depth[a_child] - 1) {
        return i;
      }
    }
    return -1;
  }

  /**
   * Checks whether a node with a given type is contained in the program.
   *
   * @param a_type the type to look for
   * @param a_exactMatch true: look for exactly the given type: false: also look
   * for sub types
   * @return true specific node found
   *
   * @author Klaus Meffert
   * @since 3.2.1
   */
  public CommandGene getNode(Class a_type, boolean a_exactMatch) {
    return getNode(a_type, a_exactMatch, 0);
  }

  public CommandGene getNode(Class a_type, boolean a_exactMatch,
                             int a_startIndex) {
    int size = m_genes.length;
    for (int i = a_startIndex; i < size; i++) {
      if (m_genes[i] != null) {
        if (a_exactMatch) {
          if (m_genes[i].getClass() == a_type) {
            m_genes[i].nodeIndex = i; /**@todo work over*/
            return m_genes[i];
          }
        }
        else {
          if (a_type.isAssignableFrom(m_genes[i].getClass())) {
            m_genes[i].nodeIndex = i; /**@todo work over*/
            return m_genes[i];
          }
        }
      }
      else {
        break;
      }
    }
    return null;
  }

  /**
   * Executes this node as a boolean.
   *
   * @param args the arguments for execution
   * @return the boolean return value of this node
   * @throws UnsupportedOperationException if the type of this node is not
   * boolean
   *
   * @author Klaus Meffert
   * @since 3.0