dewrinkler.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 Dewrinkler
  implements AsexualReproducer
{

/*
** Because we do (perhaps may times) N*( M! ) permutations, we cannot
** afford the computational burden of the global permute limit; support
** a local one as well.  Unlike Optimize Near A Point, we are not helped
** particularly by favorable geometry as we approach the solution,
** either, and for large genomes, our worst case is our usual case.
** 
** FIXME Tune this limit; the algorithm grows immensely more powerful
** with increased limit, but it also grows sloooooow!
*/

  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 Dewrinkler.reproduce( Chromosome parent)"
        );
      }

/*
** Pass the input as a less burdensome type.
*/

      TravellerChromosome child = algorithm( (TravellerChromosome) parent );

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

    }
    catch (Exception e)
    {
      System.err.println
      (
        "Dewrinkler.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( "Dewrinkler" );
      }
    }
    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 ); }

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

/*
** To cut off N points, we need N + 1 cleavage indices; the rest of the
** genome acts as the N+1st permutee.
*/

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

    int cleavageIndices[] = new int[permuteSize];

    double priorFitness = offspring.testFitness();
    double bestFitness  = offspring.testFitness();

    TravellerChromosome bestSeen  = new TravellerChromosome( offspring );

    int failureCount = 0;

    while ( failureCount < PermutationController.getCurrentPermuteLimit() )
    {

/*
** Pick a new starting point at each try.
*/

      pickCleavageIndices( cleavageIndices, genomeLength, mt );

/*
** Go around once; do a full permutation at last stop; otherwise do a
** dewrinkling permutation.
*/

      for ( int i = 0; i < genomeLength; i++ )
      {
        bladeful
        (
          cleavageIndices,
          offspring,
          world,
          mt,
          ( i == ( genomeLength - 1 ) )
        );

        advanceBlade( cleavageIndices, genomeLength );

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

        TravellerChromosome temp = new TravellerChromosome( offspring );
        temp.canonicalize();
        double currentFitness = temp.testFitness();

        if ( currentFitness < bestFitness )
        {

/*
** Form a second handle to the temporary genome; the first one will get
** garbage collected in the next iteration if this hook isn't formed.
*/

          bestSeen = temp;
          bestFitness = currentFitness;
        }

      }

/*
** Leave the loop if we have stopped improving fitness at this
** permutation length for a while.
*/

      double currentFitness = offspring.testFitness();

      if ( currentFitness >= priorFitness )
      {
        failureCount++;
      }
      else
      {
        failureCount = 0;
        priorFitness = currentFitness;
      }

    }

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

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

/*
** Check whether we have improved.  It is possible that pushing a
** wrinkle around the genome ring made things worse!  Report back so
** that adaptive permutation high limit can eventually be updated.
*/

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

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

    return bestSeen; 

  }

  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 void bladeful
  (
    int cleavageIndices[],
    TravellerChromosome mutant,
    TravellerWorld world,
    MersenneTwister mt,
    boolean override
  )
  {

    double fitnessAtStart = mutant.testFitness();

    if (DB)
    {
      System.out.println
      (
        mutant.toString()
        + "/"
        + Debugging.dump( cleavageIndices)
        + "/"
        + fitnessAtStart
        + " mutant/cleavageIndices/fitness at start of bladeful in Dewrinkler"
      );
    }

/*
** Create a local _copy_ of the input parameter; remind self not to
** scribble on it!
*/

    TravellerChromosome readOnlyVersion = new TravellerChromosome( mutant );

    int permuteSize = cleavageIndices.length;
    int genomeLength = ValuatorControls.getNumberOfCities();

    PermutationGenerator pg = new PermutationGenerator( permuteSize, false );


/*
** Create cleavage point auxiliary arrays.
*/

    int sublistBeginCities[]   = new int[permuteSize];
    int sublistEndCities[]     = new int[permuteSize];

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

/*
** 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] = mutant.getCity(cleavageIndices[i]);
      sublistEndCities[i]   =
        mutant.getCity
        (
          (
            cleavageIndices[(i + 1) % permuteSize]
            - 1
            + genomeLength
          ) % genomeLength
        );
    }

    int bestPermutation[] = new int[permuteSize];


/*
** Choose the original configuration as the best found, for a start.
*/

    for (int i = 0; i < permuteSize; i++)
    {
      bestPermutation[i] = i;
    }

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

    while ( pg.morePermutations() )
    {

      try
      {
        nextPermutation = pg.getNext();
      }
      catch (Exception e)
      {
        System.out.println
        (
          "caught pg.getNext() throw in Dewrinkler"
        );
      }

      double currentFitness = 0.0D;

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

/*
** Create a "wrinkle" by ignoring the fitness contribution around the
** the next-to-last single node, except that when overridden for the end
** of a circuit, include that fitness to clean the final genome up a
** bit.  With luck, this will move a misplaced node; like moving a rug
** too heavy to drag, by creating a wrinkle, them moving the wrinkle
** across the rug; until a proper slot into which to drop the misplaced
** node is encountered.
*/

        if ( override || ( i != permuteSize - 2 ) )
        {
          int nextIndex = ( i + 1 ) % permuteSize;
          currentFitness +=
            world.getDistance
           (
             (
               sublistEndCities[nextPermutation[i].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 mutant at the end of all this
**  foolishness.
*/

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

/*
** We are going to scribble on mutant, so use the local copy of that
** input parameter as an unclobbered data source for city names.
** 
** Starting at the beginning of the output chromosome, mutant, 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;

      int j = currentChromosomeIndex;

      while ( true )
      {
        mutant.setCity( writeToIndex, readOnlyVersion.getCity(j));
        writeToIndex++;
        if ( j == nextChromosomeIndex ) { break; }
        j = ( j + 1 ) % genomeLength;
      }
    }

    mutant.canonicalize();
    double fitnessAtEnd   = mutant.testFitness();
    if (DB)
    {
      System.out.println
      (
        mutant.toString()
        + "/"
        + fitnessAtEnd
        + " mutant/fitness at end of bladeful in Dewrinkler"
      );
    }
  }

  private void pickCleavageIndices
  (
    int cleavageIndices[],
    int genomeLength,
    MersenneTwister mt
  )
  {

    int permuteSize = cleavageIndices.length;

    int offset = mt.nextInt( genomeLength );

    for (int i = 0; i < permuteSize; i++)
    {
      cleavageIndices[i] = ( i + offset ) % genomeLength ;
    }
  }

  private void advanceBlade
  (
    int cleavageIndices[],
    int genomeLength
  )
  {
    for ( int i = 0; i < cleavageIndices.length; i++ )
    {
      cleavageIndices[i] = ( (cleavageIndices[i] + 1 ) % genomeLength) ;
    }
  }

}