title: Can a genetic algorithm be made to always produce an exact solution to a TSP-like task?
body: <p>I was trying to solve a TSP-like problem which I have asked about here: <a href="https://stackoverflow.com/questions/22396924/a-travelling-salesman-that-has-state/22397236">A travelling salesman that has state</a></p>
  
  <p>It seems that my problem is very likely NP-hard. Therefore, my options are:</p>
  
  <ul>
  <li>An algorithm which tries every single strategy</li>
  <li>An algorithm which produces an approximate solution</li>
  </ul>
  
  <p>Since my <code>n</code> is going to be small, I think it makes sense to go with the first possibility. However, for various practical and personal reasons, I would prefer to implement my solution as a genetic algorithm, rather than a more conventional brute-force solution (such as Pham Trung's answer in the link).</p>
  
  <p>I reason that a genetic algorithm, like all heuristics, examines a subset of possible solutions to the problem. Exactly which subset this happens to be depends on the specific parameters of a given GA.</p>
  
  <p>My question: For a GA, must this be a strict subset? Or is it possible to set up the GA with such parameters that it ends up checking every possible solution, and consequently running in non-polynomial time?</p>
  
  <p>If the answer is yes, it would be helpful if you can explain how I can determine the exact parameters of the GA which would accomplish this, such as:</p>
  
  <ul>
  <li>Population size</li>
  <li>Mating method</li>
  <li>Selection method</li>
  <li>Mutation method</li>
  <li>Cross over method</li>
  </ul>
  
  <p>Alternatively, if it is impossible to easily come up with a set of parameters that will cause a GA to end up checking every solution, and never check the same solution repeatedly too many times, I'll take this as a negative answer.</p>
  
  <p>I intend to implement this in C# - but for this question, feel free to disregard the language. I am pointing this out in case someone knows a library that already does what I want.</p>