Herself’s Artificial Intelligence

The ant algorithm was developed from real ants. Ants searching for food leave a trail of pheromones. An ant who takes the shortest path between the nest and the food leaves the most amount of pheromone since he makes more trips. The stronger the pheromone scent the more ants follow that trail.

This has been applied to the Traveling Salesman Problem, as well as to scheduling problems. Though it is an interesting solution it is not fast so may have limited applications with out modification.

This algorithm assumes a fully connected graph, otherwise your ants may quickly box them selves into corners. Each ant starts in a different city. Each ant chooses a city he has not yet visited. The choice is based on a greedy heuristic ( shortest path ) and the path with the greatest amount of pheromone.

Once a path is chosen, the ant puts down pheromone. The amount of pheromone is some constant divided by distance. This gives more pheromone to shortest paths.

The older pheromone evaporates. So each round we decrease the pheromone on each edge by a small amount.

Algorithm:
-choose a map or generate one
-generate map ( pick a specific number of cities, generate a random x,y for each to give it a position. )
-create one ant for each city
-start each ant in a different city

LOOP
for each ant {
pick city to move to
lay down pheromone along path just traveled
add this city to city list so we can see the path the ant took when we are done
update the total distance ant traveled so far
}

for each path {
decrease pheromone
}
END LOOP

Print shortest path
} //end

Pick_City( cities_ant_can_move_to ){
beta //is length or amount of pheromone most important? Use a number between 0 and 1

for each city ant may choose from this location{

Score = Amount_of_Pheromone + Length_to_City^Beta
If this score lowest keep
}

Move on path with least score
}

Lay_down_pheromone( edge ){
gamma //some constant between 0 & 1 to adjust pheromone

pheromone_on_this_edge += gamma/length_of_edge

}

Decrease_pheromone_with_time( edge ){
alpha // some number between 0 and 1
pheromone_on_this_edge *= alpha
}

Ant{
total_distance_traveled;
cities_traveled_in_order;
}

Edge{
City1;
City2;
length;
current_amount_of_pheromone;
}

More information:
The ant algorithm was developed from real ants. Ants searching for food leave a trail of pheromones. An ant who takes the shortest path between the nest and the food leaves the most amount of pheromone since he makes more trips. The stronger the pheromone scent the more ants follow that trail.

This has been applied to the Traveling Salesman Problem, as well as to scheduling problems. Though it is an interesting solution it is not fast so may have limited applications with out modification.

This algorithm assumes a fully connected graph, otherwise your ants may quickly box them selves into corners. Each ant starts in a different city. Each ant chooses a city he has not yet visited. The choice is based on a greedy heuristic ( shortest path ) and the path with the greatest amount of pheromone.

Once a path is chosen, the ant puts down pheromone. The amount of pheromone is some constant divided by distance. This gives more pheromone to shortest paths.

The older pheromone evaporates. So each round we decrease the pheromone on each edge by a small amount.

Algorithm:
-choose a map or generate one
-generate map ( pick a specific number of cities, generate a random x,y for each to give it a position. )
-create one ant for each city
-start each ant in a different city

LOOP
for each ant {
pick city to move to
lay down pheromone along path just traveled
add this city to city list so we can see the path the ant took when we are done
update the total distance ant traveled so far
}

for each path {
decrease pheromone
}
END LOOP

Print shortest path
} //end

Pick_City( cities_ant_can_move_to ){
0<beta<1 //is length or amount of pheromone most important?

for each city ant may choose from this location{

Score = Amount_of_Pheromone + Length_to_City^Beta
If this score lowest keep
}

Move on path with least score
}

Lay_down_pheromone( edge ){
gamma //some constant between 0 & 1 to adjust pheromone

pheromone_on_this_edge += gamma/length_of_edge

}

Decrease_pheromone_with_time( edge ){
alpha // some number between 0 and 1
pheromone_on_this_edge *= alpha
}

Ant{
total_distance_traveled;
cities_traveled_in_order;
}

Edge{
City1;
City2;
length;
current_amount_of_pheromone;
}

See also:
SantaFe Ant trail description and source code

More information:
Central Intelligence: From Ants to Web ( YouTube TED video )
Artificial Intelligence network load balancing using Ant Colony Optimisation ( source code and article )
Ant Colony System: A Cooperative Learning Approach to the TSP
ACO Algorithms for the TSP
Wiki, Ant colony optimization
Ants riddled with cheating and corruption ( perhaps they are not as simple as we think? )