randomcityloopfornearbycuts.java

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

/*
** This code was written by Kent Paul Dolan, from scratch.  So far as I
** know, it is an original, unobvious algorithm.  See accompanying file
** TravellerDoc.html for status for your use.
*/

package com.well.www.user.xanthian.java.genetic.reproducers.asexual;

import com.coyotegulch.genetic.*;

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 RandomCityLoopForNearbyCuts
  implements AsexualReproducer
{

  private final static String m_progressDisplayName =
    "Boston Carver";
  private static SmallDisplay m_progressDisplay = null;
  private static int SMALL_DISPLAY_WIDTH = 30;

/*
** Because we do up to 2^(M-1) reversals as well as M! permutations, we
** cannot afford the computational burden of the global permute limit;
** support a local one as well.  We are helped a bit by the fact that at
** least half the sublists we produce will be of length one and
** therefore not flippable.
*/

  private static final int LOCAL_PERMUTE_LIMIT = 4;

  private static boolean DB = false;
  private static boolean VDB = false;
  private static VisualDebugger m_vdb = null;

  private static double gaussianScaler = 0.0D;

  public Chromosome reproduce(Chromosome parent)
  {
    try
    {

/*
** Debugging hook abbreviation.  During development, turn on debugging
** just for this class by setting this variable to true, here.  When the
** code is stable, set it to false here, and control debugging from the
** checkbox controls panel, instead.  This variable is global to this
** class, so it controls debugging thoughout the class when set here at
** the top of the entry method for the class.
*/

      DB = false;

      if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
      {
        DB = true;
        System.out.println
        (
          "Entered RandomCityLoopForNearbyCuts.reproduce( Chromosome parent)"
        );
      }
/*
** Rename the input to a less burdensome type.
*/

      TravellerChromosome p = (TravellerChromosome) parent;

      TravellerChromosome child = algorithm( p );

      child.setOriginator( "RandomCityLoopForNearbyCuts" );
      child.checkValidity();
      return (Chromosome) child;

    }
    catch (Exception e)
    {
      System.err.println
      (
        "RandomCityLoopForNearbyCuts.reproduce() threw!"
      );
    }

/*
** This code should never be reached, it is just here to pacify javac.
*/

    return parent; 
  }

  private TravellerChromosome algorithm( TravellerChromosome parent )
  {

    VDB = false;
    if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_VISUAL_WINDOWS))
    {
      VDB = true;
    }

    if (VDB)
    {
      if ( m_vdb == null )
      {
        m_vdb = new VisualDebugger( "RandomCityLoopForNearbyCuts" );
      }
    }
    else
    {
      if ( m_vdb != null )
      {
        m_vdb.closeWindow();
        m_vdb = null;
      }
    }

    if (VDB) { m_vdb.toFront(); }
    if (m_progressDisplay != null) { m_progressDisplay.toFront(); }

    gaussianScaler =
      TravellerCanvas.WORKING_DIMENSIONS.getWidth()
      / Math.sqrt( (double) ValuatorControls.getNumberOfCities() );

    TravellerWorld world = parent.getWorld();

    TravellerChromosome offspring = new TravellerChromosome( parent );

    offspring.canonicalize();
    if (VDB) { m_vdb.setup( offspring ); }

    if (DB)
    {
      System.out.println
      (
        offspring.toString()
        + " starting RandomCityLoopForNearbyCuts"
      );
    }

    double startingFitness = offspring.testFitness();

    int genomeLength = ValuatorControls.getNumberOfCities();

    if (DB)
    {
      System.out.println
      (
        "RandomCityLoopForNearbyCuts, initial genome"
      );
      System.out.println( offspring.toString() );
    }

    MersenneTwister mt = MersenneTwister.getTwister();

    TravellerChromosome coparent = new TravellerChromosome( offspring );

    MarkArray ma = new MarkArray( genomeLength );

    int changeCount = 0;
    int improveCount = 0;
    int tryCount = 0;
    int loopCount = 0;

    updateProgressDisplay
    (
      " lC "
      + loopCount
      + " cC "
      + changeCount
      + " mC "
      + ma.getCount()
      + " iC "
      + improveCount
      + " sC "
      + tryCount
    );

    // for ( int z = 0; z < genomeLength; z++ )
    while (true)
    {

      tryCount++;

      int z = mt.nextInt( genomeLength );

      int pointsToGrab = ( new PermutationController() )
        .getAPermuteSize
        (
          Math.min
          (
            genomeLength - 1,
            LOCAL_PERMUTE_LIMIT
          )
        );

/*
** Pick the closest permutation-full of citys to some point in the world.
*/

      int cityList[] = null;
      try { cityList = pickCities( world, pointsToGrab, z ); }
      catch (Exception pc)
      {
        System.out.println( "PermuteCutsNearAPoint.pickCities threw" );
      }
      finally
      {
        if (DB) System.out.println( "PermuteCutsNearAPoint.pickCities ran" );
      }

      // fill cleavage points list with unique chromosome array indices

/*
** We don't yet know how many cleavage points we are going to have, it
** depends on whether some of the nodes we grabbed are currently
** adjacent in their genome, so we work in an oversized array until we
** find out.
*/

      int cleavagePoints[] = new int[2*pointsToGrab];

      for (int i = 0; i < cleavagePoints.length; i++)
      {
        cleavagePoints[i] = -1;
      }

      int cleavageCount = 0;

/*
** So we can have more segments, arbitrarily put the cleavage point
** either before or after the grabbed point.
*/

      for (int i = 0; i < pointsToGrab; i++)
      {

        if ( mt.nextBoolean() )
        {
          // put a cleavage point _before_ the city we grabbed earlier.
          int indexCandidate = coparent.findCity( cityList[i] );
          if ( ! inList( indexCandidate, cleavagePoints ) )
          {
            cleavagePoints[cleavageCount] = indexCandidate;
            for (int j = cleavageCount; j > 0; j--)
            {
              // Do a cheesy insertion sort, since this list has
              // a single digit length.
              if ( cleavagePoints[j] < cleavagePoints[j - 1] )
              {
                int temp = cleavagePoints[j - 1];
                cleavagePoints[j - 1] = cleavagePoints[j];
                cleavagePoints[j] = temp;
              }
            }
            cleavageCount++;
          }
        }
        else
        {
          // put a cleavage point _after_ the city we grabbed earlier.
          int indexCandidate =
            ( coparent.findCity( cityList[i] ) + 1 ) % genomeLength;
          if ( ! inList( indexCandidate, cleavagePoints ) )
          {
            cleavagePoints[cleavageCount] = indexCandidate;
            for (int j = cleavageCount; j > 0; j--)
            {
              // Do a cheesy insertion sort, since this list has
              // a single digit length.
              if ( cleavagePoints[j] < cleavagePoints[j - 1] )
              {
                int temp = cleavagePoints[j - 1];
                cleavagePoints[j - 1] = cleavagePoints[j];
                cleavagePoints[j] = temp;
              }
            }
            cleavageCount++;
          }
        }

      }

      PermutationGenerator pg = new PermutationGenerator( cleavageCount, false ) ;
      int permuteSize = pg.getPermutationSize();

      // pick cleavage points
      int cleavageIndices[]      = new int[permuteSize];
      int sublistBeginCities[]   = new int[permuteSize];
      int sublistEndCities[]     = new int[permuteSize];
      boolean sublistFlippable[] = new boolean[permuteSize];

      for (int i = 0; i < permuteSize; i++)
      {
        cleavageIndices[i] = cleavagePoints[i];
        sublistBeginCities[i] = -1;
        sublistEndCities[i] = -1;
        sublistFlippable[i] = true;
      }

      // fill in auxiliary array information.  For computing
      // relative fitness, we don't need the whole sublists,
      // the interior lengths don't change.  We just need the
      // end points to connect to each other.
      for (int i = 0; i < permuteSize; i++)
      {
        sublistBeginCities[i] = offspring.getCity(cleavageIndices[i]);
        sublistEndCities[i]   =
          offspring.getCity
          (
            (
              cleavageIndices[(i + 1) % permuteSize]
              - 1
              + genomeLength
            ) % genomeLength
          );
        // We need not bother to reverse single entry lists,
        // they look the same from either end!
        if ( sublistBeginCities[i] == sublistEndCities[i] )
        {
          sublistFlippable[i] = false;
        }
      }

      int bestPermutation[] = new int[permuteSize];
      boolean bestFlipped[] = new boolean[permuteSize];

      // Choose the original configuration as the best found,
      // for a start.  Create a needed power of two.
      int powerOfTwo = 1;
      for (int i = 0; i < permuteSize; i++)
      {
        bestPermutation[i] = i;
        bestFlipped[i] = false;
        powerOfTwo *= 2;
      }
      // We never need to flip some one of the sublists,
      // since a TSP circuit is invariant under reversal,
      // so back off by one power of two.
      powerOfTwo /= 2;