disorderedslide.java

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

/*
** This code was written from scratch by Kent Paul Dolan.  See
** accompanying file TravellerDoc.html for status of the code here for
** your use.
*/

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

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 DisorderedSlide
    implements Mutator
{

  private static boolean DB = false;
  private static boolean        VDB   = false;
  private static VisualDebugger m_vdb = null;
  private static boolean adaptPermutation = false;

  public Chromosome mutate(Chromosome parent)
  {
    adaptPermutation = false;
    return this.guts( parent );
  }

  public Chromosome reproduce(Chromosome parent)
  {
    adaptPermutation = true;
    return this.guts( parent );
  }

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

      TravellerChromosome p = (TravellerChromosome) parent;

      TravellerChromosome child = algorithm( p );

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

    }
    catch (Exception e)
    {
      System.err.println
      (
        "DisorderedSlide.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( "DisorderedSlide" );
      }
    }
    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 ); }

/*
** Develop a selection probability from fairly pure superstition.
** 
** FIXME The selection seems to be the key to making this work; the set
** selected should be more compact the further into the run we get; use
** the current permutation limit compared to the global ("high")
** permutation limit as a gauge of how far into the run we are, and
** build a selection chance from their relationship.
*/

    int genomeLength = ValuatorControls.getNumberOfCities();
    int permuteGlobalLimit =
      PermutationController.getGlobalPermuteLimit();
    int permuteStartingLimit =
      PermutationController.getStartingPermuteLimit();
    int permuteCurrentLimit =
      PermutationController.getCurrentPermuteLimit();
    double selectionChance = 0.0D;

    if ( genomeLength > permuteGlobalLimit )
    {
      selectionChance =
        ( (double) permuteCurrentLimit ) /
        ( (double) ( permuteStartingLimit + permuteGlobalLimit ) );
    }
    else
    {
      selectionChance = ( (double) permuteGlobalLimit ) / 100.0D;
    }

    int selectees[] = new int[ genomeLength ];
    boolean selected[] = new boolean[ genomeLength ];

    for ( int i = 0; i < genomeLength; i++ )
    {
      selectees[i] = -1;
      selected[i]  = false;
    }

/*
** Start at some offset into the genome, so that a compact subset will
** be in some general location.
*/

    int offset = mt.nextInt(genomeLength);

    int selectionCount = 0;

/*
** Here again we depend on the design choice that getCity() does modular
** arithmetic on the genome index, so we can pass in an index beyond the
** end of the genome with no dire consequences.
*/

    for ( int i = 0; i < genomeLength; i++ )
    {
      if ( mt.nextDouble() < selectionChance )
      {
        selectees[selectionCount] = parent.getCity(i + offset);
        selected[( i + offset ) % genomeLength] = true;
        selectionCount++;
      }

/*
** Limit ourselves to a fairly small selected set, to limit how much
** entropy we introduce.
*/

      if ( selectionCount >= permuteCurrentLimit) { break; }
    }

    if ( selectionCount != 0 )
    { 
      int unselectedIndex = 0;
      int copiedCount = 0;

/*
** Copy a leftmost random fraction of the unselected codons in order to
** the left end of the output genome.
*/

      int lefties = mt.nextInt( genomeLength - selectionCount );

      while ( copiedCount < lefties )
      {
        while ( selected[ unselectedIndex ] )
        {
          unselectedIndex++;
        }
        offspring.setCity( copiedCount, parent.getCity( unselectedIndex ) );
        unselectedIndex++;
        copiedCount++;
      }

/*
** Disorganize the selected subset of the codons.
*/

      // Permute in usual way.

      for
      (
        int currentSlot = selectionCount - 1;
        currentSlot > 0; // no need to swap only remaining slot with itself
        currentSlot--
      )
      {

        // Pick some location from self to beginning of array,
        // swap current slot's occupant with the bloke in that
        // location.

        // Picking self leaves occupant in current slot, though
        // occupant may have been moved by some previous swap.

        int swapSlot   = mt.nextInt(currentSlot + 1); // include own slot
        int temp = selectees[swapSlot];
        selectees[swapSlot]  = selectees[currentSlot];
        selectees[currentSlot] =  temp;

      }

/*
** Copy the selected codons in disorder to the middle of the output
** genome.
*/

      for ( int i = 0; i < selectionCount; i++ )
      {
        offspring.setCity( copiedCount, selectees[i] );
        copiedCount++;
      }

/*
** Copy the remaining unselected codons in order to the right end of the
** output genome.
*/

      while ( copiedCount < genomeLength )
      {
        while ( selected[ unselectedIndex ] )
        {
          unselectedIndex++;
        }
        offspring.setCity( copiedCount, parent.getCity( unselectedIndex ) );
        unselectedIndex++;
        copiedCount++;
      }

    }

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

    offspring.canonicalize();
    double finalFitness = offspring.testFitness();

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

/*
** We change for the better or worse, mostly for the worse.  Report back
** so that adaptive permutation high limit can eventually be updated,
** but only do that if we are being called as a reproducer, not as a
** mutator.
*/

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

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

  }

  public boolean isSuitableForMultipleMutationRuns() { return false; }
}