programchromosome.java

JGAP是一种遗传算法和遗传规划的组成部分提供了一个Java框架。它提供了基本的遗传机制

    }
    if (m_genes[a_startNode].getArity(ind) == 1 || paramOutput) {
      str += getFunctions()[a_startNode].toString();
    }
    if (a_startNode > 0) {
      str = "(" + str;
    }
    for (int i = 0; i < m_genes[a_startNode].getArity(ind); i++) {
      String childString = toStringNorm(getChild(a_startNode, i));
      String placeHolder = "&" + (i + 1);
      int placeholderIndex = str.indexOf(placeHolder);
      if (placeholderIndex >= 0) {
        str = str.replaceFirst(placeHolder, childString);
      }
      else {
        str += childString;
      }
      if (i == 0 && m_genes[a_startNode].getArity(ind) != 1
          && !paramOutput) {
        str += " " + m_genes[a_startNode].toString() + " ";
      }
    }
    if (a_startNode > 0) {
      str += ")";
    }
    return str;
  }

  /**
   * @return business key of the chromosome
   *
   * @author Klaus Meffert
   * @since 3.4
   */
  public String getBusinessKey() {
    return toStringNorm(0);
  }

  /**
   * @return debug representation of progrm chromosome, containing class names
   * of all children
   *
   * @author Klaus Meffert
   * @since 3.4
   */
  public String toStringDebug() {
    IGPProgram ind = getIndividual();
    if (m_genes[0].getArity(ind) == 0) {
      return getClass().getName();
    }
    String s = "";
    for (int i = 0; i < m_genes[0].getArity(ind); i++) {
      String childString = toStringNorm(getChild(0, i));
      s = s + "<" + childString + " >";
    }
    return s;
  }

  /**
   * Determines whether there exists a function or terminal in the given node
   * set with the given return and sub return type.
   *
   * @param a_returnType the return type to look for
   * @param a_subReturnType the sub return type to look for
   * @param a_nodeSet the array of nodes to look through
   * @param a_function true to look for a function, false to look for a terminal
   * @param a_growing true: grow mode, false: full mode
   *
   * @return true if such a node exists, false otherwise
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public boolean isPossible(Class a_returnType, int a_subReturnType,
                            CommandGene[] a_nodeSet,
                            boolean a_function, boolean a_growing) {
    IGPProgram ind = getIndividual();
    for (int i = 0; i < a_nodeSet.length; i++) {
      if (a_nodeSet[i].getReturnType() == a_returnType
          && (a_subReturnType == 0
              || a_subReturnType == a_nodeSet[i].getSubReturnType())) {
        if (a_nodeSet[i].getArity(ind) == 0 && (!a_function || a_growing)) {
          return true;
        }
        if (a_nodeSet[i].getArity(ind) != 0 && a_function) {
          return true;
        }
      }
    }
    return false;
  }

  /**
   * 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 (depth "
          + getDepth(0)
          + ", 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 (when called
   * recursively a_validateNode is set to true)
   *
   * @return possible modified set of functions (e.g. to avoid having a unique
   * command more than once)
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  protected CommandGene[] 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) {
    boolean mutated = false;
    boolean uncloned = true;
    GPConfiguration conf = getGPConfiguration();
    RandomGenerator random = conf.getRandomGenerator();
    if (a_rootNode == null || a_validateNode) {
      int tries = 0;
      int evolutionRound = getGPConfiguration().getGenerationNr();
      boolean aFunction = a_depth >= 1;
      // Clone the array, not the content of the array.
      // ----------------------------------------------
      CommandGene[] localFunctionSet = (CommandGene[]) a_functionSet.clone();
      do {
        CommandGene node = selectNode(a_num, a_returnType, a_subReturnType,
                                      localFunctionSet, aFunction, a_grow);
        if (!conf.validateNode(this, node, a_rootNode, tries++, a_num,
                               a_recurseLevel, a_returnType, localFunctionSet,
                               a_depth, a_grow, a_childNum, false)) {
          // In the first round of evolution ensure to always have one valid
          // individual as we need a prototype for cloning!
          // ---------------------------------------------------------------
          if (evolutionRound > 0 || tries <= 10) {
            // 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;
          }
        }
        // Optionally use a mutant/clone of the originally selected command
        // instead of reusing the same command instance.
        // ----------------------------------------------------------------
        if (random.nextDouble() <= conf.getMutationProb()) {
          if (IMutateable.class.isAssignableFrom(node.getClass())) {
            try {
              CommandGene node2 = ( (IMutateable) node).applyMutation(0,
                  random.nextDouble());
              // Check if mutant's function is allowed.
              // --------------------------------------
              if (getCommandOfClass(0, node2.getClass()) >= 0) {
                mutated = true;
                if (node2 != node) {
                  node = node2;
                  uncloned = false;
                }
              }
            } catch (InvalidConfigurationException iex) {
              // Ignore but log.
              // ---------------
              LOGGER.warn("Ignored problem", iex);
            }
          }
        }
        // Avoid using commands more than once if allowed only once.
        // ---------------------------------------------------------
        if (IUniqueCommand.class.isAssignableFrom(node.getClass())) {
          a_functionSet = remove(a_functionSet, node);
        }
        a_rootNode = node;
        break;
      } while (true);
    }
    // Generate the new node.
    // ----------------------
    m_depth[m_index] = m_maxDepth - a_depth;
    // Optional dynamize the arity for commands with a flexible number
    // of children. Normally, dynamizeArity does nothing, see declaration
    // of method in CommandGene, which can be overridden in sub classes.
    // -------------------------------------------------------------------
    boolean dynamize = random.nextDouble() <= conf.getDynamizeArityProb();
    if (dynamize) {
      a_rootNode.dynamizeArity();
    }
    // Clone node if possible and not already done via mutation.
    // ---------------------------------------------------------
    if (uncloned && !conf.isNoCommandGeneCloning()
        && a_rootNode instanceof ICloneable) {
        /**@todo we could optionally use the clone handler*/
      a_rootNode = (CommandGene) ( (ICloneable) a_rootNode).clone();
      m_genes[m_index++] = a_rootNode;
    }
    else {
      m_genes[m_index++] = a_rootNode;
    }
    if (a_depth >= 1) {
      IGPProgram ind = getIndividual();
      int arity = a_rootNode.getArity(ind);
      for (int i = 0; i < arity; i++) {
        // Ensure required depth is cared about.
        // -------------------------------------
        if (m_index < m_depth.length) {
          a_functionSet = 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"
              + " (current arity: "
              + i
              + ", overall arity: "
              + arity
              + ")!");
        }
      }
    }
    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)");
      }
    }
    return a_functionSet;
  }

  /**
   * 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
                                      + " (command gene is null)");
    }
    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);