programchromosome.java

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

/*
 * This file is part of JGAP.
 *
 * JGAP offers a dual license model containing the LGPL as well as the MPL.
 *
 * For licencing information please see the file license.txt included with JGAP
 * or have a look at the top of class org.jgap.Chromosome which representatively
 * includes the JGAP license policy applicable for any file delivered with JGAP.
 */
package org.jgap.gp.impl;

import java.io.*;
import org.jgap.*;
import org.jgap.gp.terminal.*;
import org.jgap.gp.function.*;

import org.jgap.gp.*;

/**
 * Chromosome representing a single GP Program.
 *
 * @author Klaus Meffert
 * @since 3.0
 */
public class ProgramChromosome
    //    extends BaseGPChromosome
    // implements IGPChromosome
    implements Serializable
{
  /** String containing the CVS revision. Read out via reflection!*/
  private final static String CVS_REVISION = "$Revision: 1.2 $";

  /*wodka:
   void add(Command cmd);
   java.util.Iterator commands();
   Interpreter interpreter();
   Program createEmptyChildProgram();
   SodaGlobals getGlobals();
   void setGlobals(SodaGlobals globals);
   Language getLanguage();
   */

  /**
   * The allowable function/terminal list.
   */
  private transient CommandGene[] m_functionSet;

  /**
   * Array to hold the depths of each node.
   */
  private int[] m_depth;

  /**
   * Array to hold the types of the arguments to this Chromosome.
   */
  private Class[] argTypes;

  private transient int m_index;

  private transient int m_maxDepth;

  private IGPProgram m_ind;

  /**
   * The array of genes contained in this chromosome.
   */
  private CommandGene[] m_genes;

  /**
   * The configuration object to use
   */
  private /*transient*/ GPConfiguration m_configuration;

  /**
   * Application-specific data that is attached to this Chromosome.
   * This data may assist the application in evaluating this Chromosome
   * in the fitness function. JGAP does not operate on the data, aside
   * from allowing it to be set and retrieved, and considering it with
   * comparations (if user opted in to do so).
   */
  private Object m_applicationData;

  /**
   * Method compareTo(): Should we also consider the application data when
   * comparing? Default is "false" as "true" means a Chromosome's losing its
   * identity when application data is set differently!
   *
   * @since 3.0
   */
  private boolean m_compareAppData;

  public ProgramChromosome(GPConfiguration a_configuration, int a_size,
                           IGPProgram a_ind)
      throws InvalidConfigurationException {
    if (a_size <= 0) {
      throw new IllegalArgumentException(
          "Chromosome size must be greater than zero");
    }
    if (a_configuration == null) {
      throw new InvalidConfigurationException(
          "Configuration to be set must not"
          + " be null!");
    }
    m_configuration = a_configuration;
    m_ind = a_ind;
    init(a_size);
  }

  public ProgramChromosome(GPConfiguration a_configuration, int a_size,
                           CommandGene[] a_functionSet,
                           Class[] a_argTypes,
                           IGPProgram a_ind)
      throws InvalidConfigurationException {
    if (a_size <= 0) {
      throw new IllegalArgumentException(
          "Chromosome size must be greater than zero");
    }
    if (a_configuration == null) {
      throw new InvalidConfigurationException(
          "Configuration to be set must not"
          + " be null!");
    }
    m_configuration = a_configuration;
    m_ind = a_ind;
    m_functionSet = a_functionSet;
    argTypes = a_argTypes;
    init();
  }

  public ProgramChromosome(GPConfiguration a_configuration,
                           CommandGene[] a_initialGenes)
      throws InvalidConfigurationException {
    if (a_configuration == null) {
      throw new InvalidConfigurationException(
          "Configuration to be set must not"
          + " be null!");
    }
    m_configuration = a_configuration;
    int i = 0;
    while (i < a_initialGenes.length && a_initialGenes[i] != null) {
      i++;
    }
    CommandGene[] genes = new CommandGene[i];
    for (int k = 0; k < i; k++) {
      genes[k] = a_initialGenes[k];
    }
    init(a_initialGenes.length);
  }

  public void setArgTypes(Class[] a_argTypes) {
    argTypes = a_argTypes;
  }

  /**
   * Default constructor.
   * @throws InvalidConfigurationException
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public ProgramChromosome()
      throws InvalidConfigurationException {
    this(GPGenotype.getGPConfiguration());
  }

  public ProgramChromosome(final GPConfiguration a_conf)
      throws InvalidConfigurationException {
    if (a_conf == null) {
      throw new InvalidConfigurationException(
          "Configuration to be set must not"
          + " be null!");
    }
    m_configuration = a_conf;
    init();
  }

  private void init()
      throws InvalidConfigurationException {
    init(getGPConfiguration().getPopulationSize());
  }

  private void init(final int a_size)
      throws InvalidConfigurationException {
    m_depth = new int[a_size];
    setFunctions(new CommandGene[a_size]);
  }

  public synchronized Object clone() {
    try {
      ProgramChromosome chrom = new ProgramChromosome( (GPConfiguration)
          getGPConfiguration(), (CommandGene[]) m_genes.clone());
      chrom.argTypes = (Class[]) argTypes.clone();
      chrom.setFunctionSet( (CommandGene[]) getFunctionSet().clone());
      chrom.setFunctions( (CommandGene[]) getFunctions().clone());
      chrom.m_depth = (int[]) m_depth.clone();
      return chrom;
    }
    catch (Exception cex) {
      // rethrow to have a more convenient handling
      throw new IllegalStateException(cex.getMessage());
    }
  }

  public void cleanup() {
    cleanup(0);
  }

  protected void cleanup(final int n) {
    if (n < 0) {
      return;
    }
    for (int i = 0; i < getFunctions()[n].getArity(m_ind); i++) {
      cleanup(getChild(n, i));
    }
    getFunctions()[n].cleanup();
  }

  public void addCommand(final CommandGene a_command)
      throws InvalidConfigurationException {
    if (a_command == null) {
      throw new IllegalArgumentException("Command may not be null!");
    }
    final int len = m_genes.length;
    CommandGene[] genes = new CommandGene[len + 1];
    System.arraycopy(m_genes, 0, genes, 0, len);
    m_genes[len] = a_command;
  }

  /**
   * Initialize this chromosome using the grow or the full method.
   *
   * @param a_num the chromosome's index in the individual of this chromosome
   * @param depth the maximum depth of the chromosome to create
   * @param type the type of the chromosome to create
   * @param a_argTypes the array of types of arguments for this chromosome
   * @param a_functionSet the set of nodes valid to pick from
   * @param a_grow true: use grow method; false: use full method
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public void growOrFull(final int a_num, final int depth, final Class type,
                   final Class[] a_argTypes, final CommandGene[] a_functionSet,
                   boolean a_grow) {
    try {
      argTypes = a_argTypes;
      setFunctionSet(new CommandGene[a_functionSet.length + a_argTypes.length]);
      System.arraycopy(a_functionSet, 0, getFunctionSet(), 0,
                       a_functionSet.length);
      for (int i = 0; i < a_argTypes.length; i++) {
        m_functionSet[a_functionSet.length + i]
            = new Argument(getGPConfiguration(), i, a_argTypes[i]);
      }
      /**@todo init is experimental, make dynamic*/
      // Initialization of genotype according to specific problem requirements.
      // ----------------------------------------------------------------------
      CommandGene n = null;
      if (a_num == 0 && false) {
        for (int i = 0; i < m_functionSet.length; i++) {
          CommandGene m = m_functionSet[i];
          if (m.getClass() == SubProgram.class) {
            n = m;
            break;
          }
        }
      }
      else if (a_num == 1 && false) {
        for (int i = 0; i < m_functionSet.length; i++) {
          CommandGene m = m_functionSet[i];
          if (m.getClass() == ForLoop.class) {
            n = m;
            break;
          }
        }
      }
      int tries = 0;
      int localDepth = depth;
      do {
        m_index = 0;
        m_maxDepth = localDepth;
        try {
          growOrFullNode(a_num, localDepth, type, m_functionSet, n, 0, a_grow);
          redepth();
          break;
        } catch (IllegalStateException iex) {
          tries++;
          if (tries >= getGPConfiguration().getProgramCreationMaxtries()) {
            throw new IllegalArgumentException(iex.getMessage());
          }
          // Clean up genes for next try.
          // ----------------------------
          for (int j = 0; j < size(); j++) {
            if (m_genes[j] == null) {
              break;
            }
            m_genes[j] = null;
          }
          localDepth++;
        }
      } while (true);
    }
    catch (InvalidConfigurationException iex) {
      throw new IllegalStateException(iex.getMessage());
    }
  }

  /**
   * Output program in left-hand notion (e.g.: "+ X Y" for "X + Y")
   * @param a_startNode node to start with
   * @return output in left-hand notion
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public String toString(final int a_startNode) {
    if (a_startNode < 0) {
      return "";
    }
    // Replace any occurance of placeholders (e.g. &1, &2...) in the function's
    // name.
    // ------------------------------------------------------------------------
    String funcName = getFunctions()[a_startNode].getName();
    int j = 1;
    do {
      String placeHolder = "&" + j;
      int foundIndex = funcName.indexOf(placeHolder);
      if (foundIndex < 0) {
        break;
      }
      funcName = funcName.replaceFirst(placeHolder, "");
      j++;
    }
    while (true);
    // Now remove any leading and trailing spaces.
    // -------------------------------------------
    if (j > 0) {
      funcName = funcName.trim();
    }
    if (getFunctions()[a_startNode].getArity(m_ind) == 0) {
      return funcName + " ";
    }
    String str = "";
    str += funcName + " ( ";
    for (int i = 0; i < getFunctions()[a_startNode].getArity(m_ind); i++) {
      str += toString(getChild(a_startNode, i));
    }
    if (a_startNode == 0) {
      str += ")";
    }
    else {
      str += ") ";
    }
    return str;
  }

  /**
   * Output program in "natural" notion (e.g.: "X + Y" for "X + Y")
   * @param a_startNode the node to start with
   * @return output in normalized notion
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public String toStringNorm(final int a_startNode) {
    if (a_startNode < 0) {
      return "";
    }
    if (getFunctions()[a_startNode].getArity(m_ind) == 0) {
      return getFunctions()[a_startNode].getName();
    }
    String str = "";
    boolean paramOutput = false;
    if (getFunctions()[a_startNode].getArity(m_ind) > 0) {
      if (getFunctions()[a_startNode].getName().indexOf("&1") >= 0) {
        paramOutput = true;
      }
    }
    if (getFunctions()[a_startNode].getArity(m_ind) == 1 || paramOutput) {
      str += getFunctions()[a_startNode].getName();
    }
    if (a_startNode > 0) {
      str = "(" + str;
    }
    for (int i = 0; i < getFunctions()[a_startNode].getArity(m_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 && getFunctions()[a_startNode].getArity(m_ind) != 1 && !paramOutput) {
        str += " " + getFunctions()[a_startNode].getName() + " ";
      }
    }
    if (a_startNode > 0) {
      str += ")";
    }
    return str;
  }

  /**
   * Determines whether there exists a function or terminal in the given node
   * set with the given type.
   *
   * @param a_type the 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_type, CommandGene[] a_nodeSet,
                            boolean a_function, boolean a_growing) {
    for (int i = 0; i < a_nodeSet.length; i++) {
      if (a_nodeSet[i].getReturnType() == a_type) {
        if (a_nodeSet[i].getArity(m_ind) == 0 && (!a_function || a_growing)) {
          return true;
        }
        if (a_nodeSet[i].getArity(m_ind) != 0 && a_function) {
          return true;
        }
      }
    }
    return false;
  }

  /**
   * Randomly chooses a valid node from the functions set.
   *
   * @param a_type the type of node to choose
   * @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(Class a_type, CommandGene[] a_functionSet,
                                   boolean a_function, boolean a_growing) {
    if (!isPossible(a_type, a_functionSet, a_function, a_growing)) {
      final String errormsg = "Chromosome requires a " +
          (a_function ?
           ("function" + (a_growing ? " or terminal" : ""))
           : "terminal") + " of type " +
          a_type + " but there is no such node available";
      if (!getGPConfiguration().isStrictProgramCreation()) {
        throw new IllegalStateException(errormsg);