Genetic algorithm, nonlinear constraints, TolFun and StallGenLimit

[Giovanni]

I do not understand the termination criterion TolFun for the genetic algorithm. More in detail. I am using the ga with nonlinear constraints. I have set

ga_options = gaoptimset(ga_options,'TolFun', 1e-10);
ga_options = gaoptimset(ga_options,'StallGenLimit', 20);

The ga stops after 6 generations with the message

Optimization terminated: average change in the fitness value less than options.TolFun and constraint violation is less than options.TolCon.

If I look at the last two generations, the objective function for the best element in generation 6 is equal to 21.8, and the objective function for the best element in generation 5 is equal to 22

Reading the help file for TolFun in the ga I find: Positive scalar. The algorithm runs until the cumulative change in the fitness function value over StallGenLimit is less than TolFun.

It does not seem what happened in my case. Does anyone have a hint?

Giovanni

[Rakesh Kumar]

"Giovanni " <pire...@hotmail.com> wrote in message <ic5sgd$ah6$1...@fred.mathworks.com>...

The options you are using affects the sub-problem solution only. See how the nonlinear GA solver works:
http://www.mathworks.com/help/toolbox/gads/bqf8bdd.html

The solver took major 6 iterations to solve for the original constrained problem. The TolFun' option is used to terminate the outer iteration but the 'StallGenLimit' is used only for the inner iteration when solving a sub-problem. The outer iteration does not use this option.

I think the doc should explain this more clearly. Thanks for your question.
Rakesh

[Jeff Freeman]

Rakesh,

I am having a similar problem to Giovanni, except I am not running a problem involving nonlinear constraints. My Termination description looks like:

Optimization terminated: average change in the fitness value less than options.TolFun.

The document that you posted does not seem to apply to unconstrained problems like mine. Could you explain what exactly is meant by the TolFun definition, and how it is affected by StallGenLimit?

Thank you,
Jeff

[Derya]

Hello Jeff,
For unconstrained problems the ga "algorithm stops if the weighted average change in the fitness function value over Stall generations (i.e. number of generations stated in StallGenLimit) is less than Function tolerance" (i.e. TolFun).

(See http://www.mathworks.com/help/toolbox/gads/f6174dfi10.html#f8335)

If you find that ga stops rather prematurely, you can increase the StallGenLimit.

Regards,
Derya

"Jeff Freeman" wrote in message <jim52e$dit$1...@newscl01ah.mathworks.com>...

[Jeff Freeman]

Derya,

Thank you. I'm trying to improve the speed of my optimization without dramatically affecting its accuracy (while fully understanding the stochastic nature of the ga), so I'd rather not increase StallGenLimit blindly. Instead, I want to set an appropriate value for StallGenLimit that allows me to feel confident that the global minimum (or close proximity) has been found before terminating without excess delay. Therefore, any further description will be very helpful.

The two pertinent definitions that I found in http://www.mathworks.com/help/toolbox/gads/f6174dfi10.html#f8335 are:

Stall generations (StallGenLimit) — The algorithm stops if the weighted average change in the fitness function value over Stall generations is less than Function tolerance.

Function tolerance (TolFun) — The algorithm runs until the cumulative change in the fitness function value over Stall generations is less than or equal to Function Tolerance.

Do these mean exactly the same thing: if during the most recent StallGenLimit generations the total change in my best fitness value is less than or equal to TolFun, then the algorithm will terminate? Or is there a difference in the terminology used between "weighted average change" and "cumulative change"?

Perhaps you can explain why the following case terminated prematurely when my StallGenLimit was set to 10 and TolFun to 1e-6.

Best Mean Stall
Generation f-count f(x) f(x) Generations
20 420 474.3 527.6 0
21 440 474.1 580.9 0
22 460 474.1 552.6 1
23 480 473.9 476.1 0
24 500 473.6 583.0 0
25 520 473.6 715.2 1
26 540 473.6 660.3 2
27 560 473.4 713.2 0
28 580 473.0 659.8 0
29 600 473.0 815.0 1
30 620 473.0 813.2 2
31 640 473.0 765.0 3
32 660 473.0 658.2 4
33 680 473.0 580.5 5
34 700 473.0 474.1 6
35 720 473.0 473.9 7

Optimization terminated: average change in the fitness value less than options.TolFun.

Again thank you,
-Jeff

[Alan Weiss]

The weighted change is a geometric weighting with factor (1/2)^n for the
change n steps ago. So a change 10 steps ago gets downweighted by a
factor of 1/2^10, or about 1/1000. A change 20 steps ago gets weighted
by a factor of about 10^-6.

Reading these descriptions now, I see that the TolFun description is not
accurate. It should say weighted change, not cumulative change. I will
fix that.

Alan Weiss
MATLAB mathematical toolbox documentation