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 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.

//** ACO Strawberry
//** Andrew Carson 2006

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) {
        ACOStrawberry p = new ACOStrawberry();
    }

    /* instance variables */
    private static String iAlphabet = "ABERSTWY";
    private static String iTarget = "STRAWBERRY";
    private static int iAntSteps = iTarget.length();
    private static int iColonySize = 10000;
    
    private static double iPheromoneStrength = 1.8d;
    private static int iEvaporationSpan = 100;
    private static 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 iMap = new HashMap();
        Location iStart = new Location();

        /* constructor */
        public Map() {
            iMap.put(iStart.getKey(), iStart);
        }
        
        public Location start() {
            return iStart;
        }

        public ArrayList to(Location fromHere) {
            // generate every map location that is valid from here
            ArrayList newLocations = new ArrayList();
            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 = (Location)iMap.get(n.getKey()); // existing location
                
                newLocations.add(n);
            }
            return newLocations;
        }
        
        public void tick() {
            Iterator i = iMap.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() { 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 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.start());
            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;
        }
    }
}

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 <<