Environment.java

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