antsystem.java

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

package dk.itu.nulx30.ant;

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

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

/**
 * An implementation of the Ant-cycle - algorithm presented as Ant-System (AS)
 * by Di Caro et. al. in "Ant Algorithms for Discrete Optimization".
 *
 * @author Mikkel Bundgaard
 * @author Troels C. Damgaard
 * @author Federico Decara
 * @author Jacob W. Winther
 */
public class AntSystem extends ACOMetaHeuristic {
  /** Random number generator for this class*/
  private static Random rnd = new Random();
  /**The initial trail-value on a edge*/
  private static final double INITIAL_TRAIL_VALUE = 100.0;
  /**The number of ants run in each cycle*/
  private static final int NO_OF_ANTS = 50;
  /**A constant used in the value of the trail deposited*/
  private static final double DELAYED_TRAIL_VAL = 400.0;
  /** Used to scale the relative importance of trail value*/
  private static double alpha = 1.0;
  /**
   * Used to scale the relative importance of visibility
   * ( 1/weight of Edge )
   */
  private static double beta = 2.0;
  /** The factor of the evaporation*/
  private static double evapFactor = 0.50;
  /** The number of turns the algorithm should perform*/
  private int maxNoOfTurns;

  /**
   * Class constructor for <code>AntSystem</code> which takes a graph, the number
   * of ants to use, the way to update pheromone and the maximum number of turns.
   *
   * @param graph the graph to use in <code>AntSystem</code>
   * @param noOfAnts the number of ants to use in each turn
   * @param stepByStepPheroUpdate if true then the pheromone is updated
   * step-by-step otherwise it is updated delayed.
   * @param maxNoOfTurns the maximum number of turns in the algorithm
   */
  public AntSystem( Graph graph, int noOfAnts, boolean stepByStepPheroUpdate,
                                                             int maxNoOfTurns ){
    super( graph, noOfAnts );

    if ( stepByStepPheroUpdate ) {
      onlineStepByStepPheroUpdate = true;
    }
    else {
      onlineDelayedPheroUpdate = true;
    }

    this.maxNoOfTurns = maxNoOfTurns;
  }

  /**
   * Class constructor for <code>AntSystem</code> which takes a graph, the way
   * to update pheromone and the maximum number of turns. This constructor calls
   * the other constructor for
   * {@link #AntSystem( Graph, int, boolean, int) AntSystem}.
   *
   * @param graph the graph to use in <code>AntSystem</code>
   * @param stepByStepPheroUpdate if true then the pheromone is updated
   * step-by-step otherwise it is updated delayed.
   * @param maxNoOfTurns the maximum number of turns in the algorithm
   *
   * @see #AntSystem( Graph, int, boolean, int)
   */
  public AntSystem( Graph graph, boolean stepByStepPheroUpdate, int maxNoOfTurns ){
    this( graph, NO_OF_ANTS, stepByStepPheroUpdate, maxNoOfTurns );
  }

  /**
   * This method does nothing in <code>AntSystem</code>
   *
   * @param ant the ant to register stats 
   */
  public void registerStat( Ant ant ){}

  /**
   * This method updates all the edges in the graph with new pheromone values. 
   */
  public void pheromoneUpdate(){
    List allEdges = theGraph.getAllEdges();
    double newPheroVal;

    // For all edges update their pheomone value
    for ( int i = 0; i < allEdges.size(); i++ ) {
      Edge tmpEdge = ( ( Edge ) allEdges.get( i ) );
      newPheroVal = (1 - evapFactor) * tmpEdge.getTrail() +
                                                tmpEdge.getChangeInTrailValue();

      tmpEdge.updateTrail( newPheroVal );
      // Reset changeInTrailValue
      tmpEdge.setChangeInTrailValue( 0 );
    }
  }

  /** This method does nothing in <code>AntSystem</code>*/
  public void daemonActions(){}

  /**
   * This method does nothing in <code>AntSystem</code>
   *
   * @param ant the ant to deposit pheromone
   */
  public void depositTrailOnLastEdge( Ant ant ){}

  /**
   * <code>terminationCriterion()</code> returns a boolean, which is
   * <code>true</code> if noOfTurns >= maxNoOfTurns or otherwise
   * <code>false</code>
   *
   * @return <code>true</code> if noOfTurns >= maxNoOfTurns or otherwise
   * <code>false</code>
   */
  public boolean terminationCriterion(){
    return ( noOfTurns >= maxNoOfTurns );
  }

