optimizenodesandedgesnearapoint.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 OptimizeNodesAndEdgesNearAPoint
    implements AsexualReproducer
{

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

      TravellerChromosome p = (TravellerChromosome) parent;

      TravellerChromosome child = algorithm( p );

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

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

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

    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
      (
        "OptimizeNodesAndEdgesNearAPoint, initial genome"
      );
      System.out.println( offspring.toString() );
    }

    MersenneTwister mt = MersenneTwister.getTwister();

/*
** 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 x =
      mt.nextDouble( 0.0D, TravellerCanvas.WORKING_DIMENSIONS.getWidth() );
    double y =
      mt.nextDouble( 0.0D, TravellerCanvas.WORKING_DIMENSIONS.getHeight() );

    Coordinates nearnessPoint = new Coordinates( x, y );

    if (this.DB)
    {
      System.out.println
      (
         "OptimizeNodesAndEdgesNearAPoint selected initial point at: "
         + x
         + ","
         + y
      );
    }

/*
** 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 OptimizeNodesAndEdgesNearAPoint"
        );
      }

      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) parent ).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()
          );
        }
      }
    }
    }
    catch ( Exception cl ) { if (DB) System.out.println( "copy loop threw" ); }
    finally { if (DB) System.out.println( "copy loop ran" ); }

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

    offspring.canonicalize();

    if (DB)
    {
      System.out.println
      (
        Debugging.dump(bestSlotFills)
        + " bestSlotFills in OptimizeNodesAndEdgesNearAPoint"
      );