randomcityloopfornearbynodesandedges.java

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

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

/*
** Planning:
** 
** Our goal is to find a mix of edges and nodes nearest an initial
** randomly chosen point in the playfield.  We will then create a cut in
** each nearest edge without removing a node, and a cut around each
** nearest node, by removing that node, and then use the same
** optimization as for OptimizeNearAPoint, trying all possible
** permutations of the nodes in all possible arrangements among the
** slots.  The difference here is that we hope to create our mix with
** more slots and fewer nodes than in that other algorithm.
** 
** The purpose of all this is to more easily move a node sitting out on
** a "tooth" to a passing line segment whose defining nodes are far from
** the node-to-be-moved, and therefore not responsive to the usual
** node-wise local optimization tricks.
** 
** We have swiped the algorithm for distance from a point to a line
** segment from the comp.graphics.algorithms FAQ; the pertinent section
** is included as a comment after the body of this class in this text
** file.
*/

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

import java.awt.*;
import java.awt.geom.*;
import java.awt.geom.Point2D.*;
import java.util.*;
import com.coyotegulch.genetic.*;

import com.well.www.user.xanthian.java.genetic.*;
import com.well.www.user.xanthian.java.structures.*;
import com.well.www.user.xanthian.java.tools.*;
import com.well.www.user.xanthian.java.ui.*;

