acometaheuristic.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;

import dk.itu.nulx30.util.Algorithms;

/**
 * This class represents the general algorithmic approach in the
 * Ant Colony Optimization (ACO) - metaheuristic and is a relatively
 * straightforward implementation of the pseudo-coded algorithm presented
 * in figure 3, page 10 of "Ant Algorithms for Discrete Optimization" by
 * Di Caro et. al. In this article the authors present a number of works that
 * they consider closely related and present the ACO metaheuristic as a description
 * of the common "meta-algorithmic" - approach.<br>
 * It therefore seemed obvious to start our research of the Ant-algorithms
 * by trying to implement a few of the different Ant-algorithms through an
 * implementation of this ACO-meta heuristic.<br>
 * This class is therefore made abstract and a number of methods - that
 * implement the specific action to be taken by the Ant-algorithm - is left to
 * be implemented by inheriting classes.
 *
 * @author Mikkel Bundgaard
 * @author Troels C. Damgaard
 * @author Federico Decara
 * @author Jacob W. Winther
 */
public abstract class ACOMetaHeuristic {
  /** The source index of a vertex in the graph (used by some algorithms)*/
  private int sourceIndex;
  /**
   * The source index of a vertex in the graph in the second run of an
   * algorithm (used by some algorithms).
   */
  private int secondRunsourceIndex;

  /** The number of dead ants in a run of the algorithm */
  private int numDeath = 0;

  /**
   * This flag select the trail-update method and should be set by the
   * inheriting class.
   * @see #newActiveAnt()
   */
  protected boolean onlineStepByStepPheroUpdate = false;

  /**
   * This flag select the trail-update method and should be set by the
   * inheriting class.
   * @see #newActiveAnt()
   */
  protected boolean onlineDelayedPheroUpdate = false;

  /**
   * This variable holds the length of the best tour found yet.
   */
  protected double shortestTour = Double.MAX_VALUE;

  /**
   * This list can (optionally) be used by subclasses to collect data for
   * statistics generation. It is accessed by its accessor-method
   * <code>getCollectedRunData()</code>.
   *
   * @see #getCollectedRunData()
   * @see #registerStat( Ant )
   * @see PicsAndStatGenerator
   */
  protected List statData;

  /**
   * This variable holds the edges of the best tour found yet.
   */
  protected List bestEdges;

  /**
   * This variable holds the graph that is (somehow) a representation of the
   * problem to be solved.
   */
  protected Graph theGraph;

  /**
   * This variable is set in the constructor - and controls the maximum number
   * of ants in each cycle.
   */
  protected int noOfAntsPrTurn;

  /** Default value for <code>noOfAntsPrTurn</code>*/
  private static final int DEFAULT_MAX_NUMBER_OF_ANTS = 100;

  /** This is a simple count of the number of ant-cycles run*/
  protected int noOfTurns = 0;

  /**
   * If this variable is set, the method <code>registerStat</code> is run after
   * every Ant-life cycle.
   *
   * @see #registerStat(Ant)
   * @see #newActiveAnt()
   */
  protected boolean collectStatInfo = true;

  /* ********** Abstract methods to be implemented by subclasses ********** */

  /** 
   * This method should implement pheromone (or trail) update and evaporation of the
   * algorithm.
   */
  public abstract void pheromoneUpdate();

  /**
   * This method can (optionally) be used to perform any action after each full
   * round of ants has been run.
   */
  public abstract void daemonActions();

  /**
   * This method should return a starting vertex for an ant.
   *
   * @return the starting <code>Vertex</code> for an ant
   */
  public abstract Vertex getAntStartingVertex();

  /**
   * This method should check the terminination criterion of the algorithm
   * and return true when this criterion has been met.
   *
   * @return true when the terminination criterion has been met otherwise false
   */
  public abstract boolean terminationCriterion();

  /**
   * This method should ( when <code>onlineDelayedPheroUpdate</code> is true )
   * implement a deposit of an amount of trail upon all edges that the Ant has used.
   *
   * @param ant the ant whose trail should be layed
   */
  public abstract void depositTrailOnAllEdges( Ant ant );

  /**
   * This method should ( when <code>onlineStepByStepPheroUpdate</code> is
   * true ) calculate and deposit a trail-value on the trail that an ant has
   * just moved upon.
   *
   * @param ant the ant whose trail should be layed
   */
  public abstract void depositTrailOnLastEdge( Ant ant );

  /**
   * This method is checked to see whether an Ant has achieved its goal.
   *
   * @param ant the ant
   *
   * @return true if the ant is the target state for the graph in the
   * implemented algorithm otherwise false
   */
  public abstract EnumAntState isInTargetState( Ant ant );

