antsssp.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.Graph;
import dk.itu.nulx30.graph.Vertex;

/**
 * AntSSSP is a single source shortest path algorithm implemented by the use of
 * the ACOMetaHeuristic. 
 *
 * @author Mikkel Bundgaard
 * @author Troels C. Damgaard
 * @author Federico Decara
 * @author Jacob W. Winther
 */
public class AntSSSP extends ACOMetaHeuristic {
  /**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 int noOfAnts = 50;
  /**A constant used in the value of the trail deposited*/
  private static double stepByStepTrailVal = 100.0;
  /** Used to scale the relative importance of alpha - trail value*/
  private static double alpha = 1.0;

  /**
   * Used to scale the relative importance of beta  - 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*/
  protected int maxNoOfTurns;
  /**
   * The number of the current ant, this variable is used to identify each
   * ant in the method registerStat.
   */
  protected int currentAntNo = 0;

  /**
   * This <code>List</code> contains transition probabilities calculated for
   * the current move.
   */
  protected List currentTransitionProbs;

  /**
   * Indicates whether this is the first run (initialization phase) or the
   * second run (routing of ants)
   */
  private boolean firstRun = true;

  /**
   * Class constructor for <code>AntSSSP</code> which takes a graph, the
   * number of ants pr. turn, the maximum number of turns, the value for alpha
   * and beta.
   *
   * @param graph the graph which the algorithm will work on
   * @param noOfAntsPrTurn the number of ants pr. turn in the algorithm
   * @param maxNoOfTurns the maximum number of turns in the algorithm
   * @param newAlpha the new value for alpha - the relative importance of
   * trail value
   * @param newBeta the new value for beta - the relative importance of
   * visibility
   * @param firstSource the source index of the first run of the algorithm.
   * This serves as the endpoint of the second run of the algorithm.
   * @param secondSource the source index of the second run of the algorithm.
   * This serves as the sourcepoint of the second run of the algorithm.
   */
  public AntSSSP( Graph graph, int noOfAntsPrTurn, int maxNoOfTurns,
           double newAlpha, double newBeta, int firstSource, int secondSource ){
    super( graph, noOfAntsPrTurn );

    this.maxNoOfTurns = maxNoOfTurns;
    onlineStepByStepPheroUpdate = true;
    alpha = newAlpha;
    beta = newBeta;

    setSourceIndex( firstSource );
    setSecondRunSourceIndex( secondSource );

    // initialize statData-list
    initializeStatData( noOfAntsPrTurn * maxNoOfTurns );
  }

  /**
   * Class constructor for <code>AntSSSP</code> which takes a graph and
   * the maximum number of turns. The number of ants pr. turn is set to
   * {@link #noOfAnts noOfAnts} and alpha and beta to 0.4 and 0.1
   * respectively. This constructor calls the other constructor of this class.
   *
   * @param graph the graph which the algorithm will work on
   * @param maxNoOfTurns the maximum number of turns in the algorithm
   * @param firstSource the source index of the first run of the algorithm.
   * This serves as the endpoint of the second run of the algorithm.
   * @param secondSource the source index of the second run of the algorithm.
   * This serves as the sourcepoint of the second run of the algorithm.
   *
   * @see #AntSSSP(Graph, int, int, double, double, int, int)
   */
  public AntSSSP( Graph graph, int maxNoOfTurns, int firstSource,
                                                       int secondSource ){
    this( graph, noOfAnts, maxNoOfTurns, 0.4, 0.1, firstSource, secondSource );
  }

  /**
   * Perform collection of information of the run of the ant given as argument.
   * This method is run after every ant-life cycle. The only information stored
   * is the length of the tour of the ant.
   *
   * @param ant the ant to collect information from
   */
  public void registerStat( Ant ant ){
    statData.add( currentAntNo++, new Double( ant.getLengthOfTour() ) );
  }

