Prepare genetic algorithms for abstract syntax tree

[dvberkel]

Genetic programming

In artificial intelligence, genetic programming (GP) is an evolutionary algorithm-based methodology inspired by biological evolution to find computer programs that perform a user-defined task. Essentially GP is a set of instructions and a fitness function to measure how well a computer has performed a task.

should be able to safely bring a lander to the surface of the moon. Create the various kinds of genetic operations on abstract syntax trees.

[dvberkel]

I have been musing on the various genetic operations on the moon lander program structure.

Specifically I want to raise the following concerns

Mutable or Immutable?

Should the operations mutate the program structure or should a copy be made.

Mutate recursively?

Should mutation mutate recursively? The idea behind mutation is to allow programs to escape local optima by having a small chance of changing. The problem is that with larger programs, even with a small probability of mutation for each kind of structure, we could end up mutation a lot.

Should crossover be commutative?

I have the feeling that crossovers should be commutative. I.e. For two programs p and q I feel that crossover(p,q) and crossover(q,p should be the same, in the sense that they should produce programs according to the same distribution.

The reason I am raising this concern is that with the implementation of crossover I have in mind, i.e. pick a random node of p and try to crossover with a similar random node in q, seems depend on the program you start with.

The simplest solution that springs to mind, if it is a problem at all, is to crossover twice to allow both crossover(p,q) and crossover(q,p).

[rix0rrr]

I've gotten most of my knowledge from this page, which provides a good overview yet is very accessible (imho):

http://geneticprogramming.us/Genetic_Operations.html

My take on this:

• Mutability: Immutable with persistent data structures. It'll be way more awesome while multithreading the hell out of our algorithms. Though maybe the persistence is going to be tricky in Rust, we'd probably have to use Arc<> a whole lot which would be bad for performance. For maximum performance, we might want to go arena allocating the structures.
• Recurse: every mutation mutates exactly one node at random from the entire tree.
• Crossover: I would agree. We pick a node of the same arity from both trees, and swap them, right? Producing 2 new offspring? I don't think it matters wheter crossover is commutative, but it has a nice symmetric feel to it to do it this way :)

[dvberkel]

I will take a look at the link you provided.

• I agree that Immutability will provide us with a good base before we multithread to the max.
• Good strategy
• Crossover: What happens in the off change no compatible node is found. This is probably of low probability. On the other hand. That is what could happen in biology as well

[rix0rrr]

I suppose actually the arity doesn't matter. I feel like if we swap any 2 subtrees we should be good.

[dvberkel]

Actually the program should be grammatically correct. So you can not just swap any two subtrees. See structure

[rix0rrr]

Ah, of course!

Well, we can make a list of node types that occur in both trees and draw randomly from that list. They must share at least one--even if it's only the root, which will always be the same type.

[dvberkel]

Genetic algorithms are implemented in the darwin module