A work in progress Common Lisp program facilitating genetic programming.
Install with quicklisp by using the local projects feature. Alexandria and lparallel will be installed automatically if not already present.
cd ~/quicklisp/local-projects/
git clone https://github.com/gambyte/genetic-programming.gitTo use, start your favorite common-lisp implementation and:
(ql:quickload :genetic-programming)
(in-package :genetic-programming)First define a fitness function
(defun difference-from-parabola (x)
(let ((test-function (first x)) ;Extract the function
(avg 0))
(dotimes (i 10 (/ avg i))
(incf avg
(eval ;Evaluate after splicing in the function
`(let ((x (random 100))) ;Bind the variables used in the function
(- (abs ;bigger is fitter
(-
(+ (expt x 2) (* 5 x) 3) ;The target parabola
,test-function)))))))))Next decide what functions, variables, and constants can be used as building blocks
(defvar *functions* (make-functions :function-list '(+ - *) :arg-num-list '(2 2 2)))
(defvar *terminals* '(x 1 10))Initialize and run
(gene-prog :operation :initialize :init-functions *functions* :init-terminals *terminals*)
(gene-prog :operation :next-generations)
(gene-prog :operation :best-of-generation)Sample output:
(+ (+ (+ X (+ 10 (+ X (+ (* (+ 1 (+ X X)) 10) (* X 10))))) 10) (- 10 X))Care must be taken to choose good base functions, variables, and constants. Any lisp functions can be used, including user defined ones. Currently no simplification of the result is performed. Increasing the population size will typically give better results than increasing the number of generations.
The genetic-algorithm starts with a population of randomly generated sequences which are bred by splicing the fittest sequences in each generation together.
(genetic-algorithm '(1 0) ;Terminals
50 ;Gene length
100 ;Population size
50 ;Number of generations
(lambda (x) (count 1 x)) ;Fitness function
)yields
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)The best results are found when the number of terminals is as small as possible:
(genetic-algorithm '(1 0 2) 50 100 50 (lambda (x) (count 1 x)))yields
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)Specify an initial value, an energy function, and a step function
(simulated-annealing 1d2 ;Initial value
1d10 ;Initial Temperature
(lambda (x) ;Energy function, lower is better, min @ 0
(+ (expt (* (+ (sin x) x) (cos x)) 2) (expt x 2)))
(lambda (x) ;Step function
(+ x (random 2d0) -1d0)) ;Equal probability of direction
2.0d-10 ;Minimum temperature
1.0003d0)and a minimum is found, not always the global min:
1.1196443731265049d-5The simulated-annealing function is sufficiently generic to allow for all manner of optimization problems:
(simulated-annealing '() 1d10
(lambda (x)
(abs (- (length x) 5)))
(lambda (x)
(if (= 0 (random 2))
(cdr x)
(cons 'Z x))))yields
(Z Z Z Z Z)Pull requests are welcome. Please report any issues or bugs.
This program 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.
This program 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 along with this program. If not, see http://www.gnu.org/licenses/.