An Ant Colony Optimization Algorithm

for the Stable Roommates Problem

 

Glen Upton

Earlham College

December 17th 2002

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

An Ant Colony Optimatization Algorithm

for the Stable Roommates Problem

 

            Despite the current technology, and rapid advances in every field, there are still some problems that continue to elude scientists.  Complex NP complete problems: vehicle routing, network maintenance, the traveling salesperson, matching, and computing the shortest route between two points are just a couple of examples of these types of problems.  Learning algorithms have been developed in conjunction with artificial intelligence systems such as neural networks to try and solve some of these problems, but imperfections and inefficiencies in both the hardware and software often prevent reliable results.  Genetic algorithms were also applied toward these problems, and have had some success.  The algorithms were considered too complex to re-implement, realizing the random nature of the mutation operations (Tarasewich p.63).  Genetic algorithms were also not reliable enough to produce consistent optimal solutions for these complex problems.  Scientists, now, are looking into the world of insects in search of new methods and approaches of attacking complex problems. 

Scientists and researchers are especially interested in the lives of social insects such as ants, bees, wasps, and some caterpillars.  An individual ant is relatively unintelligent, but when they are part of a colony, complex group behavior emerges from the interactions of individuals who exhibit simple behaviors by themselves (Tarasewich p.63).  This phenomenon is indicative of all swarm intelligences, where something is created that is greater than the sum of its parts.  Using their social structure ants are able to complete very complex tasks without even knowing of the existence of the problem.    One of the complex behaviors that naturally emerges from the ant colony is the ability to determine the shortest path between two points.

An individual ant makes their decision on which direction to go just on chance, they have just as much probability of going one direction as another (Fedoriw p. 2).  As soon as an ant finds some food, it will take some back to the nest.  As ants move they leave behind a chemical substance called pheromone, which other ants can smell and identify that an ant has been there before (Dorigo p. 2). 

Figure 1: Ants converging on the shortest path between a food source and the nest

