From ee594a0393f4fda550386968aaaed6aade1b5b9f Mon Sep 17 00:00:00 2001 From: Jochen Keil Date: Sun, 27 Jun 2010 07:46:00 +0200 Subject: [PATCH] initial version of a much improved (design-wise) aco framework * Communication between objects is now done over mediator * loose coupling of objects * algorithms are now strategy objects to make them exchangeable * objects for holding the data matrices * access only with setter/getter functions * any other data structure than int arrays possible * sorted code to packages --- aco/AntMain.java | 99 +++++++++ aco/ant/Ant.java | 78 +++++++ aco/environment/Environment.java | 207 ++++++++++++++++++ aco/environment/data/EnvironmentData.java | 53 +++++ aco/graph/ACOGraph.java | 291 +++++++++++++++++++++++++ aco/graph/data/ChoiceInformation.java | 32 +++ aco/graph/data/CoordinateData.java | 28 +++ aco/graph/data/DistanceData.java | 36 +++ aco/graph/data/HeuristicInformation.java | 31 +++ aco/graph/data/NearestNeighbourList.java | 67 ++++++ aco/graph/data/PheromoneData.java | 33 +++ aco/mediator/ACOMediator.java | 174 +++++++++++++++ aco/misc/CoordinatePair.java | 20 ++ aco/misc/EnvironmentShutdownHook.java | 16 ++ aco/parameter/ACOParameter.java | 278 +++++++++++++++++++++++ aco/strategy/ACOStrategy.java | 89 ++++++++ aco/strategy/AntSystemStrategy.java | 14 ++ aco/strategy/ChoiceInformationStrategy.java | 23 ++ aco/strategy/DistanceStrategy.java | 46 ++++ aco/strategy/GraphStrategy.java | 48 ++++ aco/strategy/HeuristicInformationStrategy.java | 24 ++ aco/strategy/PheromoneStrategy.java | 45 ++++ aco/strategy/TauZeroStrategy.java | 19 ++ aco/tsplibreader/TSPLibReader.java | 138 ++++++++++++ 24 files changed, 1889 insertions(+) create mode 100644 aco/AntMain.java create mode 100644 aco/ant/Ant.java create mode 100644 aco/environment/Environment.java create mode 100644 aco/environment/data/EnvironmentData.java create mode 100644 aco/graph/ACOGraph.java create mode 100644 aco/graph/data/ChoiceInformation.java create mode 100644 aco/graph/data/CoordinateData.java create mode 100644 aco/graph/data/DistanceData.java create mode 100644 aco/graph/data/HeuristicInformation.java create mode 100644 aco/graph/data/NearestNeighbourList.java create mode 100644 aco/graph/data/PheromoneData.java create mode 100644 aco/mediator/ACOMediator.java create mode 100644 aco/misc/CoordinatePair.java create mode 100644 aco/misc/EnvironmentShutdownHook.java create mode 100644 aco/parameter/ACOParameter.java create mode 100644 aco/strategy/ACOStrategy.java create mode 100644 aco/strategy/AntSystemStrategy.java create mode 100644 aco/strategy/ChoiceInformationStrategy.java create mode 100644 aco/strategy/DistanceStrategy.java create mode 100644 aco/strategy/GraphStrategy.java create mode 100644 aco/strategy/HeuristicInformationStrategy.java create mode 100644 aco/strategy/PheromoneStrategy.java create mode 100644 aco/strategy/TauZeroStrategy.java create mode 100644 aco/tsplibreader/TSPLibReader.java diff --git a/aco/AntMain.java b/aco/AntMain.java new file mode 100644 index 0000000..c0d54c2 --- /dev/null +++ b/aco/AntMain.java @@ -0,0 +1,99 @@ +package aco; + +import java.io.IOException; + +import aco.graph.*; +import aco.graph.data.*; +import aco.strategy.*; +import aco.mediator.*; +import aco.parameter.*; +import aco.environment.*; +import aco.tsplibreader.*; + +public class AntMain { + + public static void main(String[] args) { + + ACOParameter acop = new ACOParameter(); + ACOMediator acom = new ACOMediator(acop); + + acop.setACOStrategy(new AntSystemStrategy(acom)); + acop.setGraphStrategy(new GraphStrategy(acom)); + acop.setTauZeroStrategy(new TauZeroStrategy(acom)); + acop.setDistanceStrategy(new DistanceStrategy(acom)); + acop.setPheromoneStrategy(new PheromoneStrategy(acom)); + acop.setChoiceInformationStrategy(new ChoiceInformationStrategy(acom)); + acop.setHeuristicInformationStrategy(new HeuristicInformationStrategy(acom)); + + try { + TSPLibReader tsplr = new TSPLibReader(args[1]); + CoordinateData coordinates = new CoordinateData(tsplr); + + ACOGraph acog = new ACOGraph(acom); + acom.setACOGraph(acog); + + acog.initializeFromCoordinates(coordinates); + + acop.setAlpha(1.0); + acop.setBeta(2.0); + acop.setRoh(0.1); + acop.setNumOfAnts(acom.getNumOfCities()); + + acop.setMaxNumOfTours(Integer.parseInt(args[0])); + + System.out.println(acop); + + Environment env = new Environment(acom); + + env.run(); + + /* + try { + + ACOGraph acoGraph; + Environment env; + int iterations = 0, guisize = 0; + + try { + iterations = Integer.parseInt(args[0]); + } catch (Exception e) { + System.exit(1); + } + + if (args.length == 2) { + try { + guisize = Integer.parseInt(args[1]); + } catch (Exception e) { } + + if (guisize == 0) { + graph = new Graph(args[1]); + } else { + graph = Graph.sampleGraph(); + } + env = new Environment(iterations, graph); + + env.run(); + } else if (args.length == 3) { + + guisize = Integer.parseInt(args[1]); + graph = new Graph(args[2]); + env = new Environment(iterations, guisize, graph); + + env.run(); + } else { + System.exit(1); + } + */ + + System.out.print("Computation finished.."); + /* wait for a keypress before exit */ + System.in.read(); + + } catch (IOException e) { + System.out.println(e.toString() + "(" + e.getClass() + "): " + e); + } + + System.exit(0); + } + +} diff --git a/aco/ant/Ant.java b/aco/ant/Ant.java new file mode 100644 index 0000000..e9f0f91 --- /dev/null +++ b/aco/ant/Ant.java @@ -0,0 +1,78 @@ +package aco.ant; + +import aco.mediator.*; + +public class Ant { + + protected ACOMediator acom; + + public int TourLength; // the ant's tour length + public int[] Tour; // N+1; ant's memory storing (partial) tours + public boolean[] Visited; // N; visited cities + + public Ant(ACOMediator acom) { + this.acom = acom; + + Tour = new int[acom.getNumOfCities()]; + Visited = new boolean[acom.getNumOfCities()]; + + this.reset(); + } + + public int getTour(int i) { + return this.Tour[i]; + } + + public void setTour(int i, int c) { + this.Tour[i] = c; + } + + public boolean getVisited(int i) { + return Visited[i]; + } + + public void setVisited(int i, boolean b) { + Visited[i] = b; + } + + public int getTourLength() { + return this.TourLength; + } + + public void setTourLength(int i) { + this.TourLength = i; + } + + public void reset() { + TourLength = 0; + + for (int i = 0; i < acom.getNumOfCities(); i++) + setTour(i, 0); + + for (int i = 0; i < acom.getNumOfCities(); i++) + setVisited(i, false); + } + + /* + @Override + public String toString() { + StringBuilder result = new StringBuilder(); + + result.append("Tour with length: " + TourLength + "\n"); + + for (int t : Tour) { + if (graph.ids[t] != null) + result.append(graph.ids[t] + "\t"); + else + result.append(t + "\t"); + } + if (graph.ids[0] != null) + result.append(graph.ids[getTour(0)]); + else + result.append(Tour[0]); + + return result.toString(); + } + */ + +} diff --git a/aco/environment/Environment.java b/aco/environment/Environment.java new file mode 100644 index 0000000..91c114e --- /dev/null +++ b/aco/environment/Environment.java @@ -0,0 +1,207 @@ +package aco.environment; + +import java.lang.Runtime; +import java.util.Observable; + +import aco.ant.*; +import aco.misc.*; +import aco.mediator.*; +import aco.environment.data.*; + +public class Environment + extends Observable { + + protected Ant[] ants; + protected ACOMediator acom; + protected EnvironmentData ed; + //protected AntView av; + + public Environment(ACOMediator acom) { + this.acom = acom; + + this.ants = new Ant[acom.getNumOfAnts()]; + + for (int i = 0; i < acom.getNumOfAnts(); i++) + ants[i] = new Ant(acom); + + this.ed = new EnvironmentData(acom); + + /* add a shutdown hook to print out the last best solution */ + Runtime.getRuntime().addShutdownHook( + new EnvironmentShutdownHook(this)); + + /* run the garbage collector after all the initialization is done */ + System.gc(); + + /* + if (graph.hasCoordinates()) { + if (GuiSize == 0) + av = new AntView(this); + else + av = new AntView(GuiSize, this); + this.addObserver(av); + new Thread(av).start(); + } + */ + + } + + /* d'tor */ + protected void finalize() { + deleteObservers(); + } + + public void run() { + int i = 0; + while (! terminateCondition(i++)) { + constructSolutions(); + acom.pheromoneUpdate(ants); + updateStatistics(i); + /* localSearch(); + * updatePheromoneTrails(); */ + } + } + + protected void constructSolutions() { + + /* clear ants memory and .. + * assign an initial random city to ant */ + /* TODO: threading */ + for (Ant ant : ants) { + ant.reset(); + acom.pickInitialRandomCity(ant); + //ant.pickInitialRandomCity(); + } + + /* let each ant construct a complete tour + * start a 1 since every ant already has an initial city */ + /* TODO: threading */ + for (int step = 1; step < acom.getNumOfCities(); step++) { + for (Ant ant : ants) + acom.neighbourListASDecisionRule(ant, step); + } + + /* compute tour length of each ant */ + /* TODO: threading */ + for (Ant ant : ants) { + acom.computeTourLength(ant); + } + + + } + + protected void updateStatistics(int iteration) { + for (Ant ant : ants) { + + if (ant.getTourLength() < ed.getMinTourLength()) { + ed.setMinTourLength(ant.getTourLength()); + ed.setMinTourIteration(iteration); + + for (int i = 0; i < acom.getNumOfCities(); i++) { + ed.setMinTour(i, ant.getTour(i)); + } + + /* + if (acom.hasCoordinates()) { + this.setChanged(); + this.notifyObservers(this); + } + */ + } + + } + /* since we are already at it.. run the garbage collector */ + System.gc(); + } + + /* + protected boolean stagnationBehaviour() { + for (Ant antOne : ants) { + for (Ant antTwo : ants) { + for (int i : antOne.getTour()) { + for (int j : antTwo.getTour()) { + if (i != j) + return false; + } + } + } + } + return true; + } + */ + + protected boolean terminateCondition(int iteration) { + /* 1) solution within predefined distance + * 2) max number of tour constructions or algorithm iterations + * 3) max cpu time + * 4) algorithm stagnation behaviour */ + if (iteration >= acom.getMaxNumOfTours()) { + return true; + //} else if (stagnationBehaviour()) { + //return true; + } else { + return false; + } + } + + @Override + public String toString() { + StringBuilder result = new StringBuilder(); + result.append("Shortest tour at iteration " + + ed.getMinTourIteration() + + " with length " + + ed.getMinTourLength() + + "\n"); + + for (int t : ed.getMinTour()) { + //if (graph.getIds(t) != null) + //result.append(graph.ids[t] + "\t"); + //else + result.append(t + "\t"); + } + //if (graph.getIds(0) != null) + //result.append(graph.ids[MinTour[0]]); + //else + result.append(ed.getMinTour(0)); + return result.toString(); + } + + /* TODO */ + /* + public Vector getBestTours() { + } + */ + + public int[] getMinTour() { + return ed.getMinTour(); + } + + public int getMinTour(int index) { + return ed.getMinTour(index); + } + + public void setMinTour(int[] MinTour) { + ed.setMinTour(MinTour); + } + + public void setMinTour(int index, int MinTour) { + ed.setMinTour(index, MinTour); + } + + public int getMinTourLength() { + return ed.getMinTourLength(); + } + + public void setMinTourLength(int MinTourLength) { + ed.setMinTourLength(MinTourLength); + } + + public int getMinTourIteration() { + return ed.getMinTourIteration(); + } + + public void setMinTourIteration(int MinTourIteration) { + ed.setMinTourIteration(MinTourIteration); + } + +} diff --git a/aco/environment/data/EnvironmentData.java b/aco/environment/data/EnvironmentData.java new file mode 100644 index 0000000..9d77cd0 --- /dev/null +++ b/aco/environment/data/EnvironmentData.java @@ -0,0 +1,53 @@ +package aco.environment.data; + +import aco.mediator.*; + +public class EnvironmentData { + + protected ACOMediator acom; + + protected int[] MinTour; + protected int MinTourLength; + protected int MinTourIteration; + + public EnvironmentData(ACOMediator acom) { + this.acom = acom; + + this.MinTour = new int[acom.getNumOfCities()]; + this.MinTourLength = acom.getInfinity(); + this.MinTourIteration = 0; + } + + public int[] getMinTour() { + return this.MinTour; + } + + public int getMinTour(int index) { + return this.MinTour[index]; + } + + public void setMinTour(int[] MinTour) { + this.MinTour = MinTour; + } + + public void setMinTour(int index, int MinTour) { + this.MinTour[index] = MinTour; + } + + public int getMinTourLength() { + return this.MinTourLength; + } + + public void setMinTourLength(int MinTourLength) { + this.MinTourLength = MinTourLength; + } + + public int getMinTourIteration() { + return this.MinTourIteration; + } + + public void setMinTourIteration(int MinTourIteration) { + this.MinTourIteration = MinTourIteration; + } + +} diff --git a/aco/graph/ACOGraph.java b/aco/graph/ACOGraph.java new file mode 100644 index 0000000..df8f4d5 --- /dev/null +++ b/aco/graph/ACOGraph.java @@ -0,0 +1,291 @@ +package aco.graph; + +import java.util.HashMap; + +import aco.misc.*; +import aco.strategy.*; +import aco.mediator.*; +import aco.graph.data.*; + +public class ACOGraph { + + protected ACOMediator acom; + + protected CoordinateData coordinateData; + protected DistanceData distanceData; + protected PheromoneData pheromoneData; + protected ChoiceInformation choiceInformation; + protected HeuristicInformation heuristicInformation; + protected NearestNeighbourList nearestNeighbourList; + + public ACOGraph(ACOMediator acom) { + this.acom = acom; + + this.coordinateData = null; + this.distanceData = null; + this.pheromoneData = null; + this.choiceInformation = null; + this.heuristicInformation = null; + this.nearestNeighbourList = null; + } + + /* + public ACOGraph(ACOMediator acom) { + this.coordinateData = null; + this.distanceData = new DistanceData(acom); + this.pheromoneData = new PheromoneData(acom); + this.choiceInformation = new ChoiceInformation(acom); + this.heuristicInformation = new HeuristicInformation(acom); + this.nearestNeighbourList = new NearestNeighbourList(acom); + } + */ + + public ACOGraph(ACOMediator acom, CoordinateData coordinateData) { + this.acom = acom; + + acom.setACOGraph(this); + + initializeFromCoordinates(coordinateData); + } + + public void initializeFromCoordinates(CoordinateData coordinateData) { + this.coordinateData = coordinateData; + + acom.setNumOfCities(coordinateData.getNumOfCities()); + acom.computeNearestNeighbourListDepth(); + + this.distanceData = new DistanceData(acom.computeDistances()); + this.pheromoneData = new PheromoneData(acom); + this.choiceInformation = new ChoiceInformation(acom); + this.heuristicInformation = new HeuristicInformation(acom); + this.nearestNeighbourList = new NearestNeighbourList(acom); + + acom.computeTauZero(); + acom.computeChoiceInformation(); + acom.computeHeuristicInformation(); + nearestNeighbourList.computeNearestNeighbours(); + } + + public int getNearestNeighbour(int x, int y) { + return nearestNeighbourList.getNearestNeighbour(x, y); + } + + public int getDistance(int x, int y) { + return distanceData.getDistance(x, y); + } + + public void setDistance(int x, int y, int v) { + distanceData.setDistance(x, y, v); + } + + public CoordinatePair getCoordinates(int City) { + return coordinateData.getCoordinates(City); + } + + public HashMap> getCoordinateData() { + return coordinateData.getCoordinateData(); + } + + public double getPheromone(int x, int y) { + return pheromoneData.getPheromone(x, y); + } + + public void setPheromone(int x, int y, double v) { + pheromoneData.setPheromone(x, y, v); + } + + public double getChoiceInformation(int x, int y) { + return choiceInformation.getChoiceInformation(x, y); + } + + public void setChoiceInformation(int x, int y, double v) { + choiceInformation.setChoiceInformation(x, y, v); + } + + public double getHeuristicInformation(int x, int y) { + return heuristicInformation.getHeuristicInformation(x, y); + } + + public void setHeuristicInformation(int x, int y, double v) { + heuristicInformation.setHeuristicInformation(x, y, v); + } + +} + + /* + Graph() { + this.distanceData = null; + this.coordinateData = null; + this.pheromoneData = null; + this.choiceInformation = null; + this.heuristicInformation = null; + this.nearestNeighbourList = null; + } + + Graph(GraphParameter gp, String filename) throws IOException { + this.gp = gp; + + TSPLibReader tsplibreader = new TSPLibReader(filename); + this.coordinate = new Coordinate(this, tsplibreader); + + this.distance = new Distance(this, coordinate.computeDistances()); + this.pheromone = new Pheromone(this); + this.nearestneighbour = new NearestNeighbour(this); + this.choiceinformation = new ChoiceInformation(this); + + computeNearestNeighbours(); + computeChoiceInformation(); + } + + public Boolean hasCoordinates() { + return coordinate != null; + } + + public Boolean hasIds() { + return ids != null; + } + + public int getNumOfCities() { + return gp.getNumOfCities(); + } + + public int getNearestNeighboursDepth() { + return gp.getNearestNeighboursDepth(); + } + + public int getDistance(int x, int y) { + return this.distance.getDistance(x, y); + } + + public Coordinate getCoordinate() { + return this.coordinate; + } + + public double getPheromone(int x, int y) { + return this.pheromone.getPheromone(x, y); + } + + public int getNearestNeighbour(int x, int y) { + return this.nearestneighbour.getNearestNeighbour(x, y); + } + + public double getChoiceInformation(int x, int y) { + return this.choiceinformation.getChoiceInformation(x, y); + } + + public String[] getIds() { + return this.ids; + } + + public String getIds(int index) { + if (this.ids != null) { + return this.ids[index]; + } else { + return null; + } + } + + public void setIds(String[] ids) { + this.ids = ids; + } + + public void setIds(int index, String ids) { + this.ids[index] = ids; + } + + protected void setDistance(int x, int y, int Distance) { + this.distance.setDistance(x,y, Distance); + } + + protected void setDistance(int[][] Distance) { + this.distance.setDistance(Distance); + } + + protected void mirrorDistances() { + for (int i = 0; i < gp.getNumOfCities(); i++) { + for (int j = 0; j < gp.getNumOfCities(); j++) { + if (distance.getDistance(i,j) != gp.getInfinity()) { + distance.setDistance(j,i, distance.getDistance(i,j)); + } else { + distance.setDistance(i,j, distance.getDistance(j,i)); + } + } + } + } + + protected void printNearestNeighbours() { + for (int c = 0; c < getNumOfCities(); c++) { + if (getIds(c) != null) { + System.out.println("Nearest neighbours of: " + getIds(c)); + } else { + System.out.println("Nearest neighbours of: " + c); + } + for (int n = 0; n < getNearestNeighboursDepth(); n++) { + if (nearestneighbour.getNearestNeighbour(c,n) != -1) { + if ( getIds( nearestneighbour.getNearestNeighbour(c,n) ) != null ) { + System.out.print( + getIds( nearestneighbour.getNearestNeighbour(c,n) ) + "\t"); + } else { + System.out.print(nearestneighbour.getNearestNeighbour(c,n) + "\t"); + } + } else { + System.out.print("none" + "\t"); + } + } + System.out.println(); + } + } + + @Override + public String toString() { + StringBuilder result = new StringBuilder(); + + if (getIds() != null) { + for (String id : getIds()) + result.append("\t" + id); + } else { + for (int i = 0; i < gp.getNumOfCities(); i++) + result.append("\t" + i); + } + + int l = 0; + for (int i[] : distance.getDistance()) { + if (ids != null) { + if (ids[l] != null) { + result.append("\n" + ids[l++] + "\t"); + } else { + result.append("\n" + (l++) + "\t"); + } + } else { + result.append("\n" + (l++) + "\t"); + } + + for (int j : i) { + if (j == gp.getInfinity()) { + result.append("INF\t"); + } else { + result.append(j + "\t"); + } + } + } + + return result.toString(); + } + + public static void main (String[] args) { + try { + Graph graph; + if (args.length == 1) + graph = new Graph(args[0]); + else + graph = Graph.sampleGraph(); + System.out.println(graph); + graph.printNearestNeighbours(); + } catch (Exception e) { + System.out.println(e.toString() + "(" + e.getClass() + "): " + e); + System.exit(1); + } + } + +} +*/ diff --git a/aco/graph/data/ChoiceInformation.java b/aco/graph/data/ChoiceInformation.java new file mode 100644 index 0000000..f7d6269 --- /dev/null +++ b/aco/graph/data/ChoiceInformation.java @@ -0,0 +1,32 @@ +package aco.graph.data; + +import aco.mediator.*; + +public class ChoiceInformation { + + protected double[][] choiceInformation; + + protected ACOMediator acom; + + public ChoiceInformation(ACOMediator acom) { + this.acom = acom; + + this.choiceInformation = new double[acom.getNumOfCities()][acom.getNumOfCities()]; + + for (int i = 0; i < acom.getNumOfCities(); i++) { + for (int j = 0; j < acom.getNumOfCities(); j++) { + setChoiceInformation(i,j, 0); + } + } + } + + public double getChoiceInformation(int x, int y) { + return this.choiceInformation[x][y]; + } + + public void setChoiceInformation(int x, int y, double choiceInformation) { + this.choiceInformation[x][y] = choiceInformation; + this.choiceInformation[y][x] = choiceInformation; + } + +} diff --git a/aco/graph/data/CoordinateData.java b/aco/graph/data/CoordinateData.java new file mode 100644 index 0000000..ec141d3 --- /dev/null +++ b/aco/graph/data/CoordinateData.java @@ -0,0 +1,28 @@ +package aco.graph.data; + +import aco.misc.*; +import aco.tsplibreader.*; + +import java.util.HashMap; + +public class CoordinateData { + + protected final HashMap> coordinateData; + + public CoordinateData(TSPLibReader tsplibreader) { + this.coordinateData = tsplibreader.getCoordinates(); + } + + public CoordinatePair getCoordinates(int City) { + return coordinateData.get(City); + } + + public HashMap> getCoordinateData() { + return coordinateData; + } + + public int getNumOfCities() { + return coordinateData.size(); + } + +} diff --git a/aco/graph/data/DistanceData.java b/aco/graph/data/DistanceData.java new file mode 100644 index 0000000..3638519 --- /dev/null +++ b/aco/graph/data/DistanceData.java @@ -0,0 +1,36 @@ +package aco.graph.data; + +import aco.mediator.*; + +public class DistanceData { + + protected int[][] distanceData; + + protected ACOMediator acom; + + public DistanceData(ACOMediator acom) { + this.acom = acom; + + this.distanceData = new int[acom.getNumOfCities()][acom.getNumOfCities()]; + + for (int i = 0; i < acom.getNumOfCities(); i++) { + for (int j = 0; j < acom.getNumOfCities(); j++) { + setDistance(i,j, acom.getInfinity()); + } + } + } + + public DistanceData(int[][] distanceData) { + this.distanceData = distanceData; + } + + public int getDistance(int x, int y) { + return this.distanceData[x][y]; + } + + public void setDistance(int x, int y, int distance) { + this.distanceData[x][y] = distance; + this.distanceData[y][x] = distance; + } + +} diff --git a/aco/graph/data/HeuristicInformation.java b/aco/graph/data/HeuristicInformation.java new file mode 100644 index 0000000..3e04215 --- /dev/null +++ b/aco/graph/data/HeuristicInformation.java @@ -0,0 +1,31 @@ +package aco.graph.data; + +import aco.mediator.*; + +public class HeuristicInformation { + + protected double[][] heuristicInformation; + + protected ACOMediator acom; + + public HeuristicInformation(ACOMediator acom) { + this.acom = acom; + + this.heuristicInformation = new double[acom.getNumOfCities()][acom.getNumOfCities()]; + for (int i = 0; i < acom.getNumOfCities(); i++) { + for (int j = 0; j < acom.getNumOfCities(); j++) { + setHeuristicInformation(i,j, 0); + } + } + } + + public double getHeuristicInformation(int x, int y) { + return this.heuristicInformation[x][y]; + } + + public void setHeuristicInformation(int x, int y, double heuristicInformation) { + this.heuristicInformation[x][y] = heuristicInformation; + this.heuristicInformation[y][x] = heuristicInformation; + } + +} diff --git a/aco/graph/data/NearestNeighbourList.java b/aco/graph/data/NearestNeighbourList.java new file mode 100644 index 0000000..46cb29c --- /dev/null +++ b/aco/graph/data/NearestNeighbourList.java @@ -0,0 +1,67 @@ +package aco.graph.data; + +import aco.mediator.*; + +public class NearestNeighbourList { + + protected int[][] nearestNeighbourList; + + protected ACOMediator acom; + + public NearestNeighbourList(ACOMediator acom) { + this.acom = acom; + + this.nearestNeighbourList = + new int[acom.getNumOfCities()][acom.getNearestNeighbourListDepth()]; + + for (int i = 0; i < acom.getNumOfCities(); i++) { + for (int j = 0; j < acom.getNearestNeighbourListDepth(); j++) { + setNearestNeighbour(i, j, -1); + } + } + } + + public void computeNearestNeighbours() { + for (int City = 0; City < acom.getNumOfCities(); City++) { + for (int Neighbour = 0; Neighbour < acom.getNumOfCities(); Neighbour++) { + + if (City == Neighbour) { + continue; + } else { + + for (int d = 0; d < acom.getNearestNeighbourListDepth(); d++) { + + /* if there is no entry yet, then assign */ + if (getNearestNeighbour(City,d) == -1) { + setNearestNeighbour(City,d, Neighbour); + break; + } + /* if distance from city to neighbour is smaller + * than distance from city to neighbour from list */ + if (acom.getDistance(City,Neighbour) < + acom.getDistance(City, getNearestNeighbour(City,d))) { + + /* copy element n-1 to n; right shift so to say; until elem d is reached */ + for (int c = acom.getNearestNeighbourListDepth() - 1; c > d; c--) { + setNearestNeighbour(City,c, getNearestNeighbour(City,c-1)); + } + setNearestNeighbour(City,d, Neighbour); + break; + + } + + } + } + } + } + } + + public int getNearestNeighbour(int x, int y) { + return this.nearestNeighbourList[x][y]; + } + + public void setNearestNeighbour(int x, int y, int nearestNeighbour) { + this.nearestNeighbourList[x][y] = nearestNeighbour; + } + +} diff --git a/aco/graph/data/PheromoneData.java b/aco/graph/data/PheromoneData.java new file mode 100644 index 0000000..a2efcf1 --- /dev/null +++ b/aco/graph/data/PheromoneData.java @@ -0,0 +1,33 @@ +package aco.graph.data; + +import aco.mediator.*; + +public class PheromoneData { + + protected double[][] pheromoneData; + + protected ACOMediator acom; + + public PheromoneData(ACOMediator acom) { + this.acom = acom; + + this.pheromoneData = new double[acom.getNumOfCities()][acom.getNumOfCities()]; + + for (int i = 0; i < acom.getNumOfCities(); i++) { + for (int j = 0; j < acom.getNumOfCities(); j++) { + setPheromone(i,j, acom.getTauZero() ); + } + } + + } + + public double getPheromone(int x, int y) { + return this.pheromoneData[x][y]; + } + + public void setPheromone(int x, int y, double pheromone) { + this.pheromoneData[x][y] = pheromone; + this.pheromoneData[y][x] = pheromone; + } + +} diff --git a/aco/mediator/ACOMediator.java b/aco/mediator/ACOMediator.java new file mode 100644 index 0000000..037025a --- /dev/null +++ b/aco/mediator/ACOMediator.java @@ -0,0 +1,174 @@ +package aco.mediator; + +import java.util.HashMap; + +import aco.ant.*; +import aco.misc.*; +import aco.graph.*; +import aco.parameter.*; + +public class ACOMediator { + + protected ACOGraph acog; + protected ACOParameter acop; + + public ACOMediator() { + this.acog = null; + this.acop = null; + } + + public ACOMediator(ACOParameter acop) { + this.acog = null; + this.acop = acop; + } + + public ACOMediator(ACOGraph acog, ACOParameter acop) { + this.acog = acog; + this.acop = acop; + } + + public void setACOGraph(ACOGraph acog) { + this.acog = acog; + } + + public void setACOParameter(ACOParameter acop) { + this.acop = acop; + } + + public int getInfinity() { + return acop.getInfinity(); + } + + public double getAlpha() { + return acop.getAlpha(); + } + + public double getBeta() { + return acop.getBeta(); + } + + public double getRoh() { + return acop.getRoh(); + } + + public double getTauZero() { + return acop.getTauZero(); + } + + public void setTauZero(double v) { + acop.setTauZero(v); + } + + public int getMaxNumOfTours() { + return acop.getMaxNumOfTours(); + } + + public void setMaxNumOfTours(int v) { + acop.setMaxNumOfTours(v); + } + + public int getNumOfAnts() { + return acop.getNumOfAnts(); + } + + public void setNumOfAnts(int v) { + acop.setNumOfAnts(v); + } + + public int getNumOfCities() { + return acop.getNumOfCities(); + } + + public void setNumOfCities(int v) { + acop.setNumOfCities(v); + } + + public int getNearestNeighbourListDepth() { + return acop.getNearestNeighbourListDepth(); + } + + public int getNearestNeighbour(int x, int y) { + return acog.getNearestNeighbour(x, y); + } + + public int getDistance(int x, int y) { + return acog.getDistance(x, y); + } + + public void setDistance(int x, int y, int v) { + acog.setDistance(x, y, v); + } + + public CoordinatePair getCoordinates(int City) { + return acog.getCoordinates(City); + } + + public HashMap> getCoordinateData() { + return acog.getCoordinateData(); + } + + public double getPheromone(int x, int y) { + return acog.getPheromone(x, y); + } + + public void setPheromone(int x, int y, double v) { + acog.setPheromone(x, y, v); + } + + public double getChoiceInformation(int x, int y) { + return acog.getChoiceInformation(x, y); + } + + public void setChoiceInformation(int x, int y, double v) { + acog.setChoiceInformation(x, y, v); + } + + public double getHeuristicInformation(int x, int y) { + return acog.getHeuristicInformation(x, y); + } + + public void setHeuristicInformation(int x, int y, double v) { + acog.setHeuristicInformation(x, y, v); + } + + public void computeTauZero() { + acop.getTauZeroStrategy().computeTauZero(); + } + + public void computeChoiceInformation() { + acop.getChoiceInformationStrategy().computeChoiceInformation(); + } + + public void computeHeuristicInformation() { + acop.getHeuristicInformationStrategy().computeHeuristicInformation(); + } + + public void computeNearestNeighbourListDepth() { + acop.computeNearestNeighbourListDepth(); + } + + public int[][] computeDistances() { + return acop.getDistanceStrategy().computeDistances(); + } + + public int nearestNeighbourHeuristicRandomStart() { + return acop.getGraphStrategy().nearestNeighbourHeuristicRandomStart(); + } + + public void pheromoneUpdate(Ant[] ants) { + acop.getPheromoneStrategy().pheromoneUpdate(ants); + } + + public void computeTourLength(Ant ant) { + acop.getACOStrategy().computeTourLength(ant); + } + + public void pickInitialRandomCity(Ant ant) { + acop.getACOStrategy().pickInitialRandomCity(ant); + } + + public void neighbourListASDecisionRule(Ant ant, int Step) { + acop.getACOStrategy().neighbourListASDecisionRule(ant, Step); + } + +} diff --git a/aco/misc/CoordinatePair.java b/aco/misc/CoordinatePair.java new file mode 100644 index 0000000..9b92f3d --- /dev/null +++ b/aco/misc/CoordinatePair.java @@ -0,0 +1,20 @@ +package aco.misc; + +public class CoordinatePair { + private final F first; + private final S second; + + public CoordinatePair(F first, S second) { + this.first = first; + this.second = second; + } + + public F getFirst() { + return this.first; + } + + public S getSecond() { + return this.second; + } + +} diff --git a/aco/misc/EnvironmentShutdownHook.java b/aco/misc/EnvironmentShutdownHook.java new file mode 100644 index 0000000..f47d49e --- /dev/null +++ b/aco/misc/EnvironmentShutdownHook.java @@ -0,0 +1,16 @@ +package aco.misc; + +import aco.environment.*; + +public class EnvironmentShutdownHook extends Thread { + + protected Environment env; + + public EnvironmentShutdownHook(Environment env) { + this.env = env; + } + + public void run() { + System.out.println(env); + } +} diff --git a/aco/parameter/ACOParameter.java b/aco/parameter/ACOParameter.java new file mode 100644 index 0000000..5308f00 --- /dev/null +++ b/aco/parameter/ACOParameter.java @@ -0,0 +1,278 @@ +package aco.parameter; + +import aco.strategy.*; + +public class ACOParameter { + + protected final int Infinity = Integer.MAX_VALUE; + protected double Alpha; + protected double Beta; + protected double Roh; + protected double TauZero; + + protected int NumOfAnts; + protected int NumOfCities; + protected int MaxNumOfTours; + protected int NearestNeighbourListDepth; + + protected ACOStrategy acos; + protected GraphStrategy gs; + protected TauZeroStrategy tzs; + protected DistanceStrategy ds; + protected PheromoneStrategy ps; + protected ChoiceInformationStrategy cis; + protected HeuristicInformationStrategy his; + + public ACOParameter() { + this.Alpha = 0.0; + this.Beta = 0.0; + this.Roh = 0.0; + this.TauZero = 0.0; + + this.NumOfCities = 0; + this.NumOfAnts = 0; + this.MaxNumOfTours = 0; + this.NearestNeighbourListDepth = 0; + + this.acos = null; + this.gs = null; + this.tzs = null; + this.ds = null; + this.ps = null; + this.cis = null; + this.his = null; + } + + public ACOParameter(int NumOfCities) { + this.Alpha = 1.0; + this.Beta = 5.0; + this.Roh = 0.5; + this.TauZero = 0.0001; + + this.NumOfCities = NumOfCities; + this.NumOfAnts = NumOfCities; + this.MaxNumOfTours = 0; + + this.computeNearestNeighbourListDepth(); + + this.acos = null; + this.gs = null; + this.tzs = null; + this.ds = null; + this.ps = null; + this.cis = null; + this.his = null; + } + + public ACOParameter( + int NumOfCities, + ACOStrategy acos, + GraphStrategy gs, + TauZeroStrategy tzs, + DistanceStrategy ds, + PheromoneStrategy ps, + ChoiceInformationStrategy cis, + HeuristicInformationStrategy his) { + + this(1.0, 5.0, 0.5, 0.0001, + NumOfCities, NumOfCities, NumOfCities, + acos, gs, tzs, ds, ps, cis, his); + + this.computeNearestNeighbourListDepth(); + + } + + public ACOParameter( + int NumOfAnts, int NumOfCities, int NearestNeighbourListDepth, + ACOStrategy acos, + GraphStrategy gs, + TauZeroStrategy tzs, + DistanceStrategy ds, + PheromoneStrategy ps, + ChoiceInformationStrategy cis, + HeuristicInformationStrategy his) { + + this(1.0, 5.0, 0.5, 0.0001, + NumOfAnts, NumOfCities, NearestNeighbourListDepth, + acos, gs, tzs, ds, ps, cis, his); + } + + public ACOParameter( + double Alpha, double Beta, double Roh, double TauZero, + int NumOfAnts, int NumOfCities, int NearestNeighbourListDepth, + ACOStrategy acos, + GraphStrategy gs, + TauZeroStrategy tzs, + DistanceStrategy ds, + PheromoneStrategy ps, + ChoiceInformationStrategy cis, + HeuristicInformationStrategy his) { + + this.Alpha = Alpha; + this.Beta = Beta; + this.Roh = Roh; + this.TauZero = TauZero; + + this.NumOfAnts = NumOfAnts; + this.NumOfCities = NumOfCities; + this.MaxNumOfTours = 0; + this.NearestNeighbourListDepth = NearestNeighbourListDepth; + + this.acos = acos; + this.gs = gs; + this.tzs = tzs; + this.ds = ds; + this.ps = ps; + this.cis = cis; + this.his = his; + } + + public void computeNearestNeighbourListDepth() { + if (NumOfCities <= 30) + this.NearestNeighbourListDepth = NumOfCities - 1; + else if (NumOfCities > 30 && NumOfCities < 80) + this.NearestNeighbourListDepth = NumOfCities/2; + else + this.NearestNeighbourListDepth = 40; + } + + public int getInfinity() { + return this.Infinity; + } + + public double getAlpha() { + return this.Alpha; + } + + public void setAlpha(double Alpha) { + this.Alpha = Alpha; + } + + public double getBeta() { + return this.Beta; + } + + public void setBeta(double Beta) { + this.Beta = Beta; + } + + public double getRoh() { + return this.Roh; + } + + public void setRoh(double Roh) { + this.Roh = Roh; + } + + public double getTauZero() { + return this.TauZero; + } + + public void setTauZero(double v) { + this.TauZero = v; + } + + public int getNumOfAnts() { + return this.NumOfAnts; + } + + public void setNumOfAnts(int NumOfAnts) { + this.NumOfAnts = NumOfAnts; + } + + public int getNumOfCities() { + return this.NumOfCities; + } + + public void setNumOfCities(int NumOfCities) { + this.NumOfCities = NumOfCities; + } + + public int getMaxNumOfTours() { + return this.MaxNumOfTours; + } + + public void setMaxNumOfTours(int MaxNumOfTours) { + this.MaxNumOfTours = MaxNumOfTours; + } + + public int getNearestNeighbourListDepth() { + return this.NearestNeighbourListDepth; + } + + public void setNearestNeighbourListDepth(int NearestNeighbourListDepth) { + this.NearestNeighbourListDepth = NearestNeighbourListDepth; + } + + public ACOStrategy getACOStrategy() { + return acos; + } + + public GraphStrategy getGraphStrategy() { + return gs; + } + + public TauZeroStrategy getTauZeroStrategy() { + return tzs; + } + + public DistanceStrategy getDistanceStrategy() { + return ds; + } + + public PheromoneStrategy getPheromoneStrategy() { + return ps; + } + + public ChoiceInformationStrategy getChoiceInformationStrategy() { + return cis; + } + + public HeuristicInformationStrategy getHeuristicInformationStrategy() { + return his; + } + + public void setACOStrategy(ACOStrategy acos) { + this.acos = acos; + } + + public void setGraphStrategy(GraphStrategy gs) { + this.gs = gs; + } + + public void setTauZeroStrategy(TauZeroStrategy tzs) { + this.tzs = tzs; + } + + public void setDistanceStrategy(DistanceStrategy ds) { + this.ds = ds; + } + + public void setPheromoneStrategy(PheromoneStrategy ps) { + this.ps = ps; + } + + public void setChoiceInformationStrategy(ChoiceInformationStrategy cis) { + this.cis = cis; + } + + public void setHeuristicInformationStrategy(HeuristicInformationStrategy his) { + this.his = his; + } + + @Override + public String toString() { + StringBuilder result = new StringBuilder(); + result.append("Alpha: " + Alpha + "\n"); + result.append("Beta: " + Beta + "\n"); + result.append("Roh: " + Roh + "\n"); + result.append("TauZero: " + TauZero + "\n"); + result.append("NumOfAnts: " + NumOfAnts + "\n"); + result.append("NumOfCities: " + NumOfCities + "\n"); + result.append("MaxNumOfTours: " + MaxNumOfTours + "\n"); + result.append("NearestNeighbourListDepth: " + NearestNeighbourListDepth + "\n"); + + return result.toString(); + } + +} diff --git a/aco/strategy/ACOStrategy.java b/aco/strategy/ACOStrategy.java new file mode 100644 index 0000000..6e8ff8d --- /dev/null +++ b/aco/strategy/ACOStrategy.java @@ -0,0 +1,89 @@ +package aco.strategy; + +import aco.ant.*; +import aco.mediator.*; + +public abstract class ACOStrategy { + + protected ACOMediator acom; + + public ACOStrategy(ACOMediator acom) { + this.acom = acom; + } + + public void computeTourLength(Ant ant) { + for (int i = 0; i < acom.getNumOfCities() - 1; i++) { + ant.setTourLength( ant.getTourLength() + + acom.getDistance(ant.getTour(i), ant.getTour(i+1))); + } + ant.setTourLength( + ant.getTourLength() + + acom.getDistance( ant.getTour( acom.getNumOfCities() - 1 ), + ant.getTour(0) )); + } + + public void pickInitialRandomCity(Ant ant) { + int r = (int)(Math.random() * acom.getNumOfCities()); + ant.setTour(0, r); + ant.setVisited(r, true); + } + + public void neighbourListASDecisionRule(Ant ant, int Step) { + + int CurrentCity = ant.getTour(Step - 1); + + double SumProbabilities = 0.0; + double SelectionProbability[] = new double[acom.getNearestNeighbourListDepth()]; + + for (int j = 0; j < acom.getNearestNeighbourListDepth(); j++) { + + if ( ant.getVisited( acom.getNearestNeighbour(CurrentCity,j) ) ) { + SelectionProbability[j] = 0.0; + } else { + SelectionProbability[j] = + acom.getChoiceInformation( CurrentCity, + acom.getNearestNeighbour(CurrentCity,j) ); + SumProbabilities += SelectionProbability[j]; + } + + } + + if (SumProbabilities == 0.0) { + chooseBestNext(ant, Step); + } else { + + int j = 0; + double r = Math.random() * SumProbabilities; + double p = SelectionProbability[j]; + + while (p < r) { + p += SelectionProbability[++j]; + } + + ant.setTour(Step, acom.getNearestNeighbour(CurrentCity,j)); + ant.setVisited( acom.getNearestNeighbour(CurrentCity,j), true); + } + + } + + protected void chooseBestNext(Ant ant, int Step) { + int nc = 0; + /* this seems to be neccessary because some choice information + * tends to become zero after a while */ + double v = -1.0; + int CurrentCity = ant.getTour(Step - 1); + + for (int j = 0; j < acom.getNumOfCities(); j++) { + if (! ant.getVisited(j)) { + if (acom.getChoiceInformation(CurrentCity,j) > v) { + nc = j; + v = acom.getChoiceInformation(CurrentCity,j); + } + } + } + + ant.setTour(Step, nc); + ant.setVisited(nc, true); + } + +} diff --git a/aco/strategy/AntSystemStrategy.java b/aco/strategy/AntSystemStrategy.java new file mode 100644 index 0000000..1a009f2 --- /dev/null +++ b/aco/strategy/AntSystemStrategy.java @@ -0,0 +1,14 @@ +package aco.strategy; + +import aco.mediator.*; + +public class AntSystemStrategy + extends ACOStrategy { + + protected ACOMediator acom; + + public AntSystemStrategy(ACOMediator acom) { + super(acom); + } + +} diff --git a/aco/strategy/ChoiceInformationStrategy.java b/aco/strategy/ChoiceInformationStrategy.java new file mode 100644 index 0000000..4e75316 --- /dev/null +++ b/aco/strategy/ChoiceInformationStrategy.java @@ -0,0 +1,23 @@ +package aco.strategy; + +import aco.mediator.*; + +public class ChoiceInformationStrategy { + + protected ACOMediator acom; + + public ChoiceInformationStrategy(ACOMediator acom) { + this.acom = acom; + } + + public void computeChoiceInformation() { + for (int i = 0; i < acom.getNumOfCities(); i++) { + for (int j = 0; j < acom.getNumOfCities(); j++) { + acom.setChoiceInformation(i,j, + Math.pow( acom.getPheromone(i,j), acom.getAlpha() ) * + Math.pow( (1.0/(double)acom.getDistance(i,j)), acom.getBeta() )); + } + } + } + +} diff --git a/aco/strategy/DistanceStrategy.java b/aco/strategy/DistanceStrategy.java new file mode 100644 index 0000000..e8fa294 --- /dev/null +++ b/aco/strategy/DistanceStrategy.java @@ -0,0 +1,46 @@ +package aco.strategy; + +import aco.misc.*; +import aco.mediator.*; + +public class DistanceStrategy { + + protected ACOMediator acom; + + public DistanceStrategy(ACOMediator acom) { + this.acom = acom; + } + + public int[][] computeDistances() { + + int[][] Distance = new int[acom.getNumOfCities()][acom.getNumOfCities()]; + + for (int k1 : acom.getCoordinateData().keySet()) { + for (int k2 : acom.getCoordinateData().keySet()) { + if (k1 == k2) + Distance[k1][k2] = acom.getInfinity(); + else + Distance[k1][k2] = computeDistance(acom.getCoordinates(k1), acom.getCoordinates(k2)); + } + } + + return Distance; + } + + public int computeDistance(CoordinatePair CityOne, + CoordinatePair CityTwo) { + /* pythagoras: a^2 + b^2 = c^2 => c = sqrt( a^2 + b^2 ) */ + return (int)Math.sqrt( + Math.pow((double)(CityOne.getFirst() - CityTwo.getFirst()), 2) + + Math.pow( (double)(CityOne.getSecond() - CityTwo.getSecond()), 2 ) ); + + /* ATT */ + /* + double xd = (double)(CityOne.getFirst() - CityTwo.getFirst()); + double yd = (double)(CityOne.getSecond() - CityTwo.getSecond()); + double rij = Math.sqrt( (xd*xd + yd*yd) / 10.0 ); + return (int)Math.round(rij); + */ + } + +} diff --git a/aco/strategy/GraphStrategy.java b/aco/strategy/GraphStrategy.java new file mode 100644 index 0000000..c5bed5c --- /dev/null +++ b/aco/strategy/GraphStrategy.java @@ -0,0 +1,48 @@ +package aco.strategy; + +import aco.mediator.*; + +public class GraphStrategy { + + protected ACOMediator acom; + + public GraphStrategy(ACOMediator acom) { + this.acom = acom; + } + + public int nearestNeighbourHeuristicRandomStart() { + + boolean[] visited = new boolean[acom.getNumOfCities()]; + + for (int i = 0; i < acom.getNumOfCities(); i++) + visited[i] = false; + + return nearestNeighbourHeuristic( + (int)( Math.random() * acom.getNumOfCities() ), + visited, + acom.getNumOfCities()); + } + + public int nearestNeighbourHeuristic(int city, boolean[] visited, int remaining) { + + int nextmin = acom.getInfinity(); + int nextcity = 0; + + for (int i = 0; i < acom.getNumOfCities(); i++) { + if ( (i != city) && + (! visited[i]) && + (acom.getDistance(i, city) < nextmin) ) { + nextmin = acom.getDistance(i, city); + nextcity = i; + } + } + + visited[nextcity] = true; + + if (remaining == 1) + return nextmin; + else + return nextmin + nearestNeighbourHeuristic(nextcity, visited, remaining - 1); + } + +} diff --git a/aco/strategy/HeuristicInformationStrategy.java b/aco/strategy/HeuristicInformationStrategy.java new file mode 100644 index 0000000..78f9d56 --- /dev/null +++ b/aco/strategy/HeuristicInformationStrategy.java @@ -0,0 +1,24 @@ +package aco.strategy; + +import aco.mediator.*; + +public class HeuristicInformationStrategy { + + protected double[][] heuristicInformation; + + protected ACOMediator acom; + + public HeuristicInformationStrategy(ACOMediator acom) { + this.acom = acom; + } + + public void computeHeuristicInformation() { + for (int i = 0; i < acom.getNumOfCities(); i++) { + for (int j = 0; j < acom.getNumOfCities(); j++) { + acom.setHeuristicInformation(i,j, + (1.0/(double)acom.getDistance(i, j) )); + } + } + } + +} diff --git a/aco/strategy/PheromoneStrategy.java b/aco/strategy/PheromoneStrategy.java new file mode 100644 index 0000000..392fa63 --- /dev/null +++ b/aco/strategy/PheromoneStrategy.java @@ -0,0 +1,45 @@ +package aco.strategy; + +import aco.ant.*; +import aco.mediator.*; + +public class PheromoneStrategy { + + protected ACOMediator acom; + + public PheromoneStrategy(ACOMediator acom) { + this.acom = acom; + } + + public void pheromoneUpdate(Ant[] ants) { + this.evaporate(); + + for (Ant ant : ants) { + this.depositPheromone(ant); + } + + acom.computeChoiceInformation(); + } + + protected void depositPheromone(Ant ant) { + double dt = 1.0/ant.getTourLength(); + int j = 0; + int l = 0; + for (int i = 0; i < acom.getNumOfCities() - 1; i++) { + j = ant.getTour(i); + l = ant.getTour(i+1); + /* setPheromone will update j,l and l,j */ + acom.setPheromone( j, l, (acom.getPheromone(j,l) + dt) ); + } + } + + protected void evaporate() { + for (int i = 1; i < acom.getNumOfCities(); i++) { + for (int j = 1; j < acom.getNumOfCities(); j++) { + acom.setPheromone(i, j, + (1.0 - acom.getRoh()) * acom.getPheromone(i, j) ); + } + } + } + +} diff --git a/aco/strategy/TauZeroStrategy.java b/aco/strategy/TauZeroStrategy.java new file mode 100644 index 0000000..834812b --- /dev/null +++ b/aco/strategy/TauZeroStrategy.java @@ -0,0 +1,19 @@ +package aco.strategy; + +import aco.mediator.*; + +public class TauZeroStrategy { + + protected ACOMediator acom; + + public TauZeroStrategy(ACOMediator acom) { + this.acom = acom; + } + + public void computeTauZero() { + acom.setTauZero( + (double)(acom.getNumOfCities()) / + acom.nearestNeighbourHeuristicRandomStart() ); + } + +} diff --git a/aco/tsplibreader/TSPLibReader.java b/aco/tsplibreader/TSPLibReader.java new file mode 100644 index 0000000..b8e128a --- /dev/null +++ b/aco/tsplibreader/TSPLibReader.java @@ -0,0 +1,138 @@ +package aco.tsplibreader; + +import java.util.HashMap; +import java.io.File; +import java.io.FileReader; +import java.io.IOException; +import java.io.InputStream; +import java.io.BufferedReader; +import java.io.FileInputStream; +import java.io.StreamTokenizer; +import java.io.BufferedInputStream; + +import aco.misc.*; + +public class TSPLibReader { + + final static long serialVersionUID = (long)1.0; + + protected StreamTokenizer streamtokenizer; + protected HashMap> coordinates; + + public TSPLibReader(String filename) throws IOException { + this(new File(filename)); + } + + public TSPLibReader(File file) throws IOException { + coordinates = + new HashMap>(countLines(new FileInputStream(file))); + + streamtokenizer = new StreamTokenizer(new BufferedReader(new FileReader(file))); + streamtokenizer.eolIsSignificant(true); + streamtokenizer.wordChars('_','_'); + } + + public HashMap> getCoordinates() { + try { + this.parseLines(); + } catch (IOException e) { + System.out.println(e.toString() + "(" + e.getClass() + "): " + e); + return null; + } + return coordinates; + } + + public int getNumOfCities() { + return coordinates.size(); + } + + protected void parseLines() throws IOException { + + boolean SeenDisplayDataSection = false; + int i = 0, x = 0, y = 0, City = 0; + + do { + + if (!SeenDisplayDataSection) { + streamtokenizer.nextToken(); + //System.out.println(streamtokenizer); + if (streamtokenizer.ttype == StreamTokenizer.TT_WORD) + if (streamtokenizer.sval.equals("DISPLAY_DATA_SECTION") || + streamtokenizer.sval.equals("NODE_COORD_SECTION")) + SeenDisplayDataSection = true; + + continue; + } + + streamtokenizer.nextToken(); + if (streamtokenizer.ttype == StreamTokenizer.TT_NUMBER) { + i++; + } else { + i = 0; + continue; + } + + streamtokenizer.nextToken(); + if (streamtokenizer.ttype == StreamTokenizer.TT_NUMBER) { + x = (int)streamtokenizer.nval; + i++; + } else { + i = 0; + continue; + } + + streamtokenizer.nextToken(); + if (streamtokenizer.ttype == StreamTokenizer.TT_NUMBER) { + y = (int)streamtokenizer.nval; + i++; + } else { + i = 0; + continue; + } + + streamtokenizer.nextToken(); + if (streamtokenizer.ttype == StreamTokenizer.TT_EOL && i == 3) + coordinates.put(City++, new CoordinatePair(x, y)); + + i = 0; + + } while (streamtokenizer.ttype != StreamTokenizer.TT_EOF); + + } + + protected int countLines(FileInputStream fis) throws IOException { + InputStream is = new BufferedInputStream(fis); + byte[] c = new byte[1024]; + int count = 0; + int readChars = 0; + while ((readChars = is.read(c)) != -1) { + for (int i = 0; i < readChars; ++i) { + if (c[i] == '\n') + ++count; + } + } + return count; + } + + public static void main(String[] args) { + try { + TSPLibReader tlr = new TSPLibReader(args[0]); + + HashMap> coordinates = + tlr.getCoordinates(); + + System.out.println("Entries in HashMap: " + coordinates.size()); + + for (int k : coordinates.keySet()) + System.out.println("City " + k + " with Coordinates " + + coordinates.get(k).getFirst() + + "/" + + coordinates.get(k).getSecond()); + + } catch (IOException e) { + System.out.println(e.toString() + "(" + e.getClass() + "): " + e); + System.exit(1); + } + } + +} -- 2.11.4.GIT