Program 2: Ant Colony Optimization

Sample Solution and Test Data (10/24)

test.l - the test file
solution.l - Tim Montague's and John Stite's solution

Due Date

This assignment is due at the beginning of the lecture on Friday, October 19th.

Partners

Everyone is required to complete this assignment with one partner. Submit one solution with both of your names on it.

Purpose

The purpose of this assignment is to introduce you to the Ant Colony Optimization algorithm. ACO can be used to find good, but not necessarily optimal, solutions to instances of the traveling salesperson problem (TSP).

You will also gain experience using Common Lisp to solve AI problems.

Ant Colony Optimization

Implement the ACO algorithm that is described in the paper that we read for September 28th. Note carefully that

Initially, the pheromone level for all trails should be τ ₀ as defined on page 4.
There is an error in the global trail updating formula at the bottom of page 3. The formula should read τ(r,s) ← (1 - α) * τ(r,s) + α * Δ φ(r,s).

Coding Requirements

Write your solution in one file named solution.l that integrates with the file, aco.l.

The file solution.l should contain a parameterless function named aco. This is the top-level function that is called from the aco.l file.

Sample Output

When your program is run with the above aco.l file, the output that is produced should look something like what appears below. Notice that all of the output must be produced using functions that are provided for you in the aco.l file.

Ant Colony Optimization
-----------------------
Points = 
((110.0 225.0 0) (161.0 280.0 1) (157.0 443.0 2) (283.0 379.0 3)
 (306.0 360.0 4) (325.0 554.0 5) (397.0 566.0 6) (490.0 285.0 7)
 (552.0 199.0 8) (343.0 110.0 9))
Ants = 100, Iterations = 2, Alpha = 0.10, Beta = 2.00, q0 = 0.90, tau0 = 0.0001

Iteration 1

Shortest Tour: 
((110.0 225.0 0) (161.0 280.0 1) (306.0 360.0 4) (283.0 379.0 3)
 (157.0 443.0 2) (325.0 554.0 5) (397.0 566.0 6) (490.0 285.0 7)
 (552.0 199.0 8) (343.0 110.0 9) (110.0 225.0 0)) 
Shortest Tour Length: 1575.12
Longest Tour: 
((110.0 225.0 0) (397.0 566.0 6) (306.0 360.0 4) (283.0 379.0 3)
 (157.0 443.0 2) (161.0 280.0 1) (343.0 110.0 9) (552.0 199.0 8)
 (490.0 285.0 7) (325.0 554.0 5) (110.0 225.0 0)) 
Longst Tour Length: 2295.93
Average Tour Length: 1725.42

Iteration 2

Shortest Tour: 
((110.0 225.0 0) (161.0 280.0 1) (306.0 360.0 4) (283.0 379.0 3)
 (157.0 443.0 2) (325.0 554.0 5) (397.0 566.0 6) (490.0 285.0 7)
 (552.0 199.0 8) (343.0 110.0 9) (110.0 225.0 0)) 
Shortest Tour Length: 1575.12
Longest Tour: 
((110.0 225.0 0) (161.0 280.0 1) (306.0 360.0 4) (283.0 379.0 3)
 (552.0 199.0 8) (397.0 566.0 6) (325.0 554.0 5) (343.0 110.0 9)
 (490.0 285.0 7) (157.0 443.0 2) (110.0 225.0 0)) 
Longst Tour Length: 2330.00
Average Tour Length: 1722.79

What to Submit

The following materials must be received no later than Friday, October 19th at 12:00 noon.

A printout (not an e-mail) of the solution.l file.
An e-mail of the solution.l file to John at paxton@cs.montana.edu

Grading

10%. The solution.l file compiles with no errors and no warnings. Furthermore, the solution.l file should not contain any of the information that is provided in the aco.l file.
60%. Correctness. I will test your solution.l file on undisclosed sample test sets. Thus, it is very important that you anticipate and test your solution thoroughly before submitting it. Also, you will want to make extra sure that no run-time errors can occur.
20%. The quality of the solution. Does your solution use Common Lisp appropriately? Does the solution avoid duplicated code? Is the solution elegant? Is the solution easy to read and maintain? Is the solution reasonably efficient? etc.
10%. The solution is commented appropriately. The document includes a file header comment, function header comments, tricky code comments, local variable comments, etc.