elasticnet.java

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

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

/*
** class ElasticNet, used to generate  a seed tour for Traveller.
** 
** This code is unlikely at all to resemble the original code, so all
** blame should be placed on KPD for current infelicities.  The original
** author used it to "solve" the ETSP, I'm just using it to get a very,
** very good solution-approximating seed tour for a genetic algorithm.
** 
** The original of this code is due to Alexander Budnik,
** [e-mail], and was found posted at URL
** http://nuweb.jinr.dubna.su/~filipova/tsp.html.
** 
** There he describes the algorithm like this (ripped unkindly from his
** HTML original, with all the nice formatting there discarded):
*/

/*
** the Travelling Salesman Problem
** 
** The elastic net is a kind of artificial  neural networks which is
** used for optimization problems.
** 
** Let us demonstrate the elastic net method on a simple example of
** solving a travelling salesman problem. The travelling salesman
** problem is a classical problem in the field of combinatorial
** optimization, concerned with efficient methods for maximizing or
** minimizing a function of many independent variables. 
** 
** Given the positions of N cities, what is the shortest closed tour in
** which each city can be visited once?
** 
** All exact methods known for determining an optimal route require a
** computing effort that increases exponentially with number of cities,
** so in practice exact solutions can be attempted only on problems
** involving a few hundred cities or less. The travelling salesman
** problem belongs to the large class of nondeterministic polynomial
** time complete problems.
** 
** The elastic net method has been applied to the travelling salesman
** problem. The essence of the method is:
** 
** Using an iterative procedure, a circular closed path is gradually
** elongated non-uniformly until it eventually passes sufficiently near
** to all the cities to define a tour.
** 
** A tour can be viewed as a mapping from a circle to the plane so that
** each city in the plane is mapped to by some point on the circle. We
** consider mappings from a circular path of points to the plane in
** which neighboring points on the circle are mapped as close as
** possible on the plane. This is a special case of the general problem
** of best preserving neighborhood relations when mapping between
** different geometrical spaces.
** 
** The algorithm is a procedure for the successive recalculation of the
** positions of a number of points in the plane in which the cities lie.
** The points describe a closed path which is initially a small circle
** centered on the center of the distribution of cities and is gradually
** elongated non-uniformly to pass eventually near all the cities and
** thus define a tour around them.  Each point on the pass moves under
** the influence of two types of force:
** 
** 1. the first moves it towards those cities to which it is nearest;
** 
** 2. the second pulls it towards its neighbors on the path, acting to
** minimize the total path length.
** 
** By this means, each city becomes associated with a particular section
** on the path. The tightness of the association is determined by how
** the force contributed from a city depends on a distance, and the
** nature of this dependence changes as the algorithm progresses.
** Initially all cities have roughly equal influence on each point on
** the path. Subsequently, longer distance become less favored, and each
** city gradually becomes more specific for the points on the path
** closest to it.
** 
** More detailed description of the method you can find in:R.Durbin, D.
** Willshaw, "An Analogue Approach to the Travelling Salesman Problem
** Using an Elastic Net Method", Nature, v.326, n.16, April 1987, p.689.
*/

/*
** Since I don't have access to the original document describing the
** parameters here, and the names used in the original software are
** totally opaque, and since I cannot provide screen real-estate for a
** user to tune these parameters anyway, probably just hard-wiring the
** default values is as good as I can do.  This comment preserved for
** historical interest.
*/

/*
**  parameters to pass through html document:
** 
** citynum - integer number of city         (min=2 ,max=300 ,def=10  );
** waynum  - integer number of net points   (min=2 ,max=600 ,def=30  );
** itmax - integer, max number of iteration (min=10,max=6000,def=1500);
** next is now waypointToCityTension
** para - double parameter a of calculation (min=0.,max=1.  ,def=0.2 );
** next is now waypointToWaypointTension
** parb - double parameter b of calculation (min=0.,max=10. ,def=2.  );
** park - double parameter k of calculation (min=0.,max=1.  ,def=.2  );
** parke - double, parameter of conditions to stop calculation
**                                          (min=0.2,max=4.,def=1.  );
*/