public class RandomCityLoopForNearbyNodesAndEdges
    implements AsexualReproducer
{

  private final static String m_progressDisplayName =
    "The Old Ball and Chain";
  private static SmallDisplay m_progressDisplay = null;
  private static int SMALL_DISPLAY_WIDTH = 30;

  private static double gaussianScaler = 0.0D;

  private class Coordinates
    extends Point2D.Double
  {

    public Coordinates()
    {
      super();
    }

    public Coordinates( TravellerChromosome tc, int index )
    {
      super
      (
        ( ( tc.getWorld() ).getCityExactLocation( tc.getCity( index ) ) )
          [ TravellerWorld.CITY_X ],
        ( ( tc.getWorld() ).getCityExactLocation( tc.getCity( index ) ) )
          [ TravellerWorld.CITY_Y ]
      );
    }

    public Coordinates( double x, double y )
    {
       super( x, y );
    }

  }

/*
** Put defined constants in place of the magic numbers describing the
** location in the returned array of arrays of slot location data as to
** which contained array is where.
*/

  private static final int BEFORES = 0;
  private static final int BEGINS  = 1;
  private static final int ENDS    = 2;
  private static final int AFTERS  = 3;

/*
** The statistics for this style of search are just horrendous, and the
** bigger permutation useful elsewhere overwhelms us here.
*/

  private static final int LOCAL_PERMUTE_LIMIT = 5;

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

      TravellerChromosome p = (TravellerChromosome) parent;

      TravellerChromosome child = algorithm( p );

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

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

    if (VDB) { m_vdb.toFront(); }
    if (m_progressDisplay != null) { m_progressDisplay.toFront(); }

    gaussianScaler =
      TravellerCanvas.WORKING_DIMENSIONS.getWidth()
      / Math.sqrt( (double) ValuatorControls.getNumberOfCities() );

    TravellerWorld world = parent.getWorld();

    TravellerChromosome offspring = new TravellerChromosome( parent );

    offspring.canonicalize();

    double startingFitness = offspring.testFitness();

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

    int genomeLength = offspring.getNumCities();

    if (DB)
    {
      System.out.println
      (
        "RandomCityLoopForNearbyNodesAndEdges, initial genome"
      );
      System.out.println( offspring.toString() );
    }

    MersenneTwister mt = MersenneTwister.getTwister();

    TravellerChromosome coparent = new TravellerChromosome( offspring );

    MarkArray ma = new MarkArray( genomeLength );

    int changeCount = 0;
    int improveCount = 0;
    int tryCount = 0;
    int loopCount = 0;

    updateProgressDisplay
    (
      " lC "
      + loopCount
      + " cC "
      + changeCount
      + " mC "
      + ma.getCount()
      + " iC "
      + improveCount
      + " sC "
      + tryCount
    );

    // for ( int z = 0; z < genomeLength; z++ )
    while (true)
    {

      tryCount++;

      int z = mt.nextInt( genomeLength );

/*
** Our local permute limit is probably smaller than the global one, so
** compound it with the genome length limit as an "other limit" to pass
** to the permutation controller.
*/

      PermutationGenerator pg = ( new PermutationController() )
        .getGenerator
        (
          Math.min
          (
            genomeLength - 1,
            LOCAL_PERMUTE_LIMIT
          )
        );
      int permuteSize = pg.getPermutationSize();

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

      double someCityExactLocation[] = world.getCityExactLocation(z);

      double x =
        someCityExactLocation[TravellerWorld.CITY_X]
        + mt.nextGaussian() * gaussianScaler;
      double y =
        someCityExactLocation[TravellerWorld.CITY_Y]
        + mt.nextGaussian() * gaussianScaler;

      Coordinates nearnessPoint = new Coordinates( x, y );

      if (this.DB)
      {
        System.out.println
        (
           "RandomCityLoopForNearbyNodesAndEdges selected initial point at: "
           + x
           + ","
           + y
           + " for iteration and city name "
           + z
        );
      }

/*
** Pick the closest permutation-full of citys to some point in the world.
*/

      int cityList[] = null;
      try { cityList = pickCities( world , permuteSize, nearnessPoint ); }
      catch (Exception pc) { if (DB) System.out.println( "pickCities threw" ); }
      finally { if (DB) System.out.println( "pickCities ran" ); }

/*
** Pick the closest permutation-full of edges facing the point to some
** point in the world.  That is, a perpendicular to the edge dropped
** from the point should fall on the edge between the two cities
** defining the edge, not on some projection of the edge beyond its
** delimiting cities.  Notice that it is quite possible to get back a
** null result here, representing that there were no such facing edges
** for the nearnessPoint selected.
*/

      Edge cityEdges[] = null;
      try { cityEdges = pickEdges( offspring, world, permuteSize, nearnessPoint ); }
      catch (Exception pc) { if (DB) System.out.println( "pickEdges threw" ); }
      finally { if (DB) System.out.println( "pickEdges ran" ); }

/*
** Do these next assignments in a local context so that the
** slotBeginEndLists array of arrays can go to the garbage collector as
** soon as possible.
*/


      int slotBefores[]    = null;
      int slotBeginnings[] = null;
      int slotEndings[]    = null;
      int slotAfters[]     = null;

      do
      {
        try {
        int slotBeginEndLists[][] = findSlots( cityEdges, cityList, offspring ); 

        slotBefores    = slotBeginEndLists[BEFORES];
        slotBeginnings = slotBeginEndLists[BEGINS];
        slotEndings    = slotBeginEndLists[ENDS];
        slotAfters     = slotBeginEndLists[AFTERS];
        }
        catch (Exception fs) { if (DB) System.out.println( "findSlots threw" ); }
        finally { if (DB) System.out.println( "findSlots ran" ); }
      }
      while (false); // one pass loop, used for the context limit only.

      int howManySlots = slotBeginnings.length;

      Vector slotOccupants = null;
      try { slotOccupants = slotCounts( permuteSize, howManySlots ); }
      catch (Exception sc) { if (DB) System.out.println( "slotCounts threw" ); }
      finally { if (DB) System.out.println( "slotCounts ran" ); }

      int slotArrays = slotOccupants.size();

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

      int bestSlotFills[] = new int[howManySlots];
      for (int i = 0; i < howManySlots; i++)
      {
        bestSlotFills[i] = 0;
      }
      bestSlotFills[0] = permuteSize;

      double bestFitness = java.lang.Double.MAX_VALUE;

      Integer [] nextPermutation = null;

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

        try {
        for ( int i = 0; i < slotArrays; i++ )
        {
          int nextSlotFills[] = (int []) slotOccupants.get(i);

          double nextFitness =
            fitnessIncrement
            (
              nextPermutation,
              nextSlotFills,
              cityList,
              slotBefores,
              slotBeginnings,
              slotEndings,
              slotAfters,
              offspring
            );

          if ( nextFitness < bestFitness )
          {

            bestFitness = nextFitness;

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

            for (int j = 0; j < howManySlots; j++)
            {
              bestSlotFills[j] = nextSlotFills[j];
            }

//          System.out.println
//          (
//            "bP: "
//            + Debugging.dump( bestPermutation )
//            + "; bSF: "
//            + Debugging.dump( bestSlotFills )
//          );
          }
        }
        }
        catch ( Exception ml ) { if (DB) System.out.println( "fitLoop threw" ); }
        finally { /* if (DB) System.out.println( "fitLoop ran" ); */ }
      }
      }
      catch ( Exception ml ) { if (DB) System.out.println( "morePerms threw" ); }
      finally { if (DB) System.out.println( "morePerms ran" ); }


      if (DB)
      {
        for (int i = 0; i < genomeLength; i++) { offspring.setCity(i, -1); }
        System.out.println ( "cityList       : " + Debugging.dump(cityList) );
        System.out.println ( "bestSlotFills  : " + Debugging.dump(bestSlotFills) );
        System.out.println ( "bestPermutation: " + Debugging.dump(bestPermutation) );
        System.out.println ( "slotBefores    : " + Debugging.dump(slotBefores) );
        System.out.println ( "slotBeginnings : " + Debugging.dump(slotBeginnings) );
        System.out.println ( "slotEndings    : " + Debugging.dump(slotEndings) );
        System.out.println ( "slotAfters     : " + Debugging.dump(slotAfters) );
      }

      int placeInPermutation = 0;
      int placeInChildGenome = 0;
      try {
      for (int i = 0; i < howManySlots; i++)
      {
        int slotBefore = slotBefores[i];
        int slotAfter  = slotAfters[ ( i + howManySlots - 1 ) % howManySlots ];
        if (DB)
        {
          System.out.println
          (
            "slotBefore/slotAfter: " 
            + slotBefore
            + "/"
            + slotAfter
          ); 
        }

/*
** Copy the segment of genome before the current slot.
*/

        if ( slotBefore < slotAfter ) { slotBefore += genomeLength; }
        for ( int j = slotAfter; j <= slotBefore; j++ )
        {
          offspring.setCity
          (
            placeInChildGenome++,
            ( (TravellerChromosome) coparent ).getCity(j)
          );
          if (DB)
          {
            System.out.println
            (
              "adding unpermuted i/j/offspring: "
              + i
              + "/"
              + j
              + "/"
              + offspring.toString()
            );
          }
        }

/*
** Copy the segment of genome within the current slot, if any.  The "if
** any" part is the trick that makes this fairly simple copying work.
*/

        for ( int j = 0; j < bestSlotFills[i]; j++ )
        {
          offspring.setCity
          (
            placeInChildGenome++,
            cityList[bestPermutation[placeInPermutation++]]
          );
          if (DB)
          {
            System.out.println
            (
              "adding   permuted i/j/offspring: "
              + i
              + "/"
              + j
              + "/"
              + offspring.toString()
            );
          }
        }