quasishellsortinverter.java

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

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

      TravellerChromosome p = (TravellerChromosome) parent;

      TravellerChromosome child = algorithm( p );

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

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

    quasiShellSortInverter( offspring, world );

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

    return offspring; 
  }

  private void invert
  (
    TravellerChromosome goat,
    int cityIndex1,
    int cityIndex2,
    boolean freeTrialOffer
  )
  {

    int j, k;

    if ( cityIndex1 < cityIndex2 )
    {
      k = cityIndex2;
      j = cityIndex1;
    }
    else
    {
      k = cityIndex1;
      j = cityIndex2;
    }

    int s = (k - j + 1) / 2;

/*
** Notice that this works without generating array out of bounds
** exceptions only because we have cleverly made getCity() and setCity()
** employ their indices with modular arithmetic with respect to the
** genome length.
*/

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

/*
** Swap codon names for the segment being inverted.
*/

      int t = goat.getCity( k );
      goat.setCity( k, goat.getCity( j ) );
      goat.setCity( j, t );

      ++j;
      --k;
    } 

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

  private void quasiShellSortInverter
  (
    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
** inversion past that point.  Instead, we just sweep again and again
** over the same direction with the same span until no inversions 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 betterInverted
** that I just cannot recognize.  I would _swear_ that each inversion 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
            (
              betterInverted( goat, j, otherIndex, world )
            )
            {
              invert( 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 invert, 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_
** QuasiShellSortInverter 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 ( betterInverted( goat, k, alternateIndex, world ) )
                  {
                    invert( goat, k, alternateIndex, false );

//                    flips++;

                  }
                }
              }

            }
          }
        }

//      }
//      while ( flips > 0 );

    }
  }

  private boolean slowBetterInverted
  (
    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 );
    invert ( 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 betterInverted
  (
    TravellerChromosome goat,
    int cityIndex1,
    int cityIndex2,
    TravellerWorld world
  )
  {

    int genomeLength = ValuatorControls.getNumberOfCities();

    int lo, hi;

    if ( cityIndex1 < cityIndex2 )
    {
      lo = cityIndex1;
      hi = cityIndex2;
    }
    else
    {
      lo = cityIndex2;
      hi = cityIndex1;
    }

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

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

    double currentFitnessIncrement = 0.0D;
    double invertedFitnessIncrement  = 0.0D;

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

    invertedFitnessIncrement =
      world.getDistance( cityName2, cityPredecessorName1 )
      +
      world.getDistance( cityName1, citySuccessorName2 );

      return
        (
          ( invertedFitnessIncrement + TravellerStatus.LITTLE_FUZZ )
          <
          currentFitnessIncrement
        );

  }
}