Genetic Algorithm

[miningold]

I am extremely new to lisp but I heard it is good for making genetic algorithms or programs.
I am trying to write a genetic algorithm in lisp, I had attempted it in AHK (autohotkey) if you know what that is, but I hit a road block and it took forever.

I want the basis of my algorithm to act like this:

Make a DNA sequence, the sequence would have x number of digits with the condition that x is divisible by three ( I was thinking about 60 digits long)

The DNA sequence would be split into 3 digit codons, each codon would reference a number between 0 and 9 or and operator (*/-+). For example 000 would correspond to the number 0, 001 would correspond to the number 1 and so on. The reference numbers would then a make a protein sequence. An example would be 016+2*52--46/3. The sequence would have altered so that it could be evaluated in lisp.

The number resulting from the evaluation of the protein sequence would be evaluated for fitness (for simplicities sake i could determine the by how close the number is to 200 or any other number)

This entire process would be executed several times to produce several seeds, lets say 20 times. This way we have 20 DNA sequences to compare for fitness.

Then we have to pick the fittest lines of DNA, as a metaphor I can say that each line of sequence gets a piece of pie in a pie chart. The fitter the DNA sequence the larger the slice. Then we would spin a spinner over the pie chart to determine which DNA sequence move on to the next generation. Fitter DNA sequences have a higher chance of moving on but not a promise. I would spin the spinner 20 times to produce 20 more seeds

The twenty seeds would have to be crossed over at a random point in the DNA sequence.
For example:
Say I have these pieces of DNA
01203110203310
01022301220202

I would chose a random place in the sequence to cut it into two pieces then append each piece to the other two pieces from the other sequences
These:
012|03110203310
010|22301220202
Would become:
012|22301220202
010|03110203310

From here each sequence would have X number of digits mutated (where X ranges from 0 to 60 or how many digits you have in the DNA sequence) The rate of mutation would be determined by how close the sequences are to reaching the goal value. The farther away the higher the mutation rate.

The mutated sequences would then be evaluated for fitness and the process would repeat.

Sorry for all of this information but I just need help starting this off I do not even know how to make the DNA seeds.

If anyone knows how to do any of this or knows of a location on the internet that please tell me. The web sites do not even have to fallow my process, anything will do.

Thank you
All comments are appreciated

[nuntius]

GA's are not my thing, but the following code snippets should help get you started.

As a first cut, I would use arrays to store the DNA sequences. So DNA literals would look something like

Code: Select all

#(0 1 6 '+ 2 '* 5 2 '- '- 4 6 '/ 3)

Then you could define a simple function to randomly choose a DNA codon.

Code: Select all

(defun random-codon ()
  (let ((n (random 14)))
    (case n
      (10 '+)
      (11 '-)
      (12 '*)
      (13 '/)
      (t n))))

So you could create seeds by looping over random-codon something like

Code: Select all

(defun make-seed (length)
  (let ((seed (make-array (list length))))
    (dotimes (n length)
      (setf (aref seed n) (random-codon)))
    seed))

And define another function to mutate the arrays

Code: Select all

(defun make-mutants (pa pb cut)
  (let* ((l (length pa))
         (ca (make-array (list l)))
         (cb (make-array (list l))))
    (dotimes (n cut)
      (setf (aref ca n) (aref pa n)
              (aref cb n) (aref pb n)))
    (loop for n from cut below l
      do (setf (aref ca n) (aref pb n)
                  (aref cb n) (aref pa n)))
    (values ca cb)))

You can capture the results of make-mutants using multiple-value-bind.

BTW, the above code is horribly unoptimized; but don't worry about optimization until you actually have something working... Optimization tends to make code ugly and hard to change. Its best left until you know you don't need to make any more changes.

[ramarren]

If anyone knows how to do any of this or knows of a location on the internet that please tell me. The web sites do not even have to fallow my process, anything will do.

To learn Lisp I would suggest reading A Gentle Introduction to Symbolic Computation and/or Practical Common Lisp, both fully available on the net for free. Afterwards implementing what you described should be relatively easy.

[phil]

I am extremely new to lisp but I heard it is good for making genetic algorithms or programs.

I have some simple GA code in Lisp. It solves a completely different problem of course but it could help you get started. It's a bit too long to post here so send me a mail if you want a copy.

[smithzv]

I don't have any advice tonight, I just thought I would mention a small world connection here. As it turns out, I found this example in a GA tutorial on some website I found back when my boss was trying to understanding GAs and apply them to physics simulations (minimum energy configurations). Before I had ever heard of On Lisp or PCL, I implemented this example and it was the first Lisp program of any substance that I ever wrote. I imagine it would look quite a bit different if I wrote it today. I do have my implementation around somewhere, but I would be too embarrassed to post it.

Zach