AS-RFP

Performance & Benchmark results

Toby Skinner


Benchmark Tests

When running the AS-RFP algorithm you have to setup three parameters, these are alpha, beta and gamma. These determine how much of an effect pheromone, local heuristic and global heuristic have on the ants navigation (alpha determines pheromone, beta determines local inverse distance and gamma determines global inverse distance). It is quite hard to set these paramters by hand so two options were available to me, the first is to incrementally test each permutation of alpha/beta/gamma values and then select the values that work best (i.e. correctly navigate the most ants to the goal), the second choice (not yet implemented) is to use a GA to evolve the best values, this will take significantly longer but search over a larger number of values.

Test constraints

In order to run the incremental tests I had to put some constraints on the number of tests to be done :-
  1. The final success rate for each permutation would be averaged over 10 runs
  2. Each run is a permutation of alpha, beta (and gamma for global distance heuristic), 10 tours are made each run.
  3. Each of the 25 (max_nodes=100/4) ants are allowed to roam the landscape for 100 (max_nodes) discrete steps per tour (so each ant makes 10 tours per permutation).
  4. The range of alpha, beta and gamma was 0.0 to 2.0 in 0.2857 increments.
  5. Post processing was done with Matlab, this was the script I used.

Landscape

Below is the generic landscape used to perform these tests, it was not changed at any point. If you know about search algorithms and heuristics it should be fairly obvious that A* would perform perfectly because there are no dead ends and greedy search would have problems becasue of the uneven edge lengths (if it were using local distances instead of a global distance). In fact any search algorithm that used a global distance heuristic (the distance to the goal) would do well, this predicts that ants using the global distance heuristic will perform the best.
This is perhaps a little unrealistic because natural landscapes are not accessable in this way, a future test may be to remove some of the edges and create a more challanging landscape.
How to read the graphs

The 3D graphs plot the alpha and beta parameters against the number of ants to find the goal when using those values, the upper 2D graph plots this same data but sets the viewing angle to (0,90). This graph displays the data in terms of colour, the more deeper purple a point it, the higher a value it has, the more light blue a point is, the lower a value it has. Finally the lower 2D graph plots the contour of the data landscape, this can be used to find accurate points of minima and maxima (i.e. where the data was at it's highest and lowest).


Local Inverse Distance Heuristic

The first tests were performed on ants that used pheromone trails and the local inverse distance heuristic (i.e. they can only perceive as far as the neighbouring nodes), the results are shown below. The 3D plot shows the performance of the AS-RFP algorithm with different permutations of alpha and beta, the 2D plot shows the same data from a different perspctive whilst the contour plot highlights the optima points in the data. From these graphs we can see that the best perfromance was seen when alpha had a value of 0.0 and beta had a value of (0.2857*3.0)=0.8571. This implies that following the pheromone trails with more intensity lead fewer ants to the goal, however not by much. Looking at the raw data shows thet all permutations of alpha and beta (between 0.0 and 2.0 in increments of 0.2857) lead at least 160 ants to the goal on average. The difference could be attributed to the probabilistic nature of the node selection.


Global Inverse Distance Heuristic

The second tests were performed on ants that used pheromone trails and the global inverse distance heuristic (i.e. they can perceive the goal node but not local nodes), the results are shown below. The difference between low and high values of alpha is more noticable here, however interestingly the range of least successful to most successful permutations if still 160.0 to 195.0 (same as above). The main difference is that the performance of the global heuristic drops much faster than the local heuristic as soon as the alpha value is increased. Stronger beta values preserve the success rate until alpha exceeds (0.2857*2.0)=0.5714. So a global heuristic is more sensitive to changes in alpha (as can be seen from the 2D plot and the contour plot which shows a more fluctuating landscape than was seen above).



Combined Inverse Distance Heuristic

The final tests were performed on ants that used pheromone trails and a combination of the two above heuristics, the results are shown below. As I expected the combined data is somewhere between the above two, not as rugged as the global heuristic and not as smooth as the local heuristic. The performance still drops when alpha is increased but manages to settle afterwards. I predict that this algorithm would perform best in a more complex landscape because it has the advantage of both heuristics, I suspect that it would benefit from a slightly higher gamma value (global heuristic) relative to the beta value and a lower alpha value.



Overall the results show that (in the above landscape) the ants work well with a combination of both heuristic information and pheromone trails. If only local heuristic data is available (as it might be for sub-terrainian ants) then removing the pheromone trails have a seriously detrimental effect on subsequent successes. However if global heuristic data is available, the ants can perform just as well without the pheromone trails. Note that this will probably not be the case if the landscape is more rugged (i.e. not maximally connected) or changes over time, for these types of landscape the pheromone trails would provide the ants with information other than how close they are to the goal (like is this a dead end?).
It might be interesting to divide the increments of alpha,beta and gamma up further, it may be that very tiny changes in these parameters produce different results. Also it would be interesting to try the algorithms on a dynamic landscape to find out which performs better under more realistic situations.

Contact Info

Email me at toby@hc2.co.uk

References

  1. Bonabeau, Dorigo & Theraulaz. Swarm Intelligence. 1999. Oxford University Press. Santa Fe Institute (SFI) Studies In The Sciences Of Complexity.
  2. Tamassia. Algorithmics notes. 1999. Unknown. Unknown.