source

Summary

1. Read section 5.2 in de Castro's Fundamentals of Natural Computing for an overview of ant-based models in bio-inspired computing
2. Do the following problems. Complete lab is worth 5 points.
3. Attach answers as separate Python files to your submission for 'Assignment 4' in Oncourse
4. Assignment is due by 1pm on Wednesday, April 23th
   
   Questions or problems? See my email and office hours information.

1. Go through the section called "The Standard Ant Clustering Algorithm (ACA)" in section 5.2.5 of de Castro's book. Formalize the algorithm de Castro describes here in fleshed-out pseudo-code. Explicitly describe instructions for calculating the 'perceived fraction of items' f and the interactions of each ant with its environment (pickup, move, drop-off of material).
   
   
2. To implement our pseudocode, we need to setup the virtual world which ours ants will occupy. For our purposes, this will be a 2-dimensional grid with wrap-around borders. Here is a piece of code that initializes and draws a 2D-grid virtual world with one 'ant' on it.
   
   Starting from this code, please implement a WIDTH x HEIGHT virtual world. It should have a random spatial distribution of 'specs' initialized according to some density parameter DENSITY. Implement NUM_ANTS ants (marked by another color) that wander randomly around the virtual world space, without interacting with the specs.
   
   
3. Build on your previous virtual world by having the ants 'pick up' and 'drop' specs with probabilities that depend on the local concentration of specs, and parameters k1 and k2. Tune the parameters so that the initially randomly distributed specs are eventually clumped into mounds. This is the 'termite' algorithm.
   
   
4. Once the above is done, implement the ant clustering algorithm described on p.229-231 of de Castro. Instead of random 'specs', use points corresonding to the 16 animals described in this dataset (you can use membership in 'terrestrial' and 'birds' in order to color your points, so that you can see how well your clustering is proceeding). Initialize your virtual world by placing the 16 points randomly across your 2D grid. Additionally, have the ants interact with the points by picking them up, carrying, and dropping them according to the probability functions described in the book (use the Eucidian distance function between animals vectors for d(xi,xj), used for computing f). Before submitting, choose parameter values for k1, k2, and α that give you interesting clusterings of the 16 animals.