optimizenodesneareverycity.java

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

                b.append( "fitness loop mark 008" );

            }

          }
          catch ( Exception ml )
          {
            System.out.println
            (
              "ERROR! OptimizeNodesNearEveryCity.reproduce(): "
              + "fitness loop threw!"
            );
            System.err.println( b.toString() );
          }
          finally { if (DB) System.out.println( "fitLoop ran" ); }
        }

      }
      catch ( Exception ml )
      {
        System.err.println
        (
          "ERROR! OptimizeNodesNearEveryCity.morePerms() threw"
        );
      }
      finally { if (DB) { System.out.println( "morePerms ran" ); } }


      if (DB)
      {
        for (int i = 0; i < genomeLength; i++) { offspring.setCity(i, -1); }
        System.out.println ( "cityList       : " + Debugging.dump(cityList) );
        System.out.println ( "bestSlotFills  : " + Debugging.dump(bestSlotFills) );
        System.out.println ( "bestPermutation: " + Debugging.dump(bestPermutation) );
        System.out.println ( "slotBefores    : " + Debugging.dump(slotBefores) );
        System.out.println ( "slotBeginnings : " + Debugging.dump(slotBeginnings) );
        System.out.println ( "slotEndings    : " + Debugging.dump(slotEndings) );
        System.out.println ( "slotAfters     : " + Debugging.dump(slotAfters) );
      }

      int placeInPermutation = 0;
      int placeInChildGenome = 0;
      try
      {

        for (int i = 0; i < howManySlots; i++)
        {
          int slotBefore = slotBefores[i];
          int slotAfter  = slotAfters[ ( i + howManySlots - 1 ) % howManySlots ];
          if (DB)
          {
            System.out.println
            (
              "slotBefore/slotAfter: " 
              + slotBefore
              + "/"
              + slotAfter
            ); 
          }

/*
** Copy the segment of genome before the current slot.
*/

          if ( slotBefore < slotAfter ) { slotBefore += genomeLength; }
          for ( int j = slotAfter; j <= slotBefore; j++ )
          {
            offspring.setCity
            (
              placeInChildGenome++,
              coparent.getCity(j)
            );
            if (DB)
            {
              System.out.println
              (
                "adding unpermuted i/j/offspring: "
                + i
                + "/"
                + j
                + "/"
                + offspring.toString()
              );
            }
          }

/*
** Copy the segment of genome within the current slot, if any.  The "if
** any" part is the trick that makes this fairly simple copying work.
*/

          for ( int j = 0; j < bestSlotFills[i]; j++ )
          {
            offspring.setCity
            (
              placeInChildGenome++,
              cityList[bestPermutation[placeInPermutation++]]
            );
            if (DB)
            {
              System.out.println
              (
                "adding   permuted i/j/offspring: "
                + i
                + "/"
                + j
                + "/"
                + offspring.toString()
              );
            }
          }
        }

      }
      catch ( Exception cl )
      {
        System.err.println
        (
          "ERROR! OptimizeNodesNearEveryCity copy loop threw!"
        );
      }
      finally { if (DB) { System.out.println( "copy loop ran" ); } }

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

      offspring.canonicalize();

      if (DB)
      {
        System.out.println
        (
          Debugging.dump(bestSlotFills) + " bestSF NearEveryCity"
        );
      }
      if (DB)
      {
        System.out.println
        (
          Debugging.dump(bestPermutation) + " bestP NearEveryCity"
        );
      }
      if (DB)
      {
        System.out.println
        (
          offspring.toString()
          + " offspring, end of main loop OptimizeNodesNearEveryCity"
        );
      }

      coparent = new TravellerChromosome( offspring );

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

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

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

    return offspring;
  }

  private double fitnessIncrement
  (
    Integer             permutation[],
    int                 slotCounts[],
    int                 cityList[],
    int                 slotBefores[],
    int                 slotBeginnings[],
    int                 slotEndings[],
    int                 slotAfters[],
    TravellerChromosome tc
  )
  {
    TravellerWorld world = tc.getWorld();
    double increment =  0.0D;
    int howManySlots = slotBeginnings.length;
    int howManyCodons = permutation.length;

    int placeInPermutation = 0;
    for (int i = 0; i < howManySlots; i++)
    {
      if ( slotCounts[i] == 0 )
      {
        increment +=
          world.getDistance
          (
            tc.getCity(slotBefores[i]),
            tc.getCity(slotAfters[i])
          );
      }
      else
      {
        increment +=
          world.getDistance
          (
            tc.getCity(slotBefores[i]),
            cityList[permutation[placeInPermutation].intValue()]
          );
        for ( int j = 1; j < slotCounts[i]; j++ )
        {
          increment +=
            world.getDistance
            (
              cityList[permutation[placeInPermutation + j - 1].intValue()],
              cityList[permutation[placeInPermutation + j].intValue()]
            );
        }
        increment +=
          world.getDistance
          (
            cityList
            [
              permutation[placeInPermutation + slotCounts[i] - 1].intValue()
            ],
            tc.getCity(slotAfters[i])
          );
          placeInPermutation += slotCounts[i];
      }
    }
    return increment;
  }

  private int[][] findSlots( int cityList[], TravellerChromosome tc )
  {

    tc.checkValidity();

    if (DB) { System.out.println( "findSlots(): tc = " + tc.toString() );}

    int genomeLength = ValuatorControls.getNumberOfCities();

    int slotBefores[]    = new int[cityList.length];
    int slotBeginnings[] = new int[cityList.length];
    int slotEndings[]    = new int[cityList.length];
    int slotAfters[]     = new int[cityList.length];

    if (DB) { System.out.println( "findSlots() mark 001" ); }

    if
    (
      ( slotBefores == null )
      ||
      ( slotBeginnings == null )
      ||
      ( slotEndings == null )
      ||
      ( slotAfters == null )
    )
    {
      System.err.println
      (
        "ERROR! OptimizeNodesNearEveryCity.findSlots(): "
        + "failed to allocate some array at the start."
      );
    }

    for ( int i = 0; i < cityList.length; i++ )
    {
      slotBefores[i]    = -1;
      slotBeginnings[i] = -1;
      slotEndings[i]    = -1;
      slotAfters[i]     = -1;
    }

    if (DB) { System.out.println( "findSlots() mark 002" ); }

    int howManySlots = 0;

/*
** We take advantage here of the design that tc.getCity() is working
** in modular coordinates, so our arithmetic here can be sloppy about
** array boundaries.
*/

/*
** Go forward looking for the end of a slot.
*/

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

      if (DB) { System.out.println( "findSlots() mark 003; howManySlots/i = " + howManySlots + "/" + i); }

      if
      (
        (  inList( tc.getCity( i     ), cityList ) )
        &&
        (! inList( tc.getCity( i + 1 ), cityList ) )
      )
      {
        slotEndings[howManySlots] = i;
        slotAfters[howManySlots]  = ( i + 1 ) % genomeLength;

        if (DB) { System.out.println( "findSlots() mark 004" ); }

/*
** Go backward from there looking for the beginning of the same slot.
*/

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

          if (DB) { System.out.println( "findSlots() mark 005" ); }

          if
          (
            (  inList( tc.getCity( i - j + genomeLength ), cityList ) )
            &&
            (! inList( tc.getCity( i - j - 1 + genomeLength ), cityList ) )
          )
          {

            if (DB) { System.out.println( "findSlots() mark 006" ); }

            slotBeginnings[howManySlots] =
              ( i - j + genomeLength ) % genomeLength;
            slotBefores[howManySlots]    =
              ( i - j - 1 + genomeLength ) % genomeLength;
            howManySlots++;

            if (DB) { System.out.println( "findSlots() mark 007" ); }

            break;
          }

          if (DB) { System.out.println( "findSlots() mark 008" ); }

        }

        if (DB) { System.out.println( "findSlots() mark 009" ); }

      }

      if (DB) { System.out.println( "findSlots() mark 010" ); }

    }

    if (DB) { System.out.println( "findSlots() mark 011" ); }

/*
** Produce arrays sized for the numbers actually found, so that the
** array lengths accurately define the count of their valid contents.
*/

    int slotPredecessors[] = new int[howManySlots];
    int slotStarts[]       = new int[howManySlots];
    int slotStops[]        = new int[howManySlots];
    int slotSuccessors[]   = new int[howManySlots];

    if (DB) { System.out.println( "findSlots() mark 012" ); }

    if
    (
      ( slotPredecessors == null )
      ||
      ( slotStarts == null )
      ||
      ( slotStops == null )
      ||
      ( slotSuccessors == null )
    )
    {