tsp.java

A program to demonstrate the optimization process of ant colony optimization for the traveling salem

/*----------------------------------------------------------------------
  File    : TSP.java
  Contents: a traveling salesman problem
  Author  : Christian Borgelt
  History : 19.11.2005 file created
----------------------------------------------------------------------*/
package acopt;

import java.io.File;
import java.io.FileInputStream;
import java.io.InputStream;
import java.io.IOException;
import java.util.Random;
import util.Scanner;

/*--------------------------------------------------------------------*/
public class TSP {
/*--------------------------------------------------------------------*/

  /* --- constants --- */
  private static final int BLKSIZE = 16;

  /* --- instance variables --- */
  protected int        size;    /* current number of vertices */
  protected double[]   xs, ys;  /* coordinates of vertices */
  protected double[][] dists;   /* distances between vertices */
  protected boolean    sym;     /* flag for symmetric distances */
  protected boolean    euclid;  /* flag for euclidean distances */
  protected int[]      tour;    /* best (known) tour */
  private   double     bbx, bby;/* bounding box of vertices */
  private   double     bbw, bbh;/* (position and width and height) */
  private   boolean    valid;   /* flag for valid bounding box */

  /*------------------------------------------------------------------*/

  public TSP () { this(BLKSIZE); }

  public TSP (int size)
  {                             /* --- create a traveling salesman p. */
    this.size   = 0;            /* initialize the variables */
    this.xs     = new double[size];
    this.ys     = new double[size];
    this.dists  = null;         /* do not create distance matrix yet */
    this.euclid = true;         /* default: Euclidean distances */
    this.sym    = true;         /* default: symmetric distances */
    this.tour   = null;         /* there is no known (best) tour */
    this.valid  = false;        /* the bounding box is not valid */
  }  /* TSP() */

  /*------------------------------------------------------------------*/

  public TSP (int size, Random rand)
  {                             /* --- create a traveling salesman p. */
    this(size);                 /* initialize the variables, */
    this.randomize(rand);       /* create random vertices, and */
    this.makeDists(true);       /* calculate the distances */
  }  /* TSP() */

  /*------------------------------------------------------------------*/

  private void resize (int size)
  {                             /* --- resize coord. vectors */
    int    k;                   /* current/new vector size */
    double v[];                 /* buffer for reallocation */

    k = this.size;              /* get the number of nodes to copy */
    if (size < 0) size = k +((k < BLKSIZE) ? BLKSIZE : (k >> 1));
    if (size < k) k = this.size = size;
    System.arraycopy(this.xs, 0, v = new double[size], 0, k);
    this.xs = v;                /* enlarge the x-coordinates vector */
    System.arraycopy(this.ys, 0, v = new double[size], 0, k);
    this.ys = v;                /* enlarge the y-coordinates vector */
  }  /* resize() */

  /*------------------------------------------------------------------*/

  public int add (double x, double y)
  {                             /* --- add a vertex */
    if (this.size >= this.xs.length)
      this.resize(-1);          /* resize the coord. vectors if nec. */
    this.valid = false;         /* bounding box is no longer valid */
    this.xs[this.size] = x;     /* set the coordinates */
    this.ys[this.size] = y;     /* of the new vertex */
    return this.size++;         /* and return its index */
  }  /* add() */

  /*------------------------------------------------------------------*/

  public void randomize (Random rand)
  {                             /* --- create random vertices */
    for (int i = this.size = this.xs.length; --i >= 0; ) {
      this.xs[i] = rand.nextDouble();
      this.ys[i] = rand.nextDouble();
    }                           /* set random coordinates */
    this.valid = false;         /* bounding box is no longer valid */
  }  /* randomize() */

  /*------------------------------------------------------------------*/

  public int    size   ()      { return this.size; }
  public double getX   (int i) { return this.xs[i]; }
  public double getY   (int i) { return this.ys[i]; }
  public void   setPos (int i, double x, double y)
  { this.xs[i] = x; this.ys[i] = y; }

  /*------------------------------------------------------------------*/

  public void transform (double scale, double xoff, double yoff)
  {                             /* --- transform vertex coordinates */
    for (int i = this.size; --i >= 0; ) {
      this.xs[i] = this.xs[i] *scale +xoff;
      this.ys[i] = this.ys[i] *scale +yoff;
    }                           /* traverse and transform vertices */
    this.valid = false;         /* bounding box is no longer valid */
  }  /* transform() */

  /*------------------------------------------------------------------*/

  private void bbox ()
  {                             /* --- compute bounding box */
    int    i;                   /* loop variable */
    double x, y;                /* coordinates of a vertex */
    double xmax, ymax;          /* maximal x- and y-coordinates */

    this.bbx = Double.MAX_VALUE; xmax = -Double.MAX_VALUE;
    this.bby = Double.MAX_VALUE; ymax = -Double.MAX_VALUE;
    for (i = this.xs.length; --i >= 0; ) {
      x = this.xs[i];          /* traverse the vertices */
      y = this.ys[i];          /* of the problem */
      if (x < this.bbx) this.bbx = x;
      if (x > xmax)     xmax     = x;
      if (y < this.bby) this.bby = y;
      if (y > ymax)     ymax     = y;
    }                           /* find minimum and maximum coords. */
    this.bbw = xmax -this.bbx;  /* compute the width and height */
    this.bbh = ymax -this.bby;  /* of the bounding box */
    this.valid = true;          /* the bounding box is now valid */
  }  /* bbox() */

  /*------------------------------------------------------------------*/

  public double getX ()
  { if (!this.valid) this.bbox(); return this.bbx; }

  public double getY ()
  { if (!this.valid) this.bbox(); return this.bby; }

  public double getWidth ()
  { if (!this.valid) this.bbox(); return this.bbw; }

  public double getHeight ()
  { if (!this.valid) this.bbox(); return this.bbh; }

  /*------------------------------------------------------------------*/

  public void makeDists (boolean calc)
  {                             /* --- calculate distance matrix */
    int    i, k;                /* loop variables */
    double dx, dy;              /* coordinate-wise distances */
    double v[];                 /* buffer for reallocation */

    if (this.size < this.xs.length)
      this.resize(this.size);   /* shrink the coord. vectors if poss. */
    this.dists = new double[this.size][this.size];
    if (!calc) return;          /* create the distance matrix */
    for (i = this.size; --i >= 0; ) {
      this.dists[i][i] = 0;     /* set diagonal elements to zero */
      for (k = i; --k >= 0; ) { /* traverse the off-diagonal elements */
        dx = this.xs[i] -this.xs[k];
        dy = this.ys[i] -this.ys[k];
        this.dists[i][k] = this.dists[k][i] = Math.sqrt(dx*dx +dy*dy);
      }                         /* compute pairwise vertex distances */
    }                           /* (Euclidian distances, symmetric) */
    this.euclid = this.sym = true;
  }  /* makeDists() */

  /*------------------------------------------------------------------*/