An Ant Colony Optimization Algorithm for the Stable Roommates Problem
by Glen Upton


SWARM Intelligence:
What is swarm intelligence?
It is composed of lots of unintelligent individuals, but the group shows complex behavior. For example: ant colonies, bee hives, and schools of fish. Computer Science uses swarm intelligence by writing programs that utilize the natural behavior of this animals to solve complex problems. In swarm applications, the units working on the problem usually have no knowledge that a problem even exists, they are in fact just continuing with their natural behavior, and it is that behavior that helps solve the problem. For example: ant colonies have a natural ability to find the shortest path from one route to another, while avoid obstacles and danger.

The Roommate Matching Problem: A Swarm Intelligence Approach:
For my senior project I was looking into the problem of matching roommates together in a stable way. Stability, it turns out, is very hard to define. I developed an algorithm that utilizes the natural behavior of ants. Each roommate has a colony of ants, and the ants go out in search of other roommates who are similar to themselves. Wherever ants walk they leave a pheromone trail for other ants to follow. Eventually what will happen is roommate pairs will be generated by the connecting pathes being traversed by their respective ant colonies.

Here are some Java Applets that demonstrate some Swarm stuff:
Particle swarm optimization Applet (1)
Particle swarm optimization Applet (2)
Ant colony optimisation applet
Swarm Animation


My Papers:
My Final Paper: "An Ant Colony Optimization Algorithm for the Stable Roommates Problem
My Initial Survey Report
My Project Journal

My Sources
1. E. Bonabeau, M. Dorigo, and G. Théraulaz, Swarm intelligence: from natural to artificial systems, Oxford University Press, 1999.

2. M. Dorigo and G. Di Caro,"Ant colony optimization: a new meta-heuristic", Proc. 1999 Congress on Evolutionary Computation, July 6-9, 1999, pp. 1470-1477.

3. M. Dorigo, G. Di Caro, and L. M. Gambardella, "Ant algorithms for discrete optimization", Artificial Life, vol. 5. no. 2, pp. 137-172, 1999.

4. G. Fedoriw, C. Fehr, M. Good, S. Keown, "Application of Swarm Intelligence Solving the Shortest Route Problem", University of Calgary

5. Garey, Michael R., and David S. Johnson. Computer and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman and CO., 1979.

6. S. Johnson, Emergence: the connected lives of ants, brains, cities, and software, Scribner, New York, 2001.

7. J. Kennedy, R. Eberhart, and Y. Shi, Swarm intelligence, Morgan Kaufmann Publishers, San Francisco 2001.

8. T. Stützle and H. Hoos, "The MAX-MIN ant system and local search for the traveling salesman problem", Proc. IEEE International Conference on Evolutionary Computation, April 13-16 1997, pp. 309-314.

9. P. Tarasewich and P. McMullen, "Swarm intelligence power in numbers", Communications of the ACM, vol. 45, issue 8, pp. 62-67, August 2000.