Ant.java

   1 class Ant {
   2
   3   public int TourLength; // the ant's tour length
   4   public int[] Tour; // N+1; ant's memory storing (partial) tours
   5   public boolean[] Visited; // N; visited cities
   6
   7   public Graph graph;
   8
   9   Ant(Graph graph) {
  10
  11     this.graph = graph;
  12
  13     TourLength = 0;
  14
  15     Tour = new int[graph.getNumOfCities()];
  16     Visited = new boolean[graph.getNumOfCities()];
  17
  18     clearTour();
  19     clearMemory();
  20   }
  21
  22   public void computeTourLength() {
  23     for (int i = 0; i < graph.getNumOfCities() - 1; i++) {
  24       TourLength += graph.getDistance(Tour[i], Tour[i+1]);
  25     }
  26     TourLength +=
  27       graph.getDistance(Tour[graph.getNumOfCities() - 1], Tour[0]);
  28   }
  29
  30   public void pickInitialRandomCity() {
  31     int r = (int)(Math.random() * graph.NumOfCities);
  32     Tour[0] = r;
  33     Visited[r] = true;
  34   }
  35
  36   public void neighbourListASDecisionRule(int Step) {
  37
  38     int CurrentCity = Tour[Step - 1];
  39
  40     double SumProbabilities = 0.0;
  41     double SelectionProbability[] = new double[graph.getNearestNeighboursDepth()];
  42
  43     for (int j = 0; j < graph.getNearestNeighboursDepth(); j++) {
  44
  45       if ( Visited[ graph.getNearestNeighbour(CurrentCity,j) ] ) {
  46         SelectionProbability[j] = 0.0;
  47       } else {
  48         SelectionProbability[j] =
  49           graph.getChoiceInformation( CurrentCity,
  50               graph.getNearestNeighbour(CurrentCity,j) );
  51         SumProbabilities += SelectionProbability[j];
  52       }
  53
  54     }
  55
  56     if (SumProbabilities == 0.0) {
  57       chooseBestNext(Step);
  58     } else {
  59
  60       int j = 0;
  61       double r = Math.random() * SumProbabilities;
  62       double p = SelectionProbability[j];
  63
  64       while (p < r) {
  65         p += SelectionProbability[++j];
  66       }
  67
  68       Tour[Step] = graph.getNearestNeighbour(CurrentCity,j);
  69       Visited[ graph.getNearestNeighbour(CurrentCity,j) ] = true;
  70     }
  71
  72   }
  73
  74   public void chooseBestNext(int Step) {
  75     int nc = 0;
  76     /* this seems to be neccessary because some choice information
  77      * tends to become zero after a while */
  78     double v = -1.0;
  79     int CurrentCity = Tour[Step - 1];
  80
  81     for (int j = 0; j < graph.getNumOfCities(); j++) {
  82       if (! Visited[j]) {
  83         if (graph.getChoiceInformation(CurrentCity,j) > v) {
  84           nc = j;
  85           v = graph.getChoiceInformation(CurrentCity,j);
  86         }
  87       }
  88     }
  89
  90     Tour[Step] = nc;
  91     Visited[nc] = true;
  92   }
  93
  94   public int[] getTour() {
  95     return this.Tour;
  96   }
  97
  98   public int getTour(int Tour) {
  99     return this.Tour[Tour];
 100   }
 101
 102   public int getTourLength() {
 103     return this.TourLength;
 104   }
 105
 106   public void setTourLength(int TourLength) {
 107     this.TourLength = TourLength;
 108   }
 109
 110   public void clearData() {
 111     clearTour();
 112     clearTourLength();
 113     clearMemory();
 114   }
 115
 116   protected void clearTourLength() {
 117     TourLength = 0;
 118   }
 119
 120   protected void clearTour() {
 121     for (int i = 0; i < graph.NumOfCities; i++)
 122       Tour[i] = 0;
 123   }
 124
 125   protected void clearMemory() {
 126     for (int i = 0; i < graph.NumOfCities; i++)
 127       Visited[i] = false;
 128   }
 129
 130   @Override
 131     public String toString() {
 132       StringBuilder result = new StringBuilder();
 133
 134       result.append("Tour with length: " + TourLength + "\n");
 135
 136       for (int t : Tour) {
 137         if (graph.ids[t] != null)
 138           result.append(graph.ids[t] + "\t");
 139         else
 140           result.append(t + "\t");
 141       }
 142       if (graph.ids[0] != null)
 143           result.append(graph.ids[Tour[0]]);
 144         else
 145           result.append(Tour[0]);
 146
 147       return result.toString();
 148     }
 149
 150 }