programchromosome.java

来自「jgap3.2 遗传算法工具包,嘿嘿,笨鸟先飞哦」· Java 代码 · 共 1,094 行 · 第 1/3 页

/*
 * 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.util.*;
import org.jgap.*;
import org.jgap.util.*;
import org.jgap.gp.terminal.*;
import org.jgap.gp.*;

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

  /**
   * The list of allowed functions/terminals.
   */
  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;

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

  /**
   * 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 {
    super(a_configuration, a_ind);
    if (a_size <= 0) {
      throw new IllegalArgumentException(
          "Chromosome size must be greater than zero");
    }
    init(a_size);
  }

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

  public ProgramChromosome(GPConfiguration a_configuration,
                           CommandGene[] a_initialGenes)
      throws InvalidConfigurationException {
    super(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 ProgramChromosome(final GPConfiguration a_conf)
      throws InvalidConfigurationException {
    super(a_conf);
    init();
  }

  /**
   * Default constructor. Only use with dynamic instantiation.
   *
   * @throws InvalidConfigurationException
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public ProgramChromosome()
      throws InvalidConfigurationException {
    this(GPGenotype.getStaticGPConfiguration());
  }

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

  private void init(final int a_size)
      throws InvalidConfigurationException {
    m_depth = new int[a_size];
    m_genes = new CommandGene[a_size];
        /**@todo speedup possible by using dynamic list?*/
  }

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

  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());
    }
  }

  /**
   * Clean up the chromosome.
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public void cleanup() {
    int len = m_genes.length;
    for (int i = 0; i < len; i++) {
      if (m_genes[i] == null) {
        break;
      }
      m_genes[i].cleanup();
    }
  }

  /**
   * Initialize this chromosome 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 chromosome to create
   * @param a_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 a_depth, final Class a_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 make init as below dynamic/configurable*/
      // 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 localDepth = a_depth;
      m_index = 0;
      m_maxDepth = localDepth;
      growOrFullNode(a_num, localDepth, a_type, 0, m_functionSet, n, 0, a_grow,
                     -1, true);
      redepth();
    } 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 = m_genes[a_startNode].toString();
    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();
    }
    IGPProgram ind = getIndividual();
    if (getFunctions()[a_startNode].getArity(ind) == 0) {
      return funcName + " ";
    }
    String str = "";
    str += funcName + " ( ";
    int arity = m_genes[a_startNode].getArity(ind);
    for (int i = 0; i < arity; 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 "";
    }
    IGPProgram ind = getIndividual();
    if (m_genes[a_startNode].getArity(ind) == 0) {
      return getFunctions()[a_startNode].toString();
    }
    String str = "";
    boolean paramOutput = false;
    if (m_genes[a_startNode].getArity(ind) > 0) {
      if (m_genes[a_startNode].toString().indexOf("&1") >= 0) {
        paramOutput = true;
      }
    }
    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;
  }

  /**
   * 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;