travellerchromosome.java

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

//-----------------------------------------------------------------------------
//  Traveller -- A Java Application and Applet
//
//  A Genetic Algorithm for Solving the Travelling Salesman Problem
//
//  TravellerChromosome.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.  See
** accompanying file TravellerDoc.html for status of the modifications
** for your use.
*/

package com.coyotegulch.genetic;

import com.coyotegulch.tools.*;

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

/*
** [The easily lost word you want, Kent, is "canonical", for the order
** of cities in a Chromosome.]
*/

public class TravellerChromosome
    extends Chromosome
{

    // class data
//    private static boolean           m_closedPath   = true;
    protected static MersenneTwister m_mt           = null;

    // per member data
    private TravellerWorld           m_world        = null;
    private Codon []                 m_cityList     = null;
    private boolean                  m_fitnessValid = false;
    private String                   m_originator   =
      new String( "never initialized" );

//    public static void SetClosedPath(boolean closedPath)
//    {
//        m_closedPath = closedPath;
//    }

    // constructors
    public TravellerChromosome(TravellerWorld world, String originatorName)
    {

        super();
        m_world = world;
        m_originator = new String( originatorName );

        if ( m_mt == null ) { m_mt = MersenneTwister.getTwister(); }

/*
** Our fitness runs the other direction, so we override super's setting.
*/

        m_fitness = Double.MAX_VALUE;
        m_fitnessValid = false;

        if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
        {
          System.out.println
          (
            "Entered TravellerChromosome( TravellerWorld world )"
          );
        }

        m_cityList       = new Codon   [m_world.getNumberOfCities()];

        // Fill with unpermuted integers 0 - N-1.

        for (int i = 0; i < m_cityList.length; i++)
        {
          m_cityList[i] = new Codon(i);
        }

        // Permute in usual way.

        for
        (
          int currentSlot = m_cityList.length - 1;
          currentSlot > 0; // no need to swap only remaining slot with itself
          currentSlot--
        )
        {

          // Pick some location from self to beginning of array,
          // swap current slot's occupant with the bloke in that
          // location.

          // Picking self leaves occupant in current slot, though
          // occupant may have been moved by some previous swap.

          int swapSlot   = m_mt.nextInt(currentSlot + 1); // include own slot
          int temp = m_cityList[swapSlot].get();
          m_cityList[swapSlot].set( m_cityList[currentSlot].get());
          m_cityList[currentSlot].set( temp );

        }

/*
** KPD FIXED Not just "no" but "hell no"; replace with random genome
** creation; biasing the process with a semi-regular pattern from genome
** to genome is contrary to good sense.  Below really broke bigtime when
** regular layouts were implemented, because this routine frequently
** produces the identity permutation!
** 
**  KPD Fix is above.
*/

/*
        // use Josephus permutation to produce initial genes
        m_cityList       = new Codon   [m_world.getNumberOfCities()];
        boolean [] plist = new boolean [m_world.getNumberOfCities()];

        int m = m_world.getNumberOfCities() - 1;
        int s = m_mt.nextInt(1,m - 1);
        int j = m_mt.nextInt(m_world.getNumberOfCities());
        int k = 0;

        while (true)
        {
            Codon c = new Codon( j );
            m_cityList[k] = c;
            plist[j]      = true;

            if (k == m)
                break;

            for (int l = 0; l < s; ++l)
            {
                do
                {
                    ++j;
                    if (j > m) j = 0;
                }
                while (plist[j] == true);
            }

            ++k;
        }
*/

    }

    public TravellerChromosome(TravellerChromosome c)
    {

        super(c);
        m_world = c.m_world;
        m_fitness = c.m_fitness;
        m_fitnessValid = c.m_fitnessValid;
        m_originator = new String( c.m_originator );

        if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
        {
          System.out.println
          (
            "Entered TravellerChromosome( TravellerChromosome c )"
          );
        }

        // copy cities
        m_cityList = new Codon [m_world.getNumberOfCities()];

        for (int n = 0; n < m_world.getNumberOfCities(); ++n)
        {
            int got = -1;
            try
            {
                got = c.m_cityList[n].get();
            }
            catch (Exception TCcopyloopGet)
            {

              if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
              {
                System.out.println
                (
                  "in TravellerChromosome(TravellerChromosome c), "
                  + "caught an exception TCcopyloopGet"
                );
              }

            }

            try
            {
              m_cityList[n] = new Codon( got );
            }
            catch (Exception TCcopyloopSet)
            {

              if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
              {
                System.out.println
                (
                  "in TravellerChromosome(TravellerChromosome c), caught an exception TCcopyloopSet"
                );
              }

            }
        }
    }

    public TravellerChromosome
    (
      TravellerWorld world,
      String originatorName,
      int [] nodeList
    )
    {

        super();
        m_world = world;
        m_originator = new String( originatorName );
        m_fitness = Double.MAX_VALUE;
        m_fitnessValid = false;

        if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
        {
          System.out.println
          (
            "Entered TravellerChromosome( TravellerWorld world , int [] nodeList)"
          );
        }

        // copy cities
        m_cityList = new Codon [m_world.getNumberOfCities()];

        for (int n = 0; n < m_world.getNumberOfCities(); ++n)
        {
            int got = nodeList[n];

            try
            {
              m_cityList[n] = new Codon( got );
            }
            catch (Exception TCcopyloopSet)
            {

              if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
              {
                System.out.println
                (
                  "in TravellerChromosome(TravellerWorld world, int[] nodeList), caught an exception TCcopyloopSet"
                );
              }

            }
        }
    }

/*
** Debugging aid, stringifies a copy of the chromosome data into a
** pretty format to use in a debugging dump.
*/

    public String toString()
    {
      StringBuffer b = new StringBuffer("");
      b.append("[");
      if (this.m_cityList == null)
      {
        b.append( "(null city list in genome)" );
      }
      else
      {
        if (this.m_cityList.length > 0 )
        {
          for ( int i = 0; i < this.m_cityList.length; i++ )
          {
            b.append
            (
              ( (i == 0) ? "" : "," )
              + (this.m_cityList[i]).toString()
            );
          }
        }
        else
        {
          b.append( "(empty, non-null city list in genome)" );
        }
      }
      b.append("]");
      return b.toString();
    }

    public String toString( int offset )
    {
      StringBuffer b = new StringBuffer("");
      b.append("[");
      if (this.m_cityList == null)
      {
        b.append( "(null city list in genome)" );
      }
      else
      {
        int gl = this.m_cityList.length; // genomeLength, spelled shorter
        if ( gl > 0 )
        {
          for ( int i = 0; i < gl; i++ )
          {

            int realIndex = i + offset;
            while ( realIndex < 0 ) { realIndex += gl; }
            realIndex = realIndex % gl;

            b.append
            (
              ( (i == 0) ? "" : "," )
              + (this.m_cityList[realIndex]).toString()
            );
          }
        }
        else
        {
          b.append( "(empty, non-null city list in genome)" );
        }
      }
      b.append("]");
      return b.toString();
    }

    public String toString( int offset, boolean reversed )
    {
      StringBuffer b = new StringBuffer("");
      b.append("[");
      if (this.m_cityList == null)
      {
        b.append( "(null city list in genome)" );
      }
      else
      {
        int gl = this.m_cityList.length; // genomeLength, spelled shorter
        if ( gl > 0 )
        {
          for ( int i = 0; i < gl; i++ )
          {

            int realIndex = offset + ( (reversed) ? (-i) : i );
            while ( realIndex < 0 ) { realIndex += gl; }
            realIndex = realIndex % gl;

            b.append
            (
              ( (i == 0) ? "" : "," )
              + ( this.m_cityList[realIndex] ).toString()
            );
          }
        }
        else
        {
          b.append( "(empty, non-null city list in genome)" );
        }
      }
      b.append("]");
      return b.toString();
    }

/*
** Debugging aid, replaces all cities with an invalid city name marker
** value of "-1".  Use in conjunction with the dump() routine when
** building a chromosome from one or more other chromosomes, to find
** problems where not all the slots are being filled correctly.  This is
** much easier than trying to work around the trash that cloneThis()
** leaves in the child genome before it is overwritten
*/

    public void invalidateCities()
    {
      for ( int i = 0; i < this.m_cityList.length; i++ )
      {
        m_cityList[i].set(-1);
      }
      m_fitnessValid = false;
    }

    public boolean looksLikeMe(TravellerChromosome her)
    {
      this.canonicalize();
      her.canonicalize();
      for (int i = 0; i < this.m_cityList.length; i++)
      {
        if (her.getCity(i) != this.getCity(i)) return false;
      }
      return true;
    }

    public int [] getGenomeAsArray()
    {
      int numCities = ValuatorControls.getNumberOfCities();
      int value[] = new int[numCities];
      for ( int i = 0; i < numCities; i++ )
      {
        value[i] = this.getCity(i);
      }
      return value;
    }

    // for someone outside who wants to work with the city list
    // (a reproducer, for example)
    public Codon getCodon(int n)
    {

        if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
        {
          System.out.println
          (
            "Entered TravellerChromosome.getCity(int n) = "
            + n
          );
        }

        // KPD Make chromosomes rings instead of vectors to simplify
        // KPD many reproduction algorithms.
        // KPD return m_cityList[n];
        // return m_cityList[n % m_cityList.length].get();
        // KPD Unbelievable; the java2sdk "%" function is broken, it
        // KPD returns (-1) from ((-1) % 10).

        int j = n;

        while ( j < 0 )
        {
          j += this.getNumCities();
        }

        j = j % this.getNumCities();

        return m_cityList[j];
    }

    // enable arithmetic for matching genomes in general position before
    // doing crossovers.

    public Codon getCodon(int n, int offset, boolean reversed)
    {