programchromosome.java

JGAP（发音"jay-gap"）是一款用Java编写的遗传算法包。提供了基本的遗传算法.你可以使用它来解决一些适用于遗传算法解决的问题.

      }
      else {
        throw new IllegalArgumentException(errormsg);
      }
    }
    CommandGene n = null;
    int lindex;
    // Following is analog to isPossible except with the random generator.
    // -------------------------------------------------------------------
    while (n == null) {
      lindex = getGPConfiguration().getRandomGenerator().nextInt(
          a_functionSet.length);
      if (a_functionSet[lindex].getReturnType() == a_type) {
        if (a_functionSet[lindex].getArity(m_ind) == 0 &&
            (!a_function || a_growing)) {
          n = a_functionSet[lindex];
        }
        if (a_functionSet[lindex].getArity(m_ind) != 0 && a_function) {
          n = a_functionSet[lindex];
        }
      }
    }
    return n;
  }

  /**
   * Create a tree of nodes using the grow 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_type the type of node to start with
   * @param a_functionSet the set of function valid to pick from
   * @param a_rootNode null, or root node to use
   * @param a_recurseLevel 0 for first call
   * @param a_grow true: use grow method; false: use full method
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  protected void growOrFullNode(int a_num, int a_depth, Class a_type,
                          CommandGene[] a_functionSet, CommandGene a_rootNode,
                          int a_recurseLevel, boolean a_grow) {
    if (a_rootNode == null) {
      do {
        a_rootNode = selectNode(a_type, a_functionSet, a_depth > 1, a_grow);
        /**@todo following is experimental for constraints*/
        if (a_num == 0 && false) {
          // SubProgram forbidden other than as root
          if (a_recurseLevel > 0 && a_rootNode.getClass() == SubProgram.class) {
            continue;
          }
        }
        //
        if (a_num == 1 && false) {
          // ForLoop forbidden under root node
          if (a_recurseLevel > 0 && a_rootNode.getClass() == ForLoop.class) {
            continue;
          }
          // ForLoop needed as root
          if (a_recurseLevel == 0 && a_rootNode.getClass() != ForLoop.class) {
            continue;
          }
          // Variable forbidden other than directly under root
          if (a_recurseLevel > 1 && a_rootNode.getClass() == Variable.class) {
            continue;
          }
          // Variable needed directly under root
          if (a_recurseLevel == 1 && a_depth == 1
                   && a_rootNode.getClass() != Variable.class) {
            continue;
          }
          // SubProgram forbidden other than directly under root
          if (a_recurseLevel > 1 && a_depth > 1
                   && a_rootNode.getClass() == SubProgram.class) {
            continue;
          }
          // SubProgram needed directly under root
          if (a_recurseLevel == 1 && a_depth > 1 && a_type == CommandGene.VoidClass
                   && a_rootNode.getClass() != SubProgram.class) {
            continue;
          }
          // AddAndStore or TransferMemory needed 2 root
          if (a_recurseLevel == 2 && a_depth > 1 && a_type == CommandGene.VoidClass
                   && a_rootNode.getClass() != AddAndStore.class
                   && a_rootNode.getClass() != TransferMemory.class) {
            continue;
          }
          // AddAndStore or TransferMemory forbidden other than 2 root
          if (a_recurseLevel != 2 && a_depth > 1 && a_type == CommandGene.VoidClass
                   && (a_rootNode.getClass() == AddAndStore.class
                   || a_rootNode.getClass() == TransferMemory.class)) {
            continue;
          }
        }
        break;
      }
      while (true);
    }
    // Generate the node.
    // ------------------
    m_depth[m_index] = m_maxDepth - a_depth;
    getFunctions()[m_index++] = a_rootNode;
    if (a_depth > 1) {
      for (int i = 0; i < a_rootNode.getArity(m_ind); i++) {
        growOrFullNode(a_num, a_depth - 1,
                       a_rootNode.getChildType(getIndividual(), i),
                       a_functionSet, null, a_recurseLevel + 1, a_grow);
      }
    }
  }

  /**
   * Recalculate the depths 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");
    }
    int arity = command.getArity(m_ind);
    for (int i = 0; i < arity; i++) {
      m_depth[num] = m_depth[a_index] + 1;
      // children[i][n] = num;
      num = redepth(num);
      if (num < 0) {
        break;
      }
    }
    return num;
  }

  /**
   * @return the number of terminals in this chromosome
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public int numTerminals() {
    int count = 0;
    for (int i = 0; i < getFunctions().length && getFunctions()[i] != null; i++) {
      if (getFunctions()[i].getArity(m_ind) == 0) {
        count++;
      }
    }
    return count;
  }

  /**
   * @return the number of functions in this chromosome
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public int numFunctions() {
    int count = 0;
    for (int i = 0; i < getFunctions().length && getFunctions()[i] != null; i++) {
      if (getFunctions()[i].getArity(m_ind) != 0) {
        count++;
      }
    }
    return count;
  }

  /**
   * Counts the number of terminals of the given type in this chromosome.
   *
   * @param a_type the type of terminal to count
   * @return the number of terminals in this chromosome
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public int numTerminals(Class a_type) {
    int count = 0;
    for (int i = 0; i < getFunctions().length && getFunctions()[i] != null; i++) {
      if (getFunctions()[i].getArity(m_ind) == 0
          && getFunctions()[i].getReturnType() == a_type) {
        count++;
      }
    }
    return count;
  }

  /**
   * Counts the number of functions of the given type in this chromosome.
   *
   * @param a_type the type of function to count
   * @return the number of functions in this chromosome.
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public int numFunctions(Class a_type) {
    int count = 0;
    for (int i = 0; i < getFunctions().length && getFunctions()[i] != null; i++) {
      if (getFunctions()[i].getArity(m_ind) != 0
          && getFunctions()[i].getReturnType() == a_type) {
        count++;
      }
    }
    return count;
  }

  /**
   * Gets the a_index'th node in this chromosome. The nodes are counted in a
   * depth-first manner, with node 0 being the root of this chromosome.
   *
   * @param a_index the node number to get
   * @return the node
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public CommandGene getNode(int a_index) {
    if (a_index >= getFunctions().length || getFunctions()[a_index] == null) {
      return null;
    }
    return getFunctions()[a_index];
  }

  /**
   * 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.0
   */
  public int getChild(int a_index, int a_child) {
    for (int i = a_index + 1; i < getFunctions().length; 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);
  }

  /**
   * Gets the i'th node of the given type in this chromosome. The nodes are
   * counted in a depth-first manner, with node 0 being the first node of the
   * given type in this chromosome.
   *
   * @param a_index the i'th node to get
   * @param a_type the type of node to get
   * @return the node
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public int getNode(int a_index, Class a_type) {
    for (int j = 0; j < getFunctions().length && getFunctions()[j] != null; j++) {
      if (getFunctions()[j].getReturnType() == a_type) {
        if (--a_index < 0) {
          return j;
        }
      }
    }
    return -1;
  }

  /**
   * Gets the i'th terminal in this chromosome. The nodes are counted in a
   * depth-first manner, with node 0 being the first terminal in this
   * chromosome.
   *
   * @param a_index the i'th terminal to get
   * @return the terminal
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public int getTerminal(int a_index) {
    for (int j = 0; j < getFunctions().length && getFunctions()[j] != null; j++) {
      if (getFunctions()[j].getArity(m_ind) == 0) {
        if (--a_index < 0) {
          return j;
        }
      }
    }
    return -1;
  }

  /**
   * Gets the a_index'th function in this chromosome. The nodes are counted in a
   * depth-first manner, with node 0 being the first function in this
   * chromosome.
   *
   * @param a_index the a_index'th function to get
   * @return the function
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public int getFunction(int a_index) {
    for (int j = 0; j < getFunctions().length && getFunctions()[j] != null; j++) {
      if (getFunctions()[j].getArity(m_ind) != 0) {
        if (--a_index < 0) {
          return j;
        }
      }
    }
    return -1;
  }

  /**
   * Gets the a_index'th terminal of the given type in this chromosome. The nodes
   * are counted in a depth-first manner, with node 0 being the first terminal of
   * the given type in this chromosome.
   *
   * @param a_index the a_index'th terminal to get
   * @param a_type the type of terminal to get
   * @return the index of the terminal found, or -1 if no appropriate terminal
   * was found
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public int getTerminal(int a_index, Class a_type) {
    for (int j = 0; j < getFunctions().length && getFunctions()[j] != null; j++) {
      if (getFunctions()[j].getReturnType() == a_type
          && getFunctions()[j].getArity(m_ind) == 0) {
        if (--a_index < 0) {
          return j;
        }
      }
    }
    return -1;
  }

  /**
   * Gets the i'th function of the given type in this chromosome. The nodes are
   * counted in a depth-first manner, with node 0 being the first function of
   * the given type in this chromosome.
   *
   * @param a_index the i'th function to get
   * @param a_type the type of function to get
   * @return the index of the function found, or -1 if no appropriate function
   * was found
   * @author Klaus Meffert
   * @since 3.0
   */
  public int getFunction(int a_index, Class a_type) {
    for (int j = 0; j < getFunctions().length && getFunctions()[j] != null; j++) {
      if (getFunctions()[j].getReturnType() == a_type
          && getFunctions()[j].getArity(m_ind) != 0) {
        if (--a_index < 0) {
          return j;
        }
      }
    }
    return -1;
  }

  /**
   * Helper: Find GP command with given class and return index of it
   * @param a_n return the n'th found command
   * @param a_class the class to find a command for
   * @return index of first found matching GP command, or -1 if none found
   */
  public int getCommandOfClass(int a_n, Class a_class) {
    for (int j = 0; j < getFunctions().length && getFunctions()[j] != null; j++) {
      if (getFunctions()[j].getClass() == a_class) {
        if (--a_n < 0) {
          return j;
        }
      }
    }
    return -1;
  }

  /**
   * Helper: Find GP Variable with given return type and return index of it
   * @param a_n return the n'th found command
   * @param a_returnType the return type to find a Variable for
   * @return index of first found matching GP command, or -1 if none found
   */
  public int getVariableWithReturnType(int a_n, Class a_returnType) {
    for (int j = 0; j < getFunctions().length && getFunctions()[j] != null; j++) {
      if (getFunctions()[j].getClass() == Variable.class) {
        Variable v = (Variable) getFunctions()[j];
        if (v.getReturnType() == a_returnType) {
          if (--a_n < 0) {
            return j;
          }
        }
      }
    }
    return -1;
  }

  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].