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     double v = 0.0;
  77     int CurrentCity = Tour[Step - 1];
  78
  79     for (int j = 0; j < graph.getNumOfCities(); j++) {
  80       if (! Visited[j]) {
  81         if (graph.getChoiceInformation(CurrentCity,j) > v) {
  82           nc = j;
  83           v = graph.getChoiceInformation(CurrentCity,j);
  84         }
  85       }
  86     }
  87
  88     Tour[Step] = nc;
  89     Visited[nc] = true;
  90   }
  91
  92   public int[] getTour() {
  93     return this.Tour;
  94   }
  95
  96   public int getTour(int Tour) {
  97     return this.Tour[Tour];
  98   }
  99
 100   public int getTourLength() {
 101     return this.TourLength;
 102   }
 103
 104   public void setTourLength(int TourLength) {
 105     this.TourLength = TourLength;
 106   }
 107
 108   public void clearData() {
 109     clearTour();
 110     clearTourLength();
 111     clearMemory();
 112   }
 113
 114   protected void clearTourLength() {
 115     TourLength = 0;
 116   }
 117
 118   protected void clearTour() {
 119     for (int i = 0; i < graph.NumOfCities; i++)
 120       Tour[i] = 0;
 121   }
 122
 123   protected void clearMemory() {
 124     for (int i = 0; i < graph.NumOfCities; i++)
 125       Visited[i] = false;
 126   }
 127
 128   @Override
 129     public String toString() {
 130       StringBuilder result = new StringBuilder();
 131
 132       result.append("Tour with length: " + TourLength + "\n");
 133
 134       for (int t : Tour) {
 135         if (graph.ids[t] != null)
 136           result.append(graph.ids[t] + "\t");
 137         else
 138           result.append(t + "\t");
 139       }
 140       if (graph.ids[0] != null)
 141           result.append(graph.ids[Tour[0]]);
 142         else
 143           result.append(Tour[0]);
 144
 145       return result.toString();
 146     }
 147
 148 }