quasiquicksort.java

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

/*
** 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 quicksort, with no particular expectations
** about what will result, except possibly better fitness.  Like
** quicksort, expected complexity NlogN, worst case N*N.
*/

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

      TravellerChromosome p = (TravellerChromosome) parent;

      TravellerChromosome child = algorithm( p );

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

    }
    catch (Exception e)
    {
      System.err.println
      (
        "QuasiQuickSort.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( "QuasiQuickSort" );
      }
    }
    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();
    if (VDB) { m_vdb.setup( offspring ); }

    int genomeLength = ValuatorControls.getNumberOfCities();

    TravellerWorld world = parent.getWorld();

/*
** Put the genome ring into a somewhat general orientation by moving the
** divison between codons that defines the "left and right ends of the
** array", from the beginning and end of the physical array, to some
** arbitrary location in the genome.
*/

    int left = mt.nextInt( genomeLength );

    int right = ( left - 1 + genomeLength ) % genomeLength;

    quasiQuickSort( offspring, left, right , world, mt);

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

    return offspring; 

  }

  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 void quasiQuickSort
  (
    TravellerChromosome goat,
    int leftArrayEnd,
    int rightArrayEnd,
    TravellerWorld world,
    MersenneTwister mt
  )
  {

    if ( leftArrayEnd == rightArrayEnd ) { return; }

    int genomeLength = ValuatorControls.getNumberOfCities();

    int arrayLength =
      ( leftArrayEnd < rightArrayEnd )
      ? ( rightArrayEnd - leftArrayEnd + 1 )
      : ( ( rightArrayEnd + genomeLength ) - leftArrayEnd + 1 );

/*
** Randomize pivot choice, rather than using the midpoint.
*/

    int pivotArrayIndex;

    int flips = 0;

    do
    {
      flips = 0;
      pivotArrayIndex =
        ( ( leftArrayEnd + mt.nextInt( arrayLength ) ) % genomeLength );

      int lowArrayIndex  = leftArrayEnd;
      int highArrayIndex = rightArrayEnd;

      while ( lowArrayIndex != highArrayIndex )
      {
        if ( betterSwapped( goat, lowArrayIndex, pivotArrayIndex, world ) )
        {
          swap( goat, lowArrayIndex, pivotArrayIndex, false );
          flips++;
          pivotArrayIndex = lowArrayIndex;
        }
        lowArrayIndex = ( ( lowArrayIndex + 1 ) % genomeLength );
        if ( highArrayIndex != lowArrayIndex )
        {
          if ( betterSwapped( goat, pivotArrayIndex, highArrayIndex, world ) )
          {
            swap( goat, pivotArrayIndex, highArrayIndex, false );
            flips++;
            pivotArrayIndex = highArrayIndex;
          }
          highArrayIndex =
            ( ( highArrayIndex - 1 + genomeLength ) % genomeLength ) ;
        }
      }
    }
    while ( flips != 0 );

    if ( pivotArrayIndex != leftArrayEnd )
    {
      quasiQuickSort
      (
        goat,
        leftArrayEnd,
        ( ( pivotArrayIndex - 1 + genomeLength ) % genomeLength ),
        world,
        mt
      );
    }

    if ( pivotArrayIndex != rightArrayEnd )
    {
      quasiQuickSort
      (
        goat,
        ( ( pivotArrayIndex + 1 ) % genomeLength ),
        rightArrayEnd,
        world,
        mt
      );
    }
  }

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

}