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.NumOfCities];
  16     Visited = new boolean[graph.NumOfCities];
  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 += graph.getDistance(Tour[graph.NumOfCities - 1], Tour[0]);
  27   }
  28
  29   public void pickInitialRandomCity() {
  30     int r = (int)(Math.random() * graph.NumOfCities);
  31     Tour[0] = r;
  32     Visited[r] = true;
  33   }
  34
  35   public void neighbourListASDecisionRule(int Step) {
  36
  37     int CurrentCity = Step - 1;
  38
  39     double SumProbabilities = 0.0;
  40     double SelectionProbability[] = new double[graph.NearestNeighboursDepth];
  41
  42     for (int j = 0; j < graph.NearestNeighboursDepth; j++) {
  43
  44       if ( Visited[ graph.getNearestNeighbour(CurrentCity,j) ] ) {
  45         SelectionProbability[j] = 0.0;
  46       } else {
  47         SelectionProbability[j] =
  48           graph.getChoiceInformation( CurrentCity, graph.getNearestNeighbour(CurrentCity,j) );
  49         SumProbabilities += SelectionProbability[j];
  50       }
  51
  52     }
  53
  54     if (SumProbabilities == 0.0) {
  55       chooseBestNext(Step);
  56     } else {
  57
  58       int j = 0;
  59       double r = Math.random() * SumProbabilities;
  60       double p = SelectionProbability[j];
  61
  62       while (p < r) {
  63         p += SelectionProbability[++j];
  64       }
  65
  66       Tour[Step] = graph.getNearestNeighbour(CurrentCity,j);
  67       Visited[ graph.getNearestNeighbour(CurrentCity,j) ] = true;
  68     }
  69
  70   }
  71
  72   public void chooseBestNext(int Step) {
  73     int nc = 0;
  74     double v = 0.0;
  75     int CurrentCity = Tour[Step - 1];
  76
  77     for (int j = 0; j < graph.NumOfCities; j++) {
  78       if (! Visited[j]) {
  79         if (graph.getChoiceInformation(CurrentCity,j) > v) {
  80           nc = j;
  81           v = graph.getChoiceInformation(CurrentCity,j);
  82         }
  83       }
  84     }
  85
  86     Tour[Step] = nc;
  87     Visited[nc] = true;
  88   }
  89
  90   public int[] getTour() {
  91     return this.Tour;
  92   }
  93
  94   public int getTour(int Tour) {
  95     return this.Tour[Tour];
  96   }
  97
  98   public int getTourLength() {
  99     return this.TourLength;
 100   }
 101
 102   public void setTourLength(int TourLength) {
 103     this.TourLength = TourLength;
 104   }
 105
 106   public void clearData() {
 107     clearTour();
 108     clearTourLength();
 109     clearMemory();
 110   }
 111
 112   protected void clearTourLength() {
 113     TourLength = 0;
 114   }
 115
 116   protected void clearTour() {
 117     for (int i = 0; i < graph.NumOfCities; i++)
 118       Tour[i] = 0;
 119   }
 120
 121   protected void clearMemory() {
 122     for (int i = 0; i < graph.NumOfCities; i++)
 123       Visited[i] = false;
 124   }
 125
 126   @Override
 127     public String toString() {
 128       StringBuilder result = new StringBuilder();
 129
 130       result.append("Tour with length: " + TourLength + "\n");
 131
 132       for (int t : Tour) {
 133         if (graph.ids[t] != null)
 134           result.append(graph.ids[t] + "\t");
 135         else
 136           result.append(t + "\t");
 137       }
 138       if (graph.ids[0] != null)
 139           result.append(graph.ids[Tour[0]]);
 140         else
 141           result.append(Tour[0]);
 142
 143       return result.toString();
 144     }
 145
 146 }