7
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ We don't "e-mail" here. The point is that the answers can be re-used by the people which have a similar question. $\endgroup$ – user88 Feb 12 '12 at 12:04
  • $\begingroup$ Can you help me to demonstrate the convergence of genetic algorithms? $\endgroup$ – Minh Minh Jul 10 '17 at 8:05
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I'll second Dirk's answer -- that is what I do. But I do it using multiple populations. At least in the application that I'm most concerned with, convergence of a single genetic population is not much of an indication of being near the true optimum. $\endgroup$ – Patrick Burns Feb 11 '12 at 9:19
  • 1
    $\begingroup$ Thanks, this is what I'm doing now, in fact a little more. If I don't see any improvement in 10 generation, I keep the single best model, toss out and rerandomize all the others. I thought this was working well, until I just had a model that found a better solution after 45 generations, and the 2nd rerandomization. I'm working on implementing the multiple chains approach used in MCMC. Start 2 or 3 chains in parallel, when all 3 chains agree on the best 3 or 4 models, it is done. $\endgroup$ – Mark Sale Feb 12 '12 at 22:51
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ BTW, does anyone have a reference for this approach? $\endgroup$ – Mark Sale Feb 12 '12 at 22:58
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.