I485: Biologically Inspired Computing
Lab 5: Ant Clustering Algorithm
Summary
- Lab slides
- Read section 5.2 in de Castro's Fundamentals of Natural Computing for an overview of ant-based models in bio-inspired computing. Also see lecture 21.
- Complete the following problems. Lab is worth 10 points. Points for each question are shown below for I485 and H400.
- 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.
- Assignment is due before class on Monday, May 4th (Note unusual day)
Questions or problems? See my email and office hours information.
The problems:
- [2 points] [1 point] The basics: Read "The Standard Ant Clustering
Algorithm (ACA)" in section 5.2.5 of de Castro's book. Formalize the
algorithm de Castro describes there in pseudo-code or in words.
Give detailed instructions for calculating the 'perceived
fraction of items' f and the interactions of each ant with its environment (pickup, move, drop-off of material). This is only a warm-up exercise and is not asking you to solve any particular problem using ACA.
- [3 points] [3 points] Grooming an ant colony: Implement a
2-dimensional grid-world with wrap-around borders just like the cellular automata from lab3 (only, it is 2-dimensional now). Randomly place a few 'dead ants' on it (simply fill the cells of the world containing dead ants with a particular color). Now, randomly place a few 'living ants' on the world.
Your objective is to have the live ants cluster together the dead ants using ACA. Define a neighborhood size for each living ant; the immediate neighborhood of 9 cells (3x3 square) is a good choice. Compute f, as the fraction of dead ants perceived by a living ant in its neighborhood, which is a value between 0 and 1. Implement equations (5.11) and (5.12) that define the pick-up and drop-off probabilities. Choose values for
k_{1}
andk_{2}
so that they are neither too large nor too small when compared to the range of f. Run your ACA for many iterations and watch the ant colony getting groomed. How many clusters do you see? Tune the above parameters until you are satisfied with the results. For a particular parameter choice, rerun your program a few times starting from different initial conditions. Report your parameter choices and the corresponding results. You can use our sample code that draws a rectangular grid-world, and randomly places a few dead ants and live ants on it.
- [5 points] [4 points] Data clustering: (This question is also described in exercise 7 in p.260 of the textbook) Now, instead of dead ants, use the "data items" corresponding to the 16 animals described in this dataset
(you can use membership in 'terrestrial' and 'birds' in order to color
your items, so that you can see how well your clustering is
proceeding). Initialize your virtual world by placing the 16 data items
randomly across your 2D grid. (Note:
each data item is 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). Compute f as the similarity of a data item (that a living ant is sitting on) with all others in its neighborhood, using a variant of equation (5.13) described in exercise 7 in p.260. Provided is a sample piece of code to compute the similarity measure that uses equation (5.13) for a pair of 2-dimensional data items. Additionally, have the ants interact with the items by
picking them up, carrying, and dropping them according to the same
probability functions defined in equations (5.11) and (5.12). Choose parameter values for
k_{1}
,k_{2}
, andα
that give you meaningful clusterings of the 16 animals. One possible clustering you may expect to see is all the 'terrestrial' data items in one cluster and the 'bird' items in another.- [Optional, extra 2 points] [2 points] The parameter
α
defines the scale of dissimilarity: it determines when two items should be or should not be located next to each other (p.229). Once you are satisfied with the results from the above, rerun your algorithm by varying justα
. How do higher and lower values ofα
affect the clustering performance?
- [Optional, extra 2 points] [2 points] The parameter
More
Acknowledgements
- Lab originally prepared by Artemy Kolchinsky.
- Modified by Santosh Manicka.
Links
I485/I585 Biologically-inspired Computing