Baby Steps into Genetic Programming

Summary

(defun fitness (form fitness-fn test-input) (loop for input in test-input for output = (run-form form input) for target = (funcall fitness-fn input) for difference = (when output (abs (- target output))) for fitness = (when output (/ 1.0 (+ 1 difference))) when (null output) do (return-from fitness nil) collect fitness into fitness-values finally (return (reduce #'* fitness-values)))) We need a way to test the output of a generated function against our desired outcome and represent this as a number: the fitness. This is commonly a number between 0.0 and 1.0. The closer to 1.0 the better the fitness. We also need to check whether the return value of RUN-FORM is NIL in which case it executed illegal code. FITNESS will return NIL in that case as well. (Poor man's exception handling but suffices for now.) So the function needs: 1) the form to check, 2) the fitness function to check against and 3) test input. We also want to check against multiple input values. The TEST-INPUT argument is a list of input values so the most direct approach will be to iterate over these values and running both the form and the fitness functions against them. To get a fitness value between 0.0 and 1.0 we take the absolute difference between the output of the generated form (OUTPUT) and the output of the fitness function (TARGET). We then add 1 to this difference and use that to divide 1.0. To illustrate: CL-USER> (defun fit (x) (/ 1.0 (+ 1 x))) FIT CL-USER> (fit 0) ; no difference so the desired output 1.0 CL-USER> (fit 0.1) 0.9090909 CL-USER> (fit 5) 0.16666667 CL-USER> (fit 500) 0.001996008 We're not testing negative values since DIFFERENCE in FITNESS will never be negative. REPL test of FITNESS: CL-USER> (defparameter random-form (random-form *operators*)) RANDOM-FORM CL-USER> random-form (/ 8.552494 =INPUT=) CL-USER> (fitness random-form (lambda (r) (* pi r r)) '(0 1 -2)) NIL ; this is correct since we divided by zero CL-USER> (setf random-form (random-form *operators*)) (- =INPUT= 5.246...