Environment.java

   1 import java.lang.Runtime;
   2 import java.util.Observable;
   3 import java.io.IOException;
   4
   5 class Environment extends Observable {
   6
   7   public final int NumOfAnts;
   8   public final int MaxNumOfTours;
   9
  10   public int[] MinTour;
  11   public int MinTourLength;
  12   public int MinTourIteration;
  13
  14   public Ant[] ants;
  15   public static Graph graph;
  16
  17   protected AntView av;
  18
  19   Environment(int MaxNumOfTours, int GuiSize, Graph graph) {
  20     this(MaxNumOfTours, GuiSize, graph.NumOfCities, graph);
  21   }
  22
  23   Environment(int MaxNumOfTours, int GuiSize, int NumOfAnts, Graph graph) {
  24
  25     this.MaxNumOfTours = MaxNumOfTours;
  26
  27     this.MinTour = new int[graph.NumOfCities];
  28     this.MinTourLength = graph.getINFINITY();
  29     this.MinTourIteration = 0;
  30
  31     this.NumOfAnts = NumOfAnts;
  32     this.ants = new Ant[NumOfAnts];
  33     Environment.graph = graph;
  34
  35     for (int i = 0; i < NumOfAnts; i++)
  36       ants[i] = new Ant(graph);
  37
  38     av = new AntView(graph.NumOfCities, GuiSize);
  39     this.addObserver(av);
  40
  41     /* add a shutdown hook to print out the last best solution */
  42     Runtime.getRuntime().addShutdownHook(new EnvironmentShutdownHook(this));
  43
  44     /* run the garbage collector after all the initialization is done */
  45     System.gc();
  46   }
  47
  48   /* d'tor */
  49   protected void finalize() {
  50     deleteObservers();
  51   }
  52
  53   public void run() {
  54     int i = 0;
  55     while (! terminateCondition(i++)) {
  56       constructSolutions();
  57       graph.pheromoneUpdate(ants);
  58       updateStatistics(i);
  59       /* localSearch();
  60        * updatePheromoneTrails(); */
  61     }
  62   }
  63
  64   protected void constructSolutions() {
  65
  66     /* clear ants memory and ..
  67      * assign an initial random city to ant */
  68     for (Ant ant : ants) {
  69       ant.clearData();
  70       ant.pickInitialRandomCity();
  71     }
  72
  73     /* let each ant construct a complete tour
  74      * start a 1 since every ant already has an initial city */
  75     for (int step = 1; step < graph.NumOfCities; step++) {
  76       for (Ant ant : ants)
  77         ant.neighbourListASDecisionRule(step);
  78     }
  79
  80     /* compute tour length of each ant */
  81     for (Ant ant : ants) {
  82       ant.computeTourLength();
  83     }
  84
  85   }
  86
  87   protected void updateStatistics(int iteration) {
  88     for (Ant ant : ants) {
  89       if (ant.TourLength < MinTourLength) {
  90         MinTourLength = ant.TourLength;
  91         MinTourIteration = iteration;
  92         for (int i = 0; i < graph.NumOfCities; i++) {
  93           MinTour[i] = ant.Tour[i];
  94         }
  95         this.setChanged();
  96         this.notifyObservers(MinTour);
  97       }
  98     }
  99     /* since we are already at it.. run the garbage collector */
 100     System.gc();
 101   }
 102
 103   protected Boolean terminateCondition(int iteration) {
 104     /* 1) solution within predefined distance
 105      * 2) max number of tour constructions or algorithm iterations
 106      * 3) max cpu time
 107      * 4) algorithm stagnation behaviour */
 108     if (iteration >= MaxNumOfTours) {
 109       return true;
 110     } else {
 111       return false;
 112     }
 113   }
 114
 115   @Override
 116     public String toString() {
 117       StringBuilder result = new StringBuilder();
 118       result.append("Shortest tour at iteration " +
 119           MinTourIteration +
 120           " with length " +
 121           MinTourLength +
 122           "\n");
 123
 124       for (int t : MinTour) {
 125         if (graph.ids[t] != null)
 126           result.append(graph.ids[t] + "\t");
 127         else
 128           result.append(t + "\t");
 129       }
 130       if (graph.ids[0] != null)
 131         result.append(graph.ids[MinTour[0]]);
 132       else
 133         result.append(MinTour[0]);
 134       return result.toString();
 135     }
 136
 137
 138
 139
 140
 141
 142
 143
 144   }
 145
 146 }