;; ---------------------------------
;;            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 (ants by ants)  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))

(setf (info-points *info*) '(
  (288 149 0)
  (288 129 1)
  (270 133 2)
  (256 141 3)
  (256 157 4)
  (246 157 5)
  (236 169 6)
  (228 169 7)
  (228 161 8)
  (220 169 9)
 (212 169 10)
 (204 169 11)
 (196 169 12)
 (188 169 13)
 (196 161 14)
 (188 145 15)
 (172 145 16)
 (164 145 17)
 (156 145 18)
 (148 145 19)
 (140 145 20)
 (148 169 21)
 (164 169 22)
 (172 169 23)
 (156 169 24)
 (140 169 25)
 (132 169 26)
 (124 169 27)
 (116 161 28)
 (104 153 29)
 (104 161 30)
 (104 169 31)
 (90 165 32)
 (80 157 33)
 (64 157 34)
 (64 165 35)
 (56 169 36)
 (56 161 37)
 (56 153 38)
 (56 145 39)
 (56 137 40)
 (56 129 41)
 (56 121 42)
 (40 121 43)
 (40 129 44)
 (40 137 45)
 (40 145 46)
 (40 153 47)
 (40 161 48)
 (40 169 49)
))
(setf (info-ants *info*) 50)
(setf (info-iterations *info*) 25)
(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)
  (setf best-path best-path)
  (setf worst-path worst-path)
  (when (>= iteration-number (- (info-iterations *info*) 1))
    (format t "Iteration ~a~2%" iteration-number)
    (format t "Shortest Tour Length: ~,a ~%" best-length)
    (format t "Longest Tour Length: ~,a ~%" worst-length)
    (format t "Average Tour Length: ~,2f~2%" average-length)
  )
)

;; ---------------------------------

(defun experiments ()
  (time (aco))

  (setf (info-points *info*)
   '((1000 0 0) (1001 0 1) (998 0 2) (1005 0 3) (990 0 4)
     (1021 0 5) (958 0 6) (1085 0 7) (830 0 8) (1341 0 9)
     (318 0 10))
  )
  (setf (info-ants *info*) 50)
  (setf (info-iterations *info*) 100)
  (aco)

  (setf (info-iterations *info*) 1)
  (setf (info-q0 *info*) 1)
  (aco)

  (setf (info-q0 *info*) 0)
  (aco)

  (setf (info-q0 *info*) .9)
  (setf (info-alpha *info*) 0)
  (aco)

  (setf (info-alpha *info*) 1)
  (aco)

  (setf (info-alpha *info*) .1)
  (setf (info-beta *info*) 0)
  (aco)

  (setf (info-beta *info*) -2)
  (aco)
)

;; ---------------------------------

(defun test ()
  (compile-file "test.l")
  (load "test")
  (compile-file "solution.l")
  (load "solution")
  (experiments)
)