package com.well.www.user.xanthian.java.seeders;

import java.awt.*;
// import java.applet.*;

import com.coyotegulch.genetic.*;
import com.coyotegulch.tools.*;

import com.well.www.user.xanthian.java.structures.*;
import com.well.www.user.xanthian.java.tools.*;
import com.well.www.user.xanthian.java.ui.*;

public class ElasticNet
{


  public static final int ITERATION_LIMIT = 1500;  // author's default limit

  private static  final int X_INDEX = 0; 
  private static  final int Y_INDEX = 1; 

  private double  city[][];
  private double  way[][];
  private int     wayNodeList[];
  private int     wayDrawAtLocations[][];
  private TravellerWorld  m_world = null;
  private TravellerCanvas m_enCanvas = null;

  double widthMin = 0.0D;
  double widthMax = TravellerCanvas.WORKING_DIMENSIONS.getWidth();
  double heightMin = 0.0D;
  double heightMax = TravellerCanvas.WORKING_DIMENSIONS.getHeight();

/*
** We cannot, in general, afford to create an array this big; being
** tossed off into virtual memory murders execution speeds.  Instead we
** virtualize the array with class phiVirtualArray, above. We are much
** better off to recompute the values every time, than to fetch them
** already computed from hard disk every time, even thought the
** computation is an onerous exponential.
** 
**  double  phiArr[][];
*/

  phiVirtualArray phiVA = null;


/*
** Tuning constants.
*/
  // POLICY How fast to decrement parameter K
  private final static double TENSION_ADJUSTMENT_DECREMENTER = 0.995D;
  private final static double INITIAL_TENSION_ADJUSTMENT     = 0.2D;
  private final static double WAYPOINT_TO_CITY_TENSION       = 0.2D;
  private final static double WAYPOINT_TO_WAYPOINT_TENSION   = 2.0D;
  private final static double CLOSE_ENOUGH                   = 0.2D;

  double  city_norm[];
  double  waypointToCityTension;
  double  waypointToWaypointTension;
  double  tensionAdjustment;
  double  parameterK_StartingValue;
  double  closeEnough;
  double  cityScaler;
  double  endIt;
  boolean moreIterations = true;
  double  parke;
  int     citynum;
  int     waynum;
  int     wayX    = 0;
  int     wayY    = 1;
  int     waySize = 2;
//  int     itmax;
  double  delta[][] = null;
  int     iterationCount = 0;
  boolean DB = false;

  //--------------------------------------------------

/*
** We pretty much need to replace this, for the reasons noted above; the
** tuning parameters aren't any use to us, and we're passing in a city
** array rather than just specifying the size of one.  The name doesn't
** work very well in Traveller, either, where pretty much everything is
** a "TSP" thingie of some kind or other.
*/
//  public TSP
//  (
//    int cnum,
//    int wnum,
//    int max,
//    double a,
//    double b,
//    double k,
//    double ke
//  )

