edgepreservingcycliccrossover.java

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

        }
      }

      if (DB)
      {
        dbb
          .append
          (
            "\r\n"
            + Debugging.dump( (Object []) el )
            + "/"
            + matchesCount
            + " matched edges found in EPCXO's matchEdgesAndMarkMatches()"
          )
          .append
          (
           "\r\n"
           +  sel.toString() 
           + " sel after matching markups"
          )
          .append
          (
           "\r\n"
           + del.toString()
           + " del after matching markups"
          )
          .append
          (
            "\r\n"
            + Debugging.dump(sMarks)
            + " sMarks after matching markups"
          )
          .append
          (
            "\r\n"
            + Debugging.dump(dMarks)
            + " dMarks after matching markups"
          )
          ;
      }

      if (DB)
      {
        System.out.println( dbb.toString() );
        System.out.println();
      }

    return matchesCount;
  }

  private void binListToGenome
  (
    int bins[][],
    int binCount,
    TravellerChromosome g,
    boolean DB
  )
  {

        StringBuffer dbb = new StringBuffer();

        dbb.append
        (
          "\r\n"
          + Debugging.dump( bins )
          + "/"
          + binCount
          + " bins/binCount on entering binListToGenome"
        );

/*
** Fill offspring with invalid city markers when debugging.
*/

        if (DB) { g.invalidateCities(); }

        if (DB)
        {
          dbb.append
          (
            "\r\n"
            + g.toString()
            + " genome at start of build from bins"
          );
        }

        int gUsed = 0;

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

          for ( int q = 0; q < bins[i].length; q++ )
          {
            g.setCity( gUsed, bins[i][q] );
            gUsed++;
          }

          if (DB)
          {
            dbb.append
            (
              "\r\n" + g.toString() + " genome during build from bins"
            );
          }

          if (DB)
          {
            System.out.println( dbb.toString() );
            System.out.println();
            dbb = new StringBuffer();
          }

        }

  }

  private void flipBins
  (
    int bins[][],
    int binCount,
    TravellerWorld world,
    boolean DB
  )
  {

/*
** Danger, Will Robinson!  Array bins is of length genomeLength, but not
** all its elements are necessarily non-null!
*/

    StringBuffer dbb = new StringBuffer();
    int genomeLength = ValuatorControls.getNumberOfCities();

    if (DB)
    {
      dbb.append
      (
        "\r\n"
        + Debugging.dump(bins)
        + "/"
        + binCount
        + " entering flipBins"
      );
    }

    if (DB)
    {
      System.out.println( dbb.toString() );
      System.out.println();
      dbb = new StringBuffer();
    }

    int firstSingleton = -1;
    for ( int i = 0; i < binCount; i++ )
    {
      if ( bins[i].length == 1 )
      {
        firstSingleton = i;
        break;
      }
    }

    if (DB)
    {
      dbb.append
      (
        "\r\n"
        + firstSingleton
        + " firstSingleton"
      );
    }

/*
** Okay, there are two possibilities: all the bins are of length two or
** more, or at least one bin is of length 1.  They are handled entirely
** differently.
*/

/*
** To limit exposure to run-away processing requirements, don't try for
** the absolute optimim, only flip 8 bins in a cluster, maximum.
*/

    final int BIN_LIMIT = 8;

    boolean bestFlips[] = new boolean[binCount];
    for ( int i = 0; i < binCount; i++ )
    {
      bestFlips[i] = false;
    }

    if (DB)
    {
      dbb.append
     (
       "\r\n"
       + Debugging.dump(bestFlips)
       + " bestFlips"
     );
    }

    if (DB)
    {
      System.out.println( dbb.toString() );
      System.out.println();
      dbb = new StringBuffer();
    }

    if ( firstSingleton == -1 )
    {

      dbb.append( "\r\n" + "no singletons found in flipBins" );

      if (DB)
      {
        System.out.println( dbb.toString() );
        System.out.println();
        dbb = new StringBuffer();
      }

/*
** Find bins better flipped
*/

      int startBin = 0;
      int stopBin = Math.min( BIN_LIMIT , binCount - 1);

      while (true)
      {

        boolean currentFlips[] = new boolean[binCount];

        for ( int i = 0; i < binCount; i++ )
        {
          currentFlips[i] = bestFlips[i];
        }

        int powerOfTwo = 1;
        for ( int i = startBin; i < stopBin; i++ )
        {
          powerOfTwo *= 2;
        }

        double fitnessIncrement = Double.MAX_VALUE;
        for (int i = 0; i < powerOfTwo; i++ )
        {
          for ( int j = 0; j < (stopBin - startBin + 1); j++ )
          {
            currentFlips[ ( startBin + j ) %  binCount ] = ( ( ( 1 << j ) & i ) != 0 );
          }

          double thisFitnessIncrement = 
            flippedFitness
            (
              bins,
              binCount,
              startBin % binCount,
              stopBin % binCount,
              currentFlips,
              world,
              DB
            );

          if ( thisFitnessIncrement < fitnessIncrement )
          {
            fitnessIncrement = thisFitnessIncrement;
            for ( int j = 0; j < (stopBin - startBin + 1); j++ )
            {
              int jIndex = ( startBin + j ) % binCount;
              bestFlips[jIndex] = currentFlips[jIndex];
            }

            if (DB)
            {
              dbb.append
              (
                "\r\n"
                + Debugging.dump(bestFlips)
                + "/"
                + startBin
                + "/"
                + stopBin
                + " bestFlips/startBin/stopBin"
              );
            }

            if (DB)
            {
              System.out.println( dbb.toString() );
              System.out.println();
              dbb = new StringBuffer();
            }

          }

        }
        startBin = startBin + BIN_LIMIT;
        stopBin  = Math.min( startBin + BIN_LIMIT, binCount - 1 );
        if ( startBin >= binCount ) { break; }
      }

/*
** Flip bins found to need flipping.
*/

      for ( int i = 0; i < binCount; i++ )
      {
        if ( bestFlips[i] )
        {
          for ( int j = 0; j < ( bins[i].length / 2 ) ; j++ )
          {
            int temp = bins[i][j];
            bins[i][j] = bins[i][ bins[i].length - 1 - j];
            bins[i][ bins[i].length - 1 - j] = temp;
          }
        }
      }

      if (DB)
      {
        dbb.append
        (
          "\r\n"
          + Debugging.dump(bins)
          + "/"
          + " leaving flipBins at no singletons exit"
        );
      }

      if (DB)
      {
        System.out.println( dbb.toString() );
        System.out.println();
        dbb = new StringBuffer();
      }

      return;
    }

    dbb.append
    (
      "\r\n"
      + "first singleton found at "
      + firstSingleton
      + " in flipBins"
    );

    if (DB)
    {
      System.out.println( dbb.toString() );
      System.out.println();
      dbb = new StringBuffer();
    }

    int someNonSingleton = firstSingleton;

    for ( int i = 0; i < binCount; i++ )
    {
      if ( bins[( i + firstSingleton ) % binCount].length > 1 )
      {
        someNonSingleton = ( someNonSingleton + i ) % binCount;
        break;
      }
    }

    if ( someNonSingleton == firstSingleton )
    {
      dbb.append( "no flippable bins found in flipBins" );

      if (DB)
      {
        System.out.println( dbb.toString() );
        System.out.println();
        dbb = new StringBuffer();
      }

      return; // no flippable bins
    }

    dbb.append
    (
      "\r\n"
      + "someNonSingleton found at "
      + someNonSingleton
      + " in flipBins"
    );

    if (DB)
    {
      System.out.println( dbb.toString() );
      System.out.println();
      dbb = new StringBuffer();
    }

    while (true)
    {
      int currentBin = someNonSingleton;
      int subBinCount = 1;
      while ( bins[( currentBin + 1 ) % binCount].length > 1 )
      {
        currentBin = ( currentBin + 1 ) % binCount;
        subBinCount++;
      }

/*
** Flip multi-codon bins sequence.
*/

      int startBinOffset = 0;
      int binsToDo = Math.min( BIN_LIMIT, subBinCount );

      while ( true )
      {

        boolean currentFlips[] = new boolean[binCount];
        for ( int i = 0; i < binCount; i++ )
        {
          currentFlips[i] = bestFlips[i];
        }

        int powerOfTwo = 1;
        for ( int i = 0; i < binsToDo; i++ )
        {
          powerOfTwo *= 2;
        }

        double fitnessIncrement = Double.MAX_VALUE;
        for (int i = 0; i < powerOfTwo; i++ )
        {
          for ( int j = 0; j < binsToDo; j++ )
          {
            currentFlips[ ( someNonSingleton + startBinOffset + j ) % binCount ] =
              ( ( ( 1 << j ) & i ) != 0 );
          }

          double thisFitnessIncrement = 
            flippedFitness
            (
              bins,
              binCount,
              ( ( someNonSingleton + startBinOffset ) % binCount ),
              ( ( someNonSingleton + startBinOffset + binsToDo - 1 + binCount ) % binCount ),
              currentFlips,
              world,
              DB
            );

          if ( thisFitnessIncrement < fitnessIncrement )
          {
            fitnessIncrement = thisFitnessIncrement;
            for ( int j = 0; j < binsToDo; j++ )
            {
              int jIndex = ( someNonSingleton + startBinOffset + j ) % binCount;
              bestFlips[jIndex] = currentFlips[jIndex];
            }

            if (DB)
            {
              dbb.append
              (
                "\r\n"
                + Debugging.dump(bestFlips)
                + "/"
                + fitnessIncrement
                + "/"
                + someNonSingleton
                + "/"
                + startBinOffset
                + "/"
                + binsToDo
                + " bestFlips/fitnessIncrement/someNonSingleton/startBinOffset/binsToDo"
              );
            }

            if (DB)
            {
              System.out.println( dbb.toString() );
              System.out.println();
              dbb = new StringBuffer();
            }

          }
        }

        startBinOffset += BIN_LIMIT;
        subBinCount -= BIN_LIMIT;
        if ( subBinCount <= 0 ) { break; }
        binsToDo = Math.min( BIN_LIMIT, subBinCount );
      }

      someNonSingleton = ( currentBin + 1 ) % binCount;
      while ( bins[ someNonSingleton ].length == 1 )
      {
        if ( someNonSingleton == firstSingleton ) { break; } // done
        someNonSingleton = ( someNonSingleton + 1 ) % binCount;
      }
      if ( someNonSingleton == firstSingleton ) { break; } // done
    }

/*
** Flip bins found to need flipping.
*/

    for ( int i = 0; i < binCount; i++ )
    {
      if ( bestFlips[i] )
      {
        for ( int j = 0; j < ( bins[i].length / 2 ) ; j++ )
        {
          int temp = bins[i][j];
          bins[i][j] = bins[i][ bins[i].length - 1 - j];
          bins[i][ bins[i].length - 1 - j] = temp;
        }
      }
    }

    if (DB)
    {
      dbb.append
      (
        "\r\n"
        + Debugging.dump(bins)
        + " leaving flipBins at some singletons exit"
      );
    }

    if (DB)
    {
      System.out.println( dbb.toString() );
      System.out.println();
      dbb = new StringBuffer();
    }

    return;

  }

  double flippedFitness
  (
    int bins[][],
    int binCount,
    int fromBin,
    int toBin,
    boolean currentFlips[],
    TravellerWorld world,
    boolean DB
  )
  {

    StringBuffer dbb = new StringBuffer();
    int previousIndex =
      ( fromBin - 1 + binCount ) % binCount;
    int thisIndex = fromBin;
    double thisFitnessIncrement = 
      world.getDistance
      (
        (
          currentFlips[previousIndex]
          ? bins[previousIndex][0]
          : bins[previousIndex][bins[previousIndex].length - 1]
        ),
        (
          currentFlips[thisIndex]
          ? bins[thisIndex][bins[thisIndex].length - 1]
          : bins[thisIndex][0]
        )
      );

    thisIndex = fromBin;
    while ( true )
    {
      int nextIndex = ( thisIndex + 1 ) % binCount;
      thisFitnessIncrement +=
        world.getDistance
        (
          (
            currentFlips[thisIndex]
            ? bins[thisIndex][0]
            : bins[thisIndex][bins[thisIndex].length - 1]
          ),
          (
            currentFlips[nextIndex]
            ? bins[nextIndex][bins[nextIndex].length - 1]
            : bins[nextIndex][0]
          )
        );
      if ( thisIndex == toBin ) { break; }
      thisIndex = ( thisIndex + 1 ) % binCount ;
    }

    if (DB)
    {
      dbb.append
      (
        "\r\n"
        + fromBin
        + "/"
        + toBin
        + "/"
        + thisFitnessIncrement
        + " fromBin/toBin/thisFitnessIncrement out of flippedFitness"
      );
    }

    if (DB)
    {
      System.out.println( dbb.toString() );
      System.out.println();
      dbb = new StringBuffer("");
    }

    return thisFitnessIncrement;
  }
}