;; ---------------------------------
;;            John Paxton
;;              CS 436
;;         Fall Semester, 2007
;;   Program 2: Ant Colony Optimization 
;; ---------------------------------
;; Supplied data structures and functions
;; for Program 2.
;; ---------------------------------

;; ---------------------------------
;; info structure
;; ---------------------------------
;; points: a list of sublists in the form (x y n) where
;;         x is the x coordinate of a data point, y is the
;;         y coordinate of the data point, and n is the 0 based
;;         index of the data point.
;; ants:   the number of ants to use
;; iterations: the number of times for the ants to seek a solution
;; alpha:  the ACO alpha constant, [0 <= alpha <= 1]
;; beta:   the ACO beta constant
;; q0:     the ACO q0 constant, [0 <= q0 <= 1]
;; tau0:   the initial amount of pheremone on each connection
;; pheremones: a 2D (number-of-points by number-of-points)  
;;             matrix of pheremone values 
;; ---------------------------------

(defstruct info
  points
  ants
  iterations
  alpha
  beta
  q0
  tau0
  pheremones
)

;; *info* is the one and only global variable allowed for Program 2
;; It points to an "info" structure

(defvar *info* (make-info))

;; settings for one specific ACO problem
;; 1566.14 is the optimal answer for this TSP

(setf (info-points *info*)
  '((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)))
(setf (info-ants *info*) 100)
(setf (info-iterations *info*) 2)
(setf (info-alpha *info*) .1)
(setf (info-beta *info*) 2)
(setf (info-q0 *info*) .9)

;; ---------------------------------
;; print-header
;; ---------------------------------
;; Prints introductory information about
;; the ACO problem.
;; ---------------------------------

(defun print-header ()
  (format t "Ant Colony Optimization~%")
  (format t "-----------------------~%")
  (format t "Points = ~a~%" (info-points *info*))
  (format t "Ants = ~a, Iterations = ~a, Alpha = ~,2f, Beta = ~,2f, q0 = ~,2f, tau0 = ~,4f~2%"
    (info-ants *info*) (info-iterations *info*)
    (info-alpha *info*) (info-beta *info*)
    (info-q0 *info*) (info-tau0 *info*)) 
)

;; ---------------------------------
;; print-results
;; ---------------------------------
;; iteration-number: how many ACO iterations have occurred
;; best-length: length of best TSP tour found on this iteration
;; best-path: the details of the best TSP tour associated with "best-length" 
;; worst-length: lengh of worst TSP tour found on this iteration
;; worst-path: the details of the worst TSP tour associated with "worst-length" 
;; average-length: the average length of all TSP tours found on this iteration
;; ---------------------------------
;; Print out summary statistics after one iteration of the
;; ACO algorithm is complete.
;; ---------------------------------

(defun print-results (iteration-number best-length best-path worst-length worst-path average-length)
  (format t "Iteration ~a~2%" iteration-number)
  (format t "Shortest Tour: ~,a ~%" best-path)
  (format t "Shortest Tour Length: ~,2f~%" best-length)
  (format t "Longest Tour: ~,a ~%" worst-path)
  (format t "Longst Tour Length: ~,2f~%" worst-length)
  (format t "Average Tour Length: ~,2f~2%" average-length)
)

;; ---------------------------------
;; The main function in your solution must be called aco.
;; This function should take no parameters.
;; ---------------------------------

(aco)   ;; call your main function