GA is tased upon the “Survival of the Fittest” and “Natural Genetic” principal, to produce better solutions. GA operates on the population of solutions. For each new generation, a new set of solutions is formulated by selecting individuals according to their fitness value and then breeding them together using operators.
In the Nearest Neighbor, the features are, it is fast, simple, and usually not optimal.
But in the Genetic algorithm, it is slower, more complex, and the solutions trend toward optimal over time.
Since NN(nearest neighbor) is fast, nothing is preventing you from combining the techniques. Run NN to find a possibly-better-than-random starting solution. Next, feed that solution into your genetic algorithm and let it run as long as you feel is suitable.
If you wish to learn the Genetic Algorithm and Genetic Programming then visit this Artificial Intelligence Course.