  //------------ Constructor -------------------------
  public ElasticNet ( TravellerWorld world )
  {

    DB = false;  // set true to debug just this class

    if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
    {
      DB = true;
    }

    m_world = world;

    // a list of cities in a playfield defined elsewhere
    double cityList[][] = m_world.getCityExactLocations();

    // index of the x coordinate in the second array part
    int cityX = m_world.CITY_X;

    // index of the y coordinate in the second array part
    int cityY = m_world.CITY_Y;

    if (DB)
    {
      System.out.println
      (
        "original city list "
        + Debugging.dump( cityList )
      );
    }

//    itmax = maxIterations;
    citynum = cityList.length;
    waynum = 3 * citynum;  // fairly arbitrarily, to allow sufficient flex

    wayDrawAtLocations = new int[waynum][waySize];

    wayNodeList = new int[waynum];

    for ( int i = 0; i < waynum; i++ ) { wayNodeList[i] = i; }

/*
** Use defaults, as discussed above.  The constant values copied here
** could have been propagated directly for use in the calculations, but
** since these variables were originally constructor parameters, we'll
** leave the mixed case variable names for possible reparameterization
** at another implementation effort time.
*/

    waypointToCityTension     = WAYPOINT_TO_CITY_TENSION;
    waypointToWaypointTension = WAYPOINT_TO_WAYPOINT_TENSION;
    tensionAdjustment         = INITIAL_TENSION_ADJUSTMENT;

/*
** This beast is a little spooky, but eventually it is scaled to
** something approximating one pixel diameter in the remote playfield
** for a tuning constant original value of 1.0.
*/

    closeEnough = CLOSE_ENOUGH;

    iterationCount = 0;

/*
** Create arrays sized proportional to the input city list.
*/

    city      = new double[citynum][2];
    way       = new double[waynum][waySize];
    city_norm = new double[citynum];
    delta     = new double[waynum][waySize];

    phiVA     = new phiVirtualArray( citynum, waynum );
//    phiArr    = new double[citynum][waynum]; // as above


/*
** Create a drawing surface on which to display progress.
*/

    m_enCanvas              = new TravellerCanvas();

    m_enCanvas.setup( "Elastic Net" );

    cityScaler =  // we will reuse this in our stopping condition
      Math.max
      (
        ( widthMax - widthMin ),
        ( heightMax - heightMin )
      );

    endIt = closeEnough / cityScaler;
    moreIterations = true;

/*
** Scale cities from the input city list to fit this routine's
** expectations of them being in a unit square in the first quadrant,
** copy the results to the local city array.
*/

    for ( int cityIndex = 0; cityIndex < citynum; cityIndex++ )
    {
      city[cityIndex][X_INDEX] =
        ( cityList[cityIndex][cityX] - widthMin ) / cityScaler;
      city[cityIndex][Y_INDEX] =
        ( cityList[cityIndex][cityY] - heightMin ) / cityScaler;
    }

/*
** Fill in the starting waypoints list;
*/

    newpoint();

/*
** Display start state.
*/

    m_enCanvas.redraw();

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

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

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

  }

  private class phiVirtualArray
  {
    private double phiArray[][] = null;
    private boolean valuesAreStored = false;
    private static final int ARRAY_SIZE_LIMIT = 30000;

    public phiVirtualArray( int cityCount, int waypointCount )
    {
      if ( ( cityCount * waypointCount ) <= ARRAY_SIZE_LIMIT )
      {
        valuesAreStored = true;
        phiArray = new double[cityCount][waypointCount];
      }
      else
      {
        valuesAreStored = false;
      }
    }

    public void putValue(double phiValue, int cityIndex, int waypointIndex)
    {
      if ( valuesAreStored && ( phiArray != null ) )
      {
        phiArray[cityIndex][waypointIndex] = phiValue;
      }
      else {}
    }

    public double getValue( int cityIndex, int waypointIndex )
    {
      if ( valuesAreStored && ( phiArray != null ) )
      {

/*
** Trust the customer to keep track of whether these are useful values
** previously stored in the array.  That isn't the container's
** responsibility.
*/

        return phiArray[cityIndex][waypointIndex];
      }
      else // calculate virtual array contents over again
      {
         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;
         return phi(dr);
      }
    }

    public boolean storingIsUseful()
    {
      return valuesAreStored;
    }

/*
** FIXME This may not be the best packaging; a "phi" calculation method
** isn't really part of a "phi array" container object.
*/

    public double phi(double distance)
    {

/*
** This conditional calculation is a bit strange.  Since we scale cities
** to fit in a unit square, distances should never exceed its diagonal,
** unless the waypoints go wandering off into the weeds.  Better safe
** than sorry I guess, there must be situations in which weed visits
** were seen, or this wouldn't have been written this way.
*/

      return
      ( distance < 70.0D )
      ? Math.exp( ( 0.0D - distance ) / ( 2.0D * tensionAdjustment * tensionAdjustment ) )
      : 0.0D;
    }
  }

  //------------------- Salesman calculation's --------

/*
** This routine expects (notice the calculations in newpoint and
** newcity) that the cities will be distributed across the real number
** range 0 to 1, so we'd better scale our cities as input to that range
** in the constructor.
*/

/*