population.java

经典的货郎担问题解决办法

//-----------------------------------------------------------------------------
//  com.coyotegulch.genetic
//
//  A Package of Generic Tools used in Genetic Algorithms
//
//  Population.java
//  version 2.1.0
//
//  Copyright 1996-2001 Scott Robert Ladd. All rights reserved.
//
//  For more information about this program, contact:
//
//      Scott Robert Ladd
//      [e-mail]
//      http://www.coyotegulch.com
//
//-----------------------------------------------------------------------------
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the
//
//      Free Software Foundation, Inc.
//      59 Temple Place - Suite 330
//      Boston, MA 02111-1307, USA.
//-----------------------------------------------------------------------------

/*
** This code was extensively modified by Kent Paul Dolan.  See
** accompanying file TravellerDoc.html for status of the modifications
** for your use.
*/

package com.coyotegulch.genetic;
import com.coyotegulch.tools.*;

import com.well.www.user.xanthian.java.genetic.*;
import com.well.www.user.xanthian.java.tools.*;
import com.well.www.user.xanthian.java.ui.*;

public class Population
{
  private final static String m_progressDisplayName =
    "旅行商进度报告";
  private static SmallDisplay m_progressDisplay = null;
  private static int SMALL_DISPLAY_WIDTH = 30;

  // vector of chromosomes
  protected Chromosome [] m_population;

  protected double m_bestFit    = 0.0F;
  protected double m_worstFit   = 0.0F;
  protected double m_averageFit = 0.0F;
  protected RouletteWheel m_rw  = null;

  // vectors of operators
  private MutatorVector    m_mutators;
  private ReproducerVector m_reproducers;

  // probabilities
  private double  m_mutationRate;

/*
** FIXME Assume we are not going to be simultaneously running multiple
** GAs in opposite directions, so that others can ask Population which
** direction good fitnesses are supposed to lie.  If this is a bad
** assumption, do more work to make other choices possible.
*/

  private static boolean m_minimize = false;

  // private static Randomizer m_randNo   = new Randomizer();
  private MersenneTwister      m_mt       = null;
  private SimulatedAnnealing   m_annealer = null;
  private int                  m_bestGenomeIndex   = 0;

  // constructors
  public Population
  (
    Chromosome cv[],
    MutatorVector mv,
    ReproducerVector rv,
    double muteRate,
    boolean minimize
  )
  {

    if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
    {
      System.out.println
      (
        "Entered Population(Chromosome [] cv, MutatorVector mv, ReproducerVector rv, double muteRate, boolean minimize)"
        + ", muteRate is: "

        + muteRate
      );
    }

    m_population   = cv;
    m_mutators     = mv;
    m_reproducers  = rv;
    m_minimize     = minimize;
    m_mutationRate = muteRate;
    m_mt           = MersenneTwister.getTwister();
    m_annealer     = new SimulatedAnnealing();
    m_bestGenomeIndex       = 0;

  }

  public Population(Population p)
  {

    if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
    {
      System.out.println
      (
        "Entered Population(Population p)"
      );
    }

    m_population   = p.m_population;
    m_mutators     = p.m_mutators;
    m_reproducers  = p.m_reproducers;
    m_minimize     = p.m_minimize;
    m_mutationRate = p.m_mutationRate;
    m_mt           = p.m_mt;
    m_annealer     = p.m_annealer;
    m_bestGenomeIndex       = p.m_bestGenomeIndex;

  }

  private void updateProgressDisplay( String update )
  {
    if
    (
      CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PROGRESS_COUNTERS)
    ) 
    {
      if ( m_progressDisplay == null )
      {
        m_progressDisplay =
          new SmallDisplay( m_progressDisplayName, SMALL_DISPLAY_WIDTH );
      }
      m_progressDisplay.updateDisplay( update );
    }
    else
    {
      if ( m_progressDisplay != null )
      {
        m_progressDisplay.closeWindow();
        m_progressDisplay = null;
      }
    }
  }

  // interrogator
  public double getBestFit()
  {
    return m_bestFit;
  }

  public double getAverageFit()
  {
    return m_averageFit;
  }

  public double getAnnealingDecrementer()
  {
    return m_annealer.getAnnealingDecrementer();
  }

  public double getAnnealingLimit()
  {
    return m_annealer.getAnnealingLimit();
  }

  public Chromosome getMember( int memberIndex )
  {
    return m_population[memberIndex];
  }

  public static boolean areMinimizing()
  {
    return m_minimize;
  }

  public double getWorstFit()
  {
    return m_worstFit;
  }

  public int getBestName()
  {
    return m_bestGenomeIndex;
  }

  public int getSameFitnessCount()
  {
    int sameFitnessCount = 0;
    double bestFitness =
      ((TravellerChromosome) (m_population[m_bestGenomeIndex])).testFitness();
    for (int i = 0; i < m_population.length; i++)
    {
      if
      (
        Math.abs
        (
          ((TravellerChromosome)(m_population[i])).testFitness()
          -
          bestFitness
        )
        <
        TravellerStatus.LITTLE_FUZZ
      )
      {
        sameFitnessCount++;
      }
    }
    return sameFitnessCount;
  }

  public int getBestCloneCount()
  {
    int cloneCount = 0;
    for (int i = 0; i < m_population.length; i++)
    {
      if
      (
        ((TravellerChromosome)(m_population[i])).
          looksLikeMe(((TravellerChromosome)(m_population[m_bestGenomeIndex])))
      )
      {
        cloneCount++;
      }
    }
    return cloneCount;
  }

