Genetic Algorithm for Path Finding - Crossover and Mutation

0
votes

I want to use a Genetic Algorithm for finding the shortest path within an undirected graph. I have two questions about this regarding Crossover and Mutation. I've been researching how crossover can be performed in similar situations to this, and the most popular algorithm out there seems to be PMX, my understanding of this is a partial path is swapped between 2 parent chromosomes to make the offspring. The issue I'm having with this is, there is massive scope for almost all of the offspring to become invalid isn't there? I was wondering if you could confirm this for me, and if I'm wrong, please correct me and explain it.

On separate but relevant note; I did have an idea for how to do this, but I don't know if its a good idea, simply select 2 parents where they share the same node in their path and crossover at that point, so all of the offspring remain valid.

My second issue is with Mutation; I have a general idea for how this can be done; would it be wise to select one node and remove it, and relink the path by an alternative means?

Thanks :)!

1
graphgenetic-algorithmpath-findingmutation
If I might ask: why would you do this? Finding the optimal path via A* is very fast; and even you are very constrained by time, there is a simple modification to A* that can give very good, tightly-bounded approximations as quickly as you'd like. There is no need for genetic programming for this problem. - BlueRaja - Danny Pflughoeft

1 Answers

0
votes

First of all you study about the cross over and mutation, because you said that you may loss some efficient parent, but it the concept of " Elitism " in genetic algorithm. that you should overcome by your proposed cross over method. because in cross over itself we are having n method to do, i suggest you to do second variation cross over order. This is not murphy's law, so try hard you will achieve.