3
$\begingroup$

For differential evolution methods in optimization, how many generations does it typically take to reach a global optimum?

How do we know if the values are never going to converge?

$\endgroup$
6
$\begingroup$

I don't think there's enough information to give a heuristic like, "in general, it takes $k$ iterations for differential evolution to reach a global optimum".

First, we don't know how many iterations deterministic global optimizers will take to converge to global $\varepsilon$-optimality in the general case. In limited special cases, we know that certain optimization algorithms will converge within a certain number of steps (e.g., simplex algorithms for linear programs, branch-and-bound algorithms for mixed-integer linear programs, polynomial integer programs, Newton methods for unconstrained convex quadratic programs, conjugate gradient methods for unconstrained convex quadratic programs, Newton methods for unconstrained convex nonlinear programs inside the quadratic region of convergence).

Second, differential evolution is a nondeterministic global optimization algorithm. Nondeterministic global optimization algorithms have weaker convergence theory than deterministic optimization algorithms. While deterministic optimization algorithms converge with certainty (provided the hypotheses of the algorithms used are satisfied), if a nondeterministic global optimization algorithm has a convergence proof, it is usually a proof that the method converges with probability one. Here is an example of a paper that does just that for a genetic algorithm. "Convergence with probability one", while precise, and certainly better than no result at all, is akin to saying, "if we let this algorithm run for long enough, it will eventually search the entire search space, and return the correct answer". If the search space is infinite, it could take infinite time, which is...not a very helpful result. (To be fair, the deterministic case isn't that much better when it comes to global optimization.) A cursory literature search suggests that the convergence theory for differential evolution is not well-developed, and without one, it's difficult to say if the method will converge at all.

Finally, for deterministic algorithms on general problems, it's entirely possible for a significant optimality gap (i.e., the difference between the upper bound and lower bound calculated for the objective function value) to persist for tens to hundreds of iterations with little improvement, and for the rate of decrease in that optimality gap to depend on tolerances and algorithmic heuristics provided to the optimizer for a given problem instance. A significant amount of effort has gone into coming up with "best input tolerances and heuristics" for general problems, and for "autotuning algorithms" (supposedly, for instance, CPLEX has one) that will determine best values for these tolerances and heuristics. You may find that over the course of your experience with the algorithm that you get a better feel for how to pick input tolerances and heuristics for differential evolution as you work with it, and what values work best for different types of problems. Experimentation is often needed with numerical algorithms (witness, for instance, the amount of experimentation still necessary for solving systems of linear equations with iterative linear solvers). You may find the thesis Tuning & Simplifying Heuristical Optimization helpful.

$\endgroup$
1
$\begingroup$

This method makes few or no assumptions about the problem being optimized and can search very large spaces of candidate solutions. However, DE does not guarantee that an optimal solution is ever found for certain types of problems. DE is used for multidimensional real-valued functions but does not use the gradient of the problem being optimized, which means DE does not require for the optimization problem to be differentiable, as is required by classic optimization methods, such as gradient descent and quasi-newton methods. DE can, therefore, also be used on optimization problems that are not even continuous, noisy and change over time.

The generation size heavily depends on the tolerance of error (precision) you want to accept as well as the hardness of the problem. In addition, Crossover Rate (CR) is also an important parameter especially when CR≈0, DE makes very small exploratory moves. The search proceeds in a gradual but consistent fashion as the likelihood of making an improving move is higher when moves are small, even if the change in solution quality is not great. When CR≈0.9, DE makes large exploratory moves that, while being less likely to be improving, can yield large improvements in solution quality. These large moves also reduce population diversity, which is a necessary step so that subsequent moves are scaled appropriately for performing a more fine-grained search of the solution space. When CR≈0.5, DE behaves more similarly to when CR = 0.9 than when CR = 0. Large moves with large improvements also result in a reduction in population diversity, yet it appears plausible that the population is often still too spread for difference vectors to be scaled appropriately to continue the search.

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