A Genetic Algorithm in Lisp

Here’s the code: ga

You specify genes, the number of genes in your chromosome (chr-size), the size of your population (popu-size), the probabilities of crossover (p-c) and mutation (p-m), the fitness-function (fitness-function in a separate file fitness-functions.lisp), and run it.

Genes can be anything. A chromosome is coded as a list of genes. A population is a list of chromosomes, that is a list of lists of genes.

For example, genes can be a 0 and a 1. Then a chromosome is a list of zeros and ones:

(chr 10 '(0 1)) ; 10 is the number of genes in a chromosome
(1 0 1 1 0 0 0 0 0 1)

Or, genes can be more complicated, say (1 1 1), (2 2 2), (3 3 3).

Then a chromosome is, e.g.:

(chr 5 '((1 1 1) (2 2 2) (3 3 3)))
((3 3 3) (2 2 2) (2 2 2) (1 1 1) (3 3 3))

A population consisting of 3 chromosomes with such genes can be something like this:

(initial-popu 3 5 '((1 1 1) (2 2 2) (3 3 3)))

(((2 2 2) (2 2 2) (2 2 2) (3 3 3) (1 1 1))
 ((3 3 3) (3 3 3) (2 2 2) (3 3 3) (3 3 3))
 ((1 1 1) (1 1 1) (3 3 3) (3 3 3) (2 2 2)))

In some places of the programme, I combine a chromosome with its fitness value (I put its fitness value as the first element of the list because it is easier to manipulate it with car). In such cases I add the suffix -wfv — “with fitness value” to the names of corresponding variables.

Parent chromosomes are selected for reproduction according to the roulette wheel selection algorithm (the function r-wheel).

The programme runs until the termination criterion is satisfied or the number of iterations exceeds max-iterations.

As a termination criterion I use a threshold value of the fitness function, acc-fit — “acceptable fitness”. Other criteria can be added.

Some auxiliary functions are in the files utilities-numbers.lisp, utilities-random.lisp, utilities-list.lisp

I tested it on two simple examples from the book, Artificial Intelligence (Second Edition) by Michael Negnevitsky — probably the best textbook on artificial intelligence and soft computing.

The first example is to find the maximum value of the function (15x – x2) where integer parameter x varies between 0 and 15 — page 224 in the book, fitness function example-1 in fitness-functions.lisp. The second example is to find the maximum of the ‘peak’ function of two variables — page 227 in the book, fitness function example-2 in fitness-functions.lisp.

Advertisements
Published in: on 23/12/2012 at 22:13  Leave a Comment  

The URI to TrackBack this entry is: https://burubaxair.wordpress.com/2012/12/23/a-genetic-algorithm-in-lisp/trackback/

RSS feed for comments on this post.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: