The problem might be NP-hard, but with modern commercial (CPLEX, Gurobi, Xpress) and open-source (Cbc, SCIP) solvers for discrete optimization you can find a provably optimal solution in a relatively short time, even for thousands of nodes.
The disadvantage of genetic algorithms is that they are heuristics, with no guarantees on the quality of the solution found. Exact solvers such as the ones above do provide an estimate of how far you are from the optimal solution if you decide to stop them before they terminate.
The disadvantage of genetic algorithms is that they are heuristics, with no guarantees on the quality of the solution found. Exact solvers such as the ones above do provide an estimate of how far you are from the optimal solution if you decide to stop them before they terminate.