gppopulation.java

一个开源的用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.*;

/**
 * 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.23 $";

  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;

  /*
   * @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!");
    }
    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;
    }
  }

  /*
   * @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++) {
      m_fitnessRank[i] = f;
      if (m_programs[i] != null) {
        f += m_programs[i].getFitnessValue();
      }
    }
  }

  /**
   * Creates a population using the ramped half-and-half method. Adapted from
   * JGProg.
   *
   * @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 {
    int divisor;
    if (m_popSize < 2) {
      divisor = 1;
    }
    else {
      divisor = m_popSize - 1;
    }
    for (int i = 0; i < m_popSize; i++) {
      IGPProgram program = null;
      // Vary depth dependent on run index.
      // ----------------------------------
      int depth = 2 + (getGPConfiguration().getMaxInitDepth() - 1) * i
          / divisor;
      // Create new GP program.
      // ----------------------
      int tries = 0;
      do {
        try {
          program = create(a_types, a_argTypes, a_nodeSets,
                           a_minDepths, a_maxDepths, depth, (i % 2) == 0,
                           a_maxNodes, a_fullModeAllowed, tries);
          if (i == 0) {
            // Remember a prototyp of a valid program in case generation
            // cannot find a valid program within some few tries
            // --> then clone the prototype.
            // Necessary if the maxNodes parameter is chosen small
            // or a validator is used which is quite restrictive.
            // ---------------------------------------------------
            getGPConfiguration().setPrototypeProgram(program);
          }
          else if (i % 5 == 0) {
            /**@todo set prototype to new value after each some evolutions*/
            double protoFitness = getGPConfiguration().getPrototypeProgram().
                getFitnessValue();
            if (protoFitness < program.getFitnessValue()) {
              getGPConfiguration().setPrototypeProgram(program);
            }
          }
          break;
        }
        catch (IllegalStateException iex) {
          tries++;
          if (tries > getGPConfiguration().getProgramCreationMaxtries()) {
            IGPProgram prototype = getGPConfiguration().getPrototypeProgram();
            if (prototype != null) {
              ICloneHandler cloner = getGPConfiguration().getJGAPFactory().
                  getCloneHandlerFor(prototype, null);
              if (cloner != null) {
                try {
                  program = (IGPProgram) cloner.perform(prototype, null, null);
                  LOGGER.warn("Prototype program reused because random"
                              + " program did not satisfy constraints");
                  break;
                }
                catch (Exception ex) {
                  // Rethrow original error.
                  // -----------------------
                  throw iex;
                }
              }
              else {
                LOGGER.warn("Warning: no clone handler found for"
                            + " prototype program type "
                            + prototype);
              }
            }
            // Rethrow original error.
            // -----------------------
            throw iex;
          }
        }
      }
      while (true);
      setGPProgram(i, program);
    }
    setChanged(true);
  }

  /**
   * Creates a complete, valid ProgramChromosome.
   *
   * @param a_types the type of each chromosome, the length
   * is 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_depth the maximum depth of the program to create
   * @param a_grow true: grow mode, false: full mode
   * @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)
   * @return ProgramChromosome
   * @throws InvalidConfigurationException
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public IGPProgram create(Class[] a_types, Class[][] a_argTypes,
                           CommandGene[][] a_nodeSets, int[] a_minDepths,
                           int[] a_maxDepths, int a_depth, boolean a_grow,
                           int a_maxNodes, boolean[] a_fullModeAllowed,
                           int a_tries)
      throws InvalidConfigurationException {
    GPProgram program;
    // Is there a fit program to be injected?
    // --------------------------------------
    if (m_fittestToAdd != null) {
      ICloneHandler cloner = getGPConfiguration().getJGAPFactory().
          getCloneHandlerFor(m_fittestToAdd, null);
      if (cloner == null) {
        program = (GPProgram) m_fittestToAdd;
      }
      else {
        try {
          program = (GPProgram) cloner.perform(m_fittestToAdd, null, null);
        }
        catch (Exception ex) {
          ex.printStackTrace();
          program = (GPProgram) m_fittestToAdd;
        }
      }
      m_fittestToAdd = null;
    }
    else {
      // Create new GP program.
      // ----------------------
      program = new GPProgram(getGPConfiguration(), a_types,
                              a_argTypes, a_nodeSets, a_minDepths, a_maxDepths,
                              a_maxNodes);
      program.growOrFull(a_depth, a_grow, a_maxNodes, a_fullModeAllowed,
                         a_tries);
    }
    return program;
  }

  /**
   * @return fixed size of the population
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public int getPopSize() {
    return m_popSize;
  }

  /**