How to represent a path for a genetic algorithm?

Question

I want to use a GA to determine the optimal path from A to B, satisfying certain conditions (length, number of turns, etc.)

An example of a path is: Up 4, Left 8, Down 3, Right 3, Down 1, Left 10, Up 4, Left 1, Up 3

The problem is, I don't really know a good way to represent information such as this in a good way for use in a GA, especially because paths have a variable length.

Does anyone have a good idea how to do something like this?

Answer 1

I'm not sure exactly what your representation problem is, so I suspect you have this question from a misunderstanding of a GA's chromosome string. Theoretically speaking, the chromosome string does not have to be recombined explicitly on integer boundaries if you take the extra step of demarcating your individual genes, which would allow you to recombine on a gene-by-gene basis. This solves the problem of a variable-length gene, such as your "path". Recombining variable-length genes is just a matter of adding another variant to the mutation method, specifically "use this element or nuke this element" in addition to the standard "use element from A or element from B" if your gene is breakable into discrete elements, as your path is.

Answer 2

To me this sounds quite similar to the Travelling salesman problem, does that page contain some useful information?

Answer 3

I would use U, D, L, R....

So "Up 4, Left 8, Down 3, Right 3, Down 1, Left 10, Up 4, Left 1, Up 3" would be:

UUUULLLLLLLLDDDRRRDLLLLLLLLLLUUUULUUU

It would be much easier to breed strings like this.

For A (15 chars) and B (3 Chars), my breeding function between A & B would be to:

• Choose a random desired length (len) between 1 and MAX(LEN(A), LEN(B)) {between 1 and 15}
• Choose a random split point (s) between 1 and len.
• Choose if you want A or B to go first randomly.
• Take the first s characters from the one to go first, and the last (len-s) characters from the other one.

Answer 4

Sounds like you really want to be using something like the A* optimisation algorithm, which is commonly used (to good effect) for path-finding. You can specify any heuristic function you like in order to get the appropiate solution.

Answer 5

Hey.
GA can handle chromosomes with variable length. Actual Individual can be very complex. for example it can contain some number of fixed length bits, string of characters (no fixed length), and maybe some set of pairs of conjugate complex numbers. Additionally conjugate complex numbers pairs must always preserve some conditions. It can be done, but the more complex individual gets, more complex genetic operations get (e.g. cross over, mutation). Probably Fitness function would take some more lines of code. But it is still possible.

Maybe as suggested you could chose number coded path representation, but it can still be done with your example coded as Osama ALASSIRY suggested: UUUULLLLLLLLDDDRRRDLLLLLLLLLLUUUULUUU.
For cross over:

• let mutating operator read current lenght1 of given individual,
• generate two random numbers x1,y1, both x1,y1 =< lenght1 and x1 != y1 (this are your cutting points for individual 1),
• do the same for individual 2, now you have two pairs (x1,y1) and (x2,y2),
• copy from individual 1 what is between x1 and y1, and insert it into individual 2 between values x2 and y2. New version of Individual 2 may change its length as number of genes between x1y1 and x2y2 can be different, but that is ok,
• what was in original version of individual 2 between x2y2 should be inserted into new version of individual 1 between x1y1 (its lenght will also change),

To make it clear:
parent A: UUUULLLLLLLLDDDRRRDLLLLLLLLLLUUUULUUU
parent B: DRRRRLULUDDDR
you generate random pairs pairA(4,18), pairB(0,5) assuming you count genes from 0 you swap following strings:
UUUU**LLLLLLLLDDDRRRD**LLLLLLLLLLUUUULUUU
DRRRRLULUDDDR
So after cross over you get
UUUU**DRRRRL**LLLLLLLLLLUUUULUUU
LLLLLLLLDDDRRRDULUDDDR
Now you just made cross over. you can use also one point of cutting, or multiply points.

As for mutation:

• generate number between 0 and length of individual,
• generate number between 1-4 and update that gene. (if 1 was generated change it to U, 2-D, 3-L, 4-R)

you just did mutation. You can also mutate more than one gene.

But as I said, there are other possibilities.