MATLAB Answers

Is there a way to find a global minimum using genetic algorithm?

4 views (last 30 days)
As in the title : Is there a way to find a global minimum using genetic algorithm?
I've written a code to find a global minimum of a function f, but it returns a great number of local minimums. Is it possible to find the global minimum (on some interval) or create a graph, and obtain min using it.If it matters, the function f is depends on more than 1 variable.

  0 Comments

Sign in to comment.

Accepted Answer

Walter Roberson
Walter Roberson on 8 Apr 2020
Genetic algorithms use the function handles they are given as "black boxes" (ga cannot examine how the function works.) In all algorithms that treat the function as a black box, it is impossible for the algorithm to be sure that it has found a global minima.
There are certain kinds of functions for which ga has been proven to be able to find the global minima to within tolerences (given enough iterations.) But there are also certain kinds of functions for which fmincon has been proven to be able to find the global minima to within tolerences. But once you get beyond constrained multinomials in term degree no more than 2, it gets tricky to be sure you have a global minima.
There are some functions that can be analyzed using calculas techniques in order to find global minima -- but only if you use the Symbolic Toolbox.
In the general case, it has been proven that there are functions for which the only way to determine the global minima is to try all possibilities individually and compare the results (that is, there are functions for which knowing the result for one input does not help you know the output for a different value.)

  2 Comments

enter
enter on 8 Apr 2020
GA stops whenever it founds a local minimum. Is there a possibility that it will not terminate after the first minimum?
Walter Roberson
Walter Roberson on 8 Apr 2020
GA does not stop when it finds a local minimum! It continues to try cross-overs and mutations and random displacements.
If you do not specify options, most commonly ga stops due to exceeding maximum function evaluations; if you increase that then typically it stops due to exceeding maximum iterations. But if both of those are large enough, then typically it stops due to a stall:
Stall generations (MaxStallGenerations) — The algorithm stops if the average relative change in the best fitness function value over Stall generations is less than or equal to Function tolerance. (If the Stall Test (StallTest) option is 'geometricWeighted', then the test is for a geometric weighted average relative change.)
You can increase the stall generations to keep it trying longer, hoping that a random direction or mutation might happen to pop it into a better space. It does help sometimes.
You could also consider changing the mutation algorithm, or setting the Scale to use a higher standard deviation, or setting Shrink to change the schedule at which the standard deviation changes (it can be set negative to cause it to grow over time.)

Sign in to comment.

More Answers (0)

Sign in to answer this question.