optimizenodesnearapoint.java

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

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

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

import java.awt.*;
import java.util.*;
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.*;

public class OptimizeNodesNearAPoint
    implements AsexualReproducer
{

/*
** 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 = 7;

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

      TravellerChromosome p = (TravellerChromosome) parent;

      TravellerChromosome child = algorithm( p );

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

    }
    catch (Exception e)
    {
      System.err.println
      (
        "OptimizeNodesNearAPoint.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( "OptimizeNodesNearAPoint" );
      }
    }
    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
      (
        "OptimizeNodesNearAPoint, 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 the closest permutation-full of citys to some point in the world.
*/

    int cityList[] = null;
    try { cityList = pickCities( world , permuteSize); }
    catch (Exception pc) { if (DB) System.out.println( "pickCities threw" ); }
    finally { if (DB) System.out.println( "pickCities 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( 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 = 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 OptimizeNodesNearAPoint"
        );
      }

      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 OptimizeNodesNearAPoint"
      );
      System.out.println
      (
        Debugging.dump(bestPermutation)
        + " bestPermutation in OptimizeNodesNearAPoint"
      );
      System.out.println
      (
        offspring.toString()
        + " final offspring genome in OptimizeNodesNearAPoint"
      );
    }

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

    double finalFitness = offspring.testFitness();

/*
** We only change for the better, so if we haven't changed, we haven't
** improved.  Report back so that the adaptive permutation high limit
** can eventually be updated.
*/

    if
    (
      Math.abs( finalFitness - startingFitness )
      <
      TravellerStatus.LITTLE_FUZZ
    )
    {
      PermutationController.reportFailure();
      // System.out.println ( "F: " + startingFitness + " / " + finalFitness + " Near" );
    }
    else
    {
      PermutationController.reportSuccess();
      // System.out.println ( "S: " + startingFitness + " / " + finalFitness + " Near" );
    }

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

    return offspring;
  }

  private double fitnessIncrement
  (
    Integer             permutation[],
    int                 slotCounts[],
    int                 cityList[],
    int                 slotBefores[],
    int                 slotBeginnings[],
    int                 slotEndings[],