travellerworld.java

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

//-----------------------------------------------------------------------------
//  Traveller -- A Java Application and Applet
//
//  A Genetic Algorithm for Solving the Travelling Salesman Problem
//
//  TravellerWorld.java
//  version 1.1.0
//
//  Copyright 2000-2001 Scott Robert Ladd. All rights reserved.
//
//  For more information about this program, contact:
//
//      Scott Robert Ladd
//      [e-mail]
//      http://www.coyotegulch.com
//
//-----------------------------------------------------------------------------
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the
//
//      Free Software Foundation, Inc.
//      59 Temple Place - Suite 330
//      Boston, MA 02111-1307, USA.
//-----------------------------------------------------------------------------

/*
** This code was extensively modified by Kent Paul Dolan.  Parts of the
** original code are now in other classes in Traveller.  See
** accompanying file TravellerDoc.html for status of the modifications
** for your use.
*/

package com.coyotegulch.genetic;

import java.awt.*;
import java.util.*;

import com.coyotegulch.tools.*;
import com.coyotegulch.ui.*;

import com.well.www.user.xanthian.java.genetic.*;
import com.well.www.user.xanthian.java.genetic.reproducers.asexual.*;
import com.well.www.user.xanthian.java.genetic.reproducers.consultive.*;
import com.well.www.user.xanthian.java.genetic.reproducers.sexual.*;
import com.well.www.user.xanthian.java.layouts.*;
import com.well.www.user.xanthian.java.seeders.*;
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 TravellerWorld
    implements HasTasks
{
  //-------------------------
  // constants
  //-------------------------

  private static final double RADS = 180.0 / Math.PI;

  public  static final int CITY_X     =  0;
  public  static final int CITY_Y     =  1;
  public  static final int CITY_SIZE  =  2;

  // multitasking
  private static Task m_task = null;
  private boolean m_firstTaskingCall = true;

  // dimensions
  private Dimension   m_dim;

  // tools

  private        DelaunayTriangulation m_dt          = null;
  private        MersenneTwister       m_mt          = null;
  private static TravellerCanvas       m_routeCanvas = null;

  // parameters
  private int         m_numCities           =     4;
  private int         m_naturalProblemSize  =     m_numCities;
  private int         m_popSize             =     4;
  private double      m_mutationRate        = 0.01D;

  // working storage
  private int [][]    m_cityDrawAtLocations;
  private double [][] m_cityExactLocations;
  private Codon []    m_minimalSpanningTree;

/*
** 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 cityDistancesVirtualArray, below. We
** are much better off to recompute the values every time, than to fetch
** them already computed from hard disk every time, even though the
** computation is an onerous one.
** 
**    private double [][] m_distances;
*/

  CityDistancesVirtualArray cityDistancesVA = null;

  private static Population      m_population = null;
  private static TravellerWorld  m_soliton    = null;
  private final static String ROUTE_NAME = "旅行商路径显示";

  // time, useful everywhen
  // private static Date   m_tod = null;

  // flags and such for statistic reporting
  private TravellerChromosome  m_bestChromosome              = null;

  // debugging hook abbreviation
  boolean DB;

  private class CityDistancesVirtualArray
  {
    private double cityDistancesArray[][] = null;
    private boolean valuesAreStored = false;

/*
** POLICY Limit real stored distance array sizes to the case for 200 or
** fewer cities to attempt to limit spilling into virtual memory.
*/

    private static final int ARRAY_SIZE_LIMIT = 40000;

    public CityDistancesVirtualArray( int cityCount )
    {
      if ( ( cityCount * cityCount ) <= ARRAY_SIZE_LIMIT )
      {
        valuesAreStored = true;
        cityDistancesArray = new double[cityCount][cityCount];
      }
      else
      {
        valuesAreStored = false;
      }
    }

    public void putValue
    (
      double cityDistancesValue,
      int firstCity,
      int secondCity
    )
    {
      if ( valuesAreStored && ( cityDistancesArray != null ) )
      {
        cityDistancesArray[firstCity][secondCity] = cityDistancesValue;
      }
      else {}
    }

    public double getValue( int firstCity, int secondCity )
    {
      if ( valuesAreStored && ( cityDistancesArray != 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 cityDistancesArray[firstCity][secondCity];
      }
      else // calculate virtual array contents over again
      {
         return cityDistances( firstCity, secondCity );
      }
    }

    public boolean storingIsUseful()
    {
      return valuesAreStored;
    }

/*
** FIXME This may not be the best packaging; a "cityDistances"
** calculation method isn't really part of a "cityDistances array"
** container object, but passing the function in via the constructor is
** beyond my skills just now.
*/

    public double cityDistances( int firstCity, int secondCity )
    {

      double dX
        = Math.abs
          (
            m_cityExactLocations[firstCity][CITY_X] -
            m_cityExactLocations[secondCity][CITY_X]
          );

      double dY
        = Math.abs
          (
            m_cityExactLocations[firstCity][CITY_Y] -
            m_cityExactLocations[secondCity][CITY_Y]
          );

      return Math.sqrt( ( dX * dX ) + ( dY * dY ) );

    }
  }


  //-------------------------
  // initialization
  //-------------------------
  private TravellerWorld()
  {

    if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
    {
      DB = true;
      System.out.println( "Entered TravellerWorld" );
    }
    else
    {
      DB = false;
    }

    // load parameters

    m_numCities    = ValuatorControls.getNumberOfCities();
    m_popSize      = ValuatorControls.getPopulationSize();
    m_mutationRate = ValuatorControls.getMutationRate();
    if ( m_routeCanvas == null )
    {
      m_routeCanvas = new TravellerCanvas();
      m_routeCanvas.setup(ROUTE_NAME);
    }
    else
    {
      m_routeCanvas.redraw();
    }
    m_dim         = new Dimension( TravellerCanvas.WORKING_DIMENSIONS );

/*
** Attach to the random number generator.
*/

    m_mt = MersenneTwister.getTwister();

/*
** Allocate a virtual-distances-array manager.
*/

   cityDistancesVA = new CityDistancesVirtualArray( m_numCities );
/*
** Do a little setting up stuff.
*/

    m_bestChromosome      = null;

    // allocate new city arrays for exact and drawable locations
    m_cityDrawAtLocations = new int    [m_numCities][CITY_SIZE];
    m_cityExactLocations  = new double [m_numCities][CITY_SIZE];


/*
** Time this frumious beast, so we can tell the world how slow we are!
*/
    // m_tod = new Date();
    TravellerStatus.setTimeAtConfigurationStart
    (
      (new Date()).getTime()/1000
    );

/*
** FIXME The constructor should end right here, and all the rest of this
** stuff be provided as separate services, so that the constructor isn't
** doing a lot of mathematically intense work, not the job of
** constructors (which is to allocate memory, not fill it), and so that
** the canvas is available to show the work progress during layout of
** cities and seeding of genomes, to keep the user amused when things get
** slow.
*/

    // Put the cities into the layout as chosen by the user
    MasterLayout.layoutCities
    (
      m_cityExactLocations,
      CITY_X,
      CITY_Y,
      m_dim.getWidth(),
      m_dim.getHeight()
    );

    // convert the exact city locations to pixel-centric drawing locations.
    createDrawingLocationsForCites();

/*
** Put the cities on the bottom, so they show when nothing else is drawn.
*/

    m_routeCanvas.drawNodes
    (
      m_cityDrawAtLocations,
      ValuatorControls.getNumberOfCities(),
      CITY_X,
      CITY_Y,
      TravellerColors.COLOR_CITY
    );

    m_routeCanvas.repaint();

    // calculate the array distances between cities
    fillCityDistancesArray();

    // create a set of chromosomes
    resetChromosomes();

    TravellerStatus.setTimeAtConfigurationFinished
    (
      (new Date()).getTime()/1000
    );

  }

  public static void reset()
  {
    m_soliton = null;
    m_task = null;
    m_routeCanvas = null;
  }

  public static void setup()
  {
    TravellerWorld tw = getTravellerWorld();
  }

  public static synchronized TravellerWorld getTravellerWorld()
  {
    if ( m_soliton == null )
    {
      m_soliton = new TravellerWorld();
      m_task    = new Task( m_soliton, 10 );
    }
    // m_routeCanvas.repaint();
    return m_soliton;
  }

  public TravellerCanvas getRouteCanvas()
  {
    return m_routeCanvas;
  }

  public void closeWindows()
  {
    if (this.m_routeCanvas != null) { this.m_routeCanvas.windowClose(); }
  }

  public static void newWorld()
  {

    // if ( m_soliton != null ) { m_soliton.closeWindows(); }

    m_soliton = null;

    TravellerWorld tw = getTravellerWorld();

    TravellerStatus m_travellerStatus =
      TravellerStatus.getTravellerStatus( m_soliton );
    m_travellerStatus.setup();

  }

  private void fillCityDistancesArray()
  {
/*
** FIXME This badly needs to become a virtual array.  It is killing
** performance for large numbers of cities, by spilling to virtual
** memory.
*/
    // m_distances = new double [m_numCities][m_numCities];

    if ( cityDistancesVA.storingIsUseful() )
    {

      for (int city1 = 0; city1 < m_numCities; ++city1)