gpgenotype.java

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

   * @param a_evolutions number of evolution
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public void evolve(int a_evolutions) {
    getGPPopulation().sort(new GPFitnessComparator());
    // Here, we could do threading.
    for (int i = 0; i < a_evolutions; i++) {
      calcFitness();
      if (m_bestFitness < 0.000001) {
        // Optimal solution found, quit.
        // -----------------------------
        return;
      }
      if(m_verbose) {
        if (i % 25 == 0) { /**@todo make configurable --> use listener*/
          System.out.println("Evolving generation " + i
                             + ", memory free: " + getFreeMemoryMB() + " MB");
        }
      }
      evolve();
    }
    calcFitness();
  }

  /**
   * Calculates the fitness value of all programs, of the best solution as
   * well as the total fitness (sum of all fitness values).
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public void calcFitness() {
    double totalFitness = 0.0d;
    GPPopulation pop = getGPPopulation();
    for (int i = 0; i < pop.size() && pop.getGPProgram(i) != null; i++) {
      IGPProgram program = pop.getGPProgram(i);
      totalFitness += program.getFitnessValue();
    }
    m_totalFitness = totalFitness;
    IGPProgram best = pop.determineFittestProgram();
    /**@todo do something similar here as with Genotype.preserveFittestChromosome*/
    m_bestFitness = best.getFitnessValue();
    if (m_allTimeBest == null
        || m_bestFitness < m_allTimeBest.getFitnessValue()) {
      m_allTimeBest = best;
      // Fire an event to indicate a new best solution.
      // ----------------------------------------------
      getGPConfiguration().getEventManager().fireGeneticEvent(
          new GeneticEvent(GeneticEvent.GPGENOTYPE_NEW_BEST_SOLUTION, this));
      if(m_verbose) {
        // Output the new best solution found.
        // -----------------------------------
        outputSolution(best);
      }
    }
  }

  /**
   * @return the all-time best solution found
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public IGPProgram getAllTimeBest() {
    return m_allTimeBest;
  }

  /**
   * Outputs the best solution currently found.
   * @param a_best the fittest ProgramChromosome
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public void outputSolution(IGPProgram a_best) {
    System.out.println(" Best solution fitness: " + a_best.getFitnessValue());
    System.out.println(" Best solution: " + a_best.toStringNorm(0));
    String depths = "";
    int size = a_best.size();
    for (int i = 0; i < size; i++) {
      if (i > 0) {
        depths += " / ";
      }
      depths += a_best.getChromosome(i).getDepth(0);
    }
    if (size == 1) {
      System.out.println(" Depth of chromosome: " + depths);
    }
    else {
      System.out.println(" Depths of chromosomes: " + depths);
    }
    System.out.println(" --------");
  }

  /**
   * Evolve the population by one generation. Probabilistically reproduces
   * and crosses individuals into a new population which then overwrites the
   * original population.
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public void evolve() {
    try {
      int popSize = getGPConfiguration().getPopulationSize();
      GPPopulation oldPop = getGPPopulation();
      GPPopulation newPopulation = new GPPopulation(oldPop);
      float val;
      RandomGenerator random = getGPConfiguration().getRandomGenerator();
      GPConfiguration conf = getGPConfiguration();
      // Determine how many new individuals will be added to the new generation.
      // -----------------------------------------------------------------------
      int popSize1 = (int) Math.round(popSize * (1 - conf.getNewChromsPercent()));
      for (int i = 0; i < popSize1; i++) {
        // Clear the stack for each GP program (=ProgramChromosome).
        // ---------------------------------------------------------
        getGPConfiguration().clearStack();
        val = random.nextFloat();
        // Note that if we only have one slot left to fill, we don't do
        // crossover, but fall through to reproduction.
        // ------------------------------------------------------------
        if (i < popSize - 1 && val < conf.getCrossoverProb()) {
          // Do crossover.
          // -------------
          IGPProgram i1 = conf.getSelectionMethod().select(this);
          IGPProgram i2 = conf.getSelectionMethod().select(this);
          IGPProgram[] newIndividuals = conf.getCrossMethod().operate(i1, i2);
          newPopulation.setGPProgram(i++, newIndividuals[0]);
          newPopulation.setGPProgram(i, newIndividuals[1]);
        }
        else if (val < conf.getCrossoverProb() + conf.getReproductionProb()) {
          // Reproduction only.
          // ------------------
          newPopulation.setGPProgram(i, conf.getSelectionMethod().select(this));
        }
      }
      // Add new chromosomes randomly.
      // -----------------------------
      for (int i = popSize1; i < popSize; i++) {
        // Determine depth randomly and between maxInitDepth and 2*maxInitDepth.
        // ---------------------------------------------------------------------
        int depth = conf.getMaxInitDepth() - 2 + random.nextInt(2);
        IGPProgram program = newPopulation.create(m_types, m_argTypes,
            m_nodeSets, m_minDepths, m_maxDepths, depth, (i % 2) == 0,
            m_maxNodes, m_fullModeAllowed);
        newPopulation.setGPProgram(i, program);
      }
      // Now set the new population as the active one.
      // ---------------------------------------------
      setGPPopulation(newPopulation);
      // Increase number of generation.
      // ------------------------------
      conf.incrementGenerationNr();
      // Fire an event to indicate we've performed an evolution.
      // -------------------------------------------------------
      conf.getEventManager().fireGeneticEvent(
          new GeneticEvent(GeneticEvent.GPGENOTYPE_EVOLVED_EVENT, this));
    } catch (InvalidConfigurationException iex) {
      // This should never happen.
      // -------------------------
      throw new IllegalStateException(iex.getMessage());
    }
  }

  public GPPopulation getGPPopulation() {
    return m_population;
  }

  /**
   * @return the total fitness, that is the fitness over all chromosomes
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public double getTotalFitness() {
    return m_totalFitness;
  }

  /**
   * Sample implementation of method to run GPGenotype as a thread.
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public void run() {
    try {
      while (true) {
        evolve();
        calcFitness();
        // Pause between evolutions to avoid 100% CPU load.
        // ------------------------------------------------
        Thread.sleep(10);
      }
    } catch (Exception ex) {
      ex.printStackTrace();
      System.exit(1);
    }
  }

  /**
   * Retrieves the GPProgram in the population with the highest fitness
   * value.
   *
   * @return the GPProgram with the highest fitness value, or null if there
   * are no programs in this Genotype
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public synchronized IGPProgram getFittestProgram() {
    return getGPPopulation().determineFittestProgram();
  }

  protected void setGPPopulation(GPPopulation a_pop) {
    m_population = a_pop;
  }

  /**
   * Sets the configuration to use with the Genetic Algorithm.
   * @param a_configuration the configuration to use
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public static void setGPConfiguration(GPConfiguration a_configuration) {
    m_configuration = a_configuration;
  }

  /**
   * Compares this entity against the specified object.
   *
   * @param a_other the object to compare against
   * @return true: if the objects are the same, false otherwise
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public boolean equals(Object a_other) {
    try {
      return compareTo(a_other) == 0;
    } catch (ClassCastException cex) {
      return false;
    }
  }

  /**
   * Compares this Genotype against the specified object. The result is true
   * if the argument is an instance of the Genotype class, has exactly the
   * same number of programs as the given Genotype, and, for each
   * GPProgram in this Genotype, there is an equal program in the
   * given Genotype. The programs do not need to appear in the same order
   * within the populations.
   *
   * @param a_other the object to compare against
   * @return a negative number if this genotype is "less than" the given
   * genotype, zero if they are equal to each other, and a positive number if
   * this genotype is "greater than" the given genotype
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public int compareTo(Object a_other) {
    try {
      // First, if the other Genotype is null, then they're not equal.
      // -------------------------------------------------------------
      if (a_other == null) {
        return 1;
      }
      GPGenotype otherGenotype = (GPGenotype) a_other;
      // First, make sure the other Genotype has the same number of
      // chromosomes as this one.
      // ----------------------------------------------------------
      int size1 = getGPPopulation().size();
      int size2 = otherGenotype.getGPPopulation().size();
      if (size1 != size2) {
        if (size1 > size2) {
          return 1;
        }
        else {
          return -1;
        }
      }
      // Next, prepare to compare the programs of the other Genotype
      // against the programs of this Genotype. To make this a lot
      // simpler, we first sort the programs in both this Genotype
      // and the one we're comparing against. This won't affect the
      // genetic algorithm (it doesn't care about the order), but makes
      // it much easier to perform the comparison here.
      // --------------------------------------------------------------
      Arrays.sort(getGPPopulation().getGPPrograms());
      Arrays.sort(otherGenotype.getGPPopulation().getGPPrograms());
      for (int i = 0; i < getGPPopulation().size(); i++) {
        int result = (getGPPopulation().getGPProgram(i).compareTo(
            otherGenotype.getGPPopulation().getGPProgram(i)));
        if (result != 0) {
          return result;
        }
      }
      return 0;
    } catch (ClassCastException e) {
      return -1;
    }
  }

  /***
   * Hashcode function for the genotype, tries to create a unique hashcode for
   * the chromosomes within the population. The logic for the hashcode is
   *
   * Step  Result
   * ----  ------
   *    1  31*0      + hashcode_0 = y(1)
   *    2  31*y(1)   + hashcode_1 = y(2)
   *    3  31*y(2)   + hashcode_2 = y(3)
   *    n  31*y(n-1) + hashcode_n-1 = y(n)
   *
   * Each hashcode is a number and the binary equivalent is computed and
   * returned.
   * @return the computed hashcode
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public int hashCode() {
    int i, size = getGPPopulation().size();
    IGPProgram prog;
    int twopower = 1;
    // For empty genotype we want a special value different from other hashcode
    // implementations.
    // ------------------------------------------------------------------------
    int localHashCode = -573;
    for (i = 0; i < size; i++, twopower = 2 * twopower) {
      prog = getGPPopulation().getGPProgram(i);
      localHashCode = 31 * localHashCode + prog.hashCode();
    }
    return localHashCode;
  }

  /**
   * @param a_verbose true: output status information to console
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public void setVerboseOutput(boolean a_verbose) {
    m_verbose = a_verbose;
  }
}