antroutingsystem.java

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

package dk.itu.nulx30.ant;

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

import dk.itu.nulx30.graph.Vertex;

import dk.itu.nulx30.eventSimulation.EventSimulation;

import dk.itu.nulx30.networkModel.AntRoutingEntry;
import dk.itu.nulx30.networkModel.Network;
import dk.itu.nulx30.networkModel.NetworkPackage;
import dk.itu.nulx30.networkModel.Router;
import dk.itu.nulx30.networkModel.RoutingTable;
import dk.itu.nulx30.networkModel.Wire;
import dk.itu.nulx30.networkModel.RoutingAlgorithm;

import dk.itu.nulx30.networkModel.exceptions.RouterNotFoundException;
import dk.itu.nulx30.networkModel.exceptions.NoPossibleRoutingException;

import dk.itu.nulx30.util.Algorithms;

/**
 * This class is the implementation of our routing algorithm. The algorithm is
 * basically an extension of the <code>Ant System</code> algorithm.<br>
 * We have used a lot of the experience gained from our ant-algorithm for
 * the <code>Single Source Shortest Paths</code> problem, combined with inspiration
 * from the articles we have read.<br>
 * An ant-package <code>k</code> is placed in the input-queue in its source
 * router <code>s</code>, and is routed stochastically through the network until
 * it reaches its destination router <code>d</code>. A delayed trail update rule
 * then updates the routing tables in all used routers on its path immediately.<br>
 * As the ant-packages move concurrently through the network an update could change
 * routing tables at any given time.
 *
 * @author  Mikkel Bundgaard
 * @author  Troels C. Damgaard
 * @author  Federico Decara
 * @author  Jacob W. Winther
 */
public class AntRoutingSystem implements RoutingAlgorithm {
  /**
   * The network this routing algorithm has to route in.
   * Used for manipulating trail-values over all routers in the network.
   */
  private Network network;

  /** Used to scale the relative importance of trail value*/
  private double alpha;

  /**
   * Used to scale the relative importance of visibility
   * ( 1/weight of Edge )
   */
  private double beta;

  /**
   * The probability for a package to be routed randomly.
   * This chance should be set to a small double-value e.g. 0.01.
   * (Set to zero if no random routing).
   */
  private double randomRouteProbability;

  /**
   * This value is used to scale the amount of trail deposited.
   * This value should not be lesser than the minimum route in the network(!)
   */
  private double trailDepositScale;

  /**
   * This value is used to scale the negative feedback (via trailvalue) to
   * wires that are used by 'dying' ants.
   */
  private double negativeFeedbackScale;

  /**
   * This value is used setting a lower and upper bound on trail-values in
   * routing tables. The lower bound is equal to <code>boundOnTrail</code,
   * while the upper bound is <code>1 - boundOnTrail</code>.
   */
  private double boundOnTrail;

  /**
   * Class constructor for <code>AntRoutingSystem</code> which takes several
   * arguments.
   *
   * @param theNetwork the network to route in
   * @param alpha the alpha value
   * @param beta the beta value
   * @param randomRouteProbability the probability for a package to be
   * routed randomly
   * @param trailDepositScale the value to scale the amount of trail deposited
   * @param negativeFeedbackScale the value to scale the negative feedback
   * @param boundOnTrail the lower and upper bound on trail-values in the
   * routing tables
   */
  public AntRoutingSystem( Network theNetwork, Double alpha, Double beta,
                            Double randomRouteProbability, Double trailDepositScale,
                            Double negativeFeedbackScale, Double boundOnTrail ){
    this.network = theNetwork;
    this.alpha = alpha.doubleValue();
    this.beta = beta.doubleValue();
    this.randomRouteProbability = randomRouteProbability.doubleValue();
    this.trailDepositScale = trailDepositScale.doubleValue();
    this.negativeFeedbackScale = negativeFeedbackScale.doubleValue();
    this.boundOnTrail = boundOnTrail.doubleValue();
    // Normalize the trailvalues in the routing-entries to 1
    normalizeRoutingEntries( 1 );
  }

