Ant Colony Optimization

Assignment Objectives

• Learn how methods improve code by making it modular and task oriented.
• Implement a program that uses multiple static methods.
• Implement methods that call other methods.
• Practice passing arguments to methods.
• Practice returning values from methods.
• Develop code using one-dimensional and two-dimensional arrays.
• Gain more experience with concepts from your first programming assignment.

Description: Efficiently getting from one place to another requires finding the shortest route between those locations. If we could travel "as the crow flies" then that route essentially would be a straight line. If we were traveling by car, then we'd travel on the roads connecting various places. Now finding shortest route cannot be done by drawing a straight line, and it will likely require a more complex route traveling through other places on the way (e.g., like traveling through Milwaukee on the way from Madison to Chicago). In fact finding the absolute shortest route is quite difficult especially when there are many places to considered and lots of restrictions on the routes connecting them. Because of this, we're typically happy to find a route that's pretty short if not the shortest. How do we do find such a route? We could do what ants do!

Ants solve this problem whenever they find food. When locating food within their colony to bring to the queen ant, they need to navigate the tunnels and chambers of the colony until they find the chamber where food has been located. While searching for the food chamber they periodically lay pheromones on the ground behind them. Other ants smell these pheromones to find their way to the food and lay down additional pheromones as they go. This forms a scent trail that helps the ants efficiently locate the food.

Ant colony optimization algorithms are directly inspired by the method ants use. These algorithms do not guarantee to find the absolute shortest route, but they often find a very good one. They are best suited for finding good routes in very difficult situations where it would simply take too much time to find the absolute shortest route. The ant approach is also interesting because it is one the few algorithms known that can find short routes even if the locations are changing as the alrogithm runs (e.g., imagine having to find the shortest route to travel between two space ships by connecting through dozens of space ships moving in all different directions).

In this assignment, you'll implement an ant colony optimization algorithm to find a good route through the tunnels and chambers in an ant colony from the queen's nest to a chamber in colony having food.

Specifications:

These specifications define some important concepts and describe how each method should be approached. You will need to read these specifications multiple times to fully understand them.

We strongly recommend that you incrementally develop your code since this is a very effective way to program. By this we mean, code a small part of the specifications, carefully test that it works as desired, and then add another small part. Developing code incrementally minimizes the places where you have to search for bugs to the part you recently added since you've already tested the previous parts. This saves lots of time since it' unlikely you'll need to look through your entire program for the problem.

To begin download these two files and put them in your project directory as you've done in lab:

• AntColonyOptimization.java that contains the code shell we're providing as a starting point for your program. You must implement the methods as described in the code shell. Add your code directly into this file. You will need to fill in every method in this file except for the main method which you should not modify.
• AntWorld.java that describes the ant world. You do not need to change and will not be able to submit this file.

You must implement the methods EXACTLY as they appear in the program shell we've provided. By this we mean:

• Do not change method names.
• Do not add or remove parameters.
• Do not change method return types.

Of course, you will need to change each method's body so that it works as described in the program shell. When grading, we will be testing the required methods individually to verify that they work as described.

You can add additional methods as you feel are appropriate to complete the assignment.

Your program will also generate random numbers to determine the routes your ants will take. We've already added code which constructs a Random object at the start of the findShortestRoute method. This must be the only random number generator that you use in your program, and it will be passed as an argument to the methods that require it. Making another will cause you to lose points on your program.

Concepts:

