network routing using genetic algorithm [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this question

I was making an evaluation reading for a paper titled:"Network routing protocol using genetic algorithm" the paper aim is to find the optimal route from source node to destination node in a network,and the result test in this paper demonstrate that in comparison with Dijkstra's algorithm that genetic algorithm gave the same result they mean the optimal!!

also in time complexity,so as i already having my own network simulator i tested the network on both Dijkstra and the proposed algorithm,and the experiment demonstrates that they are not the same either in obtaining the optimal solution and that's the case for evaluation algorithm they doesn't guarantee to find the optimal solution",and also in execution time genetic algorithm is worst.

so i read the paper again with more investigation ,in the proposed algorithm the initial population generated randomly which could includes feasible and unfeasible solution,but in the experiment i found that in the initial population they include the optimal solution among the population which is cheating,not only but also all the remaining individuals in the population are feasible solutions and this is not the case in real situation.

but what surprise me that later i found a lot of papers demonstrates and telling the same.

so because i'am not expert in network field ,i need an explanation whether it's true that genetic algorithm finds the optimal solution or not and whether it's better to use with ad-hoc mobile networks ,wired networks with dynamic routing or any other case .

and where its preferable to use in networks over those of deterministic algorithm such as Dijkstra's i mean what are the cases.

and finally what is the pros from it.

Answer 1

Dijkstra's algorithm is optimal. This means that if there exists several paths from a source node to a target node in a weighted graph the algorithm will return the shortest possible path (or one of the shortest possible paths if there are multiple).

A genetic algorithm is not an optimal algorithm and thus there cannot be a guarantee that it finds the optimal solution regardless of what the authors claim. I would rather assume that their problem they tested on was too easy. They do not provide any charts showing the quality progress so I can't even be sure that they didn't find the optimal solution in the initial population already (which means you can find it easily by chance). The authors claim that "The obtained results affirmed the potential of the proposed algorithm where the convergence was guaranteed to obtain the optimal path in each case." is plain wrong.

Personally, I think the idea to use a genetic algorithm to solve something like a shortest path problem for which there exists Dijsktra's algorithm and also A* is quite ridiculous. I don't think it makes sense to compete with optimal algorithms on small problem instances that A* will efficiently solve anyway. Also the authors' approach of using bit string encoding is not really justified. That's a very complex representation for a list of numbers. The authors state that "The best choice of coding has been shown to be a binary coding [8]" and underpin that claim with a reference from 1975(!), in comparison their article is from 2010. Their test section would be unacceptable for any serious journal: They used a single instance with 10 nodes and 14 edges that they attempted to solve 6 times and then conclude that it is guaranteed to find the optimum.

I would use A* to solve shortest path problems. If the networks are larger you can use bidirectional search which is basically A* from both ends that meet in the middle. This should open less nodes.