permutecutsnearapoint.java

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

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

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

import com.coyotegulch.tools.*;
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 PermuteCutsNearAPoint
    implements AsexualReproducer
{

/*
** 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
** some of the sublists we produce will be of length one and therefore
** not flippable.
*/

  private static final int LOCAL_PERMUTE_LIMIT = 6;

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

  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 PermuteCutsNearAPoint.reproduce( Chromosome parent)"
        );
      }
/*
** Rename the input to a less burdensome type.
*/

      TravellerChromosome p = (TravellerChromosome) parent;

      TravellerChromosome child = algorithm( p );

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

    }
    catch (Exception e)
    {
      System.err.println
      (
        "PermuteCutsNearAPoint.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( "PermuteCutsNearAPoint" );
      }
    }
    else
    {
      if ( m_vdb != null )
      {
        m_vdb.closeWindow();
        m_vdb = null;
      }
    }

    if (VDB) { m_vdb.toFront(); }

    MersenneTwister mt = MersenneTwister.getTwister();

    TravellerChromosome offspring = new TravellerChromosome( parent );

    offspring.canonicalize();
    double startingFitness = offspring.testFitness();
    if (VDB) { m_vdb.setup( offspring ); }

    // Create a local _name_ for the input parameter; remind self
    // not to scribble on it!
    // DANGER!  Don't get caught again!  This fails spectacularly when
    // tucked inside a loop.
    TravellerChromosome readOnlyVersion = (TravellerChromosome) parent;

    TravellerWorld world = parent.getWorld();
    int genomeLength = ValuatorControls.getNumberOfCities();

    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 ); }
    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;

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

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

      if ( mt.nextBoolean() )
      {

        // put a cleavage point _before_ the city we grabbed earlier.
        int indexCandidate = readOnlyVersion.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 =
          ( readOnlyVersion.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;

    // Do spooky bit twiddling magic to save unneeded
    // work in the flipping loop.
    int antiflipMask = 0;
    for (int i = 0; i < permuteSize; i++)
    {
      if (!sublistFlippable[i]) { antiflipMask |= ( 1 << i ) ; }
    }

    double bestFitness = Double.MAX_VALUE;
    Integer [] nextPermutation = null;

    while ( pg.morePermutations() )
    {

      boolean currentFlips[] = new boolean[permuteSize];
      try
      {
        nextPermutation = pg.getNext();
      }
      catch (Exception e)
      {
        System.out.println
        (
          "caught pg.getNext() throw in TravellerPermuteCitiesWithinASublist"
        );
      }

      // Loop through the possible flips.
      for (int flipWord = 0; flipWord < powerOfTwo; flipWord++)
      {
        // Skip work for don't flipping care subset.
        if ( ( flipWord & antiflipMask ) == 0 )
        {
          for (int i = 0; i < permuteSize; i++)
          {
            currentFlips[i] = ( ( flipWord & (1 << i) ) != 0 );
          }

          double currentFitness = 0.0D;

          for (int i = 0; i < permuteSize; i++)
          {
            int nextIndex = ( i + 1 ) % permuteSize;
            currentFitness +=
              world.getDistance
             (
               (
                 currentFlips[i]
                 ? sublistBeginCities[nextPermutation[i].intValue()]
                 : sublistEndCities[nextPermutation[i].intValue()]
               ),
               (
                 currentFlips[nextIndex]
                 ? sublistEndCities[nextPermutation[nextIndex].intValue()]
                 : sublistBeginCities[nextPermutation[nextIndex].intValue()]
               )
             );
          }
          if (currentFitness < bestFitness)
          {
            bestFitness = currentFitness;

            // Notice that this time we are actually capturing the
            // permutation rather than what it indexes; we have a
            // bunch of work to do to construct the final product
            // offspring at the end of all this foolishness.

            for (int i = 0; i < permuteSize; i++)
            {
              bestPermutation[i] = nextPermutation[i].intValue();
              bestFlipped[i] = currentFlips[i];
            }
          }
        }
      }
    }

    // We are going to scribble on offspring, so use the local name of
    // the input parameter as an unclobbered data source for city names.

    // Starting at the beginning of the output chromosome, offspring,
    // write the sublists in their permuted order, flipped as needed.

    int writeToIndex = 0;

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

      int currentCleavageIndicesIndex = bestPermutation[i];
      int nextCleavageIndicesIndex =
        ( currentCleavageIndicesIndex + 1 ) % permuteSize;
      int currentChromosomeIndex =
        cleavageIndices[currentCleavageIndicesIndex];
      int nextChromosomeIndex =
        ( cleavageIndices[nextCleavageIndicesIndex] - 1 + genomeLength )
        % genomeLength;

      if ( bestFlipped[i] )
      {
        int j = nextChromosomeIndex;
        while ( true )
        {
          offspring.setCity( writeToIndex, readOnlyVersion.getCity(j));
          writeToIndex++;
          if ( j == currentChromosomeIndex ) { break; }
          j = ( j - 1 + genomeLength ) % genomeLength;
        }
      }
      else
      {
        int j = currentChromosomeIndex;
        while ( true )
        {
          offspring.setCity( writeToIndex, readOnlyVersion.getCity(j));
          writeToIndex++;
          if ( j == nextChromosomeIndex ) { break; }
          j = ( j + 1 ) % genomeLength;
        }
      }
    }

/*
** Who knows what order the result has?  Better fix it.
*/

    offspring.canonicalize();
    double finalFitness = offspring.testFitness();

/*
** We only change for the better, so if we haven't changed, we haven't
** improved.  Report back so that adaptive permutation high limit can
** eventually be updated.
*/

    if
    (
      Math.abs( finalFitness - startingFitness )
      <
      TravellerStatus.LITTLE_FUZZ
    )
    {
      PermutationController.reportFailure();
    }
    else
    {
      PermutationController.reportSuccess();
    }

    if (VDB) { m_vdb.step( offspring ); }

    if (VDB) { m_vdb.done( parent, offspring ); }

    return offspring;
  }

  private boolean inList( int c, int list[] )
  {
    for (int i = 0; i < list.length; i++)
    {
      if (c == list[i]) { return true; }
    }
    return false;
  }

  private int listIndex( int c, int list[] )
  {
    for (int i = 0; i < list.length; i++)
    {
      if (c == list[i]) { return i; }
    }
    return -1;
  }

  private int [] pickCities( TravellerWorld world, int permuteSize )
  {

    MersenneTwister mt = MersenneTwister.getTwister();

/*
** Pick a location in the working canvas playfield area from which to
** reach out for the nearest permuteSize cities.
*/

    double x =
      mt.nextDouble( 0.0D, TravellerCanvas.WORKING_DIMENSIONS.getWidth() );
    double y =
      mt.nextDouble( 0.0D, TravellerCanvas.WORKING_DIMENSIONS.getHeight() );

    if (this.DB) { System.out.println("pickedCities at: " + x + "," + y ); }

    int    cities[]    = new int[permuteSize];
    double distances[] = new double[permuteSize];

    for ( int i = 0; i < permuteSize; i++ )
    {
      cities[i]    = -1;
      distances[i] = Double.MAX_VALUE;
    }

    int genomeLength = world.getNumberOfCities();

    if (this.DB)
    {
      System.out.println( "pickCities, cities: " + Debugging.dump(cities) );
      System.out.println( "pickCities, distances: " + Debugging.dump(distances) );
    }

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

      double cityExactLocation[] = world.getCityExactLocation(i);

      double cx = cityExactLocation[TravellerWorld.CITY_X];
      double cy = cityExactLocation[TravellerWorld.CITY_Y];

      double distance =
        Math.sqrt( ( ( cx - x ) * ( cx - x ) ) + ( ( cy - y ) * ( cy - y ) ) );
      if (this.DB) { System.out.println( "pickCities OK to inner loop" ); }
      double dtemp;
      int    ctemp;
      int    itemp = i;
      for ( int j = 0 ; j < permuteSize; j++ )
      {
        if ( distance < distances[j] )
        {
          dtemp        = distances[j];
          ctemp        = cities[j];
          distances[j] = distance;
          cities[j]    = itemp;
          distance     = dtemp;
          itemp        = ctemp;
        }
      }
      if (this.DB)
      {
        System.out.println( "pickCities, cities,i: " + Debugging.dump(cities) + i );
        System.out.println( "pickCities, distances: " + Debugging.dump(distances) );
      }
    }

    return cities;
  }

}