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. Please summarize your answers in one document file (.doc,.pdf) including pictures. Organize this document well, make it clear which questions you are answering and provide appropriate labels where you can. Submit your well-documented code as separate python files. Also, mention in your summary document the names of the relevant python files for each question.
4. Assignment is due by 11am on Thursday, December 1st
   
   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 there 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 data items). This is only a warm-up exercise and is not asking you to solve any particular problem using ACA.
   
   
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 just like your cellular automata from the 2nd assignment. Here is a piece of code that initializes and draws a 2D-grid virtual world with one 'ant' on it.
   
   Starting from this code, implement a WIDTH x HEIGHT virtual world. It should have a random spatial distribution of 'specs' (or 'dead ants') initialized according to some density parameter DENSITY that is just an integer indicating the number of 'specs' that needs to be placed in the virtual world. Implement NUM_ANTS ants (marked by another color) that wander randomly around the virtual world space, without interacting with the specs. Again, this is an extended warm-up exercise where you build the foundation for the following two questions.
   
   
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.228-229 of de Castro. Instead of random 'specs', use "data items" (vectors) corresponding to the 16 animals described in this dataset. Initialize your virtual world by placing the 16 items (displayed as points) randomly across your 2D grid; 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. (Note: each data item is a vector or an array of boolean values as shown in the file. You can assign an id to each vector and then refer to the ids in your program). Additionally, have the ants interact with the data items (displayed as points) by picking them up, carrying, and dropping them according to the probability functions described in the book (use the Euclidian 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.