• Chamber: is a specific location in the ant colony where ants live, work and play. Each chamber is represented by an integer value. Two notable chambers are the queen's nest where the ants start, and the food chamber where the ants want to go. There are also other chambers that ants travel through on their journey to the food.
• Tunnel: is a connection from one chamber to another. Each tunnel is represented by a pair of integer values, such as (2,5), which means there is a tunnel from chamber 2 to chamber 5.
• Map: is the layout for the colony. A two-dimensional array of doubles is used to represent the map. The row and column indexes are chamber numbers and the elements in the array store the lengths of the tunnels connecting chambers, if one exists. For example, map[2][4] would contain the length of the tunnel from chamber 2 to chamber 4, but if it contained the value of 0 it would mean NO tunnel exists between these two chambers. Ants will not be able to travel backwards to previously visited chambers in maps used by this program.
• Route: is a sequence of chamber numbers, such as (2,7,4,6), which would be a route starting in the chamber 2 and ending at chamber 6. Consecutive pairs of numbers represent tunnels in the route as in (2,7) and (4,6). An array of integers is used to represent a route. The indexes are the position in the route and the elements contain the chamber numbers. For example, the first chamber in the route (at index 0) is chamber number 2, the second chamber (at index 1) is chamber number 7, and so on. Ultimately, we want to find a good route from the queen's nest to the food chamber, but we don't know in advance how long that route will be. Because the route length is unknown, we'll use an array that's larger than necessary and initialize its elements with -1 as a sentinel value indicating the element is unused (this is a variation of a partially-filled array). The first element we'll initilize with the queen's nest chamber number. As the route is determined, we'll replace the -1's with chamber numbers. When the route is complete, it might still have -1's in it as in this example: (2,4,7,3,-1,-1,-1), meaning the route starts in the queen's nest number 2 and ends in the food chamber number 3. The trailing -1's are unused elements.
• Ant Routes: There will be a given number of ants in the colony and each ant will determine its own route from the queen's nest chamber to the food chamber. A two-dimensional array is used to represent these ant routes. Each row index corresponds to a particular ant and the row corresponds to that ant's route (see Example Ant Routes below).
• Tunnel Attractivenesses: are how attractive each tunnel is to the ants, which simulates the pheromones wafting from that tunnel. Each tunnel's attractiveness is represented with a value of type double with higher values being more attractive. When an ant is choosing which tunnel to leave a chamber by, the one with the higher attractiveness will be more likely to be chosen. All of the tunnel attractivenesses are kept in a two-dimensional array much like the Map, where the row and column indexes are chamber numbers but the elements store the attractiveness values instead of lengths. Initially, all tunnels specified in the Map will have a value of 1.0 in the corresponding element of the tunnel attractiveness array. All other elements in this attractiveness array will be 0.0 since there isn't a corresponding tunnel. (The power of this algorithm lies in how it changes the attractivesses as the tunnels are used. The algorithm decreases the attractivenesses of all tunnels over time to simulate the evaporation of the pheromone. The algorithm increases the attractiveness based on how often the tunnels is used, but this change is based on how long the routes were that used a particular tunnel. Over time, high attractivenesses will ultimately only occur for tunnels that were a part of shorter routes.

Method Descriptions (taken from the method header comments):

• findShortestRoute: Repeatedly finds a new set of routes from the queen's nest to the food chamber for the number of iterations given, updates the attractiveness of the tunnels based on those routes, and keeps track of the shortest route found so far (but it might not be the absolute shortest route).
• initializeTunnelAttractiveness: Creates the initial tunnelAttractivenesses two-dimensional double array, with a value of 1.0 for every ordered pair of indices whose value in map was positive and 0.0 for every ordered pair of indices whose value in map was zero.
• chooseTunnel: Probabilistically chooses the next chamber a particular ant should travel to based on the attractiveness of the tunnels from the ant's current chamber to the other chambers. To do this, it:
  • Finds the sum of the attractiveness of all the tunnels from the ant's chamber to all other chambers.
  • Calculates a threshold by multiplying a randomly generated double between 0.0 and 1.0 by the sum of the attractivenesses.
  • Starting from chamber 0, again sums the attractiveness of all the tunnels from the ant's chamber to all other chambers until the sum is greater than the threshold. The chamber in which the tunnel attractiveness from the ant's chamber to that chamber caused the sum to exceed the threshold is the chamber that the ant will travel to next.
• findAntRoutes: Finds a new set of routes from the queen's nest chamber to the food chamber for each ant. To do this, it:
  • Creates the antRoutes two-dimensional int array. The length of each row is the total number of chambers.
  • For every ant (i.e., row), initializes its first chamber in antRoutes to be the queen's nest chamber, and initializes all other values in antRoutes to negative one.
  • As long as is necessary, repeatedly computes for all ants (i.e., rows) in order whether or not the ant has already reached the food. If an ant has not already reached the food, a tunnel is chosen and antRoutes is updated. All ants that have not already reached the food chamber are moved for the nth time before any ant is moved for the (n + 1)th time.
• calcLengthOfRoute: Calculates the length of a route according to the distances in the map.
• updateTunnelAttractiveness: Changes the attractiveness of tunnels based on the length of any routes they were used in, and then proportionately decreases the attractiveness of all of the tunnels. To do this, it:
  • For every tunnel taken in every route in antRoutes, the pheromoneStrengthCoefficient / the length of the route is added to the attractiveness of that tunnel.
  • The attractiveness of all tunnels is multiplied by 1.0 - the pheromoneEvaporationCoefficient.
• findShorterRoute: Finds if there is a shorter route than currentShortestRoute of the routes in antRoutes using to the distances in the map to determine their length. If there is more than one route tieing for the shortest, it will return the first one, starting from currentShortestRoute and continuing in increasing order through the indexes of antRoutes.
• trimRoute: Makes a new array representing the same sequence of chambers as in route but without any trailing negative ones.
• printRoute: Displays the route horizontally on the screen separated by spaces.

Example Ant Routes: See image.

This image (and corresponding antRoutes array above) shows the initial state of the ant colony. Note that the queen is at chamber 0, and the food is at chamber 3. The antRoutes array is intialized to all -1s, except for the first element, which is initialize to the chamber of the queen. This is the starting point for each route.

Now see what happens next. See image.

This image (and corresponding antRoutes array above) shows the state of the system after one partial iteration through the findAntRotues method. Note that the chooseTunnel method was called for each ant at this stage. The red ant chose the tunnel to chamber 3 (based on Random selection and pheromone levels) and the green ant chose the tunnel to chamber 1.

Now see what happens next. See image.

This image (and corresponding antRoutes array above) shows the state of the system after another partial iteration through findAntRoutes. Note that the red ant did not move this time--it had already reached the food on the previous iteration. The green ant chose the tunnel to chamber 3. The method is now finished; all ants have reached the food and the array is now filled and ready to be returned.

Example Choosing a Tunnel: See image.

Consider the above image which shows what the green ant had to consider when moving from the second to the third image above this one. The image immediately above show the green ant is in chamber one which is has a tunnel to chambers 2 and 3. Note an ant doesn't go backwards to chamber 0 (no arrow to 0) or stay in the current chamber (no arrow to 1); they always advance toward to the food chamber. Also note that tunnels are annotated with decimal numbers, which correspond to their attractiveness from the tunnelAttractiveness array. The following describes how the green ant would make its choice of tunnel.

First, we sum up the total attractiveness of all tunnels.

0.0 + 0.0 + 1.4 + 2.8 = 4.2

Next, we generate a generate a random number between 0 and 1 (0 inclusive and 1 exclusive) through a call to the nextDouble() method of the Random object. Suppose we generated 0.6. Then, we multiply these numbers to get our threshold.

4.2 * 0.6 = 2.52

Finally, we again add up the tunnels in order until we become greater than the threshold. Note that where no tunnel exists we use 0.0 for the tunnel attractiveness. See image.

We exceeded the threshold when adding in the attractiveness of tunnel three so the green ant will choose tunnel 3

Pheromone Updates

Recall the ant routes selected in the previous diagrams as shown below. See image.

Note that the red ant used only one tunnel (0,3) so suppose looking up map[0][3] gives the route length of = 5.0 and the green ant used two tunnels (0,1) and (1,3) so suppose looking up their lengths in the map and summing them gives a route length of = 4.0 Note these route lengths are to be calculated by the calcLengthOfRoute method and require use of the map array (not shown in this example).

Next, let's consider the updateTunnelAttractiveness method. Suppose we have a pheromoneStrengthCoefficient of 2.0, a pheromoneEvaporationCoefficient of 0.1 and the route lengths above and tunnelAttractivenesses array below.

tunnelAttractivenesses: See image.

Note that, as usual, if there is no tunnel between two chambers, the attractiveness is 0.0 (and will never increase). First, we should update the array by increasing the pheromone strength due to ants passing through tunnels. Noting the route lengths and values above, the resulting array would be the following. See image.

Note that the green bolded numbers are updated since the green ant used those tunnels and the red bolded number is updated since the red ant used that tunnel. For example, let's consider the pheromone updates for the tunnel (0,1). The formula used (as stated in the code skeleton) is (initial attractiveness + pheromoneStrengthCoefficient / route length). The total length of the gren ant's route was 4.0, so the calculation here was:

1.2 + 2.0 / 4.0 = 1.7

Next, we need to simply decrease the pheromone strength on every tunnel by the pheromoneEvaporationCoefficient (which is essentially a percentage). The following array shows this operation completed. See image.

Note that all values have decreased by 10% (that is, they were mulitplied by 0.9, which was determined by taking 1.0 minus 0.1 the pheromoneEvaporationCoefficient for this example). We have now finished our updates, and the tunnelAttractivenesses array has been updated completely.

Testing

For this program, no user input is read so you will not need to consider mistakes made by the program user. You also do not need to verify in each method that its parameter values are valid. You may assume (and you should implement your code) to pass in the correct values.

Make sure to carefully compare your program with this sample run to verify that it is working correctly.

As you write your program, you can modify the main method as a driver to test your other methods. We strongly encourage you to use incremental programming. Write a method and then add code in main that tests the new method. When you are certain that it works, continue by writing the next method. While you develop your program, do not erase your testing code. If you don't want it to run, just comment it out. That way you can uncomment it later if you find that you need to use it again. Before you submit your work, remove all testing code!

In the AntWorld class we've provided some additional (simpler) maps as well. Take a look at the contents of that class and modify the last statement in that class as follows:

public static AntWorld antWorld = antWorld#;

where # is the number of the ant world (from that same file) that you would like to use. We recommend using map2 while debugging your program. The correct output for antWorld2 and antWorld3 can be found here.