ACO Finding Strawberries
ANT COLONY OPTIMIZATION
ACO (Ant Colony Optimization) is a metaheuristic where a colony of digital ants searches for optimal solutions to complex multidimensional problems. My interest in ACO started when I began considering its usefulness in solving the Palindromic Pangram problem described ELSEWHERE.
The "project" below is a first attempt at defining a simple problem, and then implementing an ACO-based solution. The ACO concepts presented here, and my understanding of them, are all based on the book Ant Colony Optimization by Marco Dorigo and Thomas Stützle.
Real Ants and How They Forage
The following description is a very brief summary of From Real To Artificial Ants from Dorigo and Stützle's book:
An ant colony represents a highly structured insect society that can accomplish complex tasks that in some cases far exceed the individual capabilities of a single ant. Ants coordinate their activities via indirect communication; for example, a foraging ant that has found food will deposit a chemical on the ground (pheromones) that increases the probability that other ants in the colony will follow its same path.
Finding Strawberries
I have started with a very simple problem: tasking an ant colony with finding the word STRAWBERRY using permutations of the alphabet ABERSTWY. An ant leaving home chooses a path, starting with any letter from ABERSTWY. From there, the ant chooses another letter, again from ABERSTWY. And so on. Once the ant's path is 10 steps long (i.e. 10 letters), it returns home. The program evaluates the 10 letters the ant has chosen by calculating a score based on how close the 10 letters are to the word STRAWBERRY, and then marks the ant's path with a pheromone value representing this score. Pheromones build up with each passing ant, and those paths/steps with the highest pheromone values are most likely to be chosen by the next ant. This is the essence of ACO. In addition, the pheromones evaporate at a predefined rate, so that little-used ant trails become less and less likely to be chosen by the next ant. Unlike "classic" ACO, this program processes one ant at a time, but for this "Finding Strawberries" problem, this simplification is of no (known) significance.
Notes:
• The Map class generates the ant's world as a network of locations. In the case of the "Finding Strawberries" problem, the network is actually a true hierarchy, with the root as the starting node, and so no circular paths are possible (a further challenge with using ACO to solve other problems, not addressed here).
• A Location class defines each location, generated by the Map. The Location objects also maintain the pheromone values, and manage the evaporation.
• The ants' behaviour is governed by the Ant class. In particular, the step() method contains the logic to choose an ant's next step, which is a random choice biased towards the highest pheromone values of the possible locations the ant can move to.
Output results follow the listing:
• Column 1 is the ant's number
• Column 2 is the ant's trail
• Column 3 is the calculated score of the ant's trail
Output results follow the listing.
//* ACOStrawberry.java
//* Andrew Carson 2006
//* Java SE 6 Version 2009
package www;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Random;
public class ACOStrawberry {
public static void main(String[] args) {
new ACOStrawberry();
}
private String iAlphabet = "ABERSTWY";
private String iTarget = "STRAWBERRY";
private int iAntSteps = iTarget.length();
private int iColonySize = 10000;
private double iPheromoneStrength = 1.8d;
private int iEvaporationSpan = 100;
private double iEvaporationRate = 0.98d;
private Random iRandom = new Random();
// constructor
public ACOStrawberry() {
Map map = new Map();
double bestScore = -1;
System.out.println("\nACOStrawberry");
System.out.println(">>> the ants are hunting"
+ " for a strawberry! <<<\n");
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 <<<");
}
double calcScore(AntTrail trail) {
double score = 0;
for (int i = 1; i <= iAntSteps; i++) {
char v1 = iTarget.charAt(i - 1);
char v2 = trail.getStep(i).getName().charAt(0);
int v3 = 0; if (v1 == v2) v3 = 1;
score += v3 * (iAntSteps + 1 - i); // add linear bias
}
return (score / 55d) * iPheromoneStrength;
}
private class Map {
// instance variables
HashMap<String, Location> iMap =
new HashMap<String,Location>();
Location iStart = new Location();
// constructor
public Map() {
iMap.put(iStart.getKey(), iStart);
}
public Location start() {
return iStart;
}
public ArrayList<Location> to(Location fromHere) {
// generate every map location that is valid from here
ArrayList<Location> newLocations =
new ArrayList<Location>();
for (int i = 0; i < iAlphabet.length(); i++) {
Location n = new Location(fromHere,
String.valueOf(iAlphabet.charAt(i)));
if (!iMap.containsKey(n.getKey()))
iMap.put(n.getKey(), n); // add to the map
else
n = iMap.get(n.getKey()); // existing location
newLocations.add(n);
}
return newLocations;
}
public void tick() {
Iterator<java.util.Map.Entry<String,Location>> i =
iMap.entrySet().iterator();
while (i.hasNext())
if (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() { iName = ""; }
// constructor: from another location
public Location(Location from, String name) {
iKey = from.getKey() + "|" + name;
iName = name;
}
public String getKey() {
return iKey;
}
public String getName() {
return iName;
}
public void dropPheromones(double d) {
iPheromones += d;
iEvaporation = iEvaporationSpan; // reset
}
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.start());
for (int i = 0; i < steps; i++)
step(map);
}
private void step(Map map) {
ArrayList<Location> choices =
map.to(iTrail.current());
Location next = null;
double span;
// sum the available span
span = 0;
Iterator<Location> i1 = choices.iterator();
while (i1.hasNext())
span = span + (i1.next()).getPheromones();
// choose an index value
double index = iRandom.nextDouble() * span;
// find the location within the span with this index
span = 0;
Iterator<Location> i2 = choices.iterator();
while (i2.hasNext()) {
next = 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<Location> iTrail =
new ArrayList<Location>();
public void addStep(Location n) {
iTrail.add(n);
}
public Location getStep(int index) {
return iTrail.get(index);
}
public Location current() {
return getStep(iTrail.size() - 1);
}
public void dropPheromones(double score) {
Iterator<Location> i = iTrail.iterator();
while (i.hasNext())
(i.next()).dropPheromones(score);
}
public String print() {
String s1 = "";
Iterator<Location> i = iTrail.iterator();
while (i.hasNext()) {
String s2 = (i.next()).getName();
if (!s1.equals("") && !s2.equals(""))
s1 += "-";
s1 += s2;
}
return s1;
}
}
}
ACOStrawberry
>>> the ants are hunting for a strawberry! <<<
0 S-A-S-W-S-S-S-S-S-Y 0.36
5 B-Y-R-R-B-W-E-R-S-A 0.49
27 R-T-R-S-W-T-W-W-Y-T 0.75
64 S-B-R-A-A-A-E-T-B-W 0.95
157 S-T-R-E-W-A-W-R-Y-B 1.18
200 S-T-R-R-W-A-R-R-T-Y 1.21
205 S-T-R-A-W-S-S-T-Y-Y 1.34
474 S-T-R-A-E-B-E-T-T-T 1.41
541 S-T-R-A-W-B-E-B-E-W 1.60
1466 S-T-R-A-W-E-E-R-R-Y 1.64
2615 S-T-R-A-W-B-E-R-A-B 1.70
9048 S-T-R-A-W-B-E-R-R-Y 1.80
>>> finished <<<
|
