protoas/Environment.java

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