eventsimulation.java

来自「JAVA版的蚂蚁算法(Ant Colony Optimization Algor」· Java 代码 · 共 865 行 · 第 1/2 页

package dk.itu.nulx30.eventSimulation;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

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

import dk.itu.nulx30.ant.AntPackage;
import dk.itu.nulx30.ant.PicsAndStatGenerator;

import dk.itu.nulx30.networkModel.Network;
import dk.itu.nulx30.networkModel.NetworkPackage;
import dk.itu.nulx30.networkModel.Router;
import dk.itu.nulx30.networkModel.RoutingAlgorithm;

import dk.itu.nulx30.util.Algorithms;
import dk.itu.nulx30.util.BinaryHeap;

/**
 * The class <code>EventSimulation</code> is an implementation of an
 * event-driven simulation. The class contains several properties for a
 * simulation:<br>
 * the duration of the simulation<br>
 * the network, which the simulation runs on<br>
 * and some distributions of probabilities to randomize the runs.
 *
 * @author Jacob Wahl Winther
 * @author Mikkel Bundgaard
 * @author Troels C. Damgaard
 * @author Federico Decara
 */
public class EventSimulation {
  /** number of ants died from TTL*/
  protected int tllDeaths;
  /** number of ants died on inputqueues */
  protected int inputQueueDeaths;
  /** number of ants died on outputqueues */
  protected int outputQueueDeaths;
  /** number of ants died from no possible routing*/
  protected int nprDeaths;

  /** Number of packages initially created in the simulation*/
  protected int numInitPackages;

  /**
   * A random number source used to randomize the time of creation of packages.
   * This random source can be seeded in the simulation file.
   *
   * @see #collectDataFromSimMaker( String )
   */
  private Random rnd;

  /**
   * The seed of the random source <code>rnd</code>.
   *
   * @see #collectDataFromSimMaker( String )
   */
  protected long seed;

  /** The layout of the network in the simulation*/
  protected Network network;

  /** The duration of the simulation*/
  protected long duration;

  /** The interval for package creation in the simulation*/
  private int packageCreationInterval;
  /**
   * This list contains the probabilities for a given router to create a package
   * at each interval.
   */
  protected List packageCreationDistribution;
  /**
   * This list contains the probabilities for a given router to be the destination
   * for a given package.
   */
  protected List packageDestinationDistribution;

  /** The binary heap which contains all the events in the simulation*/
  protected BinaryHeap bh;

  /** The number of lost packages in this simulation*/
  protected long lostPackages;

  /**
   * This list can be used to collect various data during a run.
   * What is collected is controlled in the <code>EventGatherStat</code>
   * -class. The simulation file contains information about if, and when
   * gather-stat events are scheduled.
   */
  protected List simulationStatistics;

  /** The interval with which to collect statistical data (set in sim-file) */
  protected int statInterval;

  /** Only if this variable is true - collect stat-data (set in sim-file) */
  protected boolean statCollect;

  /** Contains the current time in simulation */
  protected double simTime;

  /** Counts the accumulated time of all packages in the network */
  protected double accumulatedPackageTime;

  /** Count ant package time for dead ants? */
  protected boolean countDeadAntPackageTime;

  /**
   * The routing algorithm, that is used for routing in this simulated network.
   */
  protected RoutingAlgorithm routingAlgorithm;

  /**
   * The array of String's read from the simulation file, that is used
   * (together with the <code>Network</code>-object) to construct the
   * routing algorithm. Saved for pretty-printing purposes.
   */
  protected String[] argsArray;

  /**
   * The <code>Class</code> of the routing algorithm, that is used for routing
   * in this simulated network.
   */
  protected Class routingClass;

  /** The file, which contains the layout of the network */
  protected String networkFile;

  /** The file, which contains the layout of the simulation */
  protected String simulationFile;

  /**
   * The path to look for the <code>simulationFile</code> and <code>networkFile
   * </code>.
   */
  protected String path;

  /**
   * This boolean is false until the <code>initialize()</code>-method has been run.
   * A simulation cannot be run until it has been initialized.
   * When a simulation has been run it becomes false again.
   */
  private boolean initialized = false;

  /**
   * Class constructor for <code>EventSimulation</code> which takes two arguments
   * <code>networkFile</code> and <code>simulationFile</code>. Both these files
   * must be in a valid format otherwise the simulation will end.
   * NOTE that the end of this method is deferred to the private
   * <code>initialize</code>-method.
   *
   * @param path the path of the two files
   * @param networkFile the file, which contains the layout of the network
   * @param simulationFile the file, which contains the layout of the simulation
   *
   * @see #initialize()
   */
  public EventSimulation( String path, String networkFile, String simulationFile ) {
    this.path = path;
    this.networkFile = networkFile;
    this.simulationFile = simulationFile;
  }

  /**
   * This method (re)initializes an <code>EventSimulation</code>-object by
   * clearing and resetting all values - and reconfiguring the network
   * event-heap.
   */
  public void initialize() {
    System.err.println( "Initializing network and simulation...");
    lostPackages = 0;
    simTime = 0;
    tllDeaths = 0;
    nprDeaths = 0;
    inputQueueDeaths = 0;
    outputQueueDeaths = 0;
    accumulatedPackageTime = 0;
    countDeadAntPackageTime = false;
    numInitPackages = 0;
    statCollect = false;
    simulationStatistics = new ArrayList();
    EventGatherStat.resetGatherStat();

    bh = new BinaryHeap( 100 );
    network = new Network();
    packageCreationDistribution = new ArrayList();
    packageDestinationDistribution = new ArrayList();

    // Create the network from the file: networkFile
    network.createFromGraphMaker( getNetworkName(), path + networkFile, 0 );
    // Create the simulation from the file: simulationFile
    collectDataFromSimMaker( path + simulationFile );
    // Create all the incoming packages
    createInputQueueEvents();
    routingAlgorithm.scheduleRoutingEvents( this );
    // Create events that print how many ants have died
    if ( statCollect ) {
      createGatherStatEvents( statInterval );
    }
    initialized = true;
    System.err.println( "Initializing completed succesfully.");
  }

  /**
   * This method creates all the <code>EventInputQueue</code> events that will
   * happen during a simulation because of incoming packages. These events are
   * created from the information given in the simulation file in the constructor.
   *
   * @see #packageCreationDistribution
   * @see #packageCreationInterval
   */
  private void createInputQueueEvents() {
    // For each package creation interval
    for ( int time = 0; time < duration; time += packageCreationInterval ) {
      // For each router
      for ( int r = 0; r < packageCreationDistribution.size(); r++ ) {
        // The probability that a router sends a package at each interval
        double prob = ( ( Double )
                           packageCreationDistribution.get( r ) ).doubleValue();

        // Should this router send a package at this interval
        if ( rnd.nextDouble() < prob ) {
          numInitPackages++;
          Router source = ( Router ) network.getVertex( r );
          Router dest = calculateDestination( source );
          NetworkPackage pack = new AntPackage( source, dest,
                                               network.getNumberOfVertices(), time );
          // Send package
          EventInputQueue input = new EventInputQueue( ( double ) time, source,
                                                               pack, bh, this );
          bh.add( input );
        }
      }
    }
  }

  /**
   * Creates all the <code>EventGatherStat</code> events which should happen in
   * this simulation.
   *
   * @param interval the interval between the <code>EventGatherStat</code> events
   * in the simulation
   */
  public void createGatherStatEvents( int interval ) {
    for ( int time = 0; time < duration; time += interval ) {
      bh.add( new EventGatherStat( time, this ) );
    }
  }

  /**
   * Returns a calculated destination from a given router. The destination is
   * calculated using the <code>packageDestinationDistribution</code> given
   * in the simulation file and the method <code>calculateChoice</code> in the
   * class <code>Algorithms</code>.
   *
   * @param source the source to calculate a destination from
   *
   * @return the calculated destination of a package.
   *
   * @see dk.itu.nulx30.util.Algorithms#calculateChoice( List )
   * @see #packageDestinationDistribution
   */
  private Router calculateDestination( Router source ) {
    int sourceIndex = source.getIndex();
    int destIndex = Algorithms.calculateChoice(
                                               packageDestinationDistribution, rnd );
    // Continue to choose a new destination until we find one that is different
    // from the source
    while ( sourceIndex == destIndex ) {
      destIndex = Algorithms.calculateChoice( packageDestinationDistribution, rnd );
    }

    return ( Router ) network.getVertex( destIndex );
  }

  /**
   * This method reads a file at the location given in <code>fileName</code> amd
   * constructs a corresponding simulation. Below is given an example
   * of a file (all text after // is comments) :<br>
   * Routing Class and arguments
   * dk.itu.nulx30.ant.AntRoutingSystem 1.0 2.0 100.0<br>
   * Duration<br>
   * 1000<br>
   * Random Seed<Br>
   * 10<br>
   * Collect statistics<Br>
   * true<Br>
   * Statistics interval<Br>
   * 1000<Br>
   * Package creation interval<br>
   * 15<br>
   * Package creation distribution<br>
   * Router probability   <i>// must be between 0 and 1</i><br>
   * 0 1         <i>// If a router is left out assume a probability of 0</i><br>
   * 1 0.25<br>
   * 2 0.1<br>
   *              <i>// An empty line indicates end of this section</i><br>
   * Package destination distribution
   *              <i>// Routers which can recieve packages</i><br>
   * Router probability
   *              <i>// If a router is left out assume a probability of 0</i><br>
   * 0 0.5              <i>// Routers must be written in ascending order</i><br>
   * 1 0.12<br>
   * 2 0.12<br>
   *               <i>// An empty line indicates end of this section</i><br>
   * Custom events  <i>// Missing arguments should contain "-" </i><br>
   * Time Eventtype Router1 Router2 Value<br>
   * 800 RemoveRouter 3 - - <br>
   * 900 SetWireDelay 2 1 10 <br>
   * <i>// Possible event types: RemoveRouter, SetWireDelay </i>
   *
   * @param fileName the name of the file to read the simulation from
   */
  private void collectDataFromSimMaker( String fileName ) {
    BufferedReader input = null;
    StringTokenizer st;
    String tmpInput;
    double time;
    int newRouterNumber;
    int newRouterNumber2;
    String eventType;
    double value;
    int currentRouterNumber;

    try {
      input = new BufferedReader( new FileReader( fileName ) );
      }
    catch ( FileNotFoundException FNFe ) {
      throw new RuntimeException("Could not find file : " + fileName );
    }
    try {
      // Skip header
      input.readLine();
      st = new StringTokenizer( input.readLine() );

      argsArray = new String[ st.countTokens() - 1 ];
      Object[] args = new Object[ st.countTokens() ];
      Class[] argsClass = new Class[ st.countTokens() ];

      try {
        // Find the class from the name in the textfile assume that the only
        // arguments are Doubles
        routingClass = Class.forName( st.nextToken() );

        Class doubleClass = new Double( 0 ).getClass();

        args[ 0 ] = network;
        argsClass[ 0 ] = network.getClass();

        int i = 1;
        while ( st.hasMoreTokens() ) {
          String token = st.nextToken();
          argsArray[ i - 1 ] = token;
          args[ i ] = new Double( token );
          argsClass[ i ] = doubleClass;
          i++;
        }

        // Instantiate the class with the correct constructor using reflection
        routingAlgorithm = ( RoutingAlgorithm )
                        routingClass.getConstructor( argsClass ).newInstance( args );

      }
      catch ( Exception e ) {
      e.printStackTrace();
        throw new RuntimeException( "Error in initializing RoutingAlgorithm from " +
                                    "simulation file" );
      }

      // Read the duration of the simulation
      while ( !input.readLine().equals( "Duration" ) ){};
      duration = Long.parseLong( input.readLine() );

      // Read the seed of the simulation, if -1 then use no seed
      while ( !input.readLine().equals( "Random Seed" ) ){};
      seed = Long.parseLong( input.readLine() );

      rnd = ( seed != -1 ) ? new Random( seed ) : new Random();

      // Read whether to collect stat-data
      while ( !input.readLine().equals( "Collect statistics" ) ){};
      if ( input.readLine().toLowerCase().equals("true") ) {
        statCollect = true;
      }

      // Read the interval with which to collect stat-data
      while ( !input.readLine().equals( "Statistics interval" ) ){};
      statInterval = Integer.parseInt( input.readLine() );

      // Read whether to count dead ant's package time for accumulated package time
      while ( !input.readLine().equals( "Count dead ant package time" ) ){};
      tmpInput = input.readLine().toLowerCase();
      if ( tmpInput.equals( "true" ) ) {
        countDeadAntPackageTime = true;
      }
      else if ( tmpInput.equals( "false" )  ) {
        countDeadAntPackageTime = false;
      }
      else {
        throw new RuntimeException( "Error in reading parameter \"Count dead ant " +
                                    "package time\" from simulation file" );
      }

      // Read the rest of the header of the file
      while ( !input.readLine().equals( "Package creation interval" ) ){};
      packageCreationInterval = Integer.parseInt( input.readLine() );

      while ( !input.readLine().equals( "Router probability" ) ){};

      tmpInput = input.readLine();
      // Read in all the probabilities until the empty line
      currentRouterNumber = 0;
      while ( !tmpInput.trim().equals( "" ) ) {

        st = new StringTokenizer( tmpInput );

        newRouterNumber = Integer.parseInt( st.nextToken() );
        // Insert the routers we have skipped
        while ( newRouterNumber > currentRouterNumber ) {
          packageCreationDistribution.add( new Double( 0 ) );
          currentRouterNumber++;
        }

        value = Double.parseDouble( st.nextToken() );

        packageCreationDistribution.add( new Double( value ) );

        currentRouterNumber++;