(Taken from Tarasewich, P “Swarm Intelligence”, Communications of the ACM, August 2002

The ants that find the closest food source will be able to leave more amounts of pheromone since their travel time is less then the other ants.  When other ants finally return to the nest, they will decide where to go based upon the amount of pheromone that they smell.  The stronger the pheromone level, the more likely an ant is to take that route (Fedoriw p.2).  As more and more ants take the shorter path, the pheromone level increases until every ant is taking the same shorter path (see Figure 1).

The natural behavior of these ants and be programmed into an ant algorithm, which can be used to find optimal solutions to some NP complete problems.  Since most NP complete problems can be reduced to a graph, being able to find the shortest path through a graph often provides the simplest and fastest solution to the problem.  Each ant can be represented by an agent in the program that has only has limited abilities, such as sensing and dispensing pheromone, and a memory so that any agent can trace its steps backwards through the graph in order to determine the length of the tour.  When an agent senses another agents pheromone it will receive positive feedback and decided to choose the popular path.  The positive feedback triggers autocatalysis, meaning that a small amount of positive feedback will result in more positive feedback and so on and so forth (Dorigo p.2).

One NP complete problem that could exploit the ant’s natural behavior is the Stable Roommates Problem.  The problem is to create stable roommates pairs out of the entire set of roommates.  The solution is unstable if and only if two paired roommates prefer each other to their current roommates.  A solution is stable if it not unstable.  There are may be possible sets of roommate preferences where a stable solution is not possible.  The stable roommates problem is reducible from the stable marriage problem, which is a well-established NP complete problem.  The stable marriage problem consists of creating pairings from two distinct sets usually described as male and female.  The females have a complete preference list for all of the males. 

 


                                                                                                           

 

                                                                                                                                   

Stable Marriage                                                                                    Stable Roommates

Figure 2: Difference between Stable Marriage and Stable Roommate Problems

The stable roommates problem remains an NP complete problem because instead of having two separate sets, the stable roommate problem is built on a completely connected graph, which contains more edges than a bipartite graph (see Figure 2).  I have designed a solution to the stable roommate problem using an ant algorithm.

In order to use an ant algorithm most efficiently, the problem needs to be able to be represented as a graph with weighted edges.  The Stable Roommates Problem can be constructed in this fashion, and an ant algorithm can exploit the use of pheromone in solving the problem.  The problem is represented as a fully connected graph, with each node connected to every other node.  A node represents a roommate (which can also be considered by a colony of ants), and the weight of an edges leading from that node (n1) to another node (n2) represents that n1’s inherent preference for n2.  The edges are constructed using an adjacency matrix.  A roommate’s preference for another roommate is determined by their similarity, by how many attributes their share.  I have chosen to work with binary attributes (smoker/non-smoker) so that a roommate can effectively be represented by a string of 1’s and 0’s.  Similarity is then determined by comparing two different strings of 1’s and 0’s.  Therefore a non-smoker, morning preferring, noisy, studious roommate could be represented with the string 0111.  For testing purposes these roommate strings are generated randomly.  The similarity is then used as the default weight for the edge between the two roommates in the adjacency matrix.

Once the similarity has been determined, then the problem has been set up and is ready for traversal by the ants from each colony/roommate.  Each colony’s swarm explores the graph, much like real ants foraging for food.  The exact number of ants per colony is a variable that can be manipulated to achieve varied results.  An optimal number of ants per colony has yet to be determined.  Once an ant finds another roommate/colony it returns to it’s own nest as if it were returning with food.  The weight of the edge should determine the probability the ant would choose that edge.  As the ants traverse the graph they dispense pheromone.  Once the ant returns to the nest, it senses the pheromone and chooses whether or not to follow the pheromone trail based on a transition equation (Bonabeau p. 67) Thus, ants that find roommates who are more similar (edges with larger weight) will deposit more pheromone on the edges that connect to more similar roommates, making those edges more attractive to other ants. 

Each time a colony searches for a roommate, the probability of an ant of the colony choosing a particular roommate must be determined.  Probability must be determined because the ants need to randomly choose and edge while giving preference to those edges, which have heavier weights and more pheromone.  Probability is determined by summing up the default weight of each edge adjacent to that colony along with the current pheromone level for each of those edges.  Then each the weight and pheromone level for each adjacent edge is divided by that sum, in effect, normalizing the weight and pheromone level.

for(j=0; j<g.size(); j++)

                    {

                      if(i!=j)

                                {

                                  if(j==0)

                                    {

                                      prob[j] = (g.get_edge(i, j).get_pheromone()+

                                                                 g.get_edge(i, j).get_weight())/sum_pheromone;

                                    }

                                  else

                                    {

                              prob[j] = prob[j-1] + ((g.get_edge(i, j).get_pheromone()+

                                                                                      g.get_edge(i, j).get_weight())/

                                                                                     sum_pheromone);

                                    }

                                }

                      else

                        {

                                  prob[j]=0.0;

}

                    }

Figure 3: Procedure for finding the probability an ant will chose an adjacent edge

The result gives the probability that an ant will choose that edge.  The probability for each edge is stored in an array with probability[n] = probability[n-1] + the probability for edge(n).  Thus the values stored in the probability array range from 0 to 1 (see Figure 3). 

Each ant in the colony then chooses a random double between 0 and 1.  Iterating through the probability array until the chosen random double is greater than the current selected probability produces the edge that the ant has chosen.  This procedure allows for the ant to randomly choose an edge with greater probability given to edges with heavier default weight and edges with more pheromone attached.  Finally a set amount of pheromone is added to that chosen edge, and the next ant in the colony chooses another random double.  The amount pheromone added to an edge is a variable that can be manipulated.  Larger amounts of pheromone will result in faster convergence, but leads to a greater possibility that a convergence may be sub-optimal.  Smaller amounts of pheromone result in slower convergence, but protects better against sub-optimal convergence. 

The procedure continues for each ant in the colony until each ant in the colony has chosen an edge.  Then the next colony in the graph must determine the probability for its adjacent edges, and the procedure continues until each ant in each colony has chosen an edge.

It is possible that a colony will converge on a sub-optimal solution, and so a rogue ant must be sent to explore the graph periodically.  The rogue ant provides thermal noise to the rest of the colony.  The colony may converge on a local maximum, not realizing there is a better choice somewhere else.  The rogue ant encourages the colony to continue to explore so that the true maximum might be found.  If the rogue ant finds a roommate who is more similar (a heavier weighted edge) than the one the colony is focused on, the rouge ant will set the pheromone level of that newly discovered edge to a level comparable to the one the colony is focused on.  This will increase the probability of the colony choosing that edge, but not completely deter the colony from its current favored roommate. 

Another step may be taken to encourage the use of shorter routes.  The pheromones have an evaporation rate, which applies to all the edges in the graph.  Therefore edges will have to be traversed more frequently if a colony truly prefers another in order to maintain a strong and attractive pheromone level.  The pheromone evaporates by a set percentage once every ant in every colony has chosen an edge.  The percentage can also be manipulated to given varied results.  Once evaporation occurs the entire procedure starts over, either for set amount of iterations, or indefinitely.  The most stable set of roommates is then determined by the edges with the most pheromone on them, which is the set of roommate the ants have converged on.

I have also developed a graphical user interface to provide display and manipulation of the algorithm.  The GUI displays the graph as an n-gon, where n is the number of colonies.  It only displays the most favored edge of each colony; the ones with the most pheromone on them because viewing all the edges would be distracting to the user.  I had wanted to develop a way of coloring the edges corresponding to how much pheromone was on them, but the formula proved too complex because average pheromone level changes with the number of colonies in the graph, and the number of ants per colony.  Several glui panels allow the user to manipulate the number of ants per colony, the number of attributes a colony has, the number of colonies in the graph, the evaporation rate, and the pheromone-dispensing rate, and the total number of iterations of the procedure.  This kind of interface can help users understand the concept of swarm intelligence. 

It is possible that in the future, the roommate pairings could be modeled on Earlham College’s application.  Instead of assuming that a person would want to live with someone similar, there could be a separate list of desirable attributes.  The questions used to determine these desirable attributes could be taken from the Earlham College application in the hope that this algorithm might possibly be used to match an incoming class of first years.  Furthermore, a web interface could be utilized by incoming first years where they could give desirable attributes in their roommate.  The web interface could link to a database and store the attributes, and the algorithm would pull its data from that database.  The algorithm could save the college money and resources by lessening the number of roommate problems and switches on campus.  This kind of application was beyond the scope of this project, but it is certainly a plausible application for future research.

Upon completion of this project, I discovered that it might not have been as complete as I had once thought.  The definition of stability is quite difficult to narrow down.  There does not seem to be a mechanism within the algorithm to insure that all roommate pairings are stable.  Another problem is that for any given number of colonies, there is a proper pheromone dispensing level and evaporation rate that will lead to convergence.  If these values are not what they are supposed to be, it is possible that a solution will not be given at all.  What it would require is another polynomial time algorithm to go through the calculated pheromone levels on each edge to determine the proper pairings.  This procedure, however, is no better than the exhaustive search the initial algorithm was trying to get away from.  The project is not a complete failure however; the definition of stability needs to be reworked in order to be able to fit with the ant colony algorithm.  This project was a first step, and perhaps future research could lead to a solution.

         

 

 

 

 

             

                

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                                                                           

 

                                                                                                                                   

            Stable Marriage                                                            Stable Roommates