13

I am a student working on an ant colony simulator for a course project. The algorithm for it is (obviously) an ant colony algorithm. I know there are various forms of the algorithm but all of those were too mathematically detailed for us so we took an approach in which we have :

  • An ant is born at a colony and must gather food from a source to sustain the colony.
  • All ants are similar.
  • The area in which the ant moves is a 1000x1000 grid, so every grid point serves as a valid point for an ant to occupy. Now, all the algorithms which I have come across involve treating vertices and edges separately but as we are restricting the ants movement to only four directions (up, down, left, right) I guess it doesn't matter where we put the pheromone.
  • The grid points mentioned above store the pheromone.
  • An ant drops pheromone only if it is carrying food.
  • For an ant at a position (i,j), it decides where to move in the next step by taking the pheromone amounts on its four adjacent nodes into account in a simple probabilistic formula,i.e. the probability of traveling to a node is given by (pheromone amount at particular adjacent node) / (sum of pheromone amounts in 4 adjacent nodes).
  • An ant cannot travel back to the position it just came from. It can only do so if it is at a site which has food or it is at its colony.

Now my concern is ( and what is actually happening in our program ) that when an ant FIRST reaches a position which has food and picks it up, then by the way our algorithm works, it can move anywhere! This is because it will only leave a pheromone trail, once it has the food and not before and as it is the first ant, there is no existing trail.

If the ant can move anywhere, the ants that reach the food source after it will also mostly tend to follow it.. EVEN IF it is not moving back towards the colony. This defeats the purpose of the entire algorithm.

So my questions are

  • Is the above concern valid? If no, then why? If yes, then how to deal with it?
  • Do we need to make some changes in our basic understanding of the algorithm to actually make it work?
  • What are some other subtle yet important things that newbies like me may miss in this case?
  • 1
    If I were building an ant colony, I'd have two types of pheromone marks: "regular", always left where an ant travels, and "food", only left by an ant carrying food. An ant moves towards greater concentration of "regular" pheromone if it's carrying food, otherwise towards "food" marks. Also I'd make ants "hungry" and "sated"; a hungry ant travels towards "food" marks but away from "regular" marks, in order to search for new food sources. (I'd also make the grid hexagonal, but it's not the point.) – 9000 Apr 13 '15 at 18:42
  • While there are many variations, I think most of the ant colony algorithms assume that the ant can remember its way back home. IOW, it knows the nodes it visited already. The pheromone's come into play for the randomly travelling ants. – Dunk Apr 13 '15 at 18:50
  • Ever play simant? – user40980 Apr 13 '15 at 18:52
  • "I know there are various forms of the algorithm but all of those were too mathematically detailed for us so we took an approach in which we have..." Are you sure you're actually doing the assignment you were given if you couldn't understand the algorithms? – Doval Apr 13 '15 at 19:38
  • @ Doval : We just have to do a project of our choice. We weren't constrained to a field in any manner. The course is an introductory one in C++. Our instructors just want us to have experience in software dev. – transistor Apr 13 '15 at 19:47
6

This isn't how ACO works. ACO only drops pheromones after ants have moved across all the points in the grid. You then evaluate something (perhaps total travel time) and then drop pheromones for good ants, and repeat.

They don't move to the same vertex twice, generally, though you can customize this for implementation specificness.

Pheromones aren't dropped each move, they drop after they move everywhere and something is evaluated to determine which ants are better. Ants which are better then drop phereomones (perhaps the best 25% performing ants).

  • I disagree - ACO can work by dropping pheremone each step, especially when the goal is to simulate an ant colony (ACO algorithms for solving problems other than "this is what a colony of ants does" take steps to make the algorithm more efficient, but not necessarily like real ants). – Logan Pickup Apr 21 '17 at 21:16
1

The implementations I've seen from others, and the ones I've written for myself, have always had the ants release the pheromones along the path the traveled to get to food, once they have reached the food. That is, the ants march from their colony to the food following a random walk; the paths followed by the ants from the colony to the food are then marked using pheromones only after the ants were successful in reaching the food. The return trip is not explicitly simulated. In general, multiple ants run their course before any pheromones are deposited for the current iteration. The pheromones are then deployed for the successful paths, and a new round begins.

Usually, the ant's odds of stepping into a given node are weighted by the amount of pheromone times some measure of "goodness." For instance, the goodness measure might be something like the inverse of the distance between the ant and the food--this will keep the ants trying to move towards the food, regardless of previous pheromone deposits. The goodness could be further weighted to account for other factors, e.g. some nodes might be easier to travel through than others. And as enderland points out, typically there is some form of path "selection" once all of the ants have successfully run their courses, where only some portion of the "best" paths are chosen for pheromone deposit. However, you should still get reasonable paths even without selection, so long as your choice of "goodness" makes sense.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.