Hi!
I'm playing arround with a Genetic Algorithm in which I want to evolve graphs. Do you know a way to apply crossover and mutation when the chromosomes are graphs?
Or am I missing a coding for the graphs that let me apply "regular" crossover and mutation over bit strings?
thanks a lot! Any help, even if it is not directly related to my problem, is appreciated!
Manuel
Well, I have never played with such an implementation, but eventually for crossover you could pick a branch of one of the graphs and swap it with a branch from another graph.
For mutation you could randomly change a node inside the graph, with small probability.
You might as well try Genetic Programming. A graph would be the closest thing to a tree and GP uses trees... if you still want to use GAs instead of GPs then take a look at how crossover is performed on a GP and that might give you an idea how to perform it on the graphs of your GA:
Here is how crossover for trees (and graphs) works:
As others have mentioned, one common way to cross graphs (or trees) in a GA is to swap subgraphs (subtrees). For mutation, just randomly change some of the nodes (w/ small probability).
Alternatively, if you are representing a graph as an adjacency matrix, then you might swap/mutate elements in the matrices (kind of like using a two-dimensional bit string).
I'm not sure if using a bitstring is the best idea, I'd rather represent at least the weights with real values. Nevertheless bitstrings may also work.
If you have a fixed topology, then both crossover and mutation are quite easy (assuming you only evolve the weights of the network):
Crossover: take some weights from one parent, the rest from the other, can be very easily done if you represent the weights as an array or list. For more details or alternatives see http://en.wikipedia.org/wiki/Crossover_%28genetic_algorithm%29.
Mutation: simply select some of the weights and adjust them slightly.
Evolving some other stuff (e.g. activation function) is pretty similar to these.
If you also want to evolve the topology then things become much more interesting. There are quite some additional mutation possibilities, like adding a node (most likely connected to two already existing nodes), splitting a connection (instead of A->B have A->C->B), adding a connection, or the opposites of these.
But crossover will not be too easy (at least if the number of nodes is not fixed), because you will probably want to find "matching" nodes (where matching can be anything, but likely be related to a similar "role", or a similar place in the network). If you also want to do it I'd highly recommend studying already existing techniques. One that I know and like is called NEAT. You can find some info about it at
http://en.wikipedia.org/wiki/Neuroevolution_of_augmenting_topologies
http://nn.cs.utexas.edu/?neat
and http://www.cs.ucf.edu/~kstanley/neat.html
I like Sandor's suggestion of using Ken Stanley's NEAT algorithm.
NEAT was designed to evolve neural networks with arbitrary topologies, but those are just basically directed graphs. There were many ways to evolve neural networks before NEAT, but one of NEAT's most important contributions was that it provided a way to perform meaningful crossover between two networks that have different toplogies.
To accomplish this, NEAT uses historical markings attached to each gene to "line up" the genes of two genomes during crossover (a process biologists call synapsis). For example:
(In this example, each gene is a box and represents a connection between two nodes. The number at the top of each gene is the historical marking for that gene.)
In summary: Lining up genes based on historical markings is a principled way to perform crossover between two networks without expensive topological analysis.