algorithms.java

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

package dk.itu.nulx30.util;

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

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

/**
 * Class <code>Algorithms</code> contains a static method for solving
 * Single-Source Shortest Paths (Dijkstra).<br>
 * Further it contains a few relevant static methods for handling the
 * stochastic choice-making in ant-algorithms.
 * As such it is simply a container-class for a few basic but widely used
 * utility functions. 
 *
 * @author  Mikkel Bundgaard
 * @author  Troels C. Damgaard
 * @author  Federico Decara
 * @author  Jacob W. Winther
 */
public class Algorithms {
  /** A random variable used to randomize the selection of a choice*/
  private static Random random = new Random();
  /** Integer.MAX_VALUE / 3 is used as a value for infinity */
  public static final int INFINITY = Integer.MAX_VALUE / 3;
  /** This class cannot be instantiated */
  protected Algorithms() {}

  /**
   * Dijkstra's algorithm for Single-source Shortest-paths. The implementation
   * is based on the description given in "Introduction to Algorithms" Second
   * Edition by Thomas H. Cormen et. al. p. 595.
   *
   * @param g the graph on which to solve Single-source Shortest-paths.
   * @param s the index of the starting vertex.
   * @param attribute the attribute to sort the graph by.
   *
   * @return a <code>ShortestPaths</code> object which contains
   * the resulting distances and predecessor vertices.
   */
  public static ShortestPaths dijkstra( Graph g, int s, String attribute ) {
    // Create a ShortestPaths object to return the result in
    ShortestPaths res = new ShortestPaths( g.getNumberOfVertices() );
    Edge edge;
    int u = 0;

    initializeSingleSource( res, s );

    BinaryHeap q = new BinaryHeap( res.getDistances() );

    while ( !q.isEmpty() ) {
      // Extract the element with the minimum priority from the priority queue
      u = ( ( Distance ) q.extractMin() ).getIndex();
      List outEdges = g.getOutgoingEdges( g.getVertex( u ) );
      for ( int i = 0; i < outEdges.size(); i++ ) {
        edge = ( Edge ) outEdges.get( i );
        // Is the new path to the vertex shorter than the old one
        if ( res.getDistances()[ edge.getDestination( g.getVertex( u
            ) ).getIndex() ].getDistance() > res.getDistances()[ u ].getDistance() +
                                                   edge.getAttribute( attribute ) ) {
          // Relax the vertex
          int tmpIndex = edge.getDestination( g.getVertex( u ) ).getIndex();
          res.getDistances()[ tmpIndex ].setDistance(
            res.getDistances()[ u ].getDistance() + edge.getAttribute( attribute ) );
          // Decrease the vertexs priority in the BinaryHeap
          q.decreaseKey( tmpIndex, res.getDistances()[ tmpIndex ].getDistance() );
          // Make u the parent of edge.vertexName
           res.getPredecessors()[ edge.getDestination(
                                  g.getVertex( u ) ).getIndex() ] = u;
        }
      }
    }

    return res;
  }

  /**
   * Initializes a ShortestPaths object given a start vertex.
   *
   * @param g the <code>ShortestPaths</code> object to initialize
   * @param s the starting vertex of the <code>ShortestPaths</code> object
   */
  private static void initializeSingleSource( ShortestPaths g, int s ) {
    for ( int i = 0; i < g.getPredecessors().length; i++ ) {
      g.getDistances()[ i ] = new Distance( INFINITY, i );
      // -1 is chosen as an arbitrary value for a pointer to null
      g.getPredecessors()[ i ] = -1;
    }
    g.getDistances()[ s ].setPriority( 0 );
  }


  /**
   * Given a <code>List</code> of normalized <code>Doubles</code>
   * (that is - summing to 1) randomly selects an index in the List.<br>
   * This utility function is used in every ant route-selection as these are
   * made as a stochastic choice between a list routes.
   * The returned <code>int</code> is intended to be used for indexing into
   * a list of possible routes.
   *
   * @param probabilityDistr a normalized <code>List</code> of probabilities
   * (type:<code>Double</code>)
   * @return the index of the calculated choice
   */
  public static int calculateChoice( List probabilityDistr ){
    return calculateChoice( probabilityDistr, Algorithms.random );
  }

  /**
   * Given a <code>List</code> of normalized <code>Doubles</code>
   * (that is - summing to 1) randomly selects an index in the List.<br>
   * This utility function is used in every ant route-selection as these are
   * made as a stochastic choice between a list routes.
   * The returned <code>int</code> is intended to be used for indexing into
   * a list of possible routes.
   *
   * @param probabilityDistr a normalized <code>List</code> of probabilities
   * (type:<code>Double</code>)
   * @param rnd a variable holding a random number generator used for seed the
   * random choices
   * @return the index of the calculated choice
   */
  public static int calculateChoice( List probabilityDistr, Random rnd ){
    double rndNumber = rnd.nextDouble();
    int counter = -1;

    do {
      rndNumber -= ( ( Double ) probabilityDistr.get( ++counter ) ).doubleValue();
    } while ( rndNumber > 0 );

    return counter;
  }

  /**
   * Given a <code>List</code> of <code>Doubles</code> modifies the values of
   * this to a <code>List</code> of <code>Doubles</code> normalized by the sum
   * of the values.
   *
   * @param probabilityDistr an unnormalized <code>List</code> of probabilities
   *  (type:<code>Double</code>)
   */
  public static void normalizeDistribution( List probabilityDistr ) {
    double sum = 0;

    for ( int i = 0; i < probabilityDistr.size(); i++ ) {
      sum += ( ( Double ) probabilityDistr.get( i ) ).doubleValue();
    }

    for ( int i = 0; i < probabilityDistr.size(); i++ ) {
      double newVal = ( ( Double ) probabilityDistr.get( i ) ).doubleValue() / sum;
      probabilityDistr.set( i, new Double( newVal ) );
    }
  }
}