  /**
   * For each edge in the graph update the edge with new pheromone values
   * calculated from evaporation and the trail added in this turn.
   */
  public void pheromoneUpdate(){
    List allEdges = theGraph.getAllEdges();
    double newPheroVal;

    // For each edge do...
    for ( int i = 0; i < allEdges.size(); i++ ) {
      Edge tmpEdge = ( ( Edge ) allEdges.get( i ) );
      for ( int j = 1; j < 3; j++ ) {
        newPheroVal = ( 1 - evapFactor ) *
                      tmpEdge.getTrail( tmpEdge.getVertex( j ) ) +
                      tmpEdge.getChangeInTrailValue( tmpEdge.getVertex( j ) );

        tmpEdge.updateTrail( newPheroVal, tmpEdge.getVertex( j ) );
        tmpEdge.setChangeInTrailValue( 0.0, tmpEdge.getVertex( j ) );
      }
    }
  }

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

  /**
   * <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 does nothing in <code>AntSSSP</code>
   *
   * @param ant the ant to deposit trail on the edges
   */
  public void depositTrailOnAllEdges( Ant ant ) {}

  /**
   * Returns the starting vertex for an ant.
   *
   * @return the starting vertex (this is different from first run to second
   * run)
   */
  public Vertex getAntStartingVertex() {
    if ( firstRun ) {
      return theGraph.getVertex( getSourceIndex() );
    }
    else {
      return theGraph.getVertex( getSecondRunSourceIndex() );
    }
  }

  /**
   * This method is called to examine an ant for its state.
   *
   * @param ant the ant to examine for target state
   *
   * @return the state of the ant. This can either be: IN_TARGETSTATE,
   * NOT_IN_TARGETSTATE or DEAD (only possible in the second run).
   */
  public EnumAntState isInTargetState( Ant ant ){
    // if tmp == null then there is no move possible
    List tmp = calcPossibleTransitionProbs( ant.getCurrentVertex().getEdges(), ant );
    if ( firstRun ) {
      return ( tmp == null ? EnumAntState.IN_TARGETSTATE
                          : EnumAntState.NOT_IN_TARGETSTATE );
    }
    else {
      if ( tmp == null ) {
        return EnumAntState.DEAD;
      }
      else {
        return ( ant.getCurrentVertex().equals(
                theGraph.getVertex( getSourceIndex() ) )
                                            ? EnumAntState.IN_TARGETSTATE
                                            : EnumAntState.NOT_IN_TARGETSTATE );
      }
    }
  }

  /**
   * Returns a <code>List</code> containing probabilities that sum to 1. If
   * there is no move possible null is returned. These probabilities are
   * calculated from the informations given in the two arguments.
   *
   * @param ant which holds the memory to use in the calculations
   * @param routingTable the routingtable to calculate the probabilities from
   *
   * @return a <code>List</code> containing probabilities that sum to 1. If
   * there is no move possible null is returned.
   */
  private List calcPossibleTransitionProbs( List routingTable, Ant ant ){
    double[] array = new double[ routingTable.size() ];
    double sum = 0;
    Edge currentEdge;

    boolean canMove = false;
    currentTransitionProbs = new ArrayList( routingTable.size() );
    for ( int i = 0; i < routingTable.size(); i++ ) {
      currentEdge = ( Edge ) routingTable.get( i );
      // Tabu list for both iterations
      if ( !ant.hasVisited( currentEdge.getDestination(
                            ant.getCurrentVertex() ) ) ) {
        array[ i ] = Math.pow( currentEdge.getTrail(
            ant.getCurrentVertex() ), alpha ) *
            Math.pow( 1.0 / currentEdge.getWeight(), beta );
        canMove = true;
      }
      else {
        array[ i ] = 0;
      }
      sum += array[ i ];
    }

    for ( int i = 0; i < routingTable.size(); i++ ) {
      currentTransitionProbs.add( i, new Double( array[ i ] / sum ) );
    }

    return ( canMove ? currentTransitionProbs : null );
  }

