Table of Contents
- 1 mgl-gpr ASDF System Details
- 2 Background
- 3 Evolutionary Algorithms
- 4 Genetic Programming
- 5 Differential Evolution
[in package MGL-GPR]
1 mgl-gpr ASDF System Details
- Version: 0.0.1
- Description: MGL-GPR is a library of evolutionary algorithms such as Genetic Programming (evolving typed expressions from a set of operators and constants) and Differential Evolution.
- Licence: MIT, see COPYING.
- Author: Gábor Melis
- Mailto: firstname.lastname@example.org
- Homepage: http://quotenil.com
Evolutionary algorithms are optimization tools that assume little of the task at hand. Often they are population based, that is, there is a set of individuals that each represent a candidate solution. Individuals are combined and changed with crossover and mutationlike operators to produce the next generation. Individuals with lower fitness have a lower probability to survive than those with higher fitness. In this way, the fitness function defines the optimization task.
Typically, EAs are quick to get up and running, can produce reasonable results across a wild variety of domains, but they may need a bit of fiddling to perform well and domain specific approaches will almost always have better results. All in all, EA can be very useful to cut down on the tedium of human trial and error. However, they have serious problems scaling to higher number of variables.
This library grew from the Genetic Programming implementation I wrote while working for Ravenpack who agreed to release it under an MIT licence. Several years later I cleaned it up, and documented it. Enjoy.
3 Evolutionary Algorithms
EVOLUTIONARY-ALGORITHMis an abstract base class for generational, population based optimization algorithms.
The currenly implemented EAs are generational. That is, they maintain a population of candidate solutions (also known as individuals) which they replace with the next generation of individuals.
[accessor] POPULATION-SIZE EVOLUTIONARY-ALGORITHM (:POPULATION-SIZE)
The number of individuals in a generation. This is a very important parameter. Too low and there won't be enough diversity in the population, too high and convergence will be slow.
[accessor] POPULATION EVOLUTIONARY-ALGORITHM (= (MAKE-ARRAY 0 :ADJUSTABLE 0 :FILL-POINTER T))
An adjustable array with a fill-pointer that holds the individuals that make up the population.
[reader] GENERATION-COUNTER EVOLUTIONARY-ALGORITHM (= 0)
A counter that starts from 0 and is incremented by
ADVANCE. All accessors of
EVOLUTIONARY-ALGORITHMare allowed to be specialized on a subclass which allows them to be functions of
[function] ADD-INDIVIDUAL EA INDIVIDUAL
EA. Usually called when initializing the
[reader] EVALUATOR EVOLUTIONARY-ALGORITHM (:EVALUATOR)
A function of two arguments: the
EVOLUTIONARY-ALGORITHMobject and an individual. It must return the fitness of the individual. For Genetic Programming, the evaluator often simply calls
FUNCALL, and compares the result to some gold standard. It is also typical to slightly penalize solutions with too many nodes to control complexity and evaluation cost (see
COUNT-NODES). For Differential Evolution, individuals are conceptually (and often implemented as) vectors of numbers so the fitness function may include an L1 or L2 penalty term.
Alternatively, one can specify
[reader] MASS-EVALUATOR EVOLUTIONARY-ALGORITHM (:MASS-EVALUATOR = NIL)
NILor a function of three arguments: the
EVOLUTIONARY-ALGORITHMobject, the population vector and the fitness vector into which the fitnesses of the individuals in the population vector shall be written. By specifying
MASS-EVALUATORinstead of an
EVALUATOR, one can, for example, distribute costly evaluations over multiple threads.
MASS-EVALUATORhas precedence over
[reader] FITNESS-KEY EVOLUTIONARY-ALGORITHM (:FITNESS-KEY = #'IDENTITY)
A function that returns a real number for an object returned by
EVALUATOR. It is called when two fitness are to be compared. The default value is #'
IDENTITYwhich is sufficient when
EVALUATORreturns real numbers. However, sometimes the evaluator returns more information about the solution (such as fitness in various situations) and
FITNESS-KEYkey be used to select the fitness value.
Training is easy: one creates an object of a subclass of
EVOLUTIONARY-ALGORITHM such as
DIFFERENTIAL-EVOLUTION, creates the initial population by adding
individuals to it (see
ADD-INDIVIDUAL) and calls
ADVANCE in a loop
to move on to the next generation until a certain number of
generations or until the
FITTEST individual is good enough.
[generic-function] ADVANCE EA
Create the next generation and place it in
[reader] FITTEST EVOLUTIONARY-ALGORITHM (= NIL)
The fittest individual ever to be seen and its fittness as a cons cell.
[accessor] FITTEST-CHANGED-FN EVOLUTIONARY-ALGORITHM (:FITTEST-CHANGED-FN = NIL)
4 Genetic Programming
What is Genetic Programming? This is what Wikipedia has to say:
In artificial intelligence, genetic programming (GP) is an evolutionary algorithm-based methodology inspired by biological evolution to find computer programs that perform a user-defined task. Essentially GP is a set of instructions and a fitness function to measure how well a computer has performed a task. It is a specialization of genetic algorithms (GA) where each individual is a computer program. It is a machine learning technique used to optimize a population of computer programs according to a fitness landscape determined by a program's ability to perform a given computational task.
Lisp has a long history of Genetic Programming because GP involves manipulation of expressions which is of course particularly easy with sexps.
GPR works with typed expressions. Mutation and crossover never produce expressions that fail with a type error. Let's define a couple of operators that work with real numbers and also return a real:
(defparameter *operators* (list (operator (+ real real) real) (operator (- real real) real) (operator (* real real) real) (operator (sin real) real)))
One cannot build an expression out of these operators because they
all have at least one argument. Let's define some literal classes
too. The first is produces random numbers, the second always returns
(defparameter *literals* (list (literal (real) (- (random 32.0) 16.0)) (literal (real) '*x*)))
*LITERALS*, one can already build
random expressions with
RANDOM-EXPRESSION, but we also need to
define how good a certain expression is which is called fitness.
In this example, we are going to perform symbolic regression, that is, try to find an expression that approximates some target expression well:
(defparameter *target-expr* '(+ 7 (sin (expt (* *x* 2 pi) 2))))
*TARGET-EXPR* as a function of
*X*. The evaluator
function will bind the special
*X* to the input and simply
the expression to be evaluated.
The evaluator function calculates the average difference between
TARGET-EXPR, penalizes large expressions and returns
the fitness of
EXPR. Expressions with higher fitness have higher
chance to produce offsprings.
(defun evaluate (gp expr target-expr) (declare (ignore gp)) (/ 1 (1+ ;; Calculate average difference from target. (/ (loop for x from 0d0 to 10d0 by 0.5d0 summing (let ((*x* x)) (abs (- (eval expr) (eval target-expr))))) 21)) ;; Penalize large expressions. (let ((min-penalized-size 40) (size (count-nodes expr))) (if (< size min-penalized-size) 1 (exp (min 120 (/ (- size min-penalized-size) 10d0)))))))
When an expression is to undergo mutation, a randomizer function is
called. Here we change literal numbers slightly, or produce an
entirely new random expression that will be substituted for
(defun randomize (gp type expr) (if (and (numberp expr) (< (random 1.0) 0.5)) (+ expr (random 1.0) -0.5) (random-gp-expression gp (lambda (level) (<= 3 level)) :type type)))
That's about it. Now we create a GP instance hooking everything up,
set up the initial population and just call
ADVANCE a couple of
times to create new generations of expressions.
(defun run () (let ((*print-length* nil) (*print-level* nil) (gp (make-instance 'gp :toplevel-type 'real :operators *operators* :literals *literals* :population-size 1000 :copy-chance 0.0 :mutation-chance 0.5 :evaluator (lambda (gp expr) (evaluate gp expr *target-expr*)) :randomizer 'randomize :selector (lambda (gp fitnesses) (declare (ignore gp)) (hold-tournament fitnesses :n-contestants 2)) :fittest-changed-fn (lambda (gp fittest fitness) (format t "Best fitness until generation ~S: ~S for~% ~S~%" (generation-counter gp) fitness fittest))))) (loop repeat (population-size gp) do (add-individual gp (random-gp-expression gp (lambda (level) (<= 5 level))))) (loop repeat 1000 do (when (zerop (mod (generation-counter gp) 20)) (format t "Generation ~S~%" (generation-counter gp))) (advance gp)) (destructuring-bind (fittest . fitness) (fittest gp) (format t "Best fitness: ~S for~% ~S~%" fitness fittest))))
Note that this example can be found in example/symbolic-regression.lisp.
Genetic programming works with a population of individuals. The
individuals are sexps that may be evaluated directly by
EVAL or by
other means. The internal nodes and the leafs of the sexp as a tree
represent the application of operators and literal objects,
respectively. Note that currently there is no way to represent
An object of
EXPRESSION-CLASSdefines two things: how to build a random expression that belongs to that expression class and what lisp type those expressions evaluate to.
[reader] RESULT-TYPE EXPRESSION-CLASS (:RESULT-TYPE)
Expressions belonging to this expression class must evaluate to a value of this lisp type.
[reader] WEIGHT EXPRESSION-CLASS (:WEIGHT = 1)
The probability of an expression class to be selected from a set of candidates is proportional to its weight.
[class] OPERATOR EXPRESSION-CLASS
Defines how the symbol
NAMEin the function position of a list can be combined arguments: how many and of what types. The following defines
+as an operator that adds two
(make-instance 'operator :name '+ :result-type float :argument-types '(float float))
See the macro
OPERATORfor a shorthand for the above.
Currently no lambda list keywords are supported and there is no way to define how an expression with a particular operator is to be built. See
[reader] NAME OPERATOR (:NAME)
A symbol that's the name of the operator.
[reader] ARGUMENT-TYPES OPERATOR (:ARGUMENT-TYPES)
A list of lisp types. One for each argument of this operator.
[macro] OPERATOR (NAME &REST ARG-TYPES) RESULT-TYPE &KEY (WEIGHT 1)
Syntactic sugar for instantiating operators. The example given for
OPERATORcould be written as:
(operator (+ float float) float)
[class] LITERAL EXPRESSION-CLASS
This is slightly misnamed. An object belonging to the
LITERALclass is not a literal itself, it's a factory for literals via its
BUILDERfunction. For example, the following literal builds bytes:
(make-instance 'literal :result-type '(unsigned-byte 8) :builder (lambda () (random 256)))
In practice, one rarely writes it out like that, because the
LITERALmacro provides a more convenient shorthand.
[reader] BUILDER LITERAL (:BUILDER)
A function of no arguments that returns a random literal that belongs to its literal class.
[macro] LITERAL (RESULT-TYPE &KEY (WEIGHT 1)) &BODY BODY
Syntactic sugar for defining literal classes. The example given for
LITERALcould be written as:
(literal ((unsigned-byte 8)) (random 256))
[function] RANDOM-EXPRESSION OPERATORS LITERALS TYPE TERMINATE-FN
Return an expression built from
LITERALSthat evaluates to values of
TERMINATE-FNis a function of one argument: the level of the root of the subexpression to be generated in the context of the entire expression. If it returns
LITERALwill be inserted (by calling its
BUILDERfunction), else an
OPERATORwith all its necessary arguments.
The algorithm recursively generates the expression starting from level 0 where only operators and literals with a
RESULT-TYPEthat's a subtype of
TYPEare considered and one is selected with the unnormalized probability given by its
WEIGHT. On lower levels, the
ARGUMENT-TYPESspecification of operators is similarly satisfied and the resulting expression should evaluate without without a type error.
The building of expressions cannot backtrack. If it finds itself in a situation where no literals or operators of the right type are available then it will fail with an error.
To start the evolutionary process one creates a GP object,
adds to it the individuals (see
ADD-INDIVIDUAL) that make up the
initial population and calls
ADVANCE in a loop to move on to the
[class] GENETIC-PROGRAMMING EVOLUTIONARY-ALGORITHM
GENETIC-PROGRAMMINGclass defines the search space, how mutation and recombination occur, and hold various parameters of the evolutionary process and the individuals themselves.
[function] RANDOM-GP-EXPRESSION GP TERMINATE-FN &KEY (TYPE (TOPLEVEL-TYPE GP))
Creating the initial population by hand is tedious. This convenience function calls
RANDOM-EXPRESSIONto create a random individual that produces
TOPLEVEL-TYPE. By passing in another
TYPEone can create expressions that fit somewhere else in a larger expression which is useful in a
4.5 Search Space
The search space of the GP is defined by the available operators, literals and the type of the final result produced. The evaluator function acts as the guiding light.
[reader] OPERATORS GENETIC-PROGRAMMING (:OPERATORS)
[reader] LITERALS GENETIC-PROGRAMMING (:LITERALS)
[reader] TOPLEVEL-TYPE GENETIC-PROGRAMMING (:TOPLEVEL-TYPE = T)
The type of the results produced by individuals. If the problem is to find the minimum a 1d real function then this may be the symbol
REAL. If the problem is to find the shortest route, then this may be a vector. It all depends on the representation of the problem, the operators and the literals.
[function] COUNT-NODES TREE &KEY INTERNAL
Count the nodes in the sexp
INTERNALthen don't count the leaves.
[reader] RANDOMIZER GENETIC-PROGRAMMING (:RANDOMIZER)
Used for mutations, this is a function of three arguments: the GP object, the type the expression must produce and current expression to be replaced with the returned value. It is called with subexpressions of individuals.
[reader] SELECTOR GENETIC-PROGRAMMING (:SELECTOR)
A function of two arguments: the GP object and a vector of fitnesses. It must return the and index into the fitness vector. The individual whose fitness was thus selected will be selected for reproduction be it copying, mutation or crossover. Typically, this defers to
[function] HOLD-TOURNAMENT FITNESSES &KEY SELECT-CONTESTANT-FN N-CONTESTANTS KEY
N-CONTESTANTS(all different) for the tournament randomly, represented by indices into
FITNESSESand return the one with the highest fitness. If
NILthen contestants are selected randomly with uniform probability. If
SELECT-CONTESTANT-FNis a function, then it's called with
FITNESSESto return an index (that may or may not be already selected for the tournament). Specifying
SELECT-CONTESTANT-FNallows one to conduct 'local' tournaments biased towards a particular region of the index range.
NILor a function that select the real fitness value from elements of
The new generation is created by applying a reproduction operator
POPULATION-SIZE is reached in the new generation. At each
step, a reproduction operator is randomly chosen.
[accessor] COPY-CHANCE GENETIC-PROGRAMMING (:COPY-CHANCE = 0)
The probability of the copying reproduction operator being chosen. Copying simply creates an exact copy of a single individual.
[accessor] MUTATION-CHANCE GENETIC-PROGRAMMING (:MUTATION-CHANCE = 0)
The probability of the mutation reproduction operator being chosen. Mutation creates a randomly altered copy of an individual. See
If neither copying nor mutation were chosen, then a crossover will take place.
[accessor] KEEP-FITTEST-P GENETIC-PROGRAMMING (:KEEP-FITTEST-P = T)
If true, then the fittest individual is always copied without mutation to the next generation. Of course, it may also have other offsprings.
5 Differential Evolution
The concepts in this section are covered by Differential Evolution: A Survey of the State-of-the-Art.
[class] DIFFERENTIAL-EVOLUTION EVOLUTIONARY-ALGORITHM
Differential evolution (DE) is an evolutionary algorithm in which individuals are represented by vectors of numbers. New individuals are created by taking linear combinations or by randomly swapping some of these numbers between two individuals.
[reader] MAP-WEIGHTS-INTO-FN DIFFERENTIAL-EVOLUTION (:MAP-WEIGHTS-INTO-FN = #'MAP-INTO)
The vector of numbers (the 'weights') are most often stored in some kind of array. All individuals must have the same number of weights, but the actual representation can be anything as long as the function in this slot mimics the semantics of
MAP-INTOthat's the default.
[reader] CREATE-INDIVIDUAL-FN DIFFERENTIAL-EVOLUTION (:CREATE-INDIVIDUAL-FN)
Holds a function of one argument, the DE, that returns a new individual that needs not be initialized in any way. Typically this just calls
[reader] MUTATE-FN DIFFERENTIAL-EVOLUTION (:MUTATE-FN)
[reader] CROSSOVER-FN DIFFERENTIAL-EVOLUTION (:CROSSOVER-FN = #'CROSSOVER/BINARY)
A function of three arguments, the DE and two individuals, that destructively modifies the second individual by using some parts of the first one. Currently, the implemented crossover function is
- [function] MUTATE/RAND/1 DE CURRENT BEST POPULATION NURSERY &KEY (F 0.5)
- [function] MUTATE/BEST/1 DE CURRENT BEST POPULATION NURSERY &KEY (F 0.5)
- [function] MUTATE/CURRENT-TO-BEST/2 DE CURRENT BEST POPULATION NURSERY &KEY (F 0.5)
[function] CROSSOVER/BINARY DE INDIVIDUAL-1 INDIVIDUAL-2 &KEY (CROSSOVER-RATE 0.5)
INDIVIDUAL-2by replacement each element with a probability of 1 -
CROSSOVER-RATEwith the corresponding element in
INDIVIDUAL-1. At least one, element is changed. Return
- [function] SELECT-DISTINCT-RANDOM-NUMBERS TABOOS N LIMIT
[class] SANSDE DIFFERENTIAL-EVOLUTION
SaNSDE is a special DE that dynamically adjust the crossover and mutation are performed. The only parameters are the generic EA ones:
EVALUATOR, etc. One also has to specify