Genetic Program

-------------------------------------
Description
-------------------------------------
The Genetic Program (GP) randomly mutates half of available choices, 
scores them, and repeats. If nothing better is found within a 
resonable number of generations, the search terminates. Unlike most
genetic programs, this version just keeps track of the top scoring
treatment in each generation. Descendants are generated by mutation
only.

------------------------------------
Pseudo-code
------------------------------------
GA(type)
  Create the first random root node

  Do
    Create 20 descendants
    Score descendants
    
    If a descendant's score is greater than the best score
      Store the new best score 
      Set MaximumGenerationsWithoutNewBest to 0
    Else
      Incriment MaximumGenerationsWithoutNewBest
  Until MaximumGenerations reached Or MaximumGenerationsWithoutNewBest reached
  
  Perform a back select on the best treatment

-----------------------------------
Actual Code
-----------------------------------
(defun ga (type)
  (let* ((best (completeAllBut (list)))
	 (bestScore (runPom2 type best))
	 (iterationsSinceLastChange 0)
	 (maxIterationsSinceChange 10)
	 (triesPerIteration 100)
	 (maxIterations 400)
	 (iterations 0)
	 (treatmentSize (length best))
	 (percentToRemove .49))
    (while (and (< iterations maxIterations) (< iterationsSinceLastChange maxIterationsSinceChange))
      (let ((newTreatments (list)))
	(dotimes (x triesPerIteration) 
	  (push (completeAllBut (removePercentFromList best percentToRemove)) newTreatments))
	
	(let (tmpBest (tmpBestScore 0))
	  (dolist (new newTreatments)
	    (let ((tmpScore (runPom2 type new)))
	      (if (> tmpScore tmpBestScore)
		  (setf tmpBest new
			tmpBestScore tmpScore))))
	  (if (> tmpBestScore bestScore)
	      (setf best tmpBest bestScore tmpBestScore iterationsSinceLastChange 0)
	      (incf iterationsSinceLastChange)))
  	(incf iterations)))
    (backSelect best type)))

-------------------------------------
Policy Commitment
-------------------------------------
1. Half of the variables are mutated within each descendant
2. It does not restart, with the number of variables changed each iteration,
   it would be difficult to get stuck in a local maxima. If only one attribute is
   changed each iteration, it had a tendancy to get stuck in local maxima's.
3. GP fixes attributes to a set value, although fixing attributes to a range could
   be done.
4. This algorithm is stochastic, although the random affects of local compleations
   are filtered out. To accomplish this filtering, random values are chosen for 
   the non-compleated attributes randomly until the mean score stabilizes.
6. Only the best treatment and score is remembered. This keeps the running memory low
7. The algorithm will terminate early if 10 generations pass with no change in the
   best algorithm.
8. The total best treatment is passed to a back select function. This back select
   function returns the best combination of values for each conjunction of size 
   k = 1 to n where n is the size of the total compleation.