3

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?

  • 3
    My understanding of GAs is that they weren't guaranteed to find global optima. They're use is in finding solutions that are good enough within a known amount of time (you set the generation count). I am a bit rusty on this though, so don't take my word for it. – MetaFight Jan 5 '17 at 21:40
7

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.

  • So it sounds like you're saying you run the algorithm a few times, for a fixed number of generations, and then compare the best result from each run to see which is overall best? I can see the sense in that, although it ends up being a bit subjective, as you wouldn't know in advance how many generations to run for for. You might be wasting time by running for too long on each run, or failing to find a good solution by not running for long enough. Are there any ways of working out when is a good time to stop? Thanks – Avrohom Yisroel Jan 8 '17 at 15:50
  • Thanks for the link to CS. I came here due a lack of response on StackOverflow. Didn't know about the CS site. Had some great help here though, so might stick with it and see. I can always repost over there if I do't get my answer. Thanks again. – Avrohom Yisroel Jan 8 '17 at 15:51
  • @AvrohomYisroel Your question on when to stop could be a question of its own - too long for a single comment here. You can run for a set number of generations, wait for them to converge (like in one of the questions you asked), wait for a set period of time, etc. You can even have a GA running multiple copies of your original GA. – Shaz Jan 9 '17 at 14:56
3

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.

Article.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.