optimizenodesneareverycity.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.layouts.*;
import com.well.www.user.xanthian.java.tools.*;
import com.well.www.user.xanthian.java.ui.*;

public class OptimizeNodesNearEveryCity
    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;

  private static double gaussianScaler = 0.0D;

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

      TravellerChromosome p = (TravellerChromosome) parent;

      TravellerChromosome child = algorithm( p );

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

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

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

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

    TravellerWorld world = parent.getWorld();

    TravellerChromosome offspring = new TravellerChromosome( parent );

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

    if (DB)
    {
      System.out.println ( offspring.toString() + " starting NearEveryCity" );
    }

    double startingFitness = offspring.testFitness();

    int genomeLength = ValuatorControls.getNumberOfCities();

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

    MersenneTwister mt = MersenneTwister.getTwister();


/*
** After merely 12 hours of debugging, I remember that when I am
** building cascaded, I need to make a fresh copy of the genome each
** pass to use for the next pass, I can't keep using the original parent
** forever.   Aaaaargh!
*/

    TravellerChromosome coparent = new TravellerChromosome( offspring );

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

/*
** 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, z ); }
      catch (Exception pc)
      {
        System.err.println
        (
          "ERROR! OptimizeNodesNearEveryCity.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
      {
        int slotBeginEndLists[][] = null; 
        try
        {

/*
** This is the guy whose storage we want to go away, because he is
** redundant as soon as copies are captured of his contents.  He exists
** only as a package that can be the single return of findSlots().
*/

          slotBeginEndLists = findSlots( cityList, offspring ); 

        }
        catch (Exception fs)
        {
          System.err.println
          (
            "ERROR! OptimizeNodesNearEveryCity.findSlots() threw"
          );
        }
        finally { if (DB) System.out.println( "findSlots ran" ); }

/*
** These guys extract copies of the data from the above fellow, these we
** keep, which is why they are declared outside of this limited context.
*/

        try
        {

          slotBefores    = slotBeginEndLists[BEFORES];
          slotBeginnings = slotBeginEndLists[BEGINS];
          slotEndings    = slotBeginEndLists[ENDS];
          slotAfters     = slotBeginEndLists[AFTERS];

        }
        catch (Exception fs)
        {
          System.err.println
          (
            "ERROR! OptimizeNodesNearEveryCity: "
            + "assignments after findSlots() threw"
          );
        }
        finally { if (DB) System.out.println( "assignments after findSlots ran" ); }
      }
      while (false); // one pass loop, used for the context limit only.

      int howManySlots = slotBeginnings.length;

      Vector slotOccupants = null;
      try { slotOccupants = createSlotCounts( permuteSize, howManySlots ); }
      catch (Exception sc)
      {
        System.err.println
        (
          "ERROR! OptimizeNodesNearEveryCity.createSlotCounts() 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.err.println
            (
              "ERROR! OptimizeNodesNearEveryCity.reproduce(): "
              + "pg.getNext() threw!"
            );
          }

          StringBuffer b = new StringBuffer();

          try
          {

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

              b.append( "fitness loop mark 001" );

              int nextSlotFills[] = (int []) slotOccupants.get(i);

              b.append( "fitness loop mark 002" );

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

              b.append( "fitness loop mark 003" );

              if ( nextFitness < bestFitness )
              {

                b.append( "fitness loop mark 004" );

                bestFitness = nextFitness;

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

                b.append( "fitness loop mark 005" );

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

                b.append( "fitness loop mark 006" );

                if (DB)
                {

/*
** The output of this is extremely voluminous, because it is in a hot
** loop; only enble it if the fitness loop starts throwing!
*/

                  b.append
                  (
                    "bP: "
                    + Debugging.dump( bestPermutation )
                    + "; bSF: "
                    + Debugging.dump( bestSlotFills )
                  );

                }

                b.append( "fitness loop mark 007" );

              }