ACO for finding best paths on a graph.
hello,
i am trying to use aco alg to print shortest path from a specified source node to a destination node. i have created a graph where i have all the vertices (array of strings) and edges(neighbours) stored. I am trying to get the ants to trail randomly on the connected edges from start to dest and then return the route.please can someone give me some advice?.
my code is as follows,...
public class ACOLevel7 {
private static myGraph g = new myGraph();
public static void main(String[] args) {
String start = "";
String finish = "";
ACOLevel7 p = new ACOLevel7(g,start,finish);
}
/* instance variables */
protected String[] names = g.getNames();
protected boolean[] Edges;
private static String istart;
private static String idestination;
private static int iAntSteps = idestination.length();
private static int iColonySize = 10000;
private static double iPheromoneStrength = 1.8d;
private static int iEvaporationSpan = 100;
private static double iEvaporationRate = 0.98d;
private boolean[][] graphEdges;
private Random iRandom = new Random();
/* constructor */
public ACOLevel7(myGraph g, String start, String finish) {
Map map = new Map();
istart = start;
idestination = finish;
graphEdges = g.getEdges();
if(g.validStartAndFinish(istart,idestination)){
double bestScore = -1;
System.out.println("Level 7");
System.out.println(">>> Here is your route planner! <<<");
for (int i = 0; i < iColonySize; i++) {
Ant ant = new Ant();
ant.wander(map, iAntSteps);
double score = calcScore(ant.getTrail());
ant.dropPheromones(score);
if (score > bestScore) {
System.out.println(String.format(" %5d %s %4.2f", (new Object[]
{ new Integer(i), ant.print(), new Double(score) })));
bestScore = score;
}
(map).tick();
}
System.out.println("\n>>> finished <<<");
}
else {
System.out.println("\n>>> start or finish not in names array<<<");
}
}
double calcScore(AntTrail trail) {
double score = 0;
for (int i = 1; i <= iAntSteps; i++);
// Gets the next Node to travel to
I NEED HELP HERE!!
{
}
String String = idestination.substring(i - 1);
return (score / 55d) * iPheromoneStrength;
}
private class Map {
/* instance variables */
HashMap Map = new HashMap();
Location iStart = new Location();
/* constructor */
public Map() {
Map.put(iStart.getKey(), iStart);
}
public Location start() {
return iStart;
}
public ArrayList to(Location fromHere) {
// generate every vertex location that is valid from here
ArrayList newLocations = new ArrayList();
for (int i = 0; i < istart.length(); i++) {
Location n = new Location(fromHere,
String.valueOf(istart.String(i)));
if (!Map.containsKey(n.getKey()))
Map.put(n.getKey(), n); // add to the map
else
n = (Location)Map.get(n.getKey()); // existing location
newLocations.add(n);
}
return newLocations;
}
public void tick() {
Iterator i = Map.entrySet().iterator();
while (i.hasNext())
if (((Location)((java.util.Map.Entry)i.next()).getValue())
.evaporate())
i.remove();
}
}
private class Location {
private String iKey;
private String iname;
private double iPheromones = 1;
private int iEvaporation = iEvaporationSpan;
/* constructor: start location */
public Location() { istartt = ""; }
/* constructor: from another location */
public Location(Location from, String names) {
iKey = from.getKey() + "|" + names;
istartt = names;
public String getKey() {
return iKey;
}
public String getName() {
return istartt;
}
//public String getidestt(){
public void dropPheromones(double d) {
iPheromones += d;
iEvaporation = iEvaporationSpan; // reset the evaporation counter
}
public double getPheromones() {
return iPheromones;
}
public boolean evaporate() {
iPheromones = iPheromones * iEvaporationRate;
return --iEvaporation == 0;
}
}
private class Ant {
private AntTrail iTrail = new AntTrail();
public void wander(Map map, int steps) {
iTrail.addStep(map.iname());
for (int i = 0; i < steps; i++)
step(map);
}
private void step(Map map) {
ArrayList choices =map.to(iTrail.current());
Location next = null;
double span;
// sum the available span
span = 0;
Iterator i1 = choices.iterator();
while (i1.hasNext())
span = span + ((Location)i1.next()).getPheromones();
// choose an index value
double index = iRandom.nextDouble() * span;
// find the location within the span with this index
span = 0;
Iterator i2 = choices.iterator();
while (i2.hasNext()) {
next = (Location)i2.next();
span = span + next.getPheromones();
if (index < span) break;
}
// add the chosen location to the trail
iTrail.addStep(next);
}
public AntTrail getTrail() {
return iTrail;
}
public void dropPheromones(double score) {
iTrail.dropPheromones(score);
}
public String print() {
return iTrail.print();
}
}
private class AntTrail {
private ArrayList iTrail = new ArrayList();
public void addStep(Location n) {
iTrail.add(n);
}
public Location getStep(int index) {
return (Location)iTrail.get(index);
}
public Location current() {
return getStep(iTrail.size() - 1);
}
public void dropPheromones(double score) {
Iterator i = iTrail.iterator();
while (i.hasNext())
((Location)i.next()).dropPheromones(score);
}
public String print() {
String s1 = "";
Iterator i = iTrail.iterator();
while (i.hasNext()) {
String s2 = ((Location)i.next()).getName();
if (!s1.equals("") && !s2.equals("")) s1 += "-";
s1 += s2;
}
return s1;
}
}
}
