Prototyping Genetic Algorithms in Lisp

Source code for Genesis is here until I get asdf-install going.

What are Genetic Algorithms?

Genetic algorithms are one of the best things that computer science has produced. Rather than figuring out a good algorithm yourself, you let your random number generator find one while you sleep! Well, after an up-front design cost to generate proper random functions, and evaluating them, and determining how you’ll evolve them, and how long they should run…

I’ve long been interested in genetic algorithms, and now that I’ve learned my first language with an eval — Lisp — I’m starting to make a library. I spent the past few days prototyping and testing my code,
and I got some encouraging initial results: I got a great almost-linear approximation to my simple test problem (finding square roots) using only addition, subtraction, multiplication, and division (see below).

I know, square roots. What a scorcher. But real people are making real solutions to real problems using genetic algorithms! NASA engineers produced an antenna. They determined acceptable design parameters for the antenna, figured out how to evaluate new designs, and let randomness determine the rest.

The result is described here.

My Genetic Algorithm Plans

I want to produce a Lisp package over the next few weeks (since I should have a boatload of freetime around Christmas) that makes it easy to define new genetic algorithms. I’m going to do it in a few stages, and blog about intermediate results if and when they are interesting.

This will also give internet denizens plenty of opportunity to criticize my awful Lisp code! I am a nublet when it comes to Lisp, and I have no illusions about the quality of the code I’m writing.

This week: prototyping. I picked an easy problem to work out the basics of genetic algorithms. My problem? Finding square roots between 0 and 99, inclusive, with just one rule set.

Disclaimer: This is potentially the stupidest use of genetic programming known to man. Attempting to regularly solve numeric problems with genetic algorithms can lead to blindness, irrational exuberance towards Republican politics, and death.

To give you a sense of the data it ingests, I present the main interface:

(defun genetic-algorithm (generations starting-rules rule-fun
                          fitness-fun)
  "Runs 'generations' number of generations. The rules are initially
  set to to 'starting-rules', the rule generating function is
  'rule-fun', and the evaluation function is 'fitness-fun'"
  (prep-rules starting-rules)
  (dotimes (gen-num generations)
    (run-generation rule-fun fitness-fun)))

Here is the invocation I used for my square root problem:

(genetic-algorithm 32000 '((/ num 2) (+ num .2))
                   #'sample-rule-fun #'sample-fitness-fun)

The typical work for defining genetic algorithms is split into a few stages:

1) Problem definition: What do I even want to solve?
2) Evaluation function: How far am I from right?
3) Picking components: How can I build my algorithms randomly?

Problem Definition

Find the square root of an integer, n, in the range [0, 99].

Evaluation Function

Sum of the squared error of all of the integers in the problem statement.

Interestingly, we can predict the quality and form of the results: since we are minimizing the sum of the squared errors, the result should mimic a least-squared approach. Since I’m only using basic arithmetic, it probably won’t be a very good one (linear at best..).

Prototype Implementation

Warning: There be dragons in the parens ahead.

The rules are stored as a list of lists:

(defvar *RULES* nil)

We also store the possible operators:

(defvar *sample-nodes* #(leaf + leaf - leaf / leaf * leaf))

Woah, what’s with all of the “leaf”s? Well, a balanced binary tree has about as many nodes as leafs (I’m generalizing…), so I started at leaf/operator parity and moved up until I stopped getting stack overflows when generating new functions, which happened at one .

How do the leafs get translated into values? First, they are picked from an array of random values:

(defvar *sample-values*
    #(-1 1 num num randomnum randomfrac))
 
(defun sample-generate-leaf (list)
  "Picks a random element from 'list' and translates it into the proper atom
  or list."
  (let ((elt (random-array-element list)))
    (case elt
         (randomnum (random 1024))
         (randomfrac
          (let ((val (ignore-errors (/ (random 1024) (random 1024)))))
            (when (null val)
              (setf val (/ 1 2)))
            val))
         (t elt))))

These are pretty self descriptive (num is the input number, and it is included twice because I got better results ). ‘randomnum‘ is a random integer in [0, 1023], and ‘randomfrac‘ is a fraction whose
coefficients are in [0, 1023].

So how is all of this put together?

(defun sample-rule-fun ()
  "Example random rule generator. Generates a random arithmetical
  expression."
  (let ((elt (random-array-element *sample-nodes*)))
    (case elt
      (leaf (sample-generate-leaf *sample-values*))
      (t
       (append (list elt) (at-least-once #'sample-rule-fun))))))
 
(defun sample-generate-leaf (arr)
  "Picks a random element from 'arr' and translates it into the proper atom
  or list."
  (let ((elt (random-array-element arr)))
    (case elt
    (randomnum (random 1024))
    (randomfrac
     (let ((val (ignore-errors (/ (random 1024) (random 1024)))))
       (when (null val)
         (setf val (/ 1 2))) ;; avoid divide by zero
       val))
    (t elt))))

This is also fairly straightforward: if you pick an operator, generate a new list, if you pick a leaf, generate a new value.

Results

Square Root Function Test

I ran it for about 18 hours (overnight and after work), and when I came back, the results were nothing short of amazing:

I included a range of values outside of the initial zone because the results are better than I could have hoped for.

I saved the data, and then was trying to save the rules (there were 18 in all), and then I lost them from my first Emacs freeze. C’est la vie. However, my initial guess that the data would fit as a least-squares appears to be a better guess than I ever could have hoped. I want to add arbitrary polynomials, and I hope to see a higher-order best-squares fit of the data plot, with much less error.

Implementation Time

The first implementation was done in a 4-hour chunk of one evening (during which I played X-Moto for at least an hour…), which I find impressive. I probably would have spent at least 3 times that on the prototype in C++. This problem is made extremely because of several of Lisp’s features:

eval: My method is based on runtime list generation, and eval-ing it as a lambda.

Insanely simple Lisp syntax: The same syntax that defines lists also defines their programs? This reduces random function generation to a random list generation problem, which is almost trivial.

REPL: Lisp is a REPL (read-eval-print loop) language, meaning that it has an interactive prompt. Combining this with Emacs’ multiple buffer capabilities, and it’s super easy to make changes and reload.

TODO

It’s never finished!

Rules

Allow more than one rule set, define the maximum number of rules per set, define rules as arrays for better lookup, etc.

Better use of eval

I eval the rules every time I need them, as opposed to the once I should generate them. I will probably see a significant speedup when I do this.

Define a package

Namespacing everything has obvious benefits.

Cross-breed rules

Allow true genetic properties by copying subsets of rules into other rules.

Better rule trimming

My current program produces some stupid rules: such as f(x)=x. In fact, my “amazing results” had 4 rules that evaluated a number to itself out of a total if 18 rules.

Allowing the user to define rule inputs.

Putting the package in an easy-to-use location

Stay tuned for more!

Popularity: 16% [?]