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.getNumOfCities()];
  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     /* TODO: threading */
  78     for (Ant ant : ants) {
  79       ant.clearData();
  80       ant.pickInitialRandomCity();
  81     }
  82
  83     /* let each ant construct a complete tour
  84      * start a 1 since every ant already has an initial city */
  85     /* TODO: threading */
  86     for (int step = 1; step < graph.getNumOfCities(); step++) {
  87       for (Ant ant : ants)
  88         ant.neighbourListASDecisionRule(step);
  89     }
  90
  91     /* compute tour length of each ant */
  92     /* TODO: threading */
  93     for (Ant ant : ants) {
  94       ant.computeTourLength();
  95     }
  96
  97
  98   }
  99
 100   protected void updateStatistics(int iteration) {
 101     for (Ant ant : ants) {
 102
 103       if (ant.getTourLength() < getMinTourLength()) {
 104         setMinTourLength(ant.getTourLength());
 105         setMinTourIteration(iteration);
 106
 107         for (int i = 0; i < graph.NumOfCities; i++) {
 108           setMinTour(i, ant.getTour(i));
 109         }
 110
 111         if (graph.hasCoordinates()) {
 112           this.setChanged();
 113           this.notifyObservers(this);
 114         }
 115       }
 116
 117     }
 118     /* since we are already at it.. run the garbage collector */
 119     System.gc();
 120   }
 121
 122   protected boolean stagnationBehaviour() {
 123     for (Ant antOne : ants) {
 124       for (Ant antTwo : ants) {
 125         for (int i : antOne.getTour()) {
 126           for (int j : antTwo.getTour()) {
 127             if (i != j)
 128               return false;
 129           }
 130         }
 131       }
 132     }
 133     return true;
 134   }
 135
 136   protected boolean terminateCondition(int iteration) {
 137     /* 1) solution within predefined distance
 138      * 2) max number of tour constructions or algorithm iterations
 139      * 3) max cpu time
 140      * 4) algorithm stagnation behaviour */
 141     if (iteration >= MaxNumOfTours) {
 142       return true;
 143     //} else if (stagnationBehaviour()) {
 144       //return true;
 145     } else {
 146       return false;
 147     }
 148   }
 149
 150   @Override
 151     public String toString() {
 152       StringBuilder result = new StringBuilder();
 153       result.append("Shortest tour at iteration " +
 154           MinTourIteration +
 155           " with length " +
 156           MinTourLength +
 157           "\n");
 158
 159       for (int t : MinTour) {
 160         if (graph.getIds(t) != null)
 161           result.append(graph.ids[t] + "\t");
 162         else
 163           result.append(t + "\t");
 164       }
 165       if (graph.getIds(0) != null)
 166         result.append(graph.ids[MinTour[0]]);
 167       else
 168         result.append(MinTour[0]);
 169       return result.toString();
 170     }
 171
 172   public int[] getMinTour() {
 173     return this.MinTour;
 174   }
 175
 176   public int getMinTour(int index) {
 177     return this.MinTour[index];
 178   }
 179
 180   public void setMinTour(int[] MinTour) {
 181     this.MinTour = MinTour;
 182   }
 183
 184   public void setMinTour(int index, int MinTour) {
 185     this.MinTour[index] = MinTour;
 186   }
 187
 188   public int getMinTourLength() {
 189     return this.MinTourLength;
 190   }
 191
 192   public void setMinTourLength(int MinTourLength) {
 193     this.MinTourLength = MinTourLength;
 194   }
 195
 196   public int getMinTourIteration() {
 197     return this.MinTourIteration;
 198   }
 199
 200   public void setMinTourIteration(int MinTourIteration) {
 201     this.MinTourIteration = MinTourIteration;
 202   }
 203
 204   public Graph getGraph() {
 205     return this.graph;
 206   }
 207
 208   public void setGraph(Graph graph) {
 209     this.graph = graph;
 210   }
 211
 212 }