  /**
   * 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.
   * If Ant has died, then a negative reinforcement is layed upon the last
   * router-entry used.
   * In <code>AntRoutingSystem</code> this is implemented, so trail-values on
   * not selected paths are decremented accordingly. This substitutes for regular
   * numberical pheromene evaporation.
   *
   * @param ant the ant whose trail should be laid
   * @param dead true, if this trail-deposit is for a dead ant
   */
  public void depositTrailOnAllEdges( Ant ant, boolean dead ) {
    AntPackage antPackage = ( AntPackage ) ant;
    List usedRouters = antPackage.getVisitedVertices();
    List usedWires   = antPackage.getVisitedEdges();
    int targetRouterIndex = antPackage.getDestination().getIndex();

    if ( dead && ant.getVisitedEdges().size() > 0 ) {
      // The ant did not die in source-input queue
      double k = -negativeFeedbackScale;
      RoutingTable rt = ( ( Router ) ant.getCurrentVertex() ).getRoutingTable();
      Wire usedWire = ( Wire ) ant.getLastEdge();
      rt.updatePheromoneNormalized( targetRouterIndex, usedWire, k, boundOnTrail );
    }
    else {
      double q = ( 1 / antPackage.getTimeInNetwork() ) * trailDepositScale;
                                        // trailDepositScale <= min. route in network

      for ( int r = 0; r < usedRouters.size() - 1; r++ ) {
        RoutingTable rt = ( ( Router ) usedRouters.get( r ) ).getRoutingTable();
        Wire wire = ( Wire ) usedWires.get( r );
        rt.updatePheromoneNormalized( targetRouterIndex, wire, q, boundOnTrail );
      }
    }
  }

  /**
   * Given a <code>List</code> containing a routing table and a
   * <code>NetworkPackage</code> this method returns a <code>List</code>
   * containing the transition probabilities.
   *
   * @param antRoutingTable the <code>List</code> of edges the ant can choose
   * between
   * @param np the network package to calculate the probabilities for
   *
   * @exception NoPossibleRoutingException a <code>NoPossibleRoutingException</code>
   * exception is thrown if is not possible to route the package any further
   *
   * @return a <code>List</code> of normalized probabilities
   */
  public List computeTransitionProbabilities( List antRoutingTable,
                              NetworkPackage np ) throws NoPossibleRoutingException {
    // The index of the destination router
    int destIndex = ( (AntPackage ) np ).getDestination().getIndex();

    // The sum of the pheromone values are used to normalize the probabilities
    double sum = 0;

    AntRoutingEntry tmpEntry;

    // A list containing probabilities for the choice of the next router
    List probabilities = new ArrayList( antRoutingTable.size() );

    double[] probVals = new double[ antRoutingTable.size() ];

    double numbOfVals = 0;
    for ( int i = 0; i < antRoutingTable.size(); i++ ) {
        // Normalize the probabilities
        tmpEntry = ( AntRoutingEntry ) antRoutingTable.get( i );
        Wire tmpWire = tmpEntry.getWire();
        try {
          if ( np.getPathList().contains( tmpWire.getTarget() ) ) {
            probVals[ i ] = 0;
          }
          else {
            double outputQueueDelay = tmpWire.getSource().getOutputQueue(
                                                    tmpWire.getTarget() ).getDelay();
            double estimatedTime = tmpWire.getDelay() + outputQueueDelay;
            double pheroVal = tmpEntry.getPheromoneValue();
            probVals[ i ] = Math.pow( pheroVal / boundOnTrail, alpha ) *
              Math.pow( 1.0 / estimatedTime, beta );
            sum += probVals[ i ];
            numbOfVals++;
          }
        }
        catch ( RouterNotFoundException RNFe ){
          RNFe.printStackTrace();
        }
    }
    if ( sum == 0 ) {
      throw new NoPossibleRoutingException( "Package from : " + np.getSource() +
                       " to " + np.getDestination() + " had not possible routing." );
    }

    // Test whether to force the ant to a random path
    boolean randomChoice = false;
    if ( Math.random() < randomRouteProbability ) {
      randomChoice = true;
    }

    // Make the probabilities sum to 1
    double tmpVal;
    for ( int i = 0; i < probVals.length; i++ ) {
      tmpVal = probVals[ i ];
      if ( randomChoice && tmpVal > 0 ) {
        tmpVal = 1;
      }
      if ( randomChoice ) {
        probabilities.add( new Double( tmpVal / numbOfVals ) );
      }
      else {
        probabilities.add( new Double( tmpVal / sum ) );
      }
    }

    return probabilities;
  }