/*
** Evaluate the population fitnesses, find the best member, und so
** weiter.  This has been separated from the nextGeneration processing
** so that this part can be done once, first, after initial genome
** seeding into the population, but before any attempts at improving
** genome fitnesses have interfered with the initial population
** statistics.  We want to do this task separately so that we can get a
** truer measure of how hard our heuristics have worked on our behalf.
*/

  public Chromosome evaluateGenomes() throws Exception
  {

    if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
    {
      System.out.println
      (
        "Entered Population.evaluateGenomes()"
      );
    }

/*
** Create a roulette wheel for this population.
*/

    m_rw = new RouletteWheel();

/*
** This design was so wrong there was no hope for it.  First, ideal
** fitness could be some huge value and the fitness variations some tiny
** fraction, making the original design ineffectual, so  we want the
** roulette wheel slot widths biased corresponding to the fitness
** variations, not the absolute fitnesses.  Second, it makes no sense to
** build the roulette wheel, be done with it, and _then_ notice that we
** are minimizing instead of maximizing fitness; the bias in the wheel
** as Scott built it is exactly in the wrong direction for Traveller!
*/

    int hi_i = 0;
    int lo_i = 0;
    m_bestGenomeIndex = 0;

    double hi_f = Double.MIN_VALUE;
    double lo_f = Double.MAX_VALUE;
    double tot_f = 0.0F;

    double f;

/*
** Test fitness for each chromosome, first.  Fitness testing is sticky
** until the genome is changed, so we can afford to do it repeatedly.
*/

    for (int i = 0; i < m_population.length; ++i)
    {
      // compute new fitness
      f = m_population[i].testFitness();

      tot_f += f;

      if (f < lo_f)
      {
          lo_f = f;
          lo_i = i;
      }

      if (f > hi_f)
      {
          hi_f = f;
          hi_i = i;
      }
    }

    m_averageFit = (double)tot_f / (double)m_population.length;

    double fitnessSpan = Math.abs(hi_f - lo_f);

/*
** POLICY What bias fraction we make to assure that the least fit member
** has at least some chance to win the turn of the roulette wheel makes
** a huge difference in how fast the heuristics converge, and also in
** how quickly population diversity vanishes.  Here we give the least
** fit member one eleventh the chance of the most fit member to be
** selected.  We have to add some constant length too, or things go bad
** when all the genomes are clones and fitness span drops to zero, so
** add a pixel width.
*/

    double unfitnessBias = 1.0D + fitnessSpan / 10.0D;

    for ( int i = 0; i < m_population.length; i++ )
    {

      f = m_population[i].getFitness();

/*
** Add fitness variation to the roulette wheel, using the bias developed
** in the previous loop.
*/

      if ( m_minimize )
      {

        m_rw.addWeight( (float) ( hi_f - f + unfitnessBias ) );

      }
      else
      {

        m_rw.addWeight( (float) ( f - lo_f + unfitnessBias ) );
      }

    }

    if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
    {
      System.out.println
      (
        "in Population.nextGeneration(), just figured average fitness"
      );
    }

    if (m_minimize)
    {
      m_bestGenomeIndex = lo_i;
      m_bestFit   = lo_f;
      m_worstFit  = hi_f;

    }
    else
    {
      m_bestGenomeIndex = hi_i;
      m_bestFit   = hi_f;
      m_worstFit  = lo_f;
    }

    updateProgressDisplay( "generation complete" );

/*
** KPD It isn't really necessary explicitly to retain the elite member,
** a genome at least that good would survive to the next generation,
** though mutation might nail it, but this doesn't cost a whole lot, and
** later changes might invalidate that lack of necessity, so do it
** anyway.  We kept track above of the location of the elite genome, and
** copied it to the new population's first slot, now do messy index
** calculations to avoid clobbering it, since its position is frozen in
** the roulette wheel already.
*/

    return m_population[m_bestGenomeIndex].cloneThis();

  }

/*
** Compute next generation.
*/