If I have a network of nodes, how can I use genetic algorithms to calculate the shortest path between any two nodes?

# How to solve for the shortest path between nodes using genetic algorithms?

genetic-algorithmgenetic-programming

Skip to content
# How to solve for the shortest path between nodes using genetic algorithms?

genetic-algorithmgenetic-programming

If I have a network of nodes, how can I use genetic algorithms to calculate the shortest path between any two nodes?

## Best Solution

How about using GA to solve the TSP problem?

TSP is a NP complete problem. That is it is not possible to find a solution to the TSP problem in Polynomial time. However, given a solution it can be verified if it is a solution in polynomial time.

Meta-heuristic methods such as Genetic Algorithms can be investigated as a tool to solve a TSP problem because of the population based approach they operate. This way they can "process" a huge number of solutions in on run of the algorithm. To solve any problem using GAs we need to define the following:

Fitness function: Here the fitness function is easy to define. It should be the distance that the salesman has to traverse for a certain tour of the cities possible. We seek to minimize this in TSP.

Chromosome: A chromosome can be defined simply as following- Suppose we have five cities A,B,C,D and E. Then imagine a chromosome of length 5, with each "slot" of the chromosome containing either of the 5 cities. For eg, A,C,D,B,E is a valid chromosome in our case.

Crossover operator: A crossover operator is used in a GA to "mix" two parents with the hope to get fitter children. Various crossover operators are available in GA literature with each having a different way to achieve the same thing. For eg, consider the single point crossover. It randomly selects a crossover point and then interchanges the bits between the two. Without getting into other specialized crossover operators, let us see what would be a good crossover operator for us. In our case, two parent chromosomes will each have a permutation of A,B,C,D,E. Whatever crossover method we choose, we have to take care of one fact here: the crossover operator should not create a child in which one city is present more than once, that is a invalid chromosome. One such crossover operator is the "Order Crossover " (OX) which can be used here.

Mutation: Mutation can be as simple as simply swapping two positions in a single chromosome here.

Overall this is how a TSP using GA would work:

You create a population of individuals with each being of size 5, and containing a permutation of A,B,C,D,E (there will be lots of repetitions of the same permutation)

You start the GA and in every run, you evaluate each individual on the basis of the fitness function by calculating the distance using the distance parameters given to you

Crossover, Mutation improves the individuals and finally the best solution would be the individual with the best tour, ie. the optimal permutation of A,B,C,D,E.

Hope that helps!