Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.
Sign up to join this community
Say I'm writing a GA to solve the travelling salesman problem. I don't know in advance what the shortest path is, so how does my GA know when to stop?
If I wait until the best fitness doesn't reduce for a few generations, how do I know I'm not temporarily stuck in a local minimum, which some mutation in the next generation may help? If the best fitness goes up, how do I know this isn't just a temporary thing that will again be solved in a future generation?
In short, you don't. If you don't know the best global answer, then you'll never know if the answer you found is the best, or only the best local answer.
To try to solve this, one idea is to restart. You restart the algorithm with different parameters, and then compare localized optima, and take the best one. Even then, though, you aren't guaranteed to have found the best answer.
As a side note, you may find better advice on the Computer Science SE site for things like genetic algorithms.
This is a problem not just for GAs but for many optimization techniques, e.g. linear programming.
One solution (which has problems of its own) is to include diversity in the fitness function, which ensures a greater search space and greater likelihood of escaping local minima.
