Student work
Self-organization
Populations
Artificial life
Ecology
Software
Links
Contact
Home
Sorting performed by ants

Please note

The simulation needs a Java-Plugin (1.3.x) installed for your internet browser. If you do not already have one installed, the browser will prompt you to download the Plugin from “Sun”, who is the inventor of Java. Please download the JRE (=Java runtime environment) into a directory on your computer (e.g. “c:\temp”), execute the downloaded file for installation on your system (double-click on the file). Afterwards you will be able to reload the simulation page. Maybe you will have to restart your browser to succeed.

Run the simulation

Please click here.

Description of the simulation

This simulation is based on the ability of ants and termites to sort material and align them to piles. This leads to the known building behavior of termites and the known ability of ants to sort seeds or corpses. One basic principle in these cases is the phenomenon called “stigmergy”, that means that the erected building itself represents the key stimulus that directs further building. This way the building itself is simultaneously its own building plan.

In our simulation virtual ants perform a random walk and find colored chips (the colored little squares). If they are unloaded (empty) they take up the chip with a certain probability. How big this probability is belongs to the structure of the local environment. If there are already many chips, the ant is more unlikely to pick one up than in an almost empty local area. But not only the number of chips in the local area influence the probability of picking one chip, also the degree of homogeneity (similarity of chip color in the local neighborhood) plays an important role. For example, an ant is quite unlikely to pick up a red chip in from an area that already contains other red chips.

When an loaded ant bumps into another chip, she might unload her chip in an adjacent empty patch with a certain probability. As with the pickup probability, the probability of dropping a chip is calculated as a measure of similarity of chips and their local density. The more similar colored chips there are in the environment, the more likely an ant will drop it into an empty patch nearby.

Constraints: An ant can only carry one chip and each patch can only hold one chip, so it is impossible to drop a chip onto an patch that already contains a chip.

But how did we measure similarity? In NetLogo, which we used for implementing the model, each shade of an color is represented by an ID-number. We used 10 shades of blue, red and green. Of course, the numbers different shades of each base color are quite near (+/- 5). Blue is nearby red, but the shades of green are quite far away from blue and red.

This figure sows you the codes associated to the colors:

How are the probabilities calculated?

The following equation is used to calculate the clusterness for a given patch (called “self”, whereby “i” counts from 1 to “N_occupied_patches”, meaning that ”N_occupied_patches” patches are occupied with chips in the neighborhood with the radius 1):

The following 2 equations calculate the probabilities that chip is dropped or uptaken by and ant:

Parameters

The slider density-of-chips sets the density of chips distributed randomly at the beginning

The slider number sets the number of ants that are used in the simulation

The sliders Puturn and turn-angle set the basic parameters of the random walk. Please note that the ants always perform simply a random walk.

The slider alpha sets the value of the parameter used in the first equation. It simply scales the interpretation of “similarity”.

What has this to do with data mining?

Imagine that the chips represent other things, e. g. personal data sets. Instead of color codes you could use other information. If you use more pieces of information, you would calculate the distances between the elements n-dimensionally. Now you can let the ants perform their work and you will end up with interesting clusters of data. Why didn’t you already hear of this technique ? Maybe because it’s quite slow and there are other techniques for data mining that are more efficient. But this nature-inspired technique seems to be very robust and adaptive, so it never hangs up, quite unlike to the computers it runs on.

Experiments

  • Check how the number of actors and of the chip density affect the sorting speed and result.
  • Study the importance of “alpha”.

Screenshot

This picture shows the initial distribution of chips:

This picture shows the distribution after a few thousand steps with different values of “alpha”::

Implementation

The presented NetLogo simulation was written by:
Thomas Schmickl (2002), Department for Zoology, Karl-Franzens-University Graz, Austria, Europe,
schmickl@nextra.at, thomas.schmickl@uni-graz.at

Further readings

  • Camazine S., Deneubourg J.-L., Franks N.R., Sneyd J., Theraulaz G. and Bonabeau E. (2001) Self-Organization in biological systems. Princeton University Press
  • Resnick M. (2000) Turtles, termites and traffic jams. MIT Press.
  • Bonabeau E., Dorigo M. and Theraulaz G. (1999) Swarm intelligence. From natural to artificial systems. Santa Fee Institute studies in the sciences of complexity. Oxford University Press.

[Home] [Self-organization] [Ecology] [Populations] [Artificial life] [Student work] [Software] [Links] [Contact]