Copyright © 2004-2006 Gene Michael Stover. All rights reserved. Permission to copy, store, & view this document unmodified & in its entirety is granted.
Here is a copy of the license agremeent that is on the source code. The same agreement appears in each source code file.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the ``Software''), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL GENE MICHAEL STOVER BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
Except as contained in this notice, the name of Gene Michael Stover shall not be used in advertising or otherwise to promote the sale, use or other dealings in this Software without prior written authorization from Gene Michael Stover.
There are two Lisp source files. The only one you need is evie.lisp. The other file, loadall.lisp, is optional & wouldn't exist if I would get around to doing the ``learn to use ASDF'' item on my To Do list.
For an introduction to genetic algorithms, see [1].
Here are some of the rules & assumptions about genetic algorithms in Evieworld.
In Evie, a population is always a proper list of organisms.
To Evie, an organism is opaque data. The client of the Evie library supplies functions to make new children (i.e., mate parents) & to obtain fitness values for organisms.
In Evie, fitness values are always scalar numbers which may
be compared with the Common Lisp function #'>.
Examples of fitness values include
Larger fitness values always indicate organisms which are better than organisms with smaller fitness values1. For example, if organism A has a fitness of 10, & organism B has fitness of -101, then Evie assumes organism A is better than organism B.
From Evie's point of view, fitness values are dimensionless2. The only purpose of a fitness value is to be compared to the fitness values of other organisms in the same population & same generation.
Given this system of three equations:
fixme
let's use a genetic algorithm to solve for x, y, & z.
The system happens to have a solution at x = 3, y = 4, z = 5, but our genetic algorithm doesn't know that.
Our genetic algorithm will not make use of some of Evie's higher-level features. Normally, I think it's best if a first example shows the highest level, easiest use of a library, but in this case & for some reason I don't understand, I think it's better to show a simple, lower-level use first. I guess I think it's good to see what's happening at a simple level first so we can understand the benefits of the higher-level features later.
The first thing to do is to decide on a representation of the organisms which will be points in the problem space. We must decide how to decode them into solutions, derive fitness values from them so we can compare them, & combine two parent solutions to make a child solution.
We'll pretend we know nothing about the solution at x = 3, y = 4, z = 5. We'll pretend that we don't even have a good idea of the range in which a solution might be found. So we'll use a numeric representation with a wide range. What numeric representation has a wide range? Floating point. In other words, an organism is a structure with three floating point values: x, y, & z.
(defstruct ex01-organism xbits ; list of 16 bits ybits ; list of 16 bits zbits) ; list of 16 bits
The three members of EX01-ORGANISM are bit strings. Each one encodes one of the x, y, or z components of 3-space. We'll need to convert them to numbers to plug them into the original equations. Here are some functions which do that. They use Evie's DECODE-BITS-AS-FIXED function for convenience.
(defun ex01-organism-x (organism) (decode-bits-as-fixed (ex01-organism-xbits organism) 16.0)) (defun ex01-organism-y (organism) (decode-bits-as-fixed (ex01-organism-ybits organism) 16.0)) (defun ex01-organism-z (organism) (decode-bits-as-fixed (ex01-organism-zbits organism) 16.0))
By calling DECODE-BITS-AS-FIXED with a SCALE argument of 16.0, we are effectively placing 4 bits of the bit string behind the binary point. Also, since 16.0 is a floating point number, the result from DECODE-BITS-AS-FIXED will be floating point.
To figure the fitness value for an organism, we apply it's three values to the system of equations, producing three new values. We take that point's distance from the right-hand sides of the original three equations. The farther the new point is from the original point, the worse the organism is. Remember that in Evie, larger values indicate organisms which are more fit, so we must negate the distance. So larger distances will produce more negative fitness values which Evie will interpret as less-fit organisms.
Here is the fitness function:
(defun ex01-fitness (organism)
(let ((x (ex01-organism-x organism))
(y (ex01-organism-y organism))
(z (ex01-organism-z organism)))
(let ((d0 (- 116 (* x x) (* 2 y y) (* 3 z z)))
(d1 (- 266 (* 4 x x) (* 5 y y) (* 6 z z)))
(d2 (- 416 (* 7 x x) (* 8 y y) (* 9 z z))))
;; Strictly speaking, the distance between the original
;; three right-hand sides of the equations & the values
;; we get from the organism would be the square root of
;; the sum of the squares of the differences, but that
;; outer square root isn't necessary. So we can shave
;; a tiny bit of computation time by omitting it.
;; We must remember to negate the sum so that smaller
;; distances become better fitnesses.
(- 0.0 (* d0 d0) (* d1 d1) (* d2 d2)))))
\end{vebatim}
Here are some examples of that fitness function
in action:
\begin{verbatim}
;; Not a very good solution
(ex01-fitness (make-ex01-organism :xbits '(1)
:ybits '(1)
:zbits '(1)))
=> -257267.53
;; Better
(ex01-fitness (make-ex01-organism
:xbits '(1 0 0 0 0 0 0 0 0 0)
:ybits '(1 1 0 0 0 0 0 0 0 0)
:zbits '(1 1 0 0 0 0 0 0 0 0 0)))
=> -381.0
;; Best
(ex01-fitness (make-ex01-organism
:xbits '(1 1 0 0 0 0 0 0 0 0)
:ybits '(1 0 0 0 0 0 0 0 0 0 0)
:zbits '(1 0 1 0 0 0 0 0 0 0 0)))
=> 0.0
Besides defining our organism type & a fitness function for it, we must write a function a new, child organism from two parent organisms. Not surprisingly, this is called mating.
A critical component of making a new child organism is crossover. Crossover is the process (or effect?) by which the child inherits genetic material from both parents. There are many type of crossover, but the basic, common one, which tends to be adequate for problem-solving in practice, is single-point crossover. Evie provides a single-point crossover function for convenience; it is called CROSSOVER1.
(defun ex01-organism-mate (a b) "Return a new organism created by a crossover operation between A & B. A & B are organisms." (make-ex01-organism :xbits (crossover1 (eth01-organism-xbits a) (eth01-organism-xbits b)) :ybits (crossover1 (eth01-organism-ybits a) (eth01-organism-ybits b)) :zbits (crossover1 (eth01-organism-zbits a) (eth01-organism-zbits b))))
Wow, that was a lot of code for a simple example. At least it's all simple code.
Now let's
fixme
Here are lists of Evie functions grouped by their uses.
![[*]](../img/latex2html/crossref.png)
I scanned some of my hand-written notes into a PDF. They are in http://cybertiggyr.com/gene/evie/notes000.pdf.