## 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.