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

      TravellerChromosome p = (TravellerChromosome) parent;

      TravellerChromosome child = algorithm( p );

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

    }
    catch (Exception e)
    {
      System.err.println
      (
        "PermuteScatteredCities.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( "PermuteScatteredCities" );
      }
    }
    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 = parent.getWorld();
    int genomeLength = ValuatorControls.getNumberOfCities();

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

    boolean [] predecessorIsPermutee = new boolean[permuteSize];
    boolean [] successorIsPermutee = new boolean[permuteSize];
    int [] predecessorIndexInPermutees = new int[permuteSize];
    int [] predecessorIndexInGenome = new int[permuteSize];
    int [] successorIndexInPermutees = new int[permuteSize];
    int [] successorIndexInGenome = new int[permuteSize];

    // pick permutee indices
    int [] permuteeIndices = new int[permuteSize];
    int cityNamesSublist[] = new int[permuteSize];

    // initialize lists
    for (int i = 0; i< permuteSize; i++)
    {
      permuteeIndices[i] = -1;
      cityNamesSublist[i] = -1;
      predecessorIsPermutee[i] = false;
      successorIsPermutee[i] = false;
      predecessorIndexInPermutees[i] = -1;
      predecessorIndexInGenome[i] = -1;
      successorIndexInPermutees[i] = -1;
      successorIndexInGenome[i] = -1;
    }

    // fill permutee list with unique entries
    for (int i = 0; i< permuteSize; i++)
    {

      int index = mt.nextInt( genomeLength );

      while ( inList( index, permuteeIndices ) )
      {
        index = mt.nextInt( genomeLength );
      }

      permuteeIndices[i] = index;

      // copy permutation targets to working array
      cityNamesSublist[i] = offspring.getCity( permuteeIndices[i] );

    }

/*
** For fitness contribution sums, we need to know whether the successor
** and predecessor chromosome elements are also permutees, so that we
** don't double count distances between permutees.  Make two lookup
** lists containing this information.  We also need to know where to go
** to get the predecessor and successor city numbers, so make two more
** lookup lists containing that information.
*/

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

       int previousIndexInGenome =
         ( ( permuteeIndices[i] - 1 + genomeLength ) % genomeLength );

       int nextIndexInGenome =
         ( ( permuteeIndices[i] + 1 ) % genomeLength );

       predecessorIsPermutee[i] =
         inList( previousIndexInGenome, permuteeIndices);

       successorIsPermutee[i] =
         inList( nextIndexInGenome, permuteeIndices);

/*
** DANGER, WILL ROBINSON!
** 
** We are putting two different _kinds_ of information in these two
** arrays.  If the associated index points to chromosome location of a
** non-permutee, we insert the index in the chromosome of the associated
** city.  If the associated index points to the chromosome location of a
** permutee, we are going to have to access that permutee indirectly via
** the permutation mechanism, so we put (omigod, my brane's on fire,
** Beelz) the location in the permutation mechanism that accesses the
** corresponding chromosome slot.
*/

       if ( predecessorIsPermutee[i] )
       {
         predecessorIndexInPermutees[i] =
           listIndex( previousIndexInGenome, permuteeIndices );
       }
       else
       {
         predecessorIndexInGenome[i] = previousIndexInGenome;
       }

       if ( successorIsPermutee[i] )
       {
         successorIndexInPermutees[i] =
           listIndex( nextIndexInGenome, permuteeIndices );
       }
       else
       {
         successorIndexInGenome[i] = nextIndexInGenome;
       }
    }

    // System.out.println( Debugging.dump( permuteeIndices ) + " permuteeIndices");
    // System.out.println( Debugging.dump( cityNamesSublist ) + " cityNamesSublist");
    // System.out.println( Debugging.dump( predecessorIsPermutee ) + " predecessorIsPermutee");
    // System.out.println( Debugging.dump( successorIsPermutee ) + " successorIsPermutee");
    // System.out.println( Debugging.dump( predecessorIndexInPermutees ) + " predecessorIndexInPermutees");
    // System.out.println( Debugging.dump( predecessorIndexInGenome ) + " predecessorIndexInGenome");
    // System.out.println( Debugging.dump( successorIndexInPermutees ) + " successorIndexInPermutees");
    // System.out.println( Debugging.dump( successorIndexInGenome ) + " successorIndexInGenome");

    int bestPermutation[] = new int[permuteSize];

    for (int i = 0; i < permuteSize; i++)
    {
      // bestPermutation[i] = cityNamesSublist[i];
      bestPermutation[i] = i;  // start with identity permutation
    }

    double bestFitness = startingFitness;
    Integer [] nextPermutation = null;

    while ( pg.morePermutations() )
    {

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

/*
** Compute fitness contribution for this permutation of the edges
** connecting the permutees to their 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.
*/
      StringBuffer b = new StringBuffer();
      double currentFitness = 0.0D;

      for (int i = 0; i < permuteSize; i++)
      {
        int predecessorCityName = -1;
        int successorCityName = -1;
        int currentCityName =
          cityNamesSublist[ nextPermutation[i].intValue() ];

        // Add contribution of predecessor edge.
        if ( predecessorIsPermutee[i] )
        {
          predecessorCityName =
            cityNamesSublist[ nextPermutation[ predecessorIndexInPermutees[i] ].intValue() ] ;
        }
        else
        {
          predecessorCityName =
            offspring.getCity( predecessorIndexInGenome[i] );
        }

        double predecessorContribution =
          world.getDistance( predecessorCityName, currentCityName );
        if ( predecessorIsPermutee[i] ) { predecessorContribution *= 0.5D; }
        currentFitness += predecessorContribution;
        b.append( " pC,cC,pIP: " + predecessorCityName + "," + currentCityName + "," + ( predecessorIsPermutee[i] ? "t" : "f" ) );

        // Add contribution of successor edge.
        if ( successorIsPermutee[i] )
        {
          successorCityName =
            cityNamesSublist[ nextPermutation[ successorIndexInPermutees[i] ].intValue() ] ;
        }
        else
        {
          successorCityName =
            offspring.getCity( successorIndexInGenome[i] );
        }

        double successorContribution =
          world.getDistance( currentCityName, successorCityName );
        if ( successorIsPermutee[i] ) { successorContribution *= 0.5D; }
        currentFitness += successorContribution;
        b.append( " cC,sC,sIP: " + currentCityName + "," + successorCityName + "," + ( successorIsPermutee[i] ? "t" : "f" ) + ";");

      }

      if ( currentFitness < bestFitness )
      {
        bestFitness = currentFitness;
        for (int i = 0; i < permuteSize; i++)
        {
          bestPermutation[i] = nextPermutation[i].intValue();
        }
        // System.out.println
        // (
        //   "bP:" + Debugging.dump( bestPermutation ) + b.toString()
        // );
      }
    }

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

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

    offspring.canonicalize();
    // System.out.println ( Debugging.dump(bestPermutation) + " bestP Scattered" );
    // System.out.println ( offspring.toString() + " final Scattered" );

    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();
      // System.out.println ( "F: " + startingFitness + " / " + finalFitness + " Scattered" );
    }
    else
    {
      PermutationController.reportSuccess();
      // System.out.println ( "S: " + startingFitness + " / " + finalFitness + " Scattered" );
    }

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

  private boolean inList( int c, int list[] )
  {
    for (int i = 0; i < list.length; i++)
    {
      if (c == list[i]) { return true; }
    }
    return false;
  }

  private int listIndex( int c, int list[] )
  {
    for (int i = 0; i < list.length; i++)
    {
      if (c == list[i]) { return i; }
    }
    return -1;
  }

}