ant.java

JAVA版的蚂蚁算法(Ant Colony Optimization Algorithms)

package dk.itu.nulx30.ant;

import java.util.ArrayList;
import java.util.List;

import dk.itu.nulx30.graph.Edge;
import dk.itu.nulx30.graph.Vertex;

/**
 * An object of this class represents an ant travelling through a
 * <code>Graph</code> in algorithms that use the algorithmic approach 
 * of the Ant Colony Optimization (ACO) - metaheuristic.<br>
 * 
 * For convenience both the visited edges and vertices are remembered 
 * by the ant.
 *
 * @see ACOMetaHeuristic
 * @see dk.itu.nulx30.graph.Graph
 * 
 * @author  Mikkel Bundgaard
 * @author  Troels C. Damgaard
 * @author  Federico Decara
 * @author  Jacob W. Winther
 */
public class Ant {
  /** The memory of the ant - visited vertices.*/
  protected List visitedVertices;
  /** The memory of the ant - visited edges.*/
  private List visitedEdges;
  
  /**
   * The length (by some measure e.g. length or time of trip) that the ant
   * has currently experienced on its trip.
   */
  private double lengthOfTour;

  /**
   * Constructs an ant given the starting <code>Vertex</code> in some
   * <code>Graph</code>.
   *
   * @param start the start vertex of the ant.
   */
  public Ant( Vertex start ) {
    visitedVertices = new ArrayList();
    visitedEdges    = new ArrayList();
    start.antArrival(); // notify the Vertex of an ant move
    visitedVertices.add( start );

    lengthOfTour = 0;
  }

  /**
   * The method moves <code>Ant</code> to the <code>Vertex dest</code> by
   * the <code>Edge via</code>.
   *
   * @param via the <code>Edge</code> to travel by.
   * @param dest the <code>Vertex</code> to travel to.
   */
  public void makeMove( Edge via, Vertex dest ) {
    if ( via != null ){
      via.antMoveBy();  // notify the Edge of an ant move
      visitedEdges.add( via );
      lengthOfTour += via.getWeight();
    }
    if ( dest != null ){
      dest.antArrival();  // notify the Vertex of an ant move
      visitedVertices.add( dest );
    }
  }

  /**
   * Check whether Node n is on ant's tabulist.
   * ( Note that this is relatively costful operation taking
   * O(|visitedVertices|) )
   *
   * @param n the <code>Vertex</code> to search for in the ants memory.
   *
   * @return true if the ant has visited the <code>Vertex</code>.
   */
  public boolean hasVisited( Vertex n ) {
    return visitedVertices.contains( n );
  }

  /**
   * This method is called when the ant has died (when the ant can not reach
   * its target state). This method is currently not in use.
   */
  public void die() {}

  /** 
   * Returns the current position of the ant.
   *
   * @return the position of the ant. Eg. the vertex which the ant
   * is at.
   */
  public Vertex getCurrentVertex() {
    return ( Vertex ) visitedVertices.get( visitedVertices.size() - 1 );
  }

  /**
   * Returns the last edge that the ant has visited.
   *
   * @return the last edge that the ant has visited.
   */
  public Edge getLastEdge() {
    return ( Edge ) visitedEdges.get( visitedEdges.size() - 1 );
  }

  /** 
   * Returns the vertex from which the ant has started.
   *
   * @return the vertex from which the ant has started.
   */
  public Vertex getStartVertex() {
   return ( Vertex ) visitedVertices.get( 0 );
  }

  /** 
   * Accessor-method for the current length of the tour (by some 
   * measure - e.g. time or edgeweight) taken by the ant.
   *
   * @return the length of the tour of the ant.
   */
  public double getLengthOfTour() {
    return lengthOfTour;
  }

  /**
   * Accessor-method for the <code>List</code> of visited edges.
   *
   * @return the edges that the ant has visited.
   */
  public List getVisitedEdges() {
    return visitedEdges;
  }

  /** 
   * Accessor-method for the <code>List</code> of visited vertices.
   *
   * @return the vertices that the ant has visited.
   */
  public List getVisitedVertices() {
    return visitedVertices;
  }
}