gppopulation.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.io.*;
import java.util.*;
import org.jgap.*;
import org.jgap.gp.*;
import org.apache.log4j.*;
import org.jgap.util.*;

/**
 * Population for GP programs.
 *
 * @author Klaus Meffert
 * @since 3.0
 */
public class GPPopulation
    implements Serializable, Comparable {
  /** String containing the CVS revision. Read out via reflection!*/
  private final static String CVS_REVISION = "$Revision: 1.39 $";

  final static String GPPROGRAM_DELIMITER_HEADING = "<";

  final static String GPPROGRAM_DELIMITER_CLOSING = ">";

  final static String GPPROGRAM_DELIMITER = "#";

  public final static double DELTA = 0.0000001d;

  private transient Logger LOGGER = Logger.getLogger(GPPopulation.class);

  /**
   * The array of GPProgram's that make-up the Genotype's population.
   */
  private IGPProgram[] m_programs;

  private
  /*transient*/ float[] m_fitnessRank;

  private int m_popSize;

  private transient IGPProgram m_fittestProgram;

  private GPConfiguration m_config;

  /**
   * Indicates whether at least one of the programs has been changed
   * (deleted, added, modified).
   */
  private boolean m_changed;

  /**
   * Indicates that the list of GPPrograms has been sorted.
   */
  private boolean m_sorted;

  private IGPProgram m_fittestToAdd;

  /**
   * Default constructor, only for dynamic instantiation.
   *
   * @throws Exception
   *
   * @author Klaus Meffert
   * @since 3.3.4
   */
  public GPPopulation()
      throws Exception {
  }

  /*
   * @param a_config the configuration to use.
   * @param a_size the maximum size of the population in GPProgram unit
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public GPPopulation(GPConfiguration a_config, int a_size)
      throws InvalidConfigurationException {
    if (a_config == null) {
      throw new InvalidConfigurationException("Configuration must not be null!");
    }
    if (a_size < 1) {
      throw new InvalidConfigurationException(
          "Population size must be greater zero!");
    }
    m_config = a_config;
    m_programs = new GPProgram[a_size];
    m_popSize = a_size;
    m_fitnessRank = new float[a_size];
    for (int i = 0; i < a_size; i++) {
      m_fitnessRank[i] = 0.5f;
    }
  }

  /*
   * Instantiate new population with parameters from other population.
   * Don't copy the GPProgram instances from the given population!
   *
   * @param a_pop the population to retrieve the parameters from
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public GPPopulation(GPPopulation a_pop)
      throws InvalidConfigurationException {
    this(a_pop, false);
  }

  /**
   *
   * @param a_pop the population to retrieve the parameters from
   * @param a_keepPrograms true copy programs of given population to this one
   * @throws InvalidConfigurationException
   *
   * @author Klaus Meffert
   */
  public GPPopulation(GPPopulation a_pop, boolean a_keepPrograms)
      throws InvalidConfigurationException {
    m_config = a_pop.getGPConfiguration();
    m_popSize = a_pop.getPopSize();
    m_programs = new GPProgram[m_popSize];
    m_fitnessRank = new float[m_popSize];
    if (a_keepPrograms) {
      synchronized (m_programs) {
        for (int i = 0; i < m_popSize; i++) {
          m_programs[i] = a_pop.getGPProgram(i);
          m_fitnessRank[i] = a_pop.getFitnessRank(i);
        }
      }
      m_fittestProgram = a_pop.determineFittestProgramComputed();
      if (m_fittestProgram != null) {
        m_fittestProgram = (IGPProgram) m_fittestProgram.clone();
      }
      setChanged(a_pop.isChanged());
      if (!m_changed) {
        m_sorted = true;
      }
    }
    else {
      for (int i = 0; i < m_popSize; i++) {
        m_fitnessRank[i] = 0.5f;
      }
    }
  }

  /**
   * Sorts the population into "ascending" order using some criterion for
   * "ascending". A Comparator is given which will compare two individuals,
   * and if one individual compares lower than another individual, the first
   * individual will appear in the population before the second individual.
   *
   * @param c the Comparator to use
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public void sort(Comparator c) {
    Arrays.sort(m_programs, c);
    float f = 0;
    for (int i = 0; i < m_programs.length; i++) {
      if (m_fitnessRank.length > i) {
        m_fitnessRank[i] = f;
      }
      if (m_programs[i] != null) {
        f += m_programs[i].getFitnessValue();
      }
    }
  }

  /**
   * Creates a population.
   *
   * @param a_types the type for each chromosome, the length of the array
   * represents the number of chromosomes
   * @param a_argTypes the types of the arguments to each chromosome, must be an
   * array of arrays, the first dimension of which is the number of chromosomes
   * and the second dimension of which is the number of arguments to the
   * chromosome
   * @param a_nodeSets the nodes which are allowed to be used by each chromosome,
   * must be an array of arrays, the first dimension of which is the number of
   * chromosomes and the second dimension of which is the number of nodes
   * @param a_minDepths contains the minimum depth allowed for each chromosome
   * @param a_maxDepths contains the maximum depth allowed for each chromosome
   * @param a_maxNodes reserve space for a_maxNodes number of nodes
   * @param a_fullModeAllowed array of boolean values. For each chromosome there
   * is one value indicating whether the full mode for creating chromosome
   * generations during evolution is allowed (true) or not (false)
   * @throws InvalidConfigurationException
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public void create(Class[] a_types, Class[][] a_argTypes,
                     CommandGene[][] a_nodeSets, int[] a_minDepths,
                     int[] a_maxDepths, int a_maxNodes,
                     boolean[] a_fullModeAllowed)
      throws InvalidConfigurationException {
    create(a_types, a_argTypes, a_nodeSets, a_minDepths, a_maxDepths,
           a_maxNodes, a_fullModeAllowed, new DefaultProgramCreator());
  }

  /**
   * Creates a population.
   *
   * @param a_types the type for each chromosome, the length of the array
   * represents the number of chromosomes
   * @param a_argTypes the types of the arguments to each chromosome, must be an
   * array of arrays, the first dimension of which is the number of chromosomes
   * and the second dimension of which is the number of arguments to the
   * chromosome
   * @param a_nodeSets the nodes which are allowed to be used by each chromosome,
   * must be an array of arrays, the first dimension of which is the number of
   * chromosomes and the second dimension of which is the number of nodes
   * @param a_minDepths contains the minimum depth allowed for each chromosome
   * @param a_maxDepths contains the maximum depth allowed for each chromosome
   * @param a_maxNodes reserve space for a_maxNodes number of nodes
   * @param a_fullModeAllowed array of boolean values. For each chromosome there
   * is one value indicating whether the full mode for creating chromosome
   * generations during evolution is allowed (true) or not (false)
   * @param a_programCreator service to create new programs with
   * @throws InvalidConfigurationException
   *
   * @author Klaus Meffert
   * @since 3.2.2
   */
  public void create(Class[] a_types, Class[][] a_argTypes,
                     CommandGene[][] a_nodeSets, int[] a_minDepths,
                     int[] a_maxDepths, int a_maxNodes,
                     boolean[] a_fullModeAllowed,
                     IProgramCreator a_programCreator)
      throws InvalidConfigurationException {
    create(a_types, a_argTypes, a_nodeSets, a_minDepths, a_maxDepths,
           a_maxNodes, a_fullModeAllowed, a_programCreator, 0);
  }

  /**
   * Creates a population.
   *
   * @param a_types the type for each chromosome, the length of the array
   * represents the number of chromosomes
   * @param a_argTypes the types of the arguments to each chromosome, must be an
   * array of arrays, the first dimension of which is the number of chromosomes
   * and the second dimension of which is the number of arguments to the
   * chromosome
   * @param a_nodeSets the nodes which are allowed to be used by each chromosome,
   * must be an array of arrays, the first dimension of which is the number of
   * chromosomes and the second dimension of which is the number of nodes
   * @param a_minDepths contains the minimum depth allowed for each chromosome
   * @param a_maxDepths contains the maximum depth allowed for each chromosome
   * @param a_maxNodes reserve space for a_maxNodes number of nodes
   * @param a_fullModeAllowed array of boolean values. For each chromosome there
   * is one value indicating whether the full mode for creating chromosome
   * generations during evolution is allowed (true) or not (false)
   * @param a_programCreator service to create new programs with
   * @param a_offset start index for new programs to put into the configuration
   *
   * @throws InvalidConfigurationException
   *
   * @author Klaus Meffert
   * @since 3.3.3
   */
  public void create(Class[] a_types, Class[][] a_argTypes,
                     CommandGene[][] a_nodeSets, int[] a_minDepths,
                     int[] a_maxDepths, int a_maxNodes,
                     boolean[] a_fullModeAllowed,
                     IProgramCreator a_programCreator,
                     int a_offset)
      throws InvalidConfigurationException {
    int divisor;
    if (m_popSize < 2) {
      divisor = 1;
    }
    else {
      divisor = m_popSize - 1;
    }
    int genNr = getGPConfiguration().getGenerationNr();
    int genI = new Random().nextInt(m_popSize);
    RandomGenerator generator = getGPConfiguration().getRandomGenerator();
    int minDepth = getGPConfiguration().getMinInitDepth();
    int maxDepth = getGPConfiguration().getMaxInitDepth();
    for (int i = a_offset; i < m_popSize; i++) {
      IGPProgram program = null;
      // Vary depth dependent on run index.
      // ----------------------------------
      /**@todo add element of randomness*/
      int depth = minDepth
          + (maxDepth - minDepth) * i
          / divisor;

      // Create new GP program.
      // ----------------------
      int tries = 0;
      int maxTries = getGPConfiguration().getProgramCreationMaxtries();
      do {
        try {
          // Randomize grow option as growing produces a valid program
          // more likely than the full mode.
          // ---------------------------------------------------------
          boolean grow;
          if (i % 2 == 0 || generator.nextInt(8) > 6) {
            grow = true;
          }
          else {
            grow = false;
          }
          program = create(i, a_types, a_argTypes, a_nodeSets,
                           a_minDepths, a_maxDepths, depth, grow,
                           a_maxNodes, a_fullModeAllowed, tries,
                           a_programCreator);
          if (program != null && getGPConfiguration().getPrototypeProgram() == null) {
            // Remember a prototyp of a valid program in case generation
            // cannot find a valid program within some few tries