  /**
   * This method deposit trail on all the edges that the <code>ant</code>
   * has visited.
   *
   * @param ant the to deposit trail on the edges
   */
  public void depositTrailOnAllEdges( Ant ant ) {
    Edge current;
    // changeInTrailValue
    for ( int i = 0; i < ant.getVisitedEdges().size(); i++){
      current = ( Edge ) ant.getVisitedEdges().get( i );

      double tmpRes = current.getChangeInTrailValue() + DELAYED_TRAIL_VAL /
                                                          ant.getLengthOfTour();
      current.setChangeInTrailValue( tmpRes );
    }
  }

  /**
   * <code>isInTargetState</code> returns the state of the ant (if it is finished
   * or not).
   *
   * @param ant the ant, which is queried about its state
   *
   * @return the state of the ant. This can either be IN_TARGETSTATE or
   * NOT_IN_TARGETSTATE.
   */
  public EnumAntState isInTargetState( Ant ant ){
    // The ant has to travel from it's start-node and all the way round, and
    // then move to it's start-node again.
    return ( ant.getVisitedVertices().size() == theGraph.getNumberOfVertices() + 1 ?
             EnumAntState.IN_TARGETSTATE :
             EnumAntState.NOT_IN_TARGETSTATE );
  }

  /**
   * Returns a <code>Vertex</code> randomly with an even probability for each
   * <code>Vertex</code>.
   *
   * @return a random <code>Vertex</code> 
   */
  public Vertex getAntStartingVertex() {
    // Vertex lies between 0 and count -1.
    return theGraph.getVertex( ( Math.abs( rnd.nextInt() ) %
                                             theGraph.getNumberOfVertices() ) );
  }

  /**
   * This method computes the probabilities for the <code>ant</code> to move
   * to a given vertex. If the ant already has visited a vertex then the
   * probability for it is 0. If the ant has completed a tour it is forced back
   * to its start vertex.
   *
   * @param routingTable the routing table of the <code>Vertex</code> at the
   * ants current location.
   * @param ant the ant containing the "memory"
   *
   * @return a <code>List</code> of probabilities, which sums to 1
   */
  public List computeTransitionProbabilities( List routingTable, Ant ant ) {
    double[] array = new double[ routingTable.size() ];
    double sum = 0;
    Edge currentEdge;

    List res = new ArrayList( routingTable.size() );
    // If the ant has moved through all vertices then move back to startvertex
    if ( ant.getVisitedVertices().size() == theGraph.getNumberOfVertices() ) {
      // Find edge that leads back to startvertex
      for ( int i = 0; i < routingTable.size(); i++ ) {
        currentEdge = ( Edge ) routingTable.get( i );
        if ( currentEdge.getDestination( ant.getCurrentVertex() ).equals(
                                                      ant.getStartVertex() ) ) {
          res.add( i, new Double( 1.0 ));
        }
        else {
          res.add( i, new Double( 0.0 ));
        }
      }
    } // else calculate possibilities given by the formula below
    else {
      for ( int i = 0; i < routingTable.size(); i++ ) {
        currentEdge = ( Edge ) routingTable.get( i );
        if ( !ant.hasVisited( currentEdge.getDestination(
                                                  ant.getCurrentVertex() ) ) ) {
          array[ i ] = Math.pow( currentEdge.getTrail(), alpha ) *
                       Math.pow( 1.0 / currentEdge.getWeight(), beta );
        }
        else {
          array[ i ] = 0;
        }
        sum += array[ i ];
      }

      // Make the probabilities sum to 1
      for ( int i = 0; i < routingTable.size(); i++ ) {
        res.add( i, new Double( array[ i ] / sum ) );
      }
    }

    return res;
  }

  /**
   * The main method for running AntSystem.
   *
   * @param args the arguments to the main method
   */
  public static void main( String args[] ) {
    Graph g = new Graph();
    g.createFromUpperRowMatrix(
                         "D:\\Projekt\\AntCode\\Data\\Old\\bayg29_tsp_gz.txt", 1.0 );
    System.err.println( "Starting AS" );
    AntSystem as = new AntSystem( g, false, 200 );
    as.runACO();

    System.err.println( as.shortestTour );
    g.drawGraph( "D:\\Projekt\\AntCode\\TSP.jpg" , as.bestEdges,
                 "AS run on bayg29", false );
    System.exit( 0 );
  }
}