programchromosome.java

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

/*
 * This file is part of JGAP.
 *
 * JGAP offers a dual license model containing the LGPL as well as the MPL.
 *
 * For licensing 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.lang.reflect.*;
import java.util.*;
import org.apache.log4j.*;
import org.jgap.*;
import org.jgap.gp.*;
import org.jgap.gp.terminal.*;
import org.jgap.util.*;

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

  final static String PERSISTENT_FIELD_DELIMITER = ":";

  final static String GENE_DELIMITER_HEADING = "<";

  final static String GENE_DELIMITER_CLOSING = ">";

  final static String GENE_DELIMITER = "#";

  private transient static Logger LOGGER = Logger.getLogger(ProgramChromosome.class);

  /**
   * The list of allowed functions/terminals.
   */
  private 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_conf, int a_size)
      throws InvalidConfigurationException {
    super(a_conf);
    if (a_size <= 0) {
      throw new IllegalArgumentException(
          "Chromosome size must be greater than zero");
    }
    init(a_size);
  }

  public ProgramChromosome(GPConfiguration a_conf, int a_size,
                           IGPProgram a_ind)
      throws InvalidConfigurationException {
    super(a_conf, a_ind);
    if (a_size <= 0) {
      throw new IllegalArgumentException(
          "Chromosome size must be greater than zero");
    }
    if (a_ind == null) {
      throw new IllegalArgumentException("Individual must not be null");
    }
    init(a_size);
  }

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

  public ProgramChromosome(GPConfiguration a_conf, CommandGene[] a_initialGenes)
      throws InvalidConfigurationException {
    super(a_conf);
    int i = 0;
    while (i < a_initialGenes.length && a_initialGenes[i] != null) {
      i++;
    }
    init(a_initialGenes.length);
    for (int k = 0; k < i; k++) {
      m_genes[k] = a_initialGenes[k];
    }
  }

  public ProgramChromosome(final GPConfiguration a_conf)
      throws InvalidConfigurationException {
    super(a_conf);
    init();
  }

  /**
   * Default constructor. Only use for 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 is speedup possible by using dynamic list?*/
  }

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

  public synchronized Object clone() {
    try {
      int size = m_genes.length;
      CommandGene[] genes = new CommandGene[size];
      for (int i = 0; i < size; i++) {
        if (m_genes[i] == null) {
          break;
        }
        // Try deep clone of genes.
        // ------------------------
        if (ICloneable.class.isAssignableFrom(m_genes[i].getClass())) {
          genes[i] = (CommandGene) ( (ICloneable) m_genes[i]).clone();
        }
        else {
          // No deep clone possible.
          // -----------------------
          genes[i] = m_genes[i];
        }
      }
      ProgramChromosome chrom = new ProgramChromosome( (GPConfiguration)
          getGPConfiguration(), (CommandGene[]) genes);
      chrom.argTypes = (Class[]) argTypes.clone();
      if (getFunctionSet() != null) {
        chrom.setFunctionSet( (CommandGene[]) getFunctionSet().clone());
      }
      if (m_depth != null) {
        chrom.m_depth = (int[]) m_depth.clone();
      }
      chrom.setIndividual(getIndividual());
      return chrom;
    } catch (Exception cex) {
      // Rethrow to have a more convenient handling.
      // -------------------------------------------
      throw new IllegalStateException(cex);
    }
  }

  /**
   * 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 argument types 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
   * @param a_tries maximum number of tries to create a valid program
   *
   * @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,
                         int a_tries) {
    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]);
      }
      // Initialization of genotype according to specific problem requirements.
      // ----------------------------------------------------------------------
      CommandGene n;
      IGPInitStrategy programIniter = getGPConfiguration().getInitStrategy();
      if (programIniter == null) {
        n = null;
      }
      else {
        try {
          n = programIniter.init(this, a_num);
        } catch (Exception ex) {
          throw new IllegalStateException(ex);
        }
      }
      // Build the (rest of the) GP program.
      // -----------------------------------
      int localDepth = a_depth;
      m_index = 0;
      m_maxDepth = localDepth;
      growOrFullNode(a_num, localDepth, a_type, 0, m_functionSet, n, 0, a_grow,
                     -1, false);
      // Give the chance of validating the whole program.
      // ------------------------------------------------
      if (!getGPConfiguration().validateNode(this, null, n, a_tries,
          a_num, 0, a_type, m_functionSet,
          a_depth, a_grow, -1, true)) {
        throw new IllegalStateException("Randomly created program violates"
                                        +
                                        " configuration constraints (symptom 3).");
      }
      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, e.g. 0 for a complete dump of
   * the program
   * @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;
      }