  /**
   * Returns a <code>List</code> containing probabilities that sum to 1. If
   * there is no move possible null is returned. These probabilities are
   * already calculated when in calcPossibleTransitionProbs, when checking
   * if the ant is in the target state.
   *
   * @param ant which holds the memory to use in the calculations
   * @param routingTable the routingtable to calculate the probabilities from
   *
   * @return a <code>List</code> containing probabilities that sum to 1. If
   * there is no move possible null is returned.
   * @see #calcPossibleTransitionProbs(List, Ant)
   * @see #isInTargetState(Ant)
   */
  public List computeTransitionProbabilities( List routingTable, Ant ant ) {
    return currentTransitionProbs;
  }

  /**
   * This method is called if the algorithm use <code>
   * onlineStepByStepPheroUpdate</code> to update each edge after each
   * step of an ant.
   *
   * @param ant the ant which must deposit trail on the last edge it has visited
   * (but only in the first run)
   */
  public void depositTrailOnLastEdge( Ant ant ) {
    if ( firstRun ) {
      double tmpRes = ant.getLastEdge().getChangeInTrailValue(
          ant.getCurrentVertex() ) +
          ( Math.pow( stepByStepTrailVal, 3.0 ) /
            Math.pow( ant.getLengthOfTour(), 2.0) );
      ant.getLastEdge().setChangeInTrailValue( tmpRes, ant.getCurrentVertex() );
    }
  }

  /**
   * Sets up a number of values and the graph for the second run of the
   * algorithm. 
   *
   * @param newAlpha the alpha value to use in the second run of the algorithm
   * @param newBeta the beta value to use in the second run of the algorithm
   */
  public void setupSecondRun( double newAlpha, double newBeta ) {
    alpha = newAlpha;
    beta = newBeta;

    evapFactor = 0.0;
    stepByStepTrailVal = 0.0;
    firstRun = false;
    noOfTurns = 0;

    List edges = theGraph.getAllEdges();

    // Reset the number of ants on all edges
    for ( int i = 0; i < edges.size(); i++ ) {
      ( ( Edge ) edges.get( i ) ).setTotalAnts( 0 );
    }
  }

  /**
   * This main method runs AntSSSP on the graph located in the file
   * "D://Projekt//AntCode//Data//bayg29_tsp_gz.txt" with max distance set
   * to 75 and initial trail value set to 100. The main methods takes 6
   * arguments which decides a source index and alpha and beta values for
   * each of the two runs. 
   *
   * @param args an array consisting of 6 elements:<br>
   * int - the source index in the first run<br>
   * int - the source index in the second run<br>
   * double - the alpha value to use in the first run<br>
   * double - the beta value to use in the first run<br>
   * double - the alpha value to use in the second run<br>
   * double - the beta value to use in the second run<br>
   */
  public static void main( String args[] ){
    Graph someGraph = new Graph();
    someGraph.createFromUpperRowMatrix(
       "D://Projekt//AntCode//Data//bayg29_tsp_gz.txt", 75, INITIAL_TRAIL_VALUE );
    AntSSSP as = new AntSSSP( someGraph, 100, 100,
       Double.parseDouble( args[ 2 ] ),
       Double.parseDouble( args[ 3 ] ),
       Integer.parseInt( args[ 0 ] ),
       Integer.parseInt( args[ 1 ] ) );

    as.setStatCollect( false );

    as.runACO();

    as.setStatCollect( true );

    as.setupSecondRun( Double.parseDouble( args[ 4 ] ),
                       Double.parseDouble( args[ 5 ] ) );

    as.runACO();

    // Generate statistics and draw graphs
    PicsAndStatGenerator picsAndStatGen = new PicsAndStatGenerator( as );
    picsAndStatGen.createAndSetPicsAndStatDir( args );
    picsAndStatGen.generateStandardACOGraphPics();
    picsAndStatGen.generateStandardACOStats();
    System.exit( 0 );
  }
}