  /**
   * This method should build a normalized (that is - summing to 1) list of
   * probabilities for choosing each of the <code>Edges</code> in the parameter
   * <code>antRoutingTable</code>. This probability-list is sent together with the
   * <code>antRoutingTable</code> to the method <code>chooseDestination()</code>
   * - and an <code>Edge</code> is selected randomly based on the probabilities
   * stated by this method.
   *
   * @param antRoutingTable the <code>List</code> of edges the ant can choose
   * between
   * @param ant the ant
   *
   * @return a <code>List</code> of normalized probabilities
   */
  public abstract List computeTransitionProbabilities(
                                                     List antRoutingTable, Ant ant );

  /**
   * This method can (optionally) be used to perform any collection of information
   * regarding the run of every ant. If the variable <code>collectStatInfo</code> is
   * set, the method is run after every Ant-life cycle.
   *
   * @param ant the ant
   *
   * @see #collectStatInfo
   * @see #statData
   * @see #newActiveAnt()
   * @see PicsAndStatGenerator
   */
  public abstract void registerStat( Ant ant );

  /* *********************************************************************** */

  /**
   * This constructor takes a <code>Graph</code> representation of a problem and
   * initializes the object with the default maximum number of ants.
   *
   * @param theGraph a <code>Graph</code> representation of a problem
   * 
   * @see #DEFAULT_MAX_NUMBER_OF_ANTS
   */
  public ACOMetaHeuristic( Graph theGraph ){
    this( theGraph, DEFAULT_MAX_NUMBER_OF_ANTS );
  }

  /** This constructor takes a <code>Graph</code> representation of a problem and 
   * a specification of the maximum number of ants pr. turn.
   *
   * @param theGraph a <code>Graph</code> representation of a problem
   * @param noOfAntsPrTurn the maximum number of ants pr. turn
   */
  public ACOMetaHeuristic( Graph theGraph, int noOfAntsPrTurn ){
    this.theGraph = theGraph;
    this.noOfAntsPrTurn = noOfAntsPrTurn;
    initialize();
  }

  /**
   * <code>initialize()</code> initializes the algorithm.
   */
  public void initialize(){
    bestEdges = new ArrayList( 30 );
    noOfTurns = 0;
  }

  /**
   * Mutator-method for the field <code>collectStatInfo</code> that controls
   * whether stat-collection is done at the end of every ant-life cycle.
   *
   * @param newVal the new value of <code>collectStatInfo</code>
   *
   * @see #collectStatInfo
   * @see #newActiveAnt()
   */
  protected void setStatCollect( boolean newVal ){
    collectStatInfo = newVal;
  }

  /**
   * Sets the initial size of the <code>statData</code> list.
   *
   * @param initSize the initial size of the <code>statData</code> list
   */
  public void initializeStatData( int initSize  ){
    statData = new ArrayList( initSize );
  }

  /**
   * Accessor-method for the field <code>statData</code>
   *
   * @return the statData for this run or null if <code>collectStatInfo</code> is
   * <code>false</code>
   *
   * @see #collectStatInfo
   * @see #newActiveAnt()
   */
  public List getCollectedRunData(){
    return ( collectStatInfo == true ) ? statData : null;
  }
  
  /**
   * Accessor for the number of dead ants.
   *
   * @return number of dead ants.
   */
  public int getNumberOfDead(){   
    return numDeath;
  }

  /**
   * Accessor for the source index of a vertex in the graph (used by some
   * algorithms).
   *
   * @return the source index of a vertex
   */
  public int getSourceIndex() {
    return sourceIndex;
  }

  /**
   * Accessor for the source index of a vertex in the graph in the second run of
   * an algorithm (used by some algorithms).
   *
   * @return the source index of a vertex in the second run of an algorithm
   */
  public int getSecondRunSourceIndex() {
    return secondRunsourceIndex;
  }

  /**
   * Mutator for the source index of a vertex in the graph (used by some
   * algorithms).
   *
   * @param index the source index of a vertex
   */
  public void setSourceIndex( int index ) {
    sourceIndex = index;
  }

  /**
   * Mutator for the source index of a vertex in the graph in the second run of
   * an algorithm (used by some algorithms).
   *
   * @param index the source index of a vertex in the second run of an algorithm
   */
  public void setSecondRunSourceIndex( int index ) {
    secondRunsourceIndex = index;
  }



  /**
   * The method selects an <code>Edge</code> randomly based on the probabilities
   * received. The method assumes that the probabilities are normalized
   * (eg. the summation of the values equals 1).
   *
   * @param routingTable the <code>List</code> of edges an ant can choose between
   * @param probabilityDistr a <code>List</code> of normalized probabilities
   *
   * @return the chosen <code>Edge</code>
   */
  private Edge chooseDestination( List routingTable, List probabilityDistr ){
    return ( Edge ) routingTable.get(
                                    Algorithms.calculateChoice( probabilityDistr ) );
  }

