permutecitieswithinasublist.java

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

/*
** This code was written by Kent Paul Dolan, from scratch.  So far as I
** know, it is an original (though obvious) algorithm.  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.*;

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

      TravellerChromosome p = (TravellerChromosome) parent;

      TravellerChromosome child = algorithm( p );

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

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

    TravellerWorld world = offspring.getWorld();
    int genomeLength = ValuatorControls.getNumberOfCities();

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

    // pick indexes
    int from, to;

    from = mt.nextInt( genomeLength );
    to   = ( ( from + permuteSize - 1 ) % genomeLength );
    int predecessorCity = offspring.getCity( from - 1 );
    int successorCity   = offspring.getCity( to + 1 );

    int sublist[] = new int[permuteSize];
    int bestPermutation[] = new int[permuteSize];

    // copy permutation targets to working array
    for (int i = 0; i < permuteSize; i++)
    {
      sublist[i] = offspring.getCity( from + i );
      bestPermutation[i] = sublist[i];
    }

    double bestFitness = Double.MAX_VALUE;
    Integer [] nextPermutation = null;

    while ( pg.morePermutations() )
    {

      try
      {
        nextPermutation = pg.getNext();
      }
      catch (Exception e)
      {
        System.out.println("caught exception in TravellerPermuteCitiesWithinASublist");
      }

      // Compute fitness contribution of this permutation of the
      // sublist being permuted, plus the edges connecting it to
      // the predecessor and successor cities.  The rest of the
      // circuit has a constant fitness, which can be ignored for
      // purposes of picking out the best permutation here.

      double currentFitness = 0.0D;

      // Add contribution of predecessor edge.
      currentFitness +=
        world.getDistance
        (
          predecessorCity,
          sublist[ nextPermutation[0].intValue() ]
        );

      // Add contribution of permuteSize - 1 internal edges.
      for (int i = 1; i < permuteSize; i++)
      {
        currentFitness +=
          world.getDistance
          (
            sublist[ nextPermutation[i - 1].intValue()] ,
            sublist[ nextPermutation[i].intValue()] 
          );
      }

      // Add contribution of successor edge.
      currentFitness +=
        world.getDistance
        (
          sublist[ nextPermutation[permuteSize - 1].intValue()],
          successorCity
        );

      if ( currentFitness < bestFitness )
      {
        bestFitness = currentFitness;
        for (int i = 0; i < permuteSize; i++)
        {
          bestPermutation[i] = sublist[ nextPermutation[i].intValue()];
        }
      }
    }

    for (int i = 0; i < permuteSize; i++)
    {
      offspring.setCity( (from + i) , bestPermutation[i] );
    }

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

    offspring.canonicalize();
    double finalFitness = offspring.testFitness();
    if (VDB) { m_vdb.step( offspring ); }

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

    if
    (
      Math.abs( finalFitness - startingFitness )
      <
      TravellerStatus.LITTLE_FUZZ
    )
    {
      PermutationController.reportFailure();
    }
    else
    {
      PermutationController.reportSuccess();
    }

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