  /**
   * This method takes a package and the router which currently holds the package
   * and calculates the next router on the path to the destination.
   *
   * @param router the router which currently holds the package
   * @param pack the pack to send to the destination router
   *
   * @exception NoPossibleRoutingException a <code>NoPossibleRoutingException</code>
   * exception is thrown if is not possible to route the package any further
   *
   * @return the next router on the path to the destination
   */
  public Router routePackage( Router router, NetworkPackage pack )
                                                  throws NoPossibleRoutingException {
    // The index of the destination router
    int destIndex = pack.getDestination().getIndex();

    List routingList = router.getRoutingTable().getRoutingList( destIndex );
    List probabilities = computeTransitionProbabilities( routingList, pack );

    // Find the next router on the path based on the probabilities
    int choice = Algorithms.calculateChoice( probabilities );

    // Get the AntRoutingEntry for this choice
    AntRoutingEntry tmpEntry = ( AntRoutingEntry ) routingList.get( choice );

    return tmpEntry.getWire().getTarget();
  }

  /**
   * This method initializes all the pheromone values on all the routers in the
   * network. Each wire receive maxTrail / number of outputwires in this router. 
   *
   * @param maxTrail the trailvalue to distribute among the wires at each router
   */
  private void normalizeRoutingEntries( double maxTrail ) {
    Vertex[] routers = network.getAllVertices();
    int numEntries;

    // For each router
    for ( int i = 0; i < routers.length; i++ ) {
      // Number of wires in the router
      numEntries = ( ( Router ) routers[ i ] ).getRoutingTable().getNumberOfWires();
      ( ( Router ) routers[ i ] ).getRoutingTable().initializePheromoneValues(
                                                             maxTrail / numEntries );
    }
  }

  /**
   * This method can be used to put routing events into the event holder.
   *
   * @param sim the simulation in which the events has to occur
   */
  public void scheduleRoutingEvents( EventSimulation sim ){}

  /**
   * This method is called from the simulation each time a package has arrived at
   * its destination.
   *
   * @param netPackage the package which has arrived
   */
  public void packageArrived( NetworkPackage netPackage ){
    depositTrailOnAllEdges( ( AntPackage ) netPackage, false );
  }

  /**
   * This method is called when a router detecs that a package did not arrive
   * at the router it was sent to. The routing algorithm gets a chance to update
   * routing tables accordingly.
   *
   * @param netPackage the package which has died
   */
  public void packageLost( NetworkPackage netPackage ){
    depositTrailOnAllEdges( ( AntPackage ) netPackage, true );
  }

  /**
   * Sets the value of <code>alpha</code> to <code>newVal</code>
   *
   * @param newVal the new value of <code>alpha</code>
   */
  public void setAlpha( double newVal ) {
    alpha = newVal;
  }

  /**
   * Sets the value of <code>beta</code> to <code>newVal</code>
   *
   * @param newVal the new value of <code>beta</code>
   */
  public void setBeta( double newVal ) {
    beta = newVal;
  }

  /**
   * Accessor for <code>alpha</code>
   *
   * @return alpha-value
   */
  public double getAlpha() {
    return alpha;
  }

  /**
   * Accessor for <code>beta</code>
   *
   * @return beta-value
   */
  public double getBeta() {
    return beta;
  }

  /**
   * Accessor for <code>randomRouteProbability</code>
   *
   * @return randomRouteProbability-value
   */
  public double getRandomRouteProbability() {
    return randomRouteProbability;
  }

  /**
   * Accessor for <code>trailDepositScale</code>
   *
   * @return trailDepositScale-value
   */
  public double getTrailDepositScale() {
    return trailDepositScale;
  }

  /**
   * Accessor for <code>negativeFeedbackScale</code>
   *
   * @return negativeFeedbackScale-value
   */
  public double getNegativeFeedbackScale() {
    return negativeFeedbackScale;
  }

  /**
   * Accessor for <code>boundOnTrail</code>
   *
   * @return boundOnTrail-value
   */
  public double getBoundOnTrail() {
    return boundOnTrail;
  }
}