;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; This file is part of "NOVA":  NOVA = search + COCOMO tools
; Copyright, 2008, Tim Menzies tim@menzies.us
;
; NOVA is free software: you can redistribute it and/or modify
; it under the terms of the GNU General Public License as published by
; the Free Software Foundation, either version 3 of the License, or
; (at your option) any later version.
;
; NOVA is distributed in the hope that it will be useful,
; but WITHOUT ANY WARRANTY; without even the implied warranty of
; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
; GNU General Public License for more details.
; You should have received a copy of the GNU General Public License
; a long with NOVA.  If not, see <http://www.gnu.org/licenses/>.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defsearch sa ((num-changes 500))

  ;; start with a random initial solution
  (move-elts (?lots open) open closed)
  (save-state)
  (if *debug-search* (print-state (first-state? path)))
  (dotimes (i num-changes)
    (push path paths)

    ;; randomly move treatments between open and closed
    (let ((treatments (?lots (append open closed))))
      (with-new-path
	(switch-elts treatments open closed)
	(save-state)
	(push path paths)))
    (let ((path2 (pop paths))
	  (path1 (pop paths)))

      ;; decide whether to continue on the new path or stay on the current path
      (when (or (< (energy? (first-state? path2)) (energy? (first-state? path1)))
		(> (accept-prob (energy? (first-state? path1))
				(energy? (first-state? path2))
				(temperature i num-changes))
		   (my-random 1)))
	(switch-path path2)
	(if *debug-search* (print-state (first-state? path))))))
  (if *debug-search* (terpri)))

(defun accept-prob (e en temperature)
  "Returns the acceptance probability for moving to a new state."
  (let* ((e-max   (max e en))
	 (e-norm  (/ e e-max))
	 (en-norm (/ en e-max)))
    (exp (/ (- e-norm en-norm) temperature))))

(defun temperature (k kmax)
  "Returns the temperature for the kth iteration."
  (exp (/ (* -5 k) kmax)))