randomcityloopfornearbycuts.java

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

      // Do spooky bit twiddling magic to save unneeded
      // work in the flipping loop.
      int antiflipMask = 0;
      for (int i = 0; i < permuteSize; i++)
      {
        if (!sublistFlippable[i]) { antiflipMask |= ( 1 << i ) ; }
      }

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

      while ( pg.morePermutations() )
      {

        boolean currentFlips[] = new boolean[permuteSize];
        try
        {
          nextPermutation = pg.getNext();
        }
        catch (Exception e)
        {
          System.out.println
          (
            "caught pg.getNext() throw in TravellerPermuteCitiesWithinASublist"
          );
        }

        // Loop through the possible flips.
        for (int flipWord = 0; flipWord < powerOfTwo; flipWord++)
        {
          // Skip work for don't flipping care subset.
          if ( ( flipWord & antiflipMask ) == 0 )
          {
            for (int i = 0; i < permuteSize; i++)
            {
              currentFlips[i] = ( ( flipWord & (1 << i) ) != 0 );
            }

            double currentFitness = 0.0D;

            for (int i = 0; i < permuteSize; i++)
            {
              int nextIndex = ( i + 1 ) % permuteSize;
              currentFitness +=
                world.getDistance
               (
                 (
                   currentFlips[i]
                   ? sublistBeginCities[nextPermutation[i].intValue()]
                   : sublistEndCities[nextPermutation[i].intValue()]
                 ),
                 (
                   currentFlips[nextIndex]
                   ? sublistEndCities[nextPermutation[nextIndex].intValue()]
                   : sublistBeginCities[nextPermutation[nextIndex].intValue()]
                 )
               );
            }
            if (currentFitness < bestFitness)
            {
              bestFitness = currentFitness;

              // Notice that this time we are actually capturing the
              // permutation rather than what it indexes; we have a
              // bunch of work to do to construct the final product
              // offspring at the end of all this foolishness.

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

      // We are going to scribble on offspring, so use the local name of
      // the input parameter as an unclobbered data source for city names.

      // Starting at the beginning of the output chromosome, offspring,
      // write the sublists in their permuted order, flipped as needed.

      int writeToIndex = 0;

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

        int currentCleavageIndicesIndex = bestPermutation[i];
        int nextCleavageIndicesIndex =
          ( currentCleavageIndicesIndex + 1 ) % permuteSize;
        int currentChromosomeIndex =
          cleavageIndices[currentCleavageIndicesIndex];
        int nextChromosomeIndex =
          ( cleavageIndices[nextCleavageIndicesIndex] - 1 + genomeLength )
          % genomeLength;

        if ( bestFlipped[i] )
        {
          int j = nextChromosomeIndex;
          while ( true )
          {
            offspring.setCity( writeToIndex, coparent.getCity(j));
            writeToIndex++;
            if ( j == currentChromosomeIndex ) { break; }
            j = ( j - 1 + genomeLength ) % genomeLength;
          }
        }
        else
        {
          int j = currentChromosomeIndex;
          while ( true )
          {
            offspring.setCity( writeToIndex, coparent.getCity(j));
            writeToIndex++;
            if ( j == nextChromosomeIndex ) { break; }
            j = ( j + 1 ) % genomeLength;
          }
        }
      }

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

      offspring.canonicalize();

      if
      (
        coparent.testFitness()
        >
        ( offspring.testFitness() + TravellerStatus.LITTLE_FUZZ )
      )
      {
        changeCount++;
        improveCount++;

        updateProgressDisplay
        (
          " lC "
          + loopCount
          + " cC "
          + changeCount
          + " mC "
          + ma.getCount()
          + " iC "
          + improveCount
          + " sC "
          + tryCount
        );

      }

      coparent = new TravellerChromosome( offspring );

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

      if ( ma.setMarkAndCheckIfAllMarksAreSet( z ) ) // seen all cities?
      {
        if ( changeCount == 0 )
        {
          break;  // give up if no improvements occurred.
        }
        else
        {
          changeCount = 0;
          loopCount++;
          ma.setAllMarksFalse(); // otherwise, start over
        }
      }

    }

    updateProgressDisplay
    (
      " lC "
      + loopCount
      + " cC "
      + changeCount
      + " mC "
      + ma.getCount()
      + " iC "
      + improveCount
      + " sC "
      + tryCount
      + " done"
    );

    double finalFitness = offspring.testFitness();

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

  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;
  }

  private int [] pickCities
  (
    TravellerWorld world,
    int permuteSize,
    int codonName
  )
  {

    MersenneTwister mt = MersenneTwister.getTwister();

/*
** Pick a location in the working canvas playfield area in a gaussian
** distribution centered around the the next city in sequence, from
** which to reach out for the nearest permuteSize cities.
*/

    double someCityExactLocation[] = world.getCityExactLocation(codonName);

    double x =
      someCityExactLocation[TravellerWorld.CITY_X]
      + mt.nextGaussian() * gaussianScaler;
    double y =
      someCityExactLocation[TravellerWorld.CITY_Y]
      + mt.nextGaussian() * gaussianScaler;

    if (this.DB) { System.out.println("pickedCities at: " + x + "," + y ); }

    int    cities[]    = new int[permuteSize];
    double distances[] = new double[permuteSize];

    for ( int i = 0; i < permuteSize; i++ )
    {
      cities[i]    = -1;
      distances[i] = Double.MAX_VALUE;
    }

    int genomeLength = world.getNumberOfCities();

    if (this.DB)
    {
      System.out.println( "pickCities, cities: " + Debugging.dump(cities) );
      System.out.println( "pickCities, distances: " + Debugging.dump(distances) );
    }

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

      double cityExactLocation[] = world.getCityExactLocation(i);

      double cx = cityExactLocation[TravellerWorld.CITY_X];
      double cy = cityExactLocation[TravellerWorld.CITY_Y];

      double distance =
        Math.sqrt( ( ( cx - x ) * ( cx - x ) ) + ( ( cy - y ) * ( cy - y ) ) );
      if (this.DB) { System.out.println( "pickCities OK to inner loop" ); }
      double dtemp;
      int    ctemp;
      int    itemp = i;
      for ( int j = 0 ; j < permuteSize; j++ )
      {
        if ( distance < distances[j] )
        {
          dtemp        = distances[j];
          ctemp        = cities[j];
          distances[j] = distance;
          cities[j]    = itemp;
          distance     = dtemp;
          itemp        = ctemp;
        }
      }
      if (this.DB)
      {
        System.out.println( "pickCities, cities,i: " + Debugging.dump(cities) + i );
        System.out.println( "pickCities, distances: " + Debugging.dump(distances) );
      }
    }

    return cities;
  }

  private void updateProgressDisplay( String update )
  {
    if
    (
      CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PROGRESS_COUNTERS)
    ) 
    {
      if ( m_progressDisplay == null )
      {
        m_progressDisplay =
          new SmallDisplay( m_progressDisplayName, SMALL_DISPLAY_WIDTH );
      }
      m_progressDisplay.updateDisplay( update );
    }
    else
    {
      if ( m_progressDisplay != null )
      {
        m_progressDisplay.closeWindow();
        m_progressDisplay = null;
      }
    }
  }

}