Genetic Algorithms - Crossover and Mutation operat

Question

I was wondering if anyone knew any intuitive crossover and mutation operators for paths within a graph? Thanks!

Answer 1

Emm.. That is very difficult question, people write dissertations for that and still there is no right answer to that.

The general rule is "it all depends on your domain".

There are some generic GA libraries that will do some work for you, but for the best results it is recommended to implement your GA operations yourself, specifically for your domain.

You might have more luck with answers on Theoretical CS, but you need to expand your question more and add more details about your task and domain.

Update: So you have a graph. In GA terms, a path through the graph represents an individual, nodes in the path would be chromosomes. In that case I would say a mutation can be represented as deviation of the path somewhere from the original - one of the nodes is moved somewhere, and the path is adjusted so the start and end values in the path are remaining the same.

Mutation can lead to invalid individuals. And in that case you need to make a decision: allow invalid ones and hope that they will converge to some unexplored solution. Or kill them on the spot. When I was working with GA, I did allow invalid solution, adding "Unfitness" value along with fitness. Some researchers suggest this can help with broad exploring of the solution space.

Crossover can only happen to the paths that are crossing each other: on the point of the crossing, swap the remains of the path with the parents.

Bear in mind that there are various ways for crossover: individuals can be crossed-over in multiple points or just in one. In the case with graphs you can have multiple crossing points, and that can naturally lead to the multiple children graphs.

As I said before, there is no right or wrong way of doing this, but you will find out the best way only by experimenting on it.

Answer 2

Question is a bit old, but the problem doesn't seem to be outdated or solved, so I think my research still might be helpful for someone.

As far as mutation and crossover is quite trivial in the TSP problem, where every mutation is valid (that is because chromosome represents an order of visiting fixed nodes - swapping order then always can create a valid result), in case of Shortest Path or Optimal Path, where the chromosome is a exact route representation, this doesn't apply and isn't that obvious. So here is how I approach problem of solving Optimal Path using GA.

For crossover, there are few options:

1. For routes that have at least one common point (besides start and end node) - find all common points and swap subroutes in the place of crossing

   Parent 1: 51 33 41 7 12 91 60

   Parent 2: 51 9 33 25 12 43 15 60

   Potential crossing point are 33 and 12. We can get following children: 51 9 33 41 7 12 43 15 60 and 51 33 25 12 91 60 that are the result of crossing using both of these crossing points.

2. When two routes don't have common point, select randomly two points from each parent and connect them (you can use for that either random traversal, backtracking or heuristic search like A* or beam search). Now this path may be treated as crossover path. For better understanding, see below picture of two crossover methods:

   see http://i.imgur.com/0gDTNAq.png

   Black and gray paths are parents, pink and orange paths are children, green point is a crossover place, and red points are start and end nodes. First graph shows first type of crossover, second graph is example of another one.

For mutation, there are also few options. Generally, dummy mutation like swapping order of nodes or adding random node is really ineffective for graphs with average density. So here are the approaches that guarantee valid mutations:

1. Take randomly two points from path and replace them with a random path between those two nodes.

   Chromosome: 51 33 41 7 12 91 60 , random points: 33 and 12, random/shortest path between then: 33 29 71 12, mutated chromosome: 51 33 29 71 12 91 60

2. Find random point from path, remove it and connect its neighbours (really very similar to the first one)

3. Find random point from path and find random path to its neighbour

4. Try subtraversing the path from some randomly chosen point, until reaching any point on the initial route (slight modification of the first method).

   see http://i.imgur.com/19mWPes.png

   Each graph corresponds to each mutation method in appropriate order. In last example, the orange path is the one that would replace original path between mutation points (green nodes).

Note: this methods obviously may have performance drawback in the case, when finding alternative subroute (using a random or heuristic method) will stuck at some place or find very long and useless subpath, so consider bounding the time of mutation execution or trials number.

For my case, which is finding an optimal path in terms of maximizing sum of vertices weights while keeping sum of nodes weight less than given bound, those methods are quite effective and give a good result. Should you have any question, feel free to ask. Also, sorry for my MS Paint skills ;)

Update

One big hint: I basically used this approach in my implementation, but there was one big drawback of using random path generating. I decided to switch to semi-random route generation using shortest path traversing randomly picked point(s) - it is much more efficent (but obviously may not be applicable for all problems).