elasticnet.java

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

** Put the initial waypoints evenly spaced around a radius 0.2 circle
** centered in the center of the 1.0 x 1.0 playfield.  Unless our city
** generation routine has been really perverse (which is entirely
** possible), this will be somewhere toward  the middle of the city
** locations.
*/

  private void newpoint()
  {
    double radianDelta = 2.0D * Math.PI / (double) waynum;
    for ( int waypointIndex = 0; waypointIndex < waynum; waypointIndex++)
    {
      way[waypointIndex][X_INDEX] =
        0.5D + ( 0.2D * Math.cos( radianDelta * (double) waypointIndex ) );
      way[waypointIndex][Y_INDEX] =
        0.5D + ( 0.2D * Math.sin( radianDelta * (double) waypointIndex ) );
    }
    createDrawingLocationsForWaypoints();
  }

  private void createDrawingLocationsForWaypoints()
  {
      // Calculate corresponding drawing locations for exact locations
      // set above.
      for (int i = 0; i < waynum; ++i)
      {
          wayDrawAtLocations[i][wayX] =
           (int)Math.round((way[i][wayX]*cityScaler) + widthMin);
          wayDrawAtLocations[i][wayY] =
            (int)Math.round((way[i][wayY]*cityScaler) + heightMin);
      }
  }

/*
** We aren't going to do this for using the original program as a
** seeding tool to which an array of cities is fed already populated.
*/

//  public void newcity()
//  {
//    for(int i=0; i<citynum; i++)
//      {
//        city[i][x] = Math.random();
//        city[i][y] = Math.random();
//      }
//    newpoint();  // I don't want to know why this is inside here.
//  }

  private double fcity( int waypointIndex, int coordinateXorY )
  {
    double result = 0.0D;
    for ( int cityIndex = 0; cityIndex < citynum; cityIndex++ )
      result +=
        (
          city[cityIndex][coordinateXorY]
          -
          way[waypointIndex][coordinateXorY]
        )
        * phiVA.getValue( cityIndex, waypointIndex )
        / city_norm[cityIndex];
    return result;
  }

/*
** This routine has a rather _huge_ side effect of filling in the phi
** array.  Since we've virtualized the phi array, that might or might
** not do any good.  If it won't, we won't do it now.
*/

  private double dist_max()
  {
    double max = 0.0D;
    for ( int cityIndex = 0; cityIndex < citynum; cityIndex++ )
     {

      double min = Double.MAX_VALUE;

      for(int waypointIndex = 0; waypointIndex < waynum; waypointIndex++)
      {
        double dx = way[waypointIndex][X_INDEX] - city[cityIndex][X_INDEX];
        double dy = way[waypointIndex][Y_INDEX] - city[cityIndex][Y_INDEX];
        double dr = dx*dx + dy*dy;

//        phiArr[i][j] = phi(dr);

/*
** Only do the expensive phi calculaton if it is going to pay off right
** now.  Notice that this calculation is based on distance _squared_,
** which makes this some (obscene) variant of a least squares algorithm
** (the obscentity being the exponenetial damping with time).
*/

        if ( phiVA.storingIsUseful() )
        {
          phiVA.putValue( phiVA.phi(dr), cityIndex, waypointIndex);
        }

        min = Math.min( min, Math.sqrt(dr) );
      }

      max = Math.max(max, min);

    }

    return max;
  }


  //--------- This is the main iteration procedure! -------

