src/aco/strategy/as/asrank/ASRankPheromoneStrategy.java

   1 package aco.strategy.as.asrank;
   2
   3 import java.util.TreeMap;
   4 import java.util.SortedMap;
   5
   6 import aco.ant.*;
   7 import aco.strategy.*;
   8 import aco.mediator.as.*;
   9 import aco.mediator.as.asrank.*;
  10
  11 public class ASRankPheromoneStrategy
  12   extends PheromoneStrategy {
  13
  14   public ASRankPheromoneStrategy(ASRankMediator acom) {
  15     super((ASMediator)acom);
  16   }
  17
  18   public void pheromoneUpdate(Ant[] ants) {
  19     this.evaporate();
  20
  21     this.applyRankPheromones(ants);
  22     this.enforceGlobalBest();
  23
  24     acom.computeChoiceInformation();
  25   }
  26
  27   protected void applyRankPheromones(Ant[] ants) {
  28     SortedMap<Integer, Ant> antmap = new TreeMap<Integer, Ant>();
  29
  30     int max = 0, slots = 0;
  31     for (Ant ant : ants) {
  32       if (ant.getTourLength() == acom.getGlobalBestTourLength())
  33         continue;
  34       if (slots++ < (int)((ASRankMediator)acom).getW()) {
  35         antmap.put(ant.getTourLength(), ant);
  36       } else if (ant.getTourLength() < antmap.lastKey()) {
  37         for (int i : antmap.keySet()) {
  38           if (i > max)
  39             max = i;
  40         }
  41         antmap.remove(max);
  42         antmap.put(ant.getTourLength(), ant);
  43         max = 0;
  44       }
  45     }
  46
  47     int w = (int)((ASRankMediator)acom).getW();
  48     int r = 1, j = 0, l = 0;
  49     double dt = 0;
  50     for (int i : antmap.keySet()) {
  51       dt = (double)(w - (r++)) * (1.0/(double)antmap.get(i).getTourLength());
  52       for (int n = 0; n < acom.getNumOfCities(); n++) {
  53         j = antmap.get(i).getTour(n);
  54         l = antmap.get(i).getTour(n+1);
  55         acom.setPheromone(j, l, (acom.getPheromone(j, l) + dt) );
  56       }
  57     }
  58   }
  59
  60   protected void enforceGlobalBest() {
  61     /* enforcement of global best route */
  62     int j = 0, l = 0;
  63     for (int i = 0; i < acom.getNumOfCities(); i++) {
  64       j = acom.getGlobalBestTour(i);
  65       l = acom.getGlobalBestTour(i+1);
  66       acom.setPheromone( j, l, (acom.getPheromone(j,l) +
  67             ((ASRankMediator)acom).getW()/(double)acom.getGlobalBestTourLength()) );
  68     }
  69   }
  70
  71   protected void depositPheromone(Ant ant) {
  72     double dt = 1.0/(double)ant.getTourLength();
  73     int j = 0;
  74     int l = 0;
  75     for (int i = 0; i < acom.getNumOfCities(); i++) {
  76       j = ant.getTour(i);
  77       l = ant.getTour(i+1);
  78       /* setPheromone will update j,l and l,j */
  79       acom.setPheromone( j, l, (acom.getPheromone(j,l) + dt) );
  80     }
  81   }
  82
  83   protected void evaporate() {
  84     for (int i = 1; i < acom.getNumOfCities(); i++) {
  85       for (int j = 1; j < acom.getNumOfCities(); j++) {
  86         acom.setPheromone(i, j,
  87             (1.0 - acom.getRoh()) * acom.getPheromone(i, j) );
  88       }
  89     }
  90   }
  91
  92 }