quasishellsortswapper.java

来自「经典的货郎担问题解决办法」· Java 代码 · 共 489 行

/*
** This code was written by Kent Paul Dolan.  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.*;

/*
** Imitate the action of a Shell sort, with no particular expectations
** about what will result, except possibly better fitness.  Like Shell
** sort, expected nice bounded worse case complexity.  Unlike Shell
** sort, we don't back up with elements, but instead make sweeping
** passes until no change occurs, but we keep the essential element of
** Shell's sort, which is that we assure that each set of elements
** separated by our current span is sorted before decreasing the span.
** In the end, where Shell sort is an enhanced insertion sort, this is
** some mix of Shell, comb, bubble, and insertion sorts.  The best
** defense of such a mongrel is that it works very well indeed!
*/

public class QuasiShellSortSwapper
    implements AsexualReproducer
{

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

      TravellerChromosome p = (TravellerChromosome) parent;

      TravellerChromosome child = algorithm( p );

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

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

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

    TravellerChromosome offspring = new TravellerChromosome( parent );
    offspring.canonicalize();
    if (VDB) { m_vdb.setup( offspring ); }

    TravellerWorld world = parent.getWorld();

    quasiShellSortSwapper( offspring, world );

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

    return offspring; 
  }

  private void quasiShellSortSwapper
  (
    TravellerChromosome goat,
    TravellerWorld world
  )
  {

    MersenneTwister mt = MersenneTwister.getTwister();

    int genomeLength = ValuatorControls.getNumberOfCities();

/*
** Start a bit too big, we want to decrease span by a (swagged value)
** 3/5ths multiple on each pass.  We'd just decrease it by one per pass
** if we could afford an order N*N heuristic, but that would be pretty
** unbearable at N = 1000, one of our quick solution goal sizes.
** 
** Do this with a bit of randomness, so that running the same heuristic
** twice on the same genome isn't necessarily a no-op the second pass.
*/

    int span = genomeLength + mt.nextInt( genomeLength );

    while ( span > 1 )
    {

      span = Math.max( 1, ( ( 3 * span ) / 5 ) );


/*
** Since we have no concept of "sort order", proceding backward with
** each element we find out of order, as the original Shell sort does,
** until it bumps into something with which it proves to be in order,
** doesn't make much sense for us; there might be another potential swap
** past that point.  Instead, we just sweep again and again over the
** same direction with the same span until no swaps occur, before we
** decrease the span or terminate when it has once reached zero.
** 
** FIXME Or at least we would if it didn't cause an endless loop!  There
** is something grossly wrong with my thinking or code in betterSwapped
** that I just cannot recognize.  I would _swear_ that each swap here
** improved the genome fitness, preventing an infinite loop, and yet
** somehow one happens anyway with the code commented out here restored.
** Help from onlookers is earnestly solicited.
*/

      int flips = 0;
      do
      {
        flips = 0;

        for ( int j = 0; j < genomeLength; j++ )
        {
          int otherIndex = ( j + span ) % genomeLength;
          if ( j != otherIndex )
          {
            if
            (
              betterSwapped( goat, j, otherIndex, world )
            )
            {
              swap( goat, j, otherIndex, false );

              flips++;

/*
** Running back the other way may possibly improve our algorithm order,
** it makes some sense to roll an out of place codon back around the
** genome; let's try it and hope it isn't pure superstition.  As noticed
** above, unlike the real Shell sort, we cannot stop when we first fail
** to swap, but must "go to the top" every time.  Sigh.  Having
** developed the whole Visual Debugging part of Traveller just to see
** what was going wrong in this one heuristic, I _know_
** QuasiShellSortSwapper works very hard for its supper; I just hope it
** doesn't have an N!  worst case.
*/

              for ( int k = j - span; k >= 0; k-- )
              {
                int alternateIndex = ( k + span ) % genomeLength;
                if ( k != alternateIndex )
                {
                  if ( betterSwapped( goat, k, alternateIndex, world ) )
                  {
                    swap( goat, k, alternateIndex, false );

                    flips++;

                  }
                }
              }

            }
          }
        }

      }
      while ( flips > 0 );

    }
  }

  private void swap
  (
    TravellerChromosome goat,
    int cityIndex1,
    int cityIndex2,
    boolean freeTrialOffer
  )
  {
    int temp = goat.getCity( cityIndex1 );
    goat.setCity( cityIndex1, goat.getCity( cityIndex2 ) );
    goat.setCity( cityIndex2, temp );

    if ( VDB && !freeTrialOffer ) { m_vdb.step( goat, false ); }
  }

  private boolean slowBetterSwapped
  (
    TravellerChromosome goat,
    int cityIndex1,
    int cityIndex2,
    TravellerWorld world
  )
  {
    TravellerChromosome ewe = new TravellerChromosome( goat );
    TravellerChromosome ram = new TravellerChromosome( goat );
    ewe.canonicalize();
    ram.canonicalize();
    int cityName1 = goat.getCity( cityIndex1 );
    int cityName2 = goat.getCity( cityIndex2 );
    int ramCityIndex1 = ram.findCity( cityName1 );
    int ramCityIndex2 = ram.findCity( cityName2 );
    swap ( ram, ramCityIndex1, ramCityIndex2, true );
    if
    (
      ewe.testFitness()
      >
      ( ram.testFitness() + TravellerStatus.LITTLE_FUZZ )
    )
    {
      ram = null;
      ewe = null;
      return true;
    }
    else
    {
      ram = null;
      ewe = null;
      return false;
    }
  }

  private boolean betterSwapped
  (
    TravellerChromosome goat,
    int cityIndex1,
    int cityIndex2,
    TravellerWorld world
  )
  {

    int genomeLength = ValuatorControls.getNumberOfCities();

    double currentFitnessIncrement = 0.0D;
    double swappedFitnessIncrement  = 0.0D;
    int cityName1, cityPredecessorName1, citySuccessorName1;
    int cityName2, cityPredecessorName2, citySuccessorName2;

    cityName1 = goat.getCity( cityIndex1 );
    cityPredecessorName1 =
      goat.getCity( ( cityIndex1 - 1 + genomeLength ) % genomeLength );
    citySuccessorName1 = 
      goat.getCity( ( cityIndex1 + 1 + genomeLength ) % genomeLength );

    cityName2 = goat.getCity( cityIndex2 );
    cityPredecessorName2 =
      goat.getCity( ( cityIndex2 - 1 + genomeLength ) % genomeLength );
    citySuccessorName2 = 
      goat.getCity( ( cityIndex2 + 1 + genomeLength ) % genomeLength );

    currentFitnessIncrement =
      world.getDistance( cityPredecessorName1, cityName1 )
      +
      world.getDistance( cityName1, citySuccessorName1 )
      +
      world.getDistance( cityPredecessorName2, cityName2 )
      +
      world.getDistance( cityName2, citySuccessorName2 );

/*
** We confess that if the two cities are adjacent, we are double
** counting the distance between them, but we don't care, since we are
** double counting the _same_ distance for both current and potentially
** swapped arrangements, and we only care about their relative sizes,
** not their absolute sizes.
*/

//    if ( Math.abs( cityIndex1 - cityIndex2 ) == 1 )
//    {
//      currentFitnessIncrement -=
//        world.getDistance( cityName1, cityName2 );
//    }

    swap( goat, cityIndex1, cityIndex2, true );

    cityName1 = goat.getCity( cityIndex1 );
    cityPredecessorName1 =
      goat.getCity( ( cityIndex1 - 1 + genomeLength ) % genomeLength );
    citySuccessorName1 = 
      goat.getCity( ( cityIndex1 + 1 + genomeLength ) % genomeLength );

    cityName2 = goat.getCity( cityIndex2 );
    cityPredecessorName2 =
      goat.getCity( ( cityIndex2 - 1 + genomeLength ) % genomeLength );
    citySuccessorName2 = 
      goat.getCity( ( cityIndex2 + 1 + genomeLength ) % genomeLength );

    swappedFitnessIncrement =
      world.getDistance( cityName1, cityPredecessorName1 )
      +
      world.getDistance( cityName1, citySuccessorName1 )
      +
      world.getDistance( cityName2, cityPredecessorName2 )
      +
      world.getDistance( cityName2, citySuccessorName2 );

    swap( goat, cityIndex1, cityIndex2, true );

//    if ( Math.abs( cityIndex1 - cityIndex2 ) == 1 )
//    {
//      swappedFitnessIncrement -=
//        world.getDistance( cityName1, cityName2 );
//    }

      boolean result = 
        (
          ( swappedFitnessIncrement + TravellerStatus.LITTLE_FUZZ )
          <
          currentFitnessIncrement
        );

      if (DB && result)
      {
        TravellerChromosome ewe = new TravellerChromosome( goat );
        TravellerChromosome ram = new TravellerChromosome( goat );
        swap( ram, cityIndex1, cityIndex2, true );
        ewe.canonicalize();
        double eweFit = ewe.testFitness();
        ram.canonicalize();
        double ramFit = ram.testFitness();
        if ( ramFit > eweFit )
        System.out.println
        (
          "\r\n"
          + "QuasiShellSortSwapper.betterSwapped(): cI1/cN1/cPN1/cSN1, cI2/cN2/cPN2/cSN2: "
          + cityIndex1 + "/"
          + cityName1 + "/"
          + cityPredecessorName1 + "/"
          + citySuccessorName1 + ", "
          + cityIndex2 + "/"
          + cityName2 + "/"
          + cityPredecessorName2 + "/"
          + citySuccessorName2 + "/"
          + "\r\n"
          + goat.toString()
          + " working version"
          + "\r\n"
          + ewe.toString()
          + " unswapped full "
          + eweFit
          + " and partial "
          + currentFitnessIncrement
          + " fitnesses;"
          + "\r\n"
          + ram.toString()
          + "   swapped full "
          + ramFit
          + " and partial "
          + swappedFitnessIncrement
          + " fitnesses."
          + "\r\n"
          + "currentFitnessIncrement = "
          + "[ world.getDistance( cityPredecessorName1: "
          + cityPredecessorName1
          + ", cityName1: "
          + cityName1
          + ") = "
          + world.getDistance( cityPredecessorName1, cityName1 )
          + "] +"
          + "\r\n"
          + "[ world.getDistance( cityName1: "
          + cityName1
          + ", citySuccessorName1: "
          + citySuccessorName1
          + ") = "
          + world.getDistance( cityName1, citySuccessorName1 )
          + "] +"
          + "\r\n"
          + "[ world.getDistance( cityPredecessorName2: "
          + cityPredecessorName2
          + ", cityName2: "
          + cityName2
          + ") = "
          + world.getDistance( cityPredecessorName2, cityName2 )
          + "] +"
          + "\r\n"
          + "[ world.getDistance( cityName2: "
          + cityName2
          + ", citySuccessorName2: "
          + citySuccessorName2
          + ") = "
          + world.getDistance( cityName2, citySuccessorName2 )
          + "]"
          + "\r\n"
          + "= "
          + currentFitnessIncrement
          + "\r\n"
          + "swappedFitnessIncrement ="
          + "[ world.getDistance( cityName2: "
          + cityName2
          + ", cityPredecessorName1: "
          + cityPredecessorName1
          + ") = "
          + world.getDistance( cityName2, cityPredecessorName1 )
          + "] +"
          + "\r\n"
          + "[ world.getDistance( cityName2: "
          + cityName2
          + ", citySuccessorName1: "
          + citySuccessorName1
          + ") = "
          + world.getDistance( cityName2, citySuccessorName1 )
          + "] +"
          + "\r\n"
          + "[ world.getDistance( cityName1: "
          + cityName1
          + ", cityPredecessorName2: "
          + cityPredecessorName2
          + ") = "
          + world.getDistance( cityName1, cityPredecessorName2 )
          + "] +"
          + "\r\n"
          + "[ world.getDistance( cityName1: "
          + cityName1
          + ", citySuccessorName2: "
          + citySuccessorName2
          + "); = "
          + world.getDistance( cityName1, citySuccessorName2 )
          + "]"
          + "\r\n"
          + "= "
          + swappedFitnessIncrement 
        );
      }
      return result;
  }
}