/*
** FIXME For seeding purposes, we want to split this into an iteration
** setup method, and an iteraton continuation method, so that we can
** snaffle (presumably inceasingly more fit) seed arrays at various
** stopping points along the iteration.  The best way is to move lots of
** this setup stuff into the constructor.
*/

  public int [] iterate( int iterateHowManyTimes )
  {
    // done in constructor now
    // tensionAdjustment = park_st;
    // newpoint();
    double maximumDistance = 0.0D;

    //---------- Main calculation ----------------

    if (DB) System.out.println("iterate " + iterateHowManyTimes + " times" );
    for ( int iter=0; iter < iterateHowManyTimes; iter++ )
    {
      iterationCount++;     // for outside reporting.
      tensionAdjustment *= TENSION_ADJUSTMENT_DECREMENTER;

/*
** Check whether each city is sufficiently close to some waypoint; as a
** side effect, calculate the inverse exponentially damped weights to
** use to adjust the waypoints, in case the answer is that some city is
** not yet sufficiently close to a waypoint.  I don't find any evidence
** that each city is uniquely matched to a waypoint, which will cause
** some algorithmic issues when using this routine as a seed mechanism.
*/

      maximumDistance = dist_max();

      if ( maximumDistance < endIt )
      {

        if (DB) System.out.println
        (
          "final iteration count / dist_max / endIt / moreIterations: "
          + iterationCount
          + "/"
          + maximumDistance
          + "/"
          + endIt
          + "/"
          + moreIterations
        );
/*
** Signal caller that further calls will be futile.  Notice that nothing
** bad happens if they ignore us, except that they get back the same
** city list with each call after we quit trying.
*/

        moreIterations = false;

/*
** Build and return a city list from which a genome can be built,
** consisting of the cities sorted in waypoint order of the waypoints to
** which each city is closest.
*/

        return spawnNextCityList();

      }

      // -------- Cities normalization -----------

/*
** For each city, sum up the inverse exponentially damped weights of
** waypoint attractions, to use as a normalizing factor.
*/

      for ( int cityIndex = 0; cityIndex < citynum; cityIndex++ )
      {
        city_norm[cityIndex] = 0.0D;

        for ( int waypointIndex = 0; waypointIndex < waynum; waypointIndex++ )
        {
          city_norm[cityIndex] += phiVA.getValue( cityIndex, waypointIndex );
        }

        if ( city_norm[cityIndex] < 1.0e-80D )
        {
          city_norm[cityIndex] = 1.0D;
        }
      }

      // --- Calculate waypoint adjustment deltas ----

      for ( int waypointIndex = 0; waypointIndex < waynum; waypointIndex++ )
      {

        int nextWaypointIndex =
          ( waypointIndex == ( waynum - 1 ) )
          ? 0
          : ( waypointIndex + 1 );

        int previousWaypointIndex =
          ( waypointIndex == 0 )
          ? ( waynum - 1 )
          : ( waypointIndex - 1 );

        for ( int coordinate = X_INDEX; coordinate <= Y_INDEX; coordinate++ )
        {
          delta[waypointIndex][coordinate] =
            (
              (
                waypointToCityTension
                *
                fcity( waypointIndex, coordinate )
              )
              +
              (
                waypointToWaypointTension
                *
                tensionAdjustment
                *
                (
                  way[nextWaypointIndex][coordinate]
                  -
                  ( 2.0D * way[waypointIndex][coordinate] )
                  +
                  way[previousWaypointIndex][coordinate]
                )
              )
            );
        }

      }

      //---------- Adjust waypoints --------------

      for ( int waypoint = 0; waypoint < waynum; waypoint++ )
      {
        for ( int coordinate = X_INDEX; coordinate <= Y_INDEX; coordinate++ )
        {

          if (DB) System.out.println
          (
            "adjusting way["
            + waypoint
            + "]["
            + coordinate
            + "] of "
            + way[waypoint][coordinate]
            + " += delta of "
            + delta[waypoint][coordinate]
          );

          way[waypoint][coordinate] += delta[waypoint][coordinate];
        }

      }

/*
** Display progress.
*/

      createDrawingLocationsForWaypoints();

      m_enCanvas.clearPlayfield();

      m_enCanvas.drawEdges
      (
        wayNodeList,
        waynum,
        wayDrawAtLocations,
        wayX,
        wayY,
        TravellerColors.COLOR_SEED_ROUTE,
        true // closed path
      );

      m_enCanvas.drawNodes
      (
        wayDrawAtLocations,
        waynum,
        wayX,
        wayY,
        TravellerColors.COLOR_WAYPOINT
      );

      m_enCanvas.drawNodes
      (
        m_world.getCityDrawAtLocations(),
        ValuatorControls.getNumberOfCities(),
        m_world.CITY_X,
        m_world.CITY_Y,
        TravellerColors.COLOR_CITY
      );

      m_enCanvas.drawImage();
      m_enCanvas.repaint();

    }

    if (DB) System.out.println
    (
      "call-end iteration count / dist_max / endIt / moreIterations: "
      + iterationCount
      + "/"
      + maximumDistance
      + "/"
      + endIt
      + "/"
      + moreIterations
    );

    return spawnNextCityList();

  }

  public boolean moreIterationsAreAvailable()
  {
    return moreIterations;
  }


  private int [] spawnNextCityList()
  {

/*
** Create a city list for output.
*/

    int newCityList[] = new int[citynum];

/*
** Create a city and waypoint list for sorting cities in waypoint order.
*/

    IntPairSortedOnSecondElement cawp[] =
      new IntPairSortedOnSecondElement[citynum];

/*
** Initialize with unworkable values, for debugging.
*/

    for ( int cityIndex = 0; cityIndex < citynum; cityIndex++ )
    {
      newCityList[cityIndex] = -1;

      cawp[cityIndex] = new IntPairSortedOnSecondElement( -1, -1 );
    }

/*
** Fill in the array to be sorted with the city index and the index of
** the waypoint closest to that city.
*/

    for ( int cityIndex = 0; cityIndex < citynum; cityIndex++ )
    {

      double bestDistance = Double.MAX_VALUE;

/*
** As noted above, the assignments of waypoint indices to city indices
** is not necessarily unique, so the sort may be sorting on identical
** waypoint indices; we don't care, since this just a good seed tour,
** not the perfect solution tour.
*/

      for ( int waypointIndex = 0; waypointIndex < waynum; waypointIndex++ )
      {

        double dx = way[waypointIndex][X_INDEX]-city[cityIndex][X_INDEX];
        double dy = way[waypointIndex][Y_INDEX]-city[cityIndex][Y_INDEX];
        double dr = Math.sqrt( dx*dx + dy*dy );

        if ( dr < bestDistance )
        {
          bestDistance = dr;
          cawp[cityIndex] =
            new IntPairSortedOnSecondElement( cityIndex, waypointIndex );
        }

      }

    }

/*
** Sort the list just created in waypoint order, which will put the
** cities in the order of the tour which the waypoints have defined due
** to the running of the elastic net algorithm.
*/

    if (DB)
    {
      StringBuffer b = new StringBuffer("");
      b.append("[");
      for ( int i = 0; i < cawp.length; i++ )
      {
        b.append( ( ( i == 0 ) ? "" : "," ) + cawp[i].toString()  );
      }
      b.append("]");

      System.out.println
      (
        "cawp before qsort :"
        + b.toString()
      );
    }

    QuickSortAlgorithm.sort( cawp );

    for ( int cityIndex = 0; cityIndex < citynum; cityIndex++ )
    {
      newCityList[cityIndex] = cawp[cityIndex].getFirst();
    }

    if (DB) System.out.println( "waypoint locations: " + Debugging.dump( way ) );
    if (DB) System.out.println( "new city list: " + Debugging.dump( newCityList ) );

    return newCityList;
  }

  public void closeWindow()
  {
    if ( m_enCanvas != null )
    {
      m_enCanvas.windowClose();
      m_enCanvas = null;
    }
  }

}