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.
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:
You must implement the methods EXACTLY as they appear in the program shell we've provided. By this we mean:
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.
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
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 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.
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.