  /**
   * Start the ACO-metaheuristic. Schedules the main activities :<br><br>
   * <code>
   * antsGenerationAndActivity()<br>
   * pheromoneUpdate()<br>
   * daemonActions()<br>
   * </code><br>
   * This loop is run until the method <code>terminationCriterion()</code>
   * returns true.
   *
   * @see #antsGenerationAndActivity()
   * @see #pheromoneUpdate()
   * @see #daemonActions()
   * @see #terminationCriterion()
   */
  public void runACO() {
    // Schedule main activities
    while ( !terminationCriterion() ){
      antsGenerationAndActivity();
      pheromoneUpdate();
      daemonActions(); //optional
      noOfTurns++;
    }
  }

  /** Runs one turn ('cycle') of ants. Every turn a number of ants equal to 
   * <code>noOfAntsPrTurn</code> is created, scheduled (via <code>scheduleNewAnt()
   * </code>) and run (via <code>newActiveAnt()</code>).
   *
   * @see #noOfAntsPrTurn
   * @see #newActiveAnt()
   */
  private void antsGenerationAndActivity(){
    int noOfAnts = 0;
    while ( noOfAnts++ < noOfAntsPrTurn ){
      newActiveAnt();
    }
  }

  /**
   * Runs a lifecycle of one single ant. An ant is created in a starting vertex; 
   * run until it meets the target criterion defined by the abstract method <code>
   * isIntargetState()</code> implemented by a subclass. The abstract method <code>
   * computeTransitionProbabilities</code> is used together with the method <code>
   * chooseDestination</code> to choose the destionation of Ant's and trail is
   * deposited delayed and/or step-by-step depending on the values of the flags
   * <code>onlineDelayedPheroUpdate</code> and
   * <code>onlineStepByStepPheroUpdate</code>. At the end of an
   * ant-lifecycle stat-info can be collected (via method
   * <code>registerStat</code>).
   *
   * @see #onlineDelayedPheroUpdate
   * @see #onlineStepByStepPheroUpdate
   * @see #collectStatInfo
   * @see #depositTrailOnLastEdge( Ant )
   * @see #depositTrailOnAllEdges( Ant )
   * 
   * @see #isInTargetState( Ant )
   * @see #chooseDestination
   * @see #computeTransitionProbabilities
   * @see #registerStat
   */
  private void newActiveAnt(){
    Vertex startVertex = getAntStartingVertex();
    Ant ant = new Ant( startVertex );

    // target State e.g = targetVertex in shortest path alg... or
    // "has been around all Vertices in Graph" in TSP
    while ( isInTargetState( ant ) == EnumAntState.NOT_IN_TARGETSTATE ){
      Vertex fromVertex = ant.getCurrentVertex();
      List routingTable = theGraph.getOutgoingEdges( fromVertex );
      List probabilityDistr = computeTransitionProbabilities( routingTable, ant );
      Edge via = chooseDestination( routingTable, probabilityDistr );

      ant.makeMove( via, via.getDestination( fromVertex ) );

      if ( onlineStepByStepPheroUpdate ){
        depositTrailOnLastEdge( ant );
      }
    }

    if ( isInTargetState( ant ) != EnumAntState.DEAD ) {
      if ( onlineDelayedPheroUpdate ){
        depositTrailOnAllEdges( ant );
      }

      if ( collectStatInfo ) {
        registerStat( ant );
      }

      // Update the current shortest tour
      if ( ant.getLengthOfTour() < shortestTour ) {
        shortestTour = ant.getLengthOfTour();
        bestEdges = ant.getVisitedEdges();
      }
    }
    // The ant could not reach its target state
    else {
      numDeath++;
      ant.die();
    }
  }

  /**
   * Typesafe enumeration to represent the various states of an ant: <br>
   * <code>IN_TARGETSTATE</code>, <code>NOT_IN_TARGETSTATE</code>, and
   * <code>DEAD</code>.
   *
   * @author  Mikkel Bundgaard
   * @author  Troels C. Damgaard
   * @author  Federico Decara
   * @author  Jacob W. Winther
   */
  public static class EnumAntState {
    /** Name of the enumerator */
    private final String enumName;
    /** Represents that the ant is in the target state.*/
    public static final EnumAntState IN_TARGETSTATE =
                                           new EnumAntState( "In targetstate" );
    /** Represents that the ant is not in the target state.*/
    public static final EnumAntState NOT_IN_TARGETSTATE =
                                       new EnumAntState( "Not in targetstate" );
    /** Represents that the ant could not reach its target state.*/
    public static final EnumAntState DEAD = new EnumAntState( "Dead" );
    
    /**
     * Private constructor which is only called within this class.
     *
     * @param name the name of the enumeration.
     */
    private EnumAntState( String name ) {
      enumName = name;
    }
    
    /**
     * Returns the <code>String</code> representation of this enumeration.
     *
     * @return the name of the enumeration.
     */
    public String toString() {
      return enumName;
    }    
  }  
}