I'm developing a genetic algorithm for the traveling salesman problem in large-scale graphs, and I'm applying the nearest neighbor algorithm to infect my population with locus arising from this technique. However, the execution time have been too high. Therefore, I would like to know if there is any alternative model of the nearest neighbor algorithm, which is faster than the simple method?
Dear friend,
It is an interesting research. I think one of the reasons for the increasing run time can be large scale data sets. As you mentioned one of the disadvantage of nearest neighbor algorithm is its computational time. kd-tree may be a good choice. Try it.
Good Luck.
Soheila
https://en.wikipedia.org/wiki/K-d_tree
Dear Denio,
We don't think based on our research into String Theory of genetic cybernetic systems that you can get a faster convergence, unless you chance the nature of the network as we have shown, please refer to our paper on Genetic Algorithms for e.g. on Research Gate page of Soumitra K. Mallick for the first part. However, if you really want to turn your computing power into quantum computation then you can try random selection of neighbours by using some random n umber generator. That will also test for quantum robustness of your algorithm and model.
SKM, NH, SM
I think you can try to use any of the methods using for generate an initial population:
- Random (Soumitra K Mallick)
- Quasi-Random
- Secuential
- Parallel (Soheila Ghambari)
- Heuristic (Dênio Júnior)
- Badges
- Science topic
- Similar topics
- Computer Science