1
$\begingroup$

I am going to rewrite an algorithm using genetic methods for mutating my solutions, and I am wondering what I should expect and only consider my algorithm "optimized" or "finished" if various runs of the algorithm give the same result.

For example, if I run the program once and get a good solution, "A", but the second time I run it and get a good solution, "B", is this expected behavior for an adequately designed genetic algorithm? Or should I only get a solution with minor variations of the same solution on each run?

$\endgroup$
1
$\begingroup$

As mentioned, you could have various global optimal solutions, so this behavior could be possible.

However, it is also possible you could have a cost function surface that has a lot of variation based on the selected hypercube you are using for your search space. If there is a lot of variation and you aren't using enough points per generation in the genetic algorithm, you may not be adequately sampling the surface to end up at a given optimal location.

So while this behavior isn't uncommon, you might want to experiment with having more points per generation to see if that helps you end up at a consistent global optimizer.

When I use methods such as this, I usually try to find a list of the top N best locations and then I 'zoom' in on those locations and do some more optimization procedures to better sort out which spots are most optimal.

$\endgroup$
3
$\begingroup$

Your optimization problem might well have multiple isolated but globally optimal solutions. It might even have infinitely many optimal solutions. You really shouldn't be surprised if you get different optimal solutions from different runs. If the optimal objective values from some runs are not as good as in other runs, then this is a sign that you can't trust the result of any one run.

$\endgroup$
0
$\begingroup$

In general, you cannot say with certainty that a solution is "optimized enough" if you get it several times. The reason is that genetic algorithms are incomplete methods that do not consider the entire design space systematically. You can only make statements with certainty once you have complete information, i.e. the design space has been explored exhaustively. This is not what genetic algorithms are designed to do; instead, they are designed to quickly lead you to a good solution.

There are two scenarios to consider if you are getting solutions of the same quality several times:

  • The solutions are actually the same.
  • The solutions are different, but evaluate to the same quality.

The first case is stronger because at the very least it tells you that the particular implementation you're using is unlikely to find something better. The second case only tells you that there are a lot of good solutions to be found. In particular, it may be reasonable to terminate the process after a sufficient number of runs in the first case, but in the second case you have no indication that a subsequent run may not give you a better solution (assuming of course no knowledge of the design space).

As pointed out in the other answers, there could be many globally optimal solutions, and these are the ones that you find. However, you have no way of knowing that. It could simply be the case that there are a lot of locally optimal solutions and you are finding those, but in the next run of your genetic algorithm you find the much better global optimum.

For example, consider a case where the global optimum can only be found by mutation of a specific gene with a very low probability. It will never be discovered by combination, because the gene is very weak and will be dominated by anything combined with it. The performance of all individuals without the mutation is the same. A genetic algorithm would give you solutions with exactly the same quality for lots of runs and never find the optimum solution, even though it may be much better.

In summary, the behaviour you get depends more on the search space than on the implementation of the genetic algorithm. In particular finding many good solutions is not necessarily a good measure of the quality of implementation of the genetic algorithm -- it may be optimized for different kinds of search spaces.

As for a termination condition, I would consider terminating if a sufficient number of separate runs give you exactly the same answer reasonable -- but not because you can now be reasonably sure that something close to the global optimum has been found, but because it is unlikely that your particular genetic algorithm will improve on what it found before.

$\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.