Does anyone know of any method for deciding when a genetic algorithm is done? In MCMC (e.g, BUGS), several chains are started at different, random points. When they all look the same, it is done. Has this approach ever been tried with GA? Any other ideas?
A simple and common test is to measure improvements in the objective functions: if you no longer improve (by a certain amount) over a set number of iterations, you may as well stop. Other optimisation algorithms use this approach too.
If you don't have any clue on the fitness landscape, i.e. existence of local optima, plateaus, valleys etc, it is hard to understand whether a GA (or other evolutionary algorithms, EAs) have found the global optima. You can use a multi-populations approach, e.g. an island-based GA, and then, with a specific migration strategy, check when all the population converge to the same solution. This is just a possible answer to your question, the problem of avoiding local optima it is a critical problem for EA design, especially in high-dimensionality.
The inherent stochasticity of genetic algorithms is what makes them such a powerful tool, however, this property also makes it difficult to know when a global minimum has been found. For example you could sit on a generation at a local minima for a long time before a lucky mutation kicks you out of it and on to a better solution.
Certainly training multiple times (if the search space is reasonably small) to get a feel for what solutions the GA produces would be recommend. Try plotting out the distribution of the solutions obtained. A higher mutation rate may slow training but will also give the algorithm more chance to jump out of local minima.
One possible solution is to look at the standard deviation of the last $n$ predictions, and stop training when it drops below a threshold. If $n$ is large enough this should provide a reasonable method that shows you have come close enough to the global minimum. Note that chasing down that absolute minmum cost value may not always produce a solution that will not generalize well on new data.
Theoretically (and possibly ironically), it is impossible to determine whether your GA's final solution is either a local optimum, the global optimum or anything else in the case of you don't know the number of optima and where they occur.
But you can reduce all possible outcomes, that is, after performing a GA search if you apply a local search algorithm (Newton's Method etc.) with the GA's final solution is given as a starting point then the produced result is either a local or the global optimum.
Restarting GA with different random populations will help to search different sides of the search space, a local optimizer will perform the 'fine tuning' operations, and if you get lucky you will obtain new local or the global solution as well. After performing many GA search, you can select the best as the global solution.
